Triangle 2d array costs more memory than rectangular

Question

I'm writing a program to my college classes. It's an implementation of dynamic programming algorithm for simple version of scheduling tasks on 2 processors. Cause it's a memory wasteful method, I thought of some improvements to it. For example, one don't have to store whole S x n rectangular array, where S is sum of times of all tasks and n is number of tasks. Because in first iterations of algorithm data will be stored only in small index values of n axis, I thought I can make my array a triangle, i.e. each next sub-array is a certain amount of elements longer.

Then I looked in Task Manager for memory usage and I was shocked. Version with rectangular array took 980KBs. Version with triangle array (so the smaller one) took almost 15MBs! Maybe I don't know something about ways of memory allocation used by system, or I have delusions. Or I made some stupid mistake in my code. But I bet that I don't know something. Can someone enlight me?

Here is my code:

#include <iostream>
#include <fstream> 
#include <conio.h>
#include <stack>

using namespace std;

void readTasks(char* filename, int*& outTaskArray, int& outTaskCount)
{
    ifstream input = ifstream();
    input.open(filename, ios::in);

    input >> outTaskCount;
    outTaskArray = new int[outTaskCount];
    for (int i = 0; i < outTaskCount; ++i)
    {
        input >> outTaskArray[i];
    }

    input.close();
}

void coutTasks(int* taskArray, int taskCount)
{
    cout << taskCount << " tasks:\n";
    for (int i = 0; i < taskCount; ++i)
    {
        cout << i << ": " << taskArray[i] << endl;
    }
}

void Scheduling2(int* taskArray, int taskCount, int memorySaving, 
    stack<int>*& outP1Stack, stack<int>*& outP2Stack)
{
    bool** scheduleArray = new bool*[taskCount];
    int sum;

    // I know that construction below is ugly cause of code repetition.
    // But I'm rather looking for performance, so I try to avoid e.g. 
    // checking the same condition too many times.
    if (memorySaving == 0)
    {   
        sum = 0;
        for (int i = 0; i < taskCount; ++i)
        {
            sum += taskArray[i];
        }

        scheduleArray[0] = new bool[sum + 1];
        for (int j = 0; j < sum + 1; ++j)
        {
            scheduleArray[0][j] = j == 0 || j == taskArray[0];
        }
        for (int i = 1; i < taskCount; ++i)
        {
            scheduleArray[i] = new bool[sum + 1];
            for (int j = 0; j < sum + 1; ++j)
            {
                scheduleArray[i][j] = scheduleArray[i - 1][j] || 
                    j >=  taskArray[i] && 
                    scheduleArray[i - 1][j - taskArray[i]];
            }
        }

        getch(); // I'm reading memory usage from Task Manager when program stops here

        int halfSum = sum >> 1;
        while (!scheduleArray[taskCount - 1][halfSum]) --halfSum;

        for (int i = taskCount - 1; i > 0; --i)
        {
            if (scheduleArray[i - 1][halfSum])
                outP1Stack->push(i);
            else if (scheduleArray[i - 1][halfSum - taskArray[i]])
            {
                outP2Stack->push(i);
                halfSum -= taskArray[i];
            }
        }
        if (halfSum) outP2Stack->push(0);
            else outP1Stack->push(0);
    }
    else if (memorySaving == 1)
    {   
        sum = 0;
        for (int i = 0; i < taskCount; ++i)
        {
            sum += taskArray[i];

            scheduleArray[0] = new bool[sum + 1];
            for (int j = 0; j < sum + 1; ++j)
            {
                scheduleArray[0][j] = j == 0 || j == taskArray[0];
            }
            for (int i = 1; i < taskCount; ++i)
            {
                scheduleArray[i] = new bool[sum + 1];
                        for (int j = 0; j < sum + 1; ++j)
                {
                    scheduleArray[i][j] = scheduleArray[i - 1][j] || 
                        j >= taskArray[i] && 
                        scheduleArray[i - 1][j - taskArray[i]];
                }
            }
        }

        getch(); // I'm reading memory usage from Task Manager when program stops here

        int halfSum = sum >> 1;
        while (!scheduleArray[taskCount - 1][halfSum]) --halfSum;

        for (int i = taskCount - 1; i > 0; --i)
        {
            if (scheduleArray[i - 1][halfSum])
                outP1Stack->push(i);
            else if (scheduleArray[i - 1][halfSum - taskArray[i]])
            {
                outP2Stack->push(i);
                halfSum -= taskArray[i];
            }
        }
        if (halfSum) outP2Stack->push(0);
        else outP1Stack->push(0);
    }

    for (int i = 0; i < taskCount; ++i)
    {
        delete[] scheduleArray[i];
    }
    delete[] scheduleArray;
}

