2

私は、メモリの小さなチャンクを大量に使用するグラフ アルゴリズムを実装する C++ コードをいくつか使用しています (gSpan に関連していますが、それは問題ではありません)。コードは C++ で実装され、std::vectors を使用して多数の小さな要素 (それぞれ 64 バイト程度) を格納します。ただし、元の作成者よりもはるかに大きなデータセットでこれを使用しているため、メモリが不足しています。

ただし、時期尚早にメモリが不足しているようです。断片化?std::vectors は、より多くのメモリが必要になるたびにサイズを大きくしようとしており、ベクトルは連続したメモリを主張しているためだと思います。私は 8GB の RAM と 18GB のスワップを持っていますが、std::bad_alloc がスローされたとき、6.5GB の常駐と最大 8GB の仮想しか使用していません。私は bad_alloc 呼び出しをキャッチし、ベクトルサイズを出力しました。これが私が見ているものです:

size: 536870912
capacity: 536870912
maxsize: 1152921504606846975
terminate called after throwing an instance of 'std::bad_alloc'
    what():  std::bad_alloc

したがって、明らかに、ベクトルの最大サイズに達しており、ライブラリはさらに割り当てようとして失敗しています。

だから私の質問は:

  • それが問題であると仮定するのは正しいですか?
  • 解決策は何ですか(「RAMを購入する」以外)。メモリに収まるように CPU 時間を犠牲にしても構わないと思っています。
  • コード全体を std::list を使用するように変換する必要があります (そして、コードが使用する場所に operator[] を実装する必要がありますか?).. RAM の効率がさらに向上しますか? 少なくとも、リスト要素が連続していないことを許可します...そうですか?
  • このユースケースのベクトルの標準をオーバーライドするために使用できる、より優れたアロケーターはありますか?
  • 私が見逃している他の解決策は何ですか?

最終的にどれだけのメモリが使用されるかわからないので、変更を加えても計算を行うにはまだ十分なメモリがない可能性があることは承知していますが、少なくとももっと多くのことを達成できると思います。すぐにあきらめているようです。

4

1 に答える 1

6

std::dequeの直接ドロップインとして使用してみvectorます。(多くの場合) チャンクのコレクションを使用するため、 を拡張する方が(追加のメモリが必要になるという点で) をdeque拡張するよりもはるかに安価になる可能性があります。vector

于 2013-04-05T19:29:40.263 に答える