folly :: fbvector-改良されたstd :: Facebookからのベクトル

FollyはFacebookによって開発され、内部プロジェクトで使用されるオープンC ++ライブラリです。 メモリとプロセッサリソースを最適化するために、ライブラリには、いくつかの標準コンテナとアルゴリズムの独自の実装が含まれています。 それらの1つはfolly :: fbvector-標準ベクトル（std :: vector）の代替です。 Facebookからの実装は、元のstd :: vectorインターフェイスと完全に互換性があり、変更は常に負ではなく、ほとんど常に測定可能で、多くの場合大幅に、そして時にはパフォーマンスやメモリ消費に大きな影響を与えます。 ヘッダーファイルfolly / FBVector.hをインクルードし、std :: vectorをfolly :: fbvectorに置き換えて、コードで使用します。

例

folly::fbvector<int> numbers({0, 1, 2, 3}); numbers.reserve(10); for (int i = 4; i < 10; i++) { numbers.push_back(i * 2); } assert(numbers[6] == 12);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

やる気

std :: vectorは、多くの人がC ++で動的に割り当てられた配列に使用する、確立された抽象概念です。 また、最も有名で最も使用されているコンテナです。 大きな驚きは、その標準実装により、ベクターの使用効率を改善する多くの機会が残されていることです。 このドキュメントでは、folly :: fbvectorの実装がstd :: vectorのいくつかの側面をどのように改善するかについて説明します。 folly / test / FBVectorTest.cppのテストを使用して、std :: vectorとfolly :: fbvectorのパフォーマンスを比較できます。

メモリ管理

std :: vectorは指数関数的に（一定の成長係数で）成長することが知られています。 この定数の正しい選択における重要なニュアンス。 数値が小さすぎると頻繁な販売につながり、数値が大きすぎると実際に必要以上のメモリを消費します。 Stepanovの初期実装では定数2を使用しました（つまり、push_back呼び出しでベクトル拡張が必要になるたびに、容量が2倍になりました）。



時間の経過とともに、一部のコンパイラはこの定数を1.5に減らしましたが、gccは2を永続的に使用します。実際、定数2がベクトルによって以前に割り当てられたメモリを再利用できないため、定数2がすべての可能な値の中で最悪であることを数学的に証明できます。



これがなぜそうなのかを理解するために、すでに完全に満たされたサイズnバイトのベクトルを想像してください。そこに別の要素を追加しようとしています。 これにより、std :: vectorの実装に従って、次の手順が実行されます。

1. 2 * nバイトのメモリが割り当てられます。 最も可能性が高いのは、現在のベクトルのアドレス空間に割り当てられることです（おそらく、しばらくしてからすぐ後ろになる可能性があります）。
2. 古いベクトルは新しいベクトルの先頭にコピーされます。
3. 新しいベクターに新しい要素が追加されます。
4. 古いベクターが削除されます。

この新しいベクトルを増やす場合は、4 * nに増やし、次に8 * nに増やします。 各ステップkで（2 ^ k）* nバイトのメモリが必要であり、これは常に合計（2 ^（k-1））より大きいため、メモリの新しい割り当てごとに、結合されたすべての以前のベクトルよりも多く必要になります* n +（2 ^（k-2））* n ... +（（2 ^ 0））* n



つまり メモリマネージャは、以前にベクターに割り当てられたメモリを再利用することはできず、常に「新しい」メモリの割り当てを強制されます。 これが本当に私たちが望んでいることではないでしょう。 したがって、2未満の数値は、ベクターの容量を増やすいくつかのステップで、新しいアドレス空間にメモリーを割り当てることはできませんが、このベクターに既に割り当てられているメモリーを再利用することを保証します。



グラフは、容量増加定数が1.5（青色の線）の場合、ベクトルを増加する4番目のステップの後、3番目の後に1.45（赤い線）、2番目の後に1.3（黒い線）でメモリを再利用できることを示しています。







もちろん、上記のグラフは、メモリアロケータが実際にどのように機能するかについていくつかの単純化を行っていますが、選択されたgcc定数2が理論的に最悪の場合は変わりません。 fbvectorは定数1.5を使用します。 また、fbvectorがjemallocと相互作用する方法のため、小さなベクトルサイズでのパフォーマンスには影響しません。

jemallocとの相互作用

ほとんどすべての最新のメモリアロケータは、メモリ管理のオーバーヘッドを最小限に抑えると同時に、割り当てられた小さなサイズのブロックで良好なパフォーマンスを提供するように選択された特定の量でメモリを割り当てます。 たとえば、アロケーターは次のようなブロックを選択できます：32、64、128、... 4096、1 MBまでのページサイズに比例して、512 KBの増分など。



上で説明したように、std :: vectorにはメモリの量子化も必要です。 次のクォンタムのサイズは、ベクトルの現在の容量と成長定数に基づいて決定されます。 したがって、ほぼすべての瞬間に、ベクターの最後に現在使用されていない一定量のメモリがあり、その直後にアロケータによって割り当てられたメモリブロックの終わりに一定量の未使用メモリがあります。 結論自体は、ベクトルアロケーターと共有メモリアロケーターの結合によりRAMの消費を最適化できることを示唆しています。ベクトルはアロケーターに「理想的な」サイズのブロックを要求し、アロケーターによって割り当てられたブロックの未使用メモリーを削除できるためです。 まあ、一般に、ベクトルとアロケーターによるメモリの割り当ての一般的な戦略は、両方の正確な実装を知っていれば、より良くすることができます。 これは、fbvectorが行うこととまったく同じです。jemallocの使用を自動的に決定し、メモリ割り当てアルゴリズムに合わせて調整します。



