CODEWITHSUNDEEP
c++memory-managementstack
Vidosen
Vidosen

Reputation: 23

Why does my custom stack class use so much memory?

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;
    }
}

Upvotes: 2

Views: 93

Answers (1)

drescherjm
drescherjm

Reputation: 10837

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.

Upvotes: 3

Related Questions