inline void add(const DataStruct& rhs) {
using namespace boost::assign;
vec.reserve(vec.size() + 3);
vec += rhs.a, rhs.b, rhs.c;
}
上記の関数は約17000回実行され、vector :: reservedを呼び出すと、 約2桁悪化しました（私が見る限り、いくつかの変換が含まれていました） 。
私はいつも、reserveは小さな値でもpush_backを高速化できるという印象を受けていましたが、これは真実ではないようで、このようにすべきではない明確な理由を見つけることができません。リザーブは関数のインライン化を防ぎますか？size（）の呼び出しは高すぎますか？これはプラットフォームに依存しますか？クリーンな環境でこれを確認するために、いくつかの小さなベンチマークをコーディングしてみます。
コンパイラ：gcc (GCC) 4.4.2-g-O2を使用
のGCC実装は、reserve()正確な数の要素を割り当てpush_back()ますが、内部バッファを2倍にすることで指数関数的に増加するため、指数関数的増加を打ち負かし、反復ごとに再割り当て/コピーを強制します。ltraceまたはの下でテストを実行し、呼び出しvalgrindの数を確認します。malloc()
使用する場所が事前にわかっている場合は、予約のみを使用してください。
Reserve はベクター全体をコピーする必要があります...
push_back を実行し、ベクトルが小さすぎる場合は、予約 (vec.size()*2) が実行されます。
ベクトルの大きさが事前にわからない場合や、ランダム アクセスが必要な場合は、std::deque の使用を検討してください。
reserve()要素の数が事前にわかっている場合にのみ使用します。その場合reserve()、一度にすべての要素のスペース。
それ以外の場合push_back()は、デフォルトの戦略を使用して依存するだけです。これにより、指数関数的に再割り当てが行われ、再割り当ての数が大幅に削減されますが、最適ではないメモリ消費がわずかに発生します。
std::vector を再割り当てする必要がある場合、その割り当てサイズは N*2 ずつ増加します。ここで、n は現在のサイズです。これにより、ベクトルが大きくなるにつれて、対数の数の再割り当てが行われます。
代わりに、std::vector が割り当てられたスペースを一定量だけ増やした場合、reallocs の数は vector が大きくなるにつれて直線的に増加します。
あなたが行ったことは、基本的に、ベクトルを一定量 3 だけ成長させることです。つまり、線形成長を意味します。線形は明らかに対数よりも悪く、特に大きな数値では顕著です。
一般に、対数よりも優れた唯一の成長は一定です。そのため、標準化委員会は予約メソッドを作成しました。すべての再割り当て (定数) を回避できれば、デフォルトの対数動作よりも優れたパフォーマンスが得られます。
とはいえ、ベクターよりも std::deque を好むことについての Herb Sutter のコメントを検討することをお勧めしますwww.gotw.ca/gotw/054.htm
コードをプロファイリングした場合、+ =が非常に高速であることがわかると思いますが、問題は予備があなたを殺していることです。ベクトルがどれだけ大きくなるかについてある程度の知識がある場合にのみ、予備を使用する必要があります。事前に推測できる場合は、1つの予約を行います。それ以外の場合は、デフォルトのpush_backを使用します。
予備を追加の外に移動します。
「追加」を呼び出すたびに、少なくとも 3 つの余分な要素が予約されます。vector の実装によっては、「add」を呼び出すたびにバッキング配列のサイズが増加する可能性があります。それは間違いなくあなたが説明するパフォーマンスの違いを引き起こすでしょう.
予約を使用する正しい方法は、次のようなものです。
vec.reserve(max*3);
for(int i=0; i<max; i++)
add(i);