std :: unordered_map非常に高いメモリ使用量

Question

昨日私はunordered_mapを使用しようとしましたが、このコードは使用したメモリの量を混乱させました。

typedef list<string> entityId_list; 
struct tile_content { 
    char cost; 
    entityId_list entities; 
}; 
unordered_map<int, tile_content> hash_map; 

for (size_t i = 0; i < 19200; i++) { 
    tile_content t; 
    t.cost = 1; 
    map[i] = t; 
} 

これらのコード部分はすべて、デバッグモードでMS VS2010でコンパイルされました。 私の仕事マネージャーで見たことは、約1200kbの "クリーン"プロセスでしたが、hash_mapを埋め込んだ後、8124kbのメモリを使用します。 unordered_mapの通常の動作ですか？なぜそんなに多くのメモリが使われたのですか

Answer 1

unordered_map構造体は、追加、削除、ルックアップ、および無秩序なトラバースを効率的にする方法で多数のオブジェクトを保持するように設計されています。これは、小さなデータ構造にとってメモリ効率の良いものではありません。サイズ変更に伴うペナルティを避けるために、最初に作成されたときに多くのハッシュチェーンヘッドを割り当てます。

Answer 2

これは必ずしもハッシュマップが非常に多くのメモリを使用しているわけではありませんが、プロセスがその量のメモリをOSから要求していることを意味します。

このメモリは、プログラムによるmalloc/new要求を満たすために使用されます。いくつか（またはほとんどの場合、私はこれについてはわかりません）メモリアロケータは、効率のためにその時点で必要とされるより多くのメモリをOSから必要とします。

unordered_mapで使用されているメモリの量を知るには、perftoolsのようなメモリプロファイラを使用します。

Answer 3

これは〜20kオブジェクトで約6MBなので、オブジェクトあたり300バイトです。ハッシュテーブルのサイズが、現在のエントリよりも数倍多くのバケットを持つことができれば、各バケット自体が衝突するオブジェクトのリストまたはベクトルへのポインタになる可能性があります。すべてのヒープ割り当ては、おそらく最も近い2の威力、そしてあなたが何らかの余分な鼓動を生み出すかもしれないデバッグがあるなら、それはすべて私にとって正しいことと思う。

とにかく、デバッグビルドの何かのメモリやCPUの効率を共感できません; -P。マイクロソフトは、そこに好きなようなものを挿入することができ、ユーザーはパフォーマンスについての期待の余地がありません。あなたが最適化されたビルドでそれが悪いと分かったら、あなたは何か話をしています。

もっと一般的には、size()でどのように拡大するのかは非常に重要ですが、プログラムがどのように比較的小さな無秩序マップで膨大なものになるのか疑問に思うのは正当です。あるベクトルの無差別な検索、ソートされたベクトルのバイナリ検索、またはバイナリツリーは、より効率的であるだけでなく、無秩序なマップよりも優れた性能を発揮するかもしれないことに注目してください。