Unexpectedly high memory usage, using a std::stack and std::map

Question

I'm trying to traverse a tree, in order to visit all possible states of a 4x4 sliding puzzle. The algorithm I wrote was originally recursive, but this proved to be impossible due to the (apparently) very deep tree. It crashed and reported a segfault. I then decided to rewrite the algorithm to do its work iteratively, and from what I can see, it works just fine. However, after a while it starts to slow down tremendously due to swapping. I did some calculations, but can't figure out where all this memory usage is originating from...

The code is posted below, but here are the significant features:

• std::stack<char, std::vector<char>> stack
• std::map<unsigned long long, int> distanceTable

Assuming the memory footprint of the stack is proportional to the number of elements it holds, and assuming the same for the map (where an element is a pair<unsigned long long, int>), I printed out the expected memory footprint:

cout << (stack.size() * sizeof(char) +
         distanceTable.size() * sizeof(pair<unsigned long long, int>))/(1<<20) << "MB\n";

And compared the output to that of top. When my own program reported around 500MB, top reported that it was using over half of all my memory (4GB). This is a factor 4 that is unaccounted for by my reasoning. What am I missing here?

Code:

#include <iostream>
#include <map>
#include <stack>
#include <vector>
#include <sstream>
#include "slider.h"
using namespace std;

typedef Slider<4> Slider4;
typedef Slider4::Move Move;
typedef map<unsigned long long, int> Map;
typedef stack<char, std::vector<char>> Stack;

Move const moves[] = {Slider4::N, Slider4::S, Slider4::E, Slider4::W};
Move const opposite[] = {Slider4::S, Slider4::N, Slider4::W, Slider4::E};

int const moveIdx[] = {0, 1, 2, 3};
int const oppositeIdx[] = {1, 0, 3, 2};


Map generateDistanceTable()
{
    // non-recursive tree-walker to generate the distance-table
    Map distanceTable;
    Stack stack;
    Slider4 slider;
    unsigned long long depth = 1;

    stack.push(-1);
    distanceTable[slider.hash()]= depth;
    while (depth != 0)
    {
        cout << (stack.size() * sizeof(char) + 
                 distanceTable.size() * sizeof(pair<unsigned long long, int>))/(1ULL<<20) << "MB\n";

        int currentMove = stack.top() + 1;

        // find next move
        while (currentMove != 4)
        {
            // Try the move
            if (!slider.move(moves[currentMove]))
            {
                ++currentMove;
                continue;
            }

            // Check the current state of the puzzle
            auto &d = distanceTable[slider.hash()];
            if (d != 0)
            { // already encountered this state -> move back
                int undoMove = oppositeIdx[currentMove];
                slider.moveUnsafe(moves[undoMove]);
                ++currentMove; // try next move
                continue;
            } 

            stack.push(currentMove);
            d = ++depth;
            currentMove = 0;
        }

        if (currentMove == 4)
        {
            int undoMove = oppositeIdx[stack.top()];
            slider.moveUnsafe(moves[undoMove]);
            --depth;
            stack.pop();
        }
    }
}

int main()
{
    Map table = generateDistanceTable();
}

Answer 1

First, std::map is particularly inefficent with regards to memory use. Each value you insert will be placed in a separate node, which in addition to the value, typically contains three pointers and some additional information (2 char in the MS implementation). In addition, each node is typically allocated separately, so the extra overhead needed by the allocator must be added. On a 32 bit system, the total overhead will be at least 20 bytes; on a 64 bit system, 40.

As for std::vector (which underlies your std::stack), it is much, much better, but if you don't use reserve to pre-allocate, it will reallocate from time to time, usually multiplying the capacity by 1.5 or 2. Which means that it may end up occupying a lot more memory than necessary. (Also, depending on the patterns of allocation, the system may not be able to effectively reuse the memory freed during a reallocation.)

Still, it's often preferrable to use an std::vector, kept in order using std::lower_bound, instead of an std::map.

Finally, if you know in advance exactly how many entries the vector will have, or can establish some reasonable upper bound, you can use reserve to pre-allocate. This avoids any risk of doubling the size.

Answer 2

Each entry in the map must have at least an unsigned long long and an int. Most likely, it has two pointers as well (to hold the entries together).

distanceTable.size() * sizeof(char)

Should probably something like:

distanceTable.size() *
    (2 * sizeof (void *) + sizeof (unsigned long long ) + sizeof (int))

Answer 3

The other answers here are nice, so I'll try taking a different tack: reduce the size of your game tree.

The wiki article on game trees shows an example using Tic-Tac-Toe:

Notice that since the board can be mirrored/reflected and rotated, there are, in fact, only 3 unique positions from which to begin the game. Depending on the type of problem you're trying to solve, you may be able to take advantage of similar possibilities.