How to get memory usage of an adjacency list / transitive closure?

[John Papadopoul]

Hi all,

I'm using the BOOST libraries to compute an adjacency list and its transitive closure. I'm defining them as follows:

...
typedef boost::adjacency_list<> AdjacencyList;
AdjacencyList g_transitiveClosure;
AdjacencyList g_adjacencyList;
...

What I'm doing is:
loop start
add edge information to the g_adjacencyList
compute the transitive closure of the adjacency list
loop end

After that I want to compute the total memory consumption in bytes of each of the above data structure.

I'm using the sizeof operator as follows:

boost::graph_traits<AdjacencyList>::vertex_iterator i, end;
    boost::graph_traits<AdjacencyList>::adjacency_iterator ai, a_end;

    unsigned int _memAL = sizeof(g_adjacencyList);

    for (boost::tie(i, end) = vertices(g_adjacencyList); i != end; ++i)
    {
        _memAL += sizeof(*i);
        tie(ai, a_end) = adjacent_vertices(*i, g_adjacencyList);
        for (; ai != a_end; ++ai)
            _memAL += sizeof(*ai);
    }

    unsigned int _memTC = sizeof(g_transitiveClosure);

    for (boost::tie(i, end) = vertices(g_transitiveClosure); i != end; ++i)
    {
        _memTC += sizeof(*i);
        tie(ai, a_end) = adjacent_vertices(*i, g_transitiveClosure);
        for (; ai != a_end; ++ai)
            _memTC += sizeof(*ai);
    }

The results I get, put me in question that I' doing something wrong.

The bottom line question is that I would like to know if the above method to get the total memory consumption of each data structure in bytes is correct or not.

Thanks in advance.

[Banfa]

It is both correct and not correct at the same time (helpful huh :D).

You need to understand what the size of operator does, it returns the size of the type or the type of the variable that is passed to it. This is calculated at compile time.

As such the number returned to you will be correct however you have to take account of what it doesn't calculate for a class. A class is a compound type made of many member variables, if any of these variables are pointers then one might expect that they point to some allocated data. Logically you might consider that data part of the object but physically the memory for that data is not part of the memory for that type. The size of operator will return the size of the pointer.

#include <iostream>

using namespace std;

class Test
{
public:
  Test()
  {
    pointer = new int [10000];
  }
  ~Test()
  {
    delete[] pointer;
  }

private:
  int *pointer;
};

int main()
{
  Test test;

  cout << sizeof test << endl;

  return 0;
}

Outputs the size of the type Test which is the size of a pointer (4 on my WinXP 32bit system) not the size of the memory allocated to the pointer.

So back to my original statement of correct and yet not correct, that would really be more accurately stated as correct but not useful. sizeof correctly returns the size of the type you have asked it to but that is not the number you want (and hence not useful), you want the size of the data allocated for the object to use and to get that you may have to add a method to call on the object that calculates it.