なぜunordered_setは、それに含まれるデータよりも大幅にRAMを使用していますか？

Question

私は比較的大きなファイルを持っています。ファイルはわずか500MBです。私はオーバーヘッドがたくさんあることを理解していますが、私は約5GBのRAM使用量を見ていました。私はこれを外部のマージソートを使って実行し、少量のRAMを維持することができましたが、これはコードの方が速いようでした。

私はVC++ 14を使用しています。

#include <string> 
#include <vector> 
#include <fstream> 
#include <iostream> 
#include <algorithm> 
#include <unordered_set> 

using std::vector; 
using std::string; 
using std::unordered_set; 

class uniqify { 
    unordered_set<string> s; 
public: 
    auto exists(const string &filename) const -> bool { 
     std::ifstream fin(filename); 
     bool good = fin.good(); 
     return fin.close(), good; 
    } 

    void read(const string &filename) { 
     std::ifstream input(filename); 
     string line; 
     while (std::getline(input, line)) 
      if (line.size()) 
       s.insert(line); 
    } 

    void write(const string &filename) const { 
     std::ofstream fout(filename); 
     for (auto line : s) 
      fout << line << "\n"; 
     fout.close(); 
    } 
}; 

int main(int argc, char **argv) { 
    uniqify u; 
    string file("file.txt"); 
    if(u.exists(file)) 
     u.read(file); 
    u.write("output_file.txt"); 
    return 0; 
} 

なぜRAMが10倍以上急増するのでしょうか？

Answer 1

unordered_setは、ノードベースのコンテナです。前回チェックしたとき、MSVCは二重リンクリストを使用して要素を格納し、イテレータのベクトルをそのリンクリストに格納してバケットの輪郭を描きました。 max_load_factor()のデフォルト値はunordered_setです。したがって、少なくとも複数のバケットがノードとして存在します。そして、1つのバケットあたり1つのポインタである約1つのlistイテレータを格納します。したがって、各ノードに対して、二重リンクリストからの2つのポインタのオーバーヘッドと、バケットからの少なくとも1つのポインタと、合計3つのポインタがあります。

次に、std::stringは、上に独自のオーバーヘッドを追加します。 MSVCのstd::stringは、2つのポインタ+ 16バイトのSSO bufferと思われます。 15文字を超える文字列は動的割り当てを使用しますが、これはより多くの費用がかかります。

したがって、セット内の各文字列は、少なくとも5つのポインタ+ 16バイトのSSOバッファを必要とします。ポインタあたり8バイトで、最小文字列あたり56バイトです。そこには約3GBの55M文字列があります。また、15文字以上の文字列やノードごとのメモリ割り当てのオーバーヘッドはカウントされていません。これにより、簡単に最大5GBまで増やすことができます。

Answer 2

C++コンパイラのベンダーがどの実装を提供しているかにかかわらず、データ構造に伴うオーバーヘッドがあります。

他の類似の性質を持つthis question以外のディスカッションに従うと、ほとんどのベンダーは順序付けられていないセットを実装するためにハッシュテーブルを使用する可能性が高く、ハッシュテーブルのサイズを変更し、かなりの数のエントリが動的に追加されました。動的なサイズ変更を考慮するのではなく、適切なサイズにテーブルを割り当てる必要があります。

しかし、あなたのシステムでどのような実装が使用されているのかわからないので、これは単なる推測です。