c++ - C++でデータのメモリサイズを減らす方法は?

Question

私は C++ に取り組んでおり、データの保存に multimap を使用しています。

 struct data
 {
      char* value1;
      char* value2;

      data(char* _value1, char* _value2)
      {
           int len1 = strlen(_value1);
           value1 = new char[len1+1];
           strcpy(value1,_value1);

           int len2 = strlen(_value2);
           value2 = new char[len2+2];
           strcpy(value2,_value2);
      }
      ~data()
      {
           delete[] value1;
           delete[] value2;
      }
 }

 struct ltstr
 {
     bool operator()(const char* s1, const char* s2) const
     {
          return strcmp(s1, s2) < 0;
     }
 };


 multimap <char*, data*, ltstr> m;

サンプル入力:

  Key               Value
  ABCD123456        Data_Mining Indent Test Fast Might Must Favor List Myself Janki Jyoti Sepal Petal Catel Katlina Katrina Tesing Must Motor blah blah.
  ABCD123456        Datfassaa_Minifasfngf Indesfsant Tfdasest Fast Might Must Favor List My\\fsad\\\self Jfasfsa Katrifasdna Tesinfasfg Must Motor blah blah.
  tretD152456       fasdfa fasfsaDfasdfsafata_Mafsfining Infdsdent Tdfsest Fast Might Must Favor List Myself Janki

入力には 2700 万のエントリがあります。入力サイズ = 14GB

しかし、メモリ消費量が 56 GB に達することに気付きました。メモリサイズを減らす方法を教えてください。

Answer 1

実際に格納するデータの量を減らすことができない場合は、オーバーヘッドの少ない別のコンテナーを使用するか (マップとマルチマップにはかなりの量があります)、データの一部のみを保持する方法を見つけることをお勧めします。メモリー。

以下のライブラリを参照してください。

• STXXL: http://stxxl.sourceforge.net/

• Google CPP-Btree: https://code.google.com/p/cpp-btree/

Answer 2

1つの可能性は、マルチマップのstd::map<char *, std::vector<data> >代わりに使用することです。マルチマップでは、各エントリにキー文字列を格納します。マップを使用すると、キー文字列のコピーが1つだけになり、複数のdataアイテムが添付されます。

Answer 3

一部のデータを表示しなくても、プロジェクトのメモリ使用量を改善できることがいくつかあります。

まず、Olaf が提案したように、データ オブジェクトへのポインターではなく、マルチマップにデータ オブジェクトを格納します。ただし、データ構造にプールを使用することはお勧めしません。マップに直接格納する場合と比較して、メモリを節約せずに複雑になるだけです。

ただし、オブジェクトを割り当てるマップ専用のアロケーターを使用できstd::pair<char*, data>ます。これにより、オーバーヘッドとヒープの断片化を抑えることができます。

char*次に、注目すべき主なことは、データ内の 2 つのポインターを取り除くことです。14 ギガのデータでは、ある程度の重複が必要です。それがどのようなデータであるかに応じて、少し異なる方法で保存できます。

たとえば、データが名前またはキーワードである場合、それらを中央ハッシュに格納することは理にかなっています。はい、上記のように DAWG のようなより洗練されたソリューションがありますが、最初に単純なソリューションを試す必要があると思います。

に格納してイテレータを格納するだけで、std::set<std::string>すべての重複が圧縮され、多くのデータが節約されます。これは、文字列を削除しないことを前提としています。文字列を削除するには、参照カウントを行う必要があるため、 のようなものを使用しますstd::map<std::string, unsinged long>。ただし、参照カウントロジックをデータクラスに入れるのではなく、このハッシュを継承する/含むクラスを作成することをお勧めします。

ただし、格納しているデータに多くのオーバーラップがない場合 (バイナリ データなど) は、代わりにstd::stringorに格納することをお勧めしますstd::vector<char>。その理由は、データ構造内のロジックを取り除き、. に置き換えることさえできるからstd::pairです。

また、キーは、データ構造に格納しているポインターの 1 つではないと想定しています。もしそうなら、間違いなくそれを取り除き、マルチマップでのfirst属性を使用std::pairしてください。

保存しているデータの種類によっては、さらに改善できる場合があります。

したがって、おそらくデータには当てはまらない多くの仮定を使用すると、次のようになります。

typedef std::set<std:string> StringMap;
typedef StringMap::const_iterator StringRef;
typedef std::multimap<StringRef, std::pair<StringRef, StringRef>> DataMap;

Answer 4

キーのメモリをリークしているか、不必要に複製していると思われます。キーchar *文字列はどこから来て、どのようにメモリを管理していますか?

データ オブジェクトと同じ文字列である場合は、 のmultiset<data *, ltdata>代わりに を使用することを検討してmultimapください。

重複する文字列が多数ある場合は、文字列を にプールしてset<char *,ltstr>重複を排除することを検討してください。

Answer 5

data最初の最適化は、ポインタの代わりにオブジェクトを格納することです

