Stack challenge - improving memory consumption

Question

I am working on this problem:

Stacks

Imagine, that you are employed by a software development company. You work now on the famous "D++ project", which is devoted to the creation of a new generation programming language. Your particular task is quite prosaic, though. You are to develop the memory manager being able to work with a large number of stacks.

Input

The first line of the input contains the total number of stack operations \$N\$, \$0 < N ≤ 100000\$. Each of the next \$N\$ lines contains a description of a stack operation, either in the form PUSH A B (meaning to push B into stack A), or in the form POP A (meaning to pop an element from stack A), where A is the number of stack (\$1 ≤ A ≤ 1000\$), and B is an integer (\$0 ≤ B ≤ 10^9\$). You may assume, that every operation is correct (i.e., before each POP operation, the respective stack is not empty).

Output

For each POP operation, described in the input, output the value, which this POP operation gets from the top of that stack, to which it is applied. Numbers should appear according to the order of the POP operations in the input. Each number should be output in a separate line.

I have developed a solution here:

#include<map>

class MyStack
{
    public:

      int data;
      MyStack *link;
      MyStack *top;

      MyStack()
      {
          link = NULL;
          top = NULL;
      }

      void push( int data )
      {
           MyStack * tmp = (MyStack *) malloc( sizeof( MyStack ) );
           tmp->data = data;
           tmp->link = top;
           top = tmp;
      }

      void pop()
      {
          MyStack *tmp = top;
          top = top->link;
          printf( "%d\n", tmp->data );
          free( tmp );
      }

      void clear()
      {
          while( top != NULL )
          {
              MyStack *tmp = top;
              top = top->link;
              free( tmp );
          }
      }

      bool isEmpty()
      {
           return top == NULL;
      }
};


int main()
{
    static MyStack* stackPtrs[1001];

    int noOfInstructions = 0;
    scanf( "%d", &noOfInstructions );

    char instruction[3];
    short stackNumber = 0;
    int stackValue = 0;
    for( int inx = 0; inx < noOfInstructions; ++inx )
    {        
        scanf("%s", &instruction );    

        scanf( "%hd", &stackNumber );

        if( instruction[1] == 'U' )
        {          
            scanf( "%d", &stackValue );

            if( stackPtrs[stackNumber] == NULL )
            {              
                MyStack *myStack = new MyStack();
                myStack->push( stackValue );
                stackPtrs[stackNumber] = myStack;
            }
            else
            {
                stackPtrs[stackNumber]->push( stackValue );
            }
        }
        else
        {
            stackPtrs[stackNumber]->pop();
            if( stackPtrs[stackNumber]->top == NULL )
            {
                stackPtrs[stackNumber] = NULL;
            }
        }
    }

    for( int inx =0; inx < 1001; ++inx )
    {
         if( stackPtrs[inx] != NULL )
         {
             stackPtrs[inx]->clear();
             stackPtrs[inx] = NULL;
         }
    }
    // Clear memory allocated here!.


    return 0;
}

The memory limit for this question is around 0.75MB = 750KB. My program, out of 20-30 runs on an average is taking around 800KB, with 770KB being the least time.

Please suggest any improvements to this program.

Answer 1

My main problem is that you are dynamically allocating all objects with new and or malloc. In C++ object can be created locally without new just by declaring them in the local scope.

MyStack   stack;      // Creates and initializes a MyStack object.


MyStack   data[10];   // Create and initialize an array of MyStack objects.

See no need to call new at all most of the time.

The second problem is that you are using malloc. This is C memory management. The blocks are not necessarily in the same areas as memory allocated by new and thus not compatible to be deleted by either. Also they don't run the constructor and free will not run the destructor. So a very bad idea.

The third observation is that you are building a container (linked list). There is already a built-in linked list.

std::list<int>   data;

For this structure of a stack. The list is not the optimal data structure. A std::vector or std::deque is probably better. But we have a built-in std::stack which is actually a container adapter that wraps another container type (by default it uses std::deque).

std::stack<int>   data;  // This is probably your best option
                         // for holding data.

If you want multiple stacks. I would just create a std::vector of stacks that you can the size at runtime to get all the stacks you need.

std::vector<std::stack<int>> data;
data.resize(<Number-Of-Stacks-You-Need>);

That should solve your memory problems.

Looking at your code we could go into your design of MyStack (but I think that is superflous). But some common rules:

1. Don't use C facilities when better C++ ones exist.
   scanf() => operator>>
2. Don't mix dynamic memory allocation.
   Only use new and delete in C++ code.
3. Every call to new should be matched with a call to delete
   But you should not even do that normally:
   a. Use local object most of the time.
   b. Use containers when you have groups of objects.
   c. When you really need dynamic allocation use smart pointers.
4. Learn the Rule of 3

Answer 2

The most obvious way to reduce memory usage of this program would be to use dynamic arrays instead of a linked lists for your stacks.

As it stands right now, for every int you store in your stack, you're also storing two pointers. That will typically mean that you end up storing at least 8 bytes of pointers for every 4 bytes of data. On some systems, it could even be 16 bytes of pointers for every byte of data.

It gets worse though: in many typical implementations, the size of block you get from malloc will be rounded up to the next power of 2 in size. As such, each node in your linked list could easily be up to half again larger (or so) than the data you're actually storing in the node.

If you really insist on using a linked list, it looks like you can still improve memory consumption a fair amount (probably enough, given that you're nearly within limits anyway). Right now, you're using MyStack as both the stack and the node. That means every node in the linked list has a top pointer. At least from the looks of things, you really only need one top pointer per stack, rather than one per node.

If you simply separate your stack node, you can eliminate this redundancy:

class MyStack { 
    class Node { 
        int data;
        Node *next;
    };

 public:
     void push(int x) { 
         Node *tmp = malloc(sizeof(*tmp));
         tmp->next = top;
         top = tmp;            
     }
 private:    
    Node *top;
};

Although it (probably) won't affect memory usage, I'd also switch to using new instead of malloc, and probably provide a constructor for the Node type:

struct Node { 
    int data;
    Node *next;

    Node(int data, Node *next) : data(data), next(next) { }
};

That simplifies the code to (for example) add an item:

void MyStack::push(int data) { 
    top = new Node(data, top);
}

[Note that the classes here are not intended to be anywhere close to complete; they're fragments to demonstrate specific points.]