🕳️ 🧓🏽 🈳 軽量コンテナー実装ベクトル 🅿️ ⚖️ 🕙

STLライブラリのベクターテンプレートは、ほぼすべての点で通常のC ++配列で勝ちます。要素を追加および削除したり、破棄時に割り当てられたメモリを解放したり、配列から抜け出す方法を制御したりできます。それにもかかわらず、彼には1つの欠点があります-彼の仕事には小さなメモリが必要ですが、場合によっては重要です。コンテナの実装について以下に説明します。これにより、メモリコストをわずかに削減し、パフォーマンスを向上させることができます。

まず、このメモリが使用される理由と必要な量を把握する必要があります。配列の先頭へのポインタに加えて、テンプレートには、埋められた配列の末尾へのポインタ、割り当てられた配列の末尾へのポインタ、およびメモリアロケータが格納されます。説明のために、コードを示します。

//       
      

        
        
        
      

     template < class TEntry, class TAllocator > class TArrayBase 
      

        
        
        
      

     { 
      

        
        
        
      

     //   
      

        
        
        
      

     TEntry* GetStart() const { return m_Start; } 
      

        
        
        
      

     //   (  ,   ) 
      

        
        
        
      

     TEntry* GetFinish() const { return m_Finish; } 
      

        
        
        
      

     //    (  ,   ) 
      

        
        
        
      

     TEntry* GetEndAllocated() const { return m_Storage._M_data; } 
      

        
        
        
      

     //      
      

        
        
        
      

     TEntry* m_Start; 
      

        
        
        
      

     TEntry* m_Finish; 
      

        
        
        
      

     // ,     
      

        
        
        
      

     //        
      

        
        
        
      

     _STLP_alloc_proxy<TEntry*, TEntry, allocator_type> m_Storage; 
      

        
        
        
      

     };

ポインターが4バイトを必要とする32ビットx86コードの場合、そのようなオブジェクトには12バイトが必要です。メモリアロケーターがデータフィールドと仮想関数なしで使用される場合（標準のアロケーターはそれだけです）、少なくともSTLPortの実装では、実装の成功に置き換わりません。 VS2005のライブラリでは、実装はあまり成功せず、アロケーターはさらに4バイトを追加します。したがって、通常の配列へのポインターと比較して、少なくとも8バイトの追加が必要です。

これらの8バイトは、配列自体の要素を格納するために必要なメモリのサイズの次に失われる些細なことのように思えます。ただし、かなりの数の配列が空になることがよくあります。たとえば、ゲームモデルがあり、光源、音源、損傷、その他の属性を持つことができます。それらはどこかに保存する必要があり、配列はこれに非常に適していますが、ほとんどのモデルにはジオメトリのみがあり、これらの配列は未入力のままになります。

これらの余分なバイトが悪いのはなぜですか？私たちの時代のメモリは安価であり、モデル上の余分なバイト数が合計で数百キロバイトになりますが、これは既存のギガバイトに比べてそれほど大きな損失ではありません。実際、オブジェクト内の過剰なデータもパフォーマンスを低下させます。モデルは、たとえば2つのキャッシュラインに収まる代わりに、すでに3つのキャッシュラインを占有し始めます。これにより、処理中のデータのサンプリング時間が長くなります。したがって、ベクトルの機能を維持しながら、何らかの方法で余分なデータを取り除く必要があります。

最初の解決策は、auto_ptr <vector>ポインターを保存することでした。ポインターは同じ4バイトを占有します。ヌルポインターは配列が空であることを意味し、空でないポインターはヒープ上のベクトルオブジェクトを参照します。しかし、このソリューションには多くの欠点があります。

空でない配列の場合、ポインター（4バイト）およびヒープ上のブロックに追加のメモリが必要です（使用されるヒープ実装は、ブロックごとに4サービスバイトを追加します）。
vectorはヒープの別のブロックにあるため、追加の間接性が現れますが、これもキャッシュにとっては悪いことです。
使用中は、常にポインターをチェックする必要があり、エラーが発生します。

最後の欠点は、ポインターを格納するプロキシコンテナーを作成し、そのメソッド内にチェックを実装することで簡単に解消できます。

より良い解決策は、データを2つの部分に分割することです。オブジェクトでは、配列の先頭へのポインタを1つだけ残し、残りの2つのポインタとメモリアロケータを、配列の要素と同じメモリブロックに、最初の要素の直前にプレフィックスの形式で格納します。この場合、空でないメモリ配列には、通常のベクターとまったく同じ量が必要です。空の配列の場合、静的な空の配列へのポインターを1つだけ格納します。これは、多くのメソッドで不要なチェックを回避するため、nullポインターよりも優れています。

コードの次のセクションでは、最初と同じ機能が実装されていますが、データの一部がプレフィックスに格納されています。

