首页 文章

减少邻接列表的内存需求

提问于
浏览
9

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

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

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

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

最好的祝福,

Sören

4 回答

  • 0

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

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

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

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

  • 0
    • 开销取决于您使用的是哪个版本,以及您是否选择了“捆绑”属性 . 我只使用捆绑属性并阅读代码我希望每个属性包花费你2个指针大小的捆绑类型你正在使用每个附加属性的sizeof . 没有概念检查的东西留在二进制afaik . 既然你有代码,为什么不测量成本呢?如果您没有任何工具来帮助尝试在已知大小的缓冲区中生成已知大小的图形 . 有些东西最终会失败,那时你应该有计数 .

    • 你试过调用 adjacency_list<blah>.swap(adjacency_list& x) 吗?我希望能够适当地收缩容器 .

    • ???

    我开始编写类似你正在描述的系统的东西,但最终放弃了BGL并切换到编写我自己的算法以在所有链接器符号的sqlite数据库上运行 .

  • 1

    由于BGL设计为interoperate with legacy or custom graphs,因此您最好自己编写自己的图形 .

  • 8

    作为答案:

    3)是否可以在BGL中使用boost池分配器?据我所知,BGL目前执行大量的小分配 - 我真的希望避免出于空间和运行时效率的原因 .

    here复制的代码:

    template <class Allocator>
      struct list_with_allocatorS { };
    
      namespace boost {
        template <class Alloc, class ValueType>
        struct container_gen<list_with_allocatorS<Alloc>, ValueType>
        {
          typedef typename Alloc::template rebind<ValueType>::other Allocator;
          typedef std::list<ValueType, Allocator> type;
        };
      }
    
      // now you can define a graph using std::list 
      //   and a specific allocator  
      typedef adjacency_list< list_with_allocatorS< std::allocator<int> >, vecS, directedS> MyGraph;
    

相关问题