Re: [Boost-users] [BGL] reducing memory requirements for adjacency list

Subject: Re: [Boost-users] [BGL] reducing memory requirements for adjacency list
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2009-09-01 10:51:28

On Tue, 1 Sep 2009, Soeren Meyer-Eppler wrote:

> Hi,
>
> I'm using adjacency_list< vecS, vecS, bidirectionalS ... >
> extensively. I have so many graphs loaded at once that memory
> becomes an issue. I'm doing static program analysis and store the
> callgraph and flowgraphs of the disassembled binary in boost graphs.
> Thus I can have several ten thausand functions==flowgraphs and one
> gigantic callgraph. I'd really like to reduce memory usage for my
> graphs while still using the BGL.
>
> Since my graphs are static after loading and edge and vertex counts
> are known beforehand I see huge potential for optimization. For
> example, I'd like to allocate a single buffer for all vertices/edges
> of a single graph and let the graph just store indices into that buffer.

The compressed sparse row (CSR) graph provides exactly that.

> more questions:
> 1) what's the memory overhead of using vertex and edge properties? I
> have quite a few of them.

With CSR, the overhead for the properties is just the space the raw data 
takes up.

> 2) is it possible to convince the BGL to use the shrink to fit
> idiom? As I understand it the adjacency lists use push_back to add
> edges. Is it possible to reduce memory usage by swapping the
> resulting vector with a copy of itself? Maybe by copying the whole
> graph?

I believe swapping would work.  If you have the sizes in advance, CSR will 
only allocate each of its buffers once with their final sizes.

> 3) Is it possible to use boost pool allocators with the BGL? As far
> as I can tell the BGL currently performs lots of small allocations -
> I'd really like to avoid that for space and runtime efficiency reasons.

BGL does not currently support allocators.  There is a Trac ticket 
requesting this feature, but I do not believe anyone is working on it.

> Did anyone already build a BGL version optimized for memory usage?
> Should I try using the existing graph structures and augment it with
> custom allocators or somesuch or is it more fruitful to write my own
> implementation and try to stay interface compatible with the BGL so
> I may continue to use it's algorithms?

If you have static graphs, try to use the compressed sparse row graph 
type.  Note that you should use the new interface (see the documentation 
for details) that allows more flexibility in graph construction (edges do 
not need to be sorted, for example).  If you are getting very close to the 
size of your memory (such that you are unable to fit 12 bytes per edge as 
temporary storage, for example), there are other techniques that can be 
used; I can describe those if your memory is that tight.

-- Jeremiah Willcock