减少邻接表的内存需求

Question

我广泛使用adjacency_list 。 我一次装载了许多图形，导致内存成为问题。我正在进行静态程序分析，并在boost图中存储反汇编二进制文件的调用图和流程图。因此，我可能会有几万个函数==流程图和一个巨大的调用图。尽管如此，我仍然希望在使用BGL的情况下减少我的图形的内存使用率。

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

更多问题： 1）使用顶点和边属性的内存开销是多少？ 我有相当多的它们。 2）是否可以说服BGL使用shrink_to_fit习语？ 据我所知，邻接列表使用push_back添加边缘。 是否可以通过将生成的向量与自身的副本交换来减少内存使用？ 也许通过复制整个图形？ 3）是否可以在BGL中使用boost池分配器？ 据我所知，BGL目前执行许多小型分配-出于空间和运行时效率原因，我真的很想避免这种情况。

是否有人已经构建了针对内存使用进行优化的BGL版本？ 我应该尝试使用现有的图形结构并将其与自定义分配器等相结合，还是编写自己的实现并尝试保持与BGL的接口兼容性，以便可以继续使用其算法？

最好的问候。

Sören

- BuschnicK

---

也许这不是你想要的答案，但是当涉及到字节计数作为一些准备工作用于某些仅用于少数任务的boost库的黑客攻击时，你会更快地在Boost用户邮件列表中得到更好的答案http://lists.boost.org/mailman/listinfo.cgi/boost-users。另一个选择是阅读源代码... - gimpf

Answer 1

BGL中有一种名为"压缩稀疏行"的图形类型，它似乎是相当新的，没有从索引页面链接过来。然而，它使用了一个非常巧妙的小技巧，使得图形表示尽可能地小。 http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/compressed_sparse_row.html 对于我们的某些图形，使用这个方法已经成功地将总内存使用量减少了20%——因此，这是一种非常值得优化的方法。

它还将顶点/边属性存储在向量中，因此对于这些属性也具有最小的开销。

请注意，与最新的boost 1.40一起提供的版本仅支持定向图（而不是双向图）。如果您需要能够有效地迭代顶点的出边和入边（就像我一样），则需要从子版本控制中检查boost trunk。Jeremiah非常乐意在我的请求下添加了该功能。

- BuschnicK

Answer 2

1. 开销取决于您使用的版本，以及是否选择了“捆绑”属性。我只使用过捆绑属性，并且在阅读代码时，我预计每个属性捆绑会花费您2个指针+您正在使用的捆绑类型的大小+每个附加属性的大小。据我所知，二进制文件中没有留下任何概念检查内容。但是，既然您有代码，为什么不测量成本呢？如果您没有任何工具可用于尝试，在已知大小的缓冲区中生成已知大小的图形。最终将会失败，此时您应该拥有数量。

2. 您是否尝试过调用adjacency_list<blah>.swap(adjacency_list& x)？ 我希望这将适当地缩小容器。

3. ???

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

- Mike Burrows

---

是的，我已经尝试了收缩到适合大小（建议2），但没有什么帮助。我们还在使用数据库后端，当前支持mySQL、postgreSQL和SQLite。然而，我们对这些特定算法的访问模式确实需要一种内存中的专用数据结构。 - BuschnicK

Answer 3

由于BGL旨在与传统或自定义图形进行互操作,因此最好编写自己的图形。

- me22

Answer 4

回答：

3）是否可以在BGL中使用boost池分配器？据我所知，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;

- Lior Kogan