std::multimap <char*, data, ltstr> m;

を使用data*すると、割り当てに追加のメモリ オーバーヘッドが追加されるためです。

もう 1 つは、プール アロケータ/メモリ プールを使用して、動的メモリ割り当てのフットプリントを削減することです。

同一のキー文字列が多数ある場合は、キーを再利用できれば、それも改善できます。

Answer 6

ここで何が起こっているのかはまだ完全にはわかりませんが、メモリのオーバーヘッドが少なくとも問題の一部であるようです。ただし、全体のメモリ消費量は、data構造体に必要なメモリの約 4 倍です。27M のレコードが 14GB を占有している場合、1 レコードあたり約 500 バイトありますが、占有されるスペースは 56GB です。私には、これは、ここに示されているよりも多くのデータが保存されているか、少なくとも一部のデータが複数回保存されていることを示しています。

そして、「ヒープストレージの追加データ」は、実際には私にとっては役に立ちません。Linux では、メモリ割り当てには、最小で約 32 バイトのデータが必要です。16 バイトのオーバーヘッドがあり、割り当てられたメモリ自体が 16 バイトの倍数を占有します。

したがってdata *、マルチマップに格納された 1 つのレコードには、次のものが必要です。

 16 bytes of header for the memory allocation
 8 bytes for pointer of `value1`
 8 bytes for pointer of `value2`
 16 bytes of header for the string in value1
 16 bytes of header for the string in value2
 8 bytes (on average) "size rounding" for string in value 1
 8 bytes (on average) "size rounding" for string in value 2

 ?? bytes from the file. (X)

 80 + X bytes total. 

次にchar *、マルチマップに次のものがあります。

 16 bytes of header for the memory allocation. 
 8 bytes of rounding on average. 

 ?? bytes from the file. (Y)

 24 + Y bytes total. 

マルチマップの各ノードには 2 つのポインターがあります (ある種のバイナリ ツリーであると想定しています)。

 16 bytes of header for the memory allocation of the node. 
 8 bytes of pointer to "left"
 8 bytes of pointer to "right"

 32 bytes total. 

そのため、ファイル内のエントリごとに 136 バイトの「オーバーヘッド」が発生します。27M レコードの場合、4GB をわずかに上回ります。

先ほど言ったように、ファイルにはエントリごとに 500 バイトが含まれているため、14GB になります。

全部で18GBです。

つまり、どこかで何かが漏れているか、計算が間違っています。ここでの計算は間違っているかもしれませんが、上記のすべてが計算したスペースの 2 倍になるとしても、まだ 20GB は計算されていません。

確かに、メモリを節約するためにできることがいくつかあります。

1) に 2 つの文字列を割り当てないでくださいdata。最初に両方の長さを計算し、メモリの 1 つの塊を割り当て、文字列を互いに直後に格納します。

  data(char* _value1, char* _value2)
  {
       int len1 = strlen(_value1);
       int len2 = strlen(_value2);
       value1 = new char[len1 + len2 +2];
       strcpy(value1,_value1);

       value2 = value1 + len1 + 1; 
       strcpy(value2,_value2);
  }

これにより、エントリごとに平均 24 バイトが節約されます。賢く、data、value1、および value2 に一度にメモリを割り当てることで、さらに節約できる可能性があります。しかし、それは少し「賢すぎる」かもしれません。

2) 大量のdataアイテムを割り当てて、一度に 1 つずつ配布することも役立ちます。これが機能するには、空のコンストラクターと「setvalues」メソッドが必要です。

struct data
{
    ...
    data() {};
    ... 
    set_values(char* _value1, char* _value2)
    {
         int len1 = strlen(_value1);
         int len2 = strlen(_value2);
         value1 = new char[len1 + len2 +2];
         strcpy(value1,_value1);

         value2 = value1 + len1 + 1; 
         strcpy(value2,_value2);
    }
}

std::string v1[100], v2[100], key[100];

for(i = 0; i < 100; i++)
{
    if (!read_line_from_file(key[i], v1[i], v2[i]))
    {
        break;
    }
}    

data* data_block = new data[i]; 

for(j = 0; j < i; j++)
{
    data_block[j].setValues[v1[j].c_str(), v2[j].c_str());
    m.insert(key[i].c_str(), &data_block[j]);
}

繰り返しますが、これによって大量のメモリが節約されるわけではありませんが、16 バイトの領域ごとにいくらかのメモリが節約されます。もちろん、上記は完全なコードではなく、「どのように実行できるかを示したもの」です。

3）「キー」がマルチマップのどこから来たのかはまだわかりませんが、キーがvalue1とvalue2のエントリの1つである場合、別のコピーを保存するのではなく、それらの1つを再利用できます[そのようになっていると仮定します現在行われている]。

これが本当の答えではない場合は申し訳ありませんが、「あなたがしていることの説明のどこかで何かが説明されていない」という意味での答えだと思います.

プログラムでどのような割り当てが行われるかを理解することは、間違いなく役立ちます。