减少邻接列表的内存需求

Question

我正广泛使用adjacency_list <vecS,vecS,bidirectionalS ...>.我有很多图表一次加载,内存成为一个问题.我正在进行静态程序分析,并将反汇编二进制文件的调用图和流程图存储在boost图中.因此,我可以拥有几万个函数== flowgraphs和一个巨大的调用图.我还是希望在使用BGL的同时减少图形的内存使用量.

由于我的图形在加载后是静态的,并且预先知道边缘和顶点计数,因此我看到了巨大的优化潜力.例如,我想为单个图的所有顶点/边分配一个缓冲区,让图只将索引存储到该缓冲区中.

更多问题:
1)使用顶点和边缘属性的内存开销是多少？我有很多.
2)是否有可能说服BGL使用收缩来拟合成语？据我所知,邻接列表使用push_back来添加边.是否可以通过将结果向量与自身副本交换来减少内存使用量？也许通过复制整个图表？
3)是否可以将升压池分配器与BGL一起使用？据我所知,BGL目前执行大量的小分配 - 我真的希望避免出于空间和运行时效率的原因.

有没有人已经构建了针对内存使用优化的BGL版本？我应该尝试使用现有的图形结构并使用自定义分配器或其他类似的增加它,或者编写我自己的实现并尝试保持与BGL的接口兼容性更有成效,以便我可以继续使用它的算法？

最好的祝福,

Sören

Answer 1

在BGL中有一个鲜为人知的图形类型称为"压缩稀疏行"图.它看起来很新,并没有从索引页面链接.然而,它确实采用了一个漂亮的小技巧来使图形表示尽可能小. http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/compressed_sparse_row.html

对于我们的一些图表使用它,我已经能够将总内存使用量减少20% - 所以这确实非常值得优化.

它还将顶点/边缘属性存储在向量中,从而为这些属性提供尽可能小的开销.

请注意,使用最新boost 1.40的版本仅支持方向图(而不是双向).如果你需要能够有效地迭代顶点的边缘和边缘(就像我所做的那样),你需要从subversion中检出boost trunk.Jeremiah非常乐于根据我的要求添加该功能.