//        ( ) 
      

        
        
        
      

     template < class TAllocator > 
      

        
        
        
      

     class TTinyArrayStorage 
      

        
        
        
      

     { 
      

        
        
        
      

     //   
      

        
        
        
      

     char *Finish; 
      

        
        
        
      

     //      
      

        
        
        
      

     _STLP_alloc_proxy< char *, char , allocator_type> Storage; 
      

        
        
        
      

     //    
      

        
        
        
      

     static TTinyArrayStorage<TAllocator> EmptyStorage; 
      

        
        
        
      

     }; 
      

        
        
        
      

     
      

        
        
        
      

     //       
      

        
        
        
      

     template < class TEntry, class TAllocator > 
      

        
        
        
      

     class TTinyArrayBase 
      

        
        
        
      

     { 
      

        
        
        
      

     //   
      

        
        
        
      

     TEntry* GetStart() const { return m_Data; } 
      

        
        
        
      

     //   (  ,   ) 
      

        
        
        
      

     TEntry* GetFinish() const { return (TEntry*)GetStorage()->Finish; } 
      

        
        
        
      

     //    (  ,   ) 
      

        
        
        
      

     TEntry* GetEndAllocated() const 
      

        
        
        
      

     { return (TEntry*)GetStorage()->Storage._M_data; } 
      

        
        
        
      

     //        
      

        
        
        
      

     TTinyArrayStorage<TAllocator> *GetStorage() const 
      

        
        
        
      

     { return (TTinyArrayStorage<TAllocator>*)((( char *)m_Data) - 
      

        
        
        
      

     sizeof (TTinyArrayStorage<TAllocator>)); } 
      

        
        
        
      

     //   
      

        
        
        
      

     TEntry *m_Data; 
      

        
        
        
      

     };

すべての方法ではありませんが、追加の間接性が残ります。インデックスで要素を取得するには、配列の先頭へのポインタで十分ですが、要素を追加または削除するには、プレフィックスブロックからの情報が必要です。配列の要素を調べるには、プレフィックスブロックからのポインターも必要になりますが、この場合、配列の最初の要素からデータを選択する必要があります。最初の要素は、多くの場合、プレフィックスブロックと同じキャッシュラインにあります。生成されたコードのサイズについて話すと、ほとんど増加しません。たとえば、配列のすべての要素を通る通常のループを考えてみましょう。

for (vector<TFoo>::iterator i = in_data.begin(), e = in_data.end(); i != e; ++i) 
      

        
        
        
      

     i->Process();

VS2005コンパイラは、標準ベクトル用に次のコードを作成します。

 00401340 8B 44 24 04 mov eax,dword ptr [esp+4] 00401344 56 push esi 00401345 8B 30 mov esi,dword ptr [eax] 00401347 57 push edi 00401348 8B 78 04 mov edi,dword ptr [eax+4] 0040134B 3B F7 cmp esi,edi 0040134D 74 0F je Test+1Eh (40135Eh) 0040134F 90 nop 00401350 8B CE mov ecx,esi 00401352 E8 D9 FF FF FF call TFoo::Process (401330h) 00401357 83 C6 04 add esi,4 0040135A 3B F7 cmp esi,edi 0040135C 75 F2 jne Test+10h (401350h) 0040135E 5F pop edi 0040135F 5E pop esi 00401360 C3 ret

「ライト」ベクトルの場合：

 00401370 8B 44 24 04 mov eax,dword ptr [esp+4] 00401374 56 push esi 00401375 8B 30 mov esi,dword ptr [eax] 00401377 57 push edi 00401378 8B 7E F8 mov edi,dword ptr [esi-8] 0040137B 3B F7 cmp esi,edi 0040137D 74 0F je Test+1Eh (40138Eh) 0040137F 90 nop 00401380 8B CE mov ecx,esi 00401382 E8 A9 FF FF FF call TFoo::Process (401330h) 00401387 83 C6 04 add esi,4 0040138A 3B F7 cmp esi,edi 0040138C 75 F2 jne Test+10h (401380h) 0040138E 5F pop edi 0040138F 5E pop esi 00401390 C3 ret

ご覧のとおり、コードは5行目を除いてほぼ同じように作成されました。最初の場合、配列の最後へのポインターはベクトルオブジェクトへのポインター（[eax + 4]）に対して、2番目の場合は配列の最初の要素へのポインター（[esi-8] ）

このような実装で発生するメモリアロケーターのいくつかの困難に注意する必要があります。ディストリビュータが標準ではないが、たとえば、2の累乗の倍数を境界に揃える場合、プレフィックスブロックの先頭を揃え、要素はこのブロックのサイズだけシフトします。このような場合、プレフィックスブロックのサイズを考慮する特別なディストリビューターを作成するか、同様の機会をアレイテンプレート自体に入力する必要があります。

結論として、このようなコンテナが積極的に使用されている実際のプロジェクトの数字を引用します。ベクターオブジェクトの合計数は約27万で、約17万が空のままです。つまり、1メガバイト以上のメモリを節約できます。標準のベクターコンテナを使用したコードと比較すると、コードサイズはわずかに増加しました。合計容量は約10 MBで、48 kb増加しています。生産性はわずかに増加し、約1％増加しました。

軽量コンテナー実装ベクトル

More articles: