10

私は adjacency_list< vecS, vecS, bidirectionalS ... > を広範囲に使用しています。一度に多数のグラフをロードすると、メモリが問題になります。私は静的プログラム分析を行っており、逆アセンブルされたバイナリのコールグラフとフローグラフをブースト グラフに格納しています。したがって、数万の functions==flowgraphs と 1 つの巨大な callgraph を持つことができます。BGL を使用しながら、グラフのメモリ使用量を削減したいと考えています。

私のグラフはロード後に静的であり、エッジと頂点の数が事前にわかっているため、最適化の大きな可能性が見えます。たとえば、1 つのグラフのすべての頂点/エッジに 1 つのバッファーを割り当て、グラフがそのバッファーにインデックスを格納するだけにしたいと考えています。

その他の質問:
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% 削減できました。つまり、最適化には非常に価値があります。

また、頂点/エッジのプロパティをベクトルに保存するため、それらのオーバーヘッドも最小限に抑えられます。

最新のブースト 1.40 に同梱されているバージョンは、(双方向ではなく) 方向グラフのみをサポートすることに注意してください。頂点のアウトエッジとインエッジを効率的に反復できるようにする必要がある場合 (私が行ったように)、subversion からブーストトランクをチェックアウトする必要があります。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

への答えとして：

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 に答える
0

BGL はレガシー グラフまたはカスタム グラフと相互運用するように設計されているため、独自のグラフを作成することをお勧めします。

于 2009-09-09T18:40:38.820 に答える