10

我正在广泛使用 adjacency_list< vecS, vecS, bidirectionalS ... >。我一次加载了这么多图表，以至于内存成为问题。我正在进行静态程序分析，并将反汇编二进制文件的调用图和流程图存储在升压图中。因此我可以拥有数万个函数==流程图和一个巨大的调用图。我真的很想在仍然使用 BGL 的同时减少图表的内存使用量。

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

更多问题：
1）使用顶点和边属性的内存开销是多少？我有很多。
2）是否有可能说服 BGL 使用收缩来适应成语？据我了解，邻接列表使用 push_back 来添加边。是否可以通过将结果向量与自身的副本交换来减少内存使用？也许通过复制整个图表？
3) 是否可以在 BGL 中使用提升池分配器？据我所知，BGL 目前执行了大量的小分配——出于空间和运行时效率的原因，我真的很想避免这种情况。

是否有人已经构建了针对内存使用优化的 BGL 版本？我应该尝试使用现有的图形结构并使用自定义分配器或类似的东西来增加它，还是编写我自己的实现并尝试保持与 BGL 的接口兼容以便我可以继续使用它的算法？

最好的祝福，

Sören
4

4 回答 4

8

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 在我的请求中添加了该功能非常有帮助。

于 2009-09-15T10:42:24.633 回答
1

  1. 开销取决于您使用的版本以及您是否使用“捆绑”属性。我只使用了捆绑属性并阅读了我希望每个属性捆绑包花费您 2 个指针 + 您正在使用的捆绑包类型的大小 + 每个附加属性的大小的代码。二进制 afaik 中没有任何概念检查内容。既然你有代码，为什么不直接衡量成本呢？如果您没有任何工具可以帮助您尝试在已知大小的缓冲区中生成已知大小的图形。有些事情最终会失败，那时你应该有数。

  2. 你试过打电话adjacency_list<blah>.swap(adjacency_list& x)吗？我希望这会适当地缩小容器。

  3. ？？？

我开始编写类似于您所描述的系统的东西，但最终放弃了 BGL，转而编写自己的算法以在所有链接器符号的 sqlite 数据库上运行。

于 2009-09-14T15:14:06.770 回答
0

由于 BGL 旨在与旧图或自定义图互操作，因此您最好编写自己的图。

于 2009-09-09T18:40:38.820 回答
0

作为答案：

3) 是否可以在 BGL 中使用提升池分配器？据我所知，BGL 目前执行了大量的小分配——出于空间和运行时效率的原因，我真的很想避免这种情况。

从这里复制的代码：

 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;
于 2014-02-04T15:20:29.737 回答