ヒープフラグメンテーションを避けるためのベストSTLコンテナ

Question

私は150,000のファイルを分析するプログラムを持っています。 Valgrindはメモリリークを報告しませんが、プログラムは時間の経過と共に減速します。

std :: stringをあまりに頻繁に使用し、mktimeを使用することに時間がかかるという問題がありました。 （C++ slows over time reading 70,000 filesを参照してください）

しかし、それはまだ時間の経過とともに減速します。 Lotharyxは、コンテナの使用がヒープフラグメンテーションを引き起こしていることを示唆しています。

私はさまざまなSTLコンテナの賛否両論について様々なフローチャートを読んだが、それほど得られなかった。

以下の擬似コードでは、ヒープの断片化を避けるための適切な選択を行ったかどうかはわかりません。

fileList.clear() 
scan all disks and build "fileList", a std::set of file paths matching a pattern. 

// filepaths are named by date, eg 20160530.051000, so are intrinsically ordered 

foreach(filePath in fileList) 
{ 
    if (alreadyHaveFileDetails(filePath)) 
     continue; 

    // otherwise 
    collect file details into a fileInfoStruct; // like size, contents, mod 

    fileInfoMap[time_t date] = fileInfoStruct; 
} 

// fileInfoMap is ordered collection of information structs of about 100,000 files 

// traverse the list in order 
foreach (fileInfo in fileInfoMap) 
{ 
    if (meetsCondition(fileInfo)) 
    { 
     TEventInfo event = makeEventInfo() 
     eventList.push_back(event); 
    } 
} 

そして、上記の配列は永遠に繰り返されます。

ので、容器の選択のために、私が使用した（または必要性）：

fileList - 15万パス名を含むユニークな文字列のリスト。
私は自動的に重複を処理し、自動的にソート順を維持するので、std :: setを選択しました。 ランダムアクセスはありません。エントリを追加し、それらを（手動または自動で）並べ替え、それらを反復処理するだけです。

fileInfoMap - ファイルの日付に対応するtime_tタイムスタンプでキーを付けられた構造体の配列。 私はstd :: mapを選択しました。それも150,000のエントリを持っているので、多くのメモリを占有します。 ランダムアクセスはありません。エントリを一方のエンドに追加するだけです。それらを反復処理し、必要に応じて中間からエントリを削除する必要があります。

eventList - 「イベント」構造の小さなリスト、たとえば50個のアイテム。 私はstd :: vectorを選択しました。なぜ本当にわからない。 ランダムアクセスはありません。一方のエントリにのみエントリを追加し、後でコレクションを反復処理します。

私はC++をかなり新しくしています。ご検討いただきありがとうございます。

Answer 1

メモリ管理について、コンテナは2つの大きなファミリに属します。つまり、すべての要素をまとめて割り当てるものと、別々に要素を割り当てるものです。

ベクトルとdequeは、最初のファミリに属し、list、set、および2番目のファミリにマップします。

グローバル再配置をサポートしていないコンテナから要素が継続的に追加されたり削除されたりすると、メモリの断片化が発生します。

問題を回避する1つの方法は、を使用し、 "reserve"を使用して、再配置を減らすために必要なメモリを予測し、挿入時にデータを並べ替えることです。

もう1つの方法は、リストやセットなどのような「リンクベースのコンテナ」を使用して、より大きなチャンクからメモリを割り当てるアロケータを提供し、単一の要素の挿入/削除ごとにraw malloc/freeを呼び出すのではなく、 。

あなたは簡単にはstd ::アロケータから派生し、必要なすべてのロジックを追加allocate/deallocate関数をオーバーライドして、コンテナのオプションのテンプレートパラメータとしてyourallocatorを渡すことで、アロケータを書くことができますstd::allocator

に外観を与えますあなたは使いたいです。