[BGL] reducing memory requirements for adjacency list
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. more questions: 1) what's the memory overhead of using vertex and edge properties? I have quite a few of them. 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? 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. 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? best regards, Sören
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
On Sep 1, 2009, at 7:51 AM, Jeremiah Willcock wrote:
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.
Pages 232 and 233 of the BGL book provide an example of how to use the container_gen class to specify an allocator type.
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.
more questions: 1) what's the memory overhead of using vertex and edge properties? I have quite a few of them. 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? 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.
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?
One issue with my last reply: I didn't see that you were using a bidirectional graph type. The CSR graph does not support bidirectional graphs currently; I can put that together or describe how to do it if you want (with the graph structure being about 3x as large, but not duplicating the properties). That might be your best option. -- Jeremiah Willcock
One issue with my last reply: I didn't see that you were using a bidirectional graph type. The CSR graph does not support bidirectional graphs currently; I can put that together or describe how to do it if you want (with the graph structure being about 3x as large, but not duplicating the properties). That might be your best option.
Yes, I absolutely require bi-directional graphs. As I mentioned, the application is static code analysis and a callgraph is inherently bi-directional. So yes, I'd really like to know how to use the CSR graph in a bidirectional manner.
With CSR, the overhead for the properties is just the space the raw data takes up.
Does that mean raw data gets allocated per vertex/edge or in one big buffer indexed by vertex/edge? I'd prefer the later of course. I need to get the number of small memory allocations down to an absolute minimum (i.e. calls to new/mallow with only a few bytes). best regards, Sören
On Tue, 1 Sep 2009, Soeren Meyer-Eppler wrote:
One issue with my last reply: I didn't see that you were using a bidirectional graph type. The CSR graph does not support bidirectional graphs currently; I can put that together or describe how to do it if you want (with the graph structure being about 3x as large, but not duplicating the properties). That might be your best option.
Yes, I absolutely require bi-directional graphs. As I mentioned, the application is static code analysis and a callgraph is inherently bi-directional. So yes, I'd really like to know how to use the CSR graph in a bidirectional manner.
OK. I would suggest creating a wrapper class that contains a CSR graph, an index vector (similar to m_rowstart in the CSR graph but containing start indices for each target), and a vector of edge indices ordered by target. You should easily be able to wrap that up to match the bidirectional graph interfaces. If you would not like to do that yourself, please file a Trac ticket requesting the feature.
With CSR, the overhead for the properties is just the space the raw data takes up.
Does that mean raw data gets allocated per vertex/edge or in one big buffer indexed by vertex/edge? I'd prefer the later of course. I need to get the number of small memory allocations down to an absolute minimum (i.e. calls to new/mallow with only a few bytes).
The latter; there is a vector of vertex properties and a vector of edge properties, each indexed by the numbers of the corresponding objects. -- Jeremiah Willcock
bidirectional graph interfaces. If you would not like to do that yourself, please file a Trac ticket requesting the feature.
I have filed a new ticket #3386. I do believe this feature to be of general interest, so I think a library implementation is preferable to me hacking my own. You'd be the one implementing it? Any idea when it might become available?
The latter; there is a vector of vertex properties and a vector of edge properties, each indexed by the numbers of the corresponding objects.
sweet. best regards, Sören
I have filed a new ticket #3386. I do believe this feature to be of general interest, so I think a library implementation is preferable to me hacking my own.
You'd be the one implementing it? Any idea when it might become available?
I would advise against modifying adjacency list directly. The change is too intrusive. Creating new selectors and specializing the container generation logic can be accomplished without changes to the adjacency_list and will have the effect. Also, I think this approach follows actually matches the design of the data structure more closely. It assigns the allocator to the container, not the graph, which doesn't actually allocate anything. Andrew Sutton andrew.n.sutton@gmail.com
On Wed, 2 Sep 2009, Andrew Sutton wrote:
I have filed a new ticket #3386. I do believe this feature to be of general interest, so I think a library implementation is preferable to me hacking my own.
You'd be the one implementing it? Any idea when it might become available?
I would advise against modifying adjacency list directly. The change is too intrusive. Creating new selectors and specializing the container generation logic can be accomplished without changes to the adjacency_list and will have the effect.
Also, I think this approach follows actually matches the design of the data structure more closely. It assigns the allocator to the container, not the graph, which doesn't actually allocate anything.
I was actually referring to adding bidirectional support to the compressed sparse row graph, since the user's graph is static but needs bidirectional access. The CSR code is much simpler than the adjacency list. -- Jeremiah Willcock
participants (4)
-
Andrew Sutton -
Jeremiah Willcock -
Michael Olea -
Soeren Meyer-Eppler