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

2014-01-27

An answer to this question on Stack Overflow.

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

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:

Tic-Tac-Toe Game Tree

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.