20

データの小さなベクトルが多数ある場合にケースを最適化できるかどうかを確認しようとしています。私の使用例では、これらのベクトルが 100,000 以上ある可能性があるため、ベクトル ストレージのサイズが重要になります。それぞれが 1 つまたは 2 つの要素しか持たないこともありますが、多くの場合、容量が大きくなる可能性があります。

シンプルな std::vector を使用してみましたが、メモリを浪費し、タイムクリティカルな環境では時間がかかりすぎるヒープに N 個の小さなバッファーを割り当てるため、これは非常に遅くなります。効果的には、ベクターに対するスモール バッファー最適化 (SBO) が実行可能なソリューションのように見えます。これは、ベクターの内部 (つまりスタック) データがそれを超えるまで使用され、それを超えて初めてヒープを使用する必要があることを意味します。

まさにそれを行うように見えるLLVM SmallVectorに出くわしました。ただし、LLVM フレームワーク内には多くの依存関係があるようで、Boost にも同様のものがあるかどうか疑問に思っていましたか? Boost 実装によって SBO 最適化が実行される可能性がありますが、検索でこれに関する参照が見つかりません。STL 実装は、イテレータに関するいくつかのルールのために、この最適化を行うことは技術的に禁止されていることがわかりましたか?

リンク: LLVM SmallVectorは、LLVM ソフトウェアの内部ソース コードにあります。

4

6 に答える 6

21

Boost v1.58 (2015 年 4 月)のContainerライブラリには、実験的なコンテナーがあります。small_vector

small_vector要素がほとんど含まれていない場合に最適化されたベクターのようなコンテナーです。いくつかの事前割り当て済み要素がインプレースで含まれているため、実際の要素数がその事前割り当て済みしきい値を下回っている場合に、動的ストレージ割り当ての使用を回避できます。LLVM のコンテナにsmall_vector触発されています。SmallVectorとは異なりstatic_vector、small_vector の容量は、最初に事前に割り当てられた容量を超えて拡大する可能性があります。

small_vector<T, N, Allocator>は、事前に割り当てられた要素数から独立した型である に変換可能であり、その引数small_vector_base<T, Allocator>でテンプレート化する必要のないクライアント コードを許可します。Nsmall_vector はすべての vector のメンバー関数を継承するため、配置、ステートフル アロケータなどのすべての標準機能をサポートします。

Electronic Arts Standard Template Libraryのコンテナにも興味があるかもしれません。

Github にリポジトリがあります(固定サイズのコンテナーを見てくださいeastl::vector_*。LLVM の SmallVector に似ています)。

QtにはQVarLengthArrayクラスがあります。

于 2015-05-26T20:55:22.617 に答える
4

まず、LLVM の SmallVector を確実に抽出できます。これには、かなり少量の依存関係とリベラルなライセンスがあります。私の知る限り、SmallVector に直接相当する STL/Boost はありません。ただし、Folly には小さなベクター クラスがあります ( https://github.com/facebook/folly )

于 2013-08-30T18:49:51.440 に答える
4

機能リクエストとして、boost でチケットを作成します: チケット #9165 ( https://svn.boost.org/trac/boost/ticket/9165 )

于 2013-09-26T12:20:01.910 に答える