Edvard's blog

STL stack uses a lot of memory
By Edvard, 9 years ago, In English

Hi Codeforces!

Today while solving problem F from Zepto-cup I need an array of linked lists of size about 6·105 and I decided to use std::stack. But I got ML cause that array has a size of about 350MB. Then I replaced std::stack by std::list and got AC. Anyone know why std::stack use so lot of memory?

#include <stack>
#include <cstdlib>
#include <iostream>

using namespace std;

const int N = 600 * 1000 + 3;

stack<int> z[N];

int main()
{
	z[rand()].push(rand());
	cout << z[rand()].size() << endl;
	return 0;
}
=====
Used: 420 ms, 352524 KB

#include <list>
#include <cstdlib>
#include <iostream>

using namespace std;

const int N = 600 * 1000 + 3;

list<int> z[N];

int main()
{
	z[rand()].push_back(rand());
	cout << z[rand()].size() << endl;
	return 0;
}
=====
Used: 0 ms, 4704 KB
  • Vote: I like it
  • +50
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

Cause of tricky deque structure. Deque is not a linked list in GCC right now: you can access to arbitrary element in O(1) time.

Good start to digg into deque implementation.

On my PC this code gives as output:

64
512
64
512
→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +39 Vote: I do not like it

    Deque is just a default container, we can replace it: 

    --- std::stack<int> stack;
+++ std::stack<int, std::vector<int>> stack;

    Output: 4

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      But why stack was not implemented simply as linked list?

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        If you use std::list<> to implement std::stack<>, then for each push/pop there is a heap allocation/deallocation, which is slow.

        If you use std::vector<> to implement std::stack<>, then the allocated memory might be significantly bigger than really used by the stack; also, std::vector<> is required to store data contiguously, and allocating one big chunk of memory is more problematic than allocating many small chunks.

        Therefore we arrive to a container that is "in the middle" between std::list<> and std::vector<>, and is the default underlying container for std::stack<>: std::deque<>.

        P.S. In competitive programming std::stack<T, std::vector<T>> is actually quite good most of the time.

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Actually I asked why stack wasn't implemented as separate container, why it should use another container to store data?

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            First, to reduce code duplication. std::list<>, std::vector<>, std::deque<> are all distinct data structures, and so are implemented separately. But implementing std::stack<> nearly means writing one of the above again. Instead of this it is better to just re-use the existing solution.

            Second, you can see that std::stack<> can be implemented in more than one way. The current interface allows to choose freely between implementations.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              9 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Thanks for an explanation.

              → Reply
»
9 years ago, # |
  Vote: I like it +24 Vote: I do not like it

I've looked at the source of std::deque<T> implementation in libstdc++.

The underlying structure of this type is not just an array of T, but an array of arrays of T. Each of these arrays of T is at least 512 bytes long.

It's obvious that the authors wanted to make the memory footprint be a constant value, instead of C * size(), but the solution appears to be awful.

If you want to get more details, you can read <bits/stl_deque.h>.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    std::deque<T> needs to support constant-time element insertion and removal at the front. This places restrictions on the container implementation.

    → Reply