一部のメモリアロケータは、インプレース割り当てをサポートしていません（ただし、ほとんどのメモリアロケータはサポートしています）。 これは、以前に割り当てられたメモリを再利用するか、新しいメモリを割り当てるか、そこにデータをコピーして古いメモリを解放するかを決定するrealloc（）関数の設計があまり成功していないためです。 このメモリ割り当ての制御の欠如は、C ++のnew演算子とstd：allocatorの動作の両方に影響します。 これはパフォーマンスに重大な打撃を与えます。インプレース展開は非常に安価であるため、メモリ消費を増やすための攻撃的な戦略がはるかに少ないためです。

オブジェクトの割り当て

C ++オブジェクトをメモリに配置する際の重要な問題の1つは、デフォルトでは不動と見なされることです。 タイプのオブジェクトは移動可能であると見なされ、ビット単位のコピーによって別のメモリ位置にコピーでき、同時に新しい場所でオブジェクトはその有効性と完全性を完全に保持します。 たとえば、int32は移動可能です。これは、4バイトが32ビット符号付き数値の状態を完全に記述しているため、これらの4バイトを別のメモリ位置にコピーすると、このメモリブロックが完全に同じ数値として完全に解釈できるためです。



オブジェクトが移動不可能であるというC ++の仮定は、すべての人に害を及ぼし、物議を醸すいくつかのアーキテクチャ上の問題のためにのみそうします。 オブジェクトの移動には、新しいオブジェクトのメモリの割り当て、コピーコンストラクターの呼び出し、古いオブジェクトの破棄が含まれます。 これはあまり快適ではなく、一般的に常識に反します。 キャプテンピカードと懐疑的なエイリアンの理論的な会話を想像してください。



懐疑的なエイリアン ：それで、あなたのこのテレポート-それはどのように機能しますか？

ピカード ：彼は男を連れて行き、ある場所で物質化を解除し、別の場所で物質化する

懐疑的なエイリアン ：うーん...それは安全ですか？

Picard ：はい、最初のモデルの真実は小さな欠陥でした。 最初は、人は単純にクローン化され、新しい場所で作成されました。 その後、テレポートオペレーターはオリジナルを手動で撮影する必要がありました。 オブライエンに聞いてください。彼はこの役職でインターンとして働いていました。 実装はあまりエレガントではありませんでした。



（ 翻訳者のメモ ：どうやら、これは最新のC ++標準でムーブコンストラクターが導入される前に書かれたようです）。



実際、オブジェクトの一部のみが本当に動かないものです。

• 外部オブジェクトへのポインターを持つもの
• 他のオブジェクトからのポインターが指すもの

最初のタイプのオブジェクトは、最小限のコストでいつでもやり直すことができます。 2番目のタイプのオブジェクトは、new演算子で作成したり、delete演算子で削除したりしないでください。スマートポインターで制御する必要があり、問題はありません。



移動可能なオブジェクトは、std :: vectorにとって非常に興味深いものです。ベクトル内でオブジェクトを移動する方法に関する知識は、これらのオブジェクトのベクトル分布の効率に大きく影響するためです。 上記のピカルドフ移動ループの代わりに、オブジェクトを単純なmemcpyまたはmemmoveで移動できます。 たとえば、ベクター<vector>またはベクター<hash_map <int、string >>などのタイプの操作は、大幅に高速化できます。



オブジェクトの安全な移動をサポートするために、fbvectorは「folly / Traits.h」で定義されている特性folly :: IsRelocatableを使用します。 デフォルトでは、folly :: IsRelocatable :: valueは保守的にfalseを返します。 ウィジェットタイプが再配置可能であることが確実にわかっている場合は、このタイプを宣言した直後に以下を追加できます。

 namespace folly { struct IsRelocatable<Widget> : boost::true_type {}; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そうしないと、fbvectorはBOOST_STATIC_ASSERTでコンパイルされません。

追加の制限

「単純な」型（より正確には、単純な代入操作を持つ型）または例外をスローしないコンストラクターを持つ型（デフォルトコンストラクターをスローしない）に対しても、いくつかの改善が可能です。 幸いなことに、これらの特性はC ++標準に既に存在しています（まあ、またはBoostにあります）。 要約すると、fbvectorを使用するには、ウィジェットタイプが次の条件を満たす必要があります。

 BOOST_STATIC_ASSERT( IsRelocatable::value && (boost::has_trivial_assign::value || boost::has_nothrow_constructor::value));
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これらのタイプは実際には非常に似ています-条件の一部を満たし、他の部分に違反するクラスを構築するのはかなり困難です（実際に一生懸命努力しない限り）。 fbvectorは、これらの単純な条件を使用して、基本的なベクトル操作（push_back、insert、resize）のコピー操作を最小化します。



Traits.hのfbvectorとの互換性の型チェックを簡素化するために、マクロFOLLY_ASSUME_FBVECTOR_COMPATIBLEがあります。

その他

fbvectorの実装は、メモリ効率に重点を置いています。 memcpyはgccの組み込み関数ではなく、大きなデータブロックに対して完全に機能しないため、将来、コピーの実装が改善される可能性があります。 jemallocとの相互作用の改善も可能です。



fbvectorを使用して頑張ってください。