Why does my custom stack class use so much memory?

Question

I made own stack based on single linked list, and it works fine, but when I took a look at the memory usage... A console application using a stack containing 100k integers took 6.5 MB. It's terrible, because 4 byte * 100k = 0.38 MB. I allocate memory for every 'Unit' struct, which one contains a pointer to the next, but I don't think it would take a lot of memory. What the cause the problem?

template <typename T>
class Stack
{
        struct Unit
    {
        Unit *prev;
        T value;
        Unit(T value);
    };
public:
    Stack();
    void Push(T value);
    int Count();
    T Top();
    T Pop();
    ~Stack();
private:
    unsigned int count;
    Unit *top;

};

template<typename T>
Stack<T>::Unit::Unit(T value)
{
    this->value = value;
    prev = nullptr;
}

template<typename T>
Stack<T>::Stack()
{
    top = nullptr;
    count = 0;
}

template<typename T>
void Stack<T>::Push(T value)
{
    if (top == nullptr)
    {
        top = new Unit(value);
    }
    else
    {
        Unit *tmp = new Unit(value);
        tmp->prev = top;
        top = tmp;
    }
    count++;
}

template<typename T>
T Stack<T>::Pop()
{
    T value = top->value;
    Unit *tmp = top->prev;
    delete top;
    top = tmp;
    count--;
    return value;
}

template<typename T>
Stack<T>::~Stack()
{
    Unit *curr = top;
    if (!curr)
    {
        return;
    }
    while (curr)
    {
        Unit* tmp = curr->prev;
        delete curr;
        curr = tmp;
    }
}

***A console application using a stack containing 100k integers took 6.5 MB. It's terrible, because 4 byte * 100k = 0.38 MB.*** You are not counting the size of the pointer. This should be 4 or 8 bytes. Also your struct may have padding. Print the `sizeof(Unit)` to see how much space each `Unit` occupies. — drescherjm, May 18 '19 at 11:39
How are you measuring memory? Do you know how much of the 6.5MB is typical overhead? — John3136, May 18 '19 at 11:41
When you are done experimenting, just use [std::stack](https://en.cppreference.com/w/cpp/container/stack) — Jesper Juhl, May 18 '19 at 11:43
Here is an example of what I was talking about in the first comment: https://ideone.com/TWPvDv — drescherjm, May 18 '19 at 11:59
I would also be interested in understanding how you got the 6.5MB number. — drescherjm, May 18 '19 at 12:38
I was oriented by the memory occupied by the application depending on the amount of numbers. 100k - https://yadi.sk/i/niuXqIE8U7q72A 1kk - https://yadi.sk/i/SF2YWXUSTiJhPw — Vidosen, May 18 '19 at 12:55
I know that it's an inaccurate way to measure the memory expenditure, but I don't know better. — Vidosen, May 18 '19 at 13:05
I believe that is for your entire process not just the your `st` variable. Your process has memory for all .dlls loaded + 1MB process stack. I am testing now in VS 2017. — drescherjm, May 18 '19 at 13:15
There is also additional memory per allocation in debug mode for heap corruption detection. This is probably the reason for the additional memory over the 100000* sizeof(Unit). In release mode the total application allocation in TaskManager before exiting is 2.6MB. In debug mode it was over 12MB. — drescherjm, May 18 '19 at 13:25
Oh, I didn't know about an additional memory usage in Debug mode, switched it to the release, and everything worked as expected, thank you so much. — Vidosen, May 18 '19 at 13:36

drescherjm · Accepted Answer · 2019-05-18T13:46:06.570

In your calculation for size you did not consider the size of the pointer and any padding the structure may have. A pointer is probably 4 or 8 bytes on your platform. Padding is discussed here: Struct padding in C++

I added a cout in the constructor for your stack to show the size of your struct Unit:

#include <iostream>
template<typename T>
Stack<T>::Stack()
{
    top = nullptr;
    count = 0;

    std::cout << "The size of each unit is "  << sizeof(Unit) << " bytes." << std::endl;
} 

// Rest of code is copied directly from the question.

int main() {

    Stack<int> myStack;

    return 0;
}

And the result was:

The size of each unit is 16 bytes.

The full example is here: https://ideone.com/TWPvDv

Edit:

After seeing that the person asking the question was using Visual Studio I did some additional debugging to understand the situation. In debug mode the debug runtime adds additional space to each allocation to allow for heap corruption detection and heap tracking. I set a break point before the end of main and looked at the memory usage in TaskManager (yes not the most accurate measurement). In Debug mode the whole application used over 12MB while in Release the total memory usage was 2.6MB.

Information about the additional allocation per block is here:

https://learn.microsoft.com/en-us/visualstudio/debugger/crt-debug-heap-details?view=vs-2019

The Debug versions of the heap functions call the standard or base versions used in Release builds. When you request a memory block, the debug heap manager allocates from the base heap a slightly larger block of memory than requested and returns a pointer to your portion of that block. For example, suppose your application contains the call: malloc( 10 ). In a Release build, malloc would call the base heap allocation routine requesting an allocation of 10 bytes. In a Debug build, however, malloc would call _malloc_dbg, which would then call the base heap allocation routine requesting an allocation of 10 bytes plus approximately 36 bytes of additional memory. All the resulting memory blocks in the debug heap are connected in a single linked list, ordered according to when they were allocated.

Why does my custom stack class use so much memory?

1 Answers1