int main()
{
    char* filename = "input2.txt";
    int memorySaving = 0; //changing to 1 in code when testing memory usage

    int* taskArray; // each number in array equals time taken by task
    int taskCount;
    readTasks(filename, taskArray, taskCount);

    coutTasks(taskArray, taskCount);

    stack<int>* p1Stack = new stack<int>();
    stack<int>* p2Stack = new stack<int>();

    Scheduling2(taskArray, taskCount, memorySaving, p1Stack, p2Stack);

    cout << "\np1: ";
    while (p1Stack->size())
    {
        cout << p1Stack->top() << ", ";
        p1Stack->pop();
    }
    cout << "\np2: ";
    while (p2Stack->size())
    {
        cout << p2Stack->top() << ", ";
        p2Stack->pop();
    }

    delete p1Stack;
    delete p2Stack;

    delete[] taskArray;
    return 0;
}

Answer 1

Damn it, I'm blind. I have a damn big memory leak and I didn't see that. I just looked into the part executed, when memorySaving == 1 and noticed that I'm allocating (god knows why) every row of my array taskCount times... It's completely not what I meant, when I was writing this. Well. It was late night.

Sorry for bothering you all. Question should be closed.

Answer 2

Since my suggestions would have fixed your problem had you taken them (as I suspected), I'll make them an answer!

But why using vector would help me in this case? I don't need to use any of its functions.

Yes, you did! You needed one of its most important "functions"...the automatic management of the array memory block. Note that if your declaration was vector< vector<bool> > scheduleArray, you couldn't have had a leak. There wouldn't have been any new or delete in your code...how would it be possible?

Other benefits of using vector:

• You can't accidentally do a delete instead of delete[] on the pointer

• It can do bounds checking (if you enable it, which you should in your debug builds...try a test with just vector<int> v; v[0] = 1; to make sure you have this turned on.)

• Vector knows how many elements it is holding, so you don't run into situations where you have to pass parameters like taskCount. This eliminates one more place where you have the opportunity to make a mistake in your bookkeeping. (e.g. what if you remove an element from the vector and forget to reflect that in the count variable?)

Answers to your comments:

Isn't a bit shift operation faster than division by two?

No.

If you're coding in raw assembly, then sometimes it might be, on certain architectures. But for the most part integer division and bit shift costs a whole cycle either way. And I'm sure some wacky architecture exists out there that can divide faster than it can shift.

Remember that this is C++, not assembly. It's best to keep your code clear and trust the optimizer to do the right thing. For instance what if SHIFT and DIV both take one instruction cycle, but you can get more speed by alternating which you use if you're in a tight loop due to something about the pipeline?

memorySaving is going to have more values than just two.

Then use an enumerated type.

Has std::vector O(1) access time to every element by index, as array has?

Yes, as you discovered. There is a small amount of per-vector overhead in terms of storage (which varies by compiler). But as I mentioned above this is a small price to pay. Also, you were probably usually tracking the length in some variable outside your array in the first place.

As for pointers to stacks - isn't dynamic memory allocation generally better, as I can decide when to release memory myself?

It's generally not better, precisely for that reason. If you're responsible for deciding when to release memory yourself, then you can drop the ball on managing that responsibility.

So wherever possible, you should let C++'s scoping handle the lifetime of your objects. Sometimes making a dynamic object that survives outside of the scope of its creation simply can't be avoided, but that's why Modern C++ has smart pointers. Use 'em!

http://en.wikipedia.org/wiki/Smart_pointer

For instance, your readTasks would be cleaner and safer if it returned a shared_ptr< vector<int> >.

Why should I use std::string, if I don't use any functions it supports, and char* is as good as std::string here?

To get into the habit of not using it for reasons that parallel the above arguments for vector. Bounds-checking, for instance. Also, quiz question: what do you think will happen if you wanted to capitalize "input2.txt" and said filename[0] = 'I';?

When you're done with implementing all my suggestions, then you can go look at boost::dynamic_bitset. :-)