ホーム>source

バイトブロックをstd :: vectorにコピーする簡単な関数があります:

std::vector<uint8_t> v;
void Write(const uint8_t * buffer, size_t count)
{
    //std::copy(buffer, buffer + count, std::back_inserter(v));
    v.insert(v.end(), buffer, buffer + count);
}
v.reserve(<buffer size>);
v.resize(0);
Write(<some buffer>, <buffer size>);

std::vector<uint8_t>::insert を使用する場合   std::copy を使用する場合よりも5倍速く動作します 。

最適化を有効または無効にしてMSVC 2015でこのコードをコンパイルしようとすると、同じ結果が得られました。

std::copy で何かがおかしいように見える  または std::back_inserter  実装。

あなたの答え
  • 解決した方法 # 1

    std::vector の適切な実装 、 v.insert(v.end(), buffer, buffer + count);  次のように実装できます。

    size_t count = last-first;
    resize(size() + count);
    memcpy(data+offset, first, count);
    
    

    std::copy(buffer, buffer + count, std::back_inserter(v))  一方、次のように実装されます。

    while ( first != last )
    {
       *output++ = *first++;
    }
    
    

    次と同等です:

    while ( first != last )
    {
       v.push_back( *first++ );
    }
    
    

    または(大まかに):

    while ( first != last )
    {
       // push_back should be slightly more efficient than this
       v.resize(v.size() + 1);
       v.back() = *first++;
    }
    
    

    理論的には、コンパイラは上記を memcpy に最適化できます  めったにありませんが、関数呼び出しのオーバーヘッドがないように、おそらくメソッドをインライン化することになるでしょう。memcpyは通常、ベクトル命令を使用して複数のバイトをコピーしますが、一度。

  • 解決した方法 # 2

    標準ライブラリの実装はパフォーマンスを考慮して記述されていますが、パフォーマンスは最適化がオンの場合にのみ達成されます。

    
    //This reduces the performance dramatically if the optimization is switched off.
    
    

    最適化をオフにして関数のパフォーマンスを測定しようとすると、宇宙に質量が残っていない場合に重力の法則がまだ当てはまるかどうかを尋ねるのと同じくらい無意味です。

  • 解決した方法 # 3

    v.insert の呼び出し  コンテナのメンバー関数を呼び出しています。メンバー関数は、コンテナがどのように実装されているかを知っているため、より汎用的なアルゴリズムではできないことを実行できます。特に、ランダムアクセス反復子によって指定された値の範囲をベクターに挿入するとき、実装は追加される要素の数を知っているため、内部ストレージを一度サイズ変更してから要素をコピーするだけです。

    std::copy の呼び出し  一方、挿入反復子では、 insert を呼び出す必要があります  各要素に対して。 std::copy のため、事前に割り当てることができません  コンテナではなくシーケンスで動作します。コンテナのサイズを調整する方法がわかりません。したがって、ベクターへの大規模な挿入の場合、ベクターがいっぱいになるたびに内部ストレージのサイズが変更され、新しい挿入が必要になります。その再割り当てのオーバーヘッドは一定時間で償却されますが、1つのサイズ変更のみが行われる場合、定数は定数よりもはるかに大きくなります。

    reserve への呼び出しで  (見過ごされました、ありがとう、@ ChrisDrew)、再割り当てのオーバーヘッドはそれほど重要ではありません。しかし、 insert の実装  コピーされる値の数を知っており、それらの値がメモリ内で連続していることを知っています(反復子はポインターであるため)。また、値が簡単にコピー可能であることを知っているため、 std::memcpy を使用します  一度にすべてのビットを爆破する。 std::copy を使用 、そのいずれも当てはまりません。バックインサーターは再割り当てが必要かどうかをチェックする必要があり、そのコードは最適化できないため、一度に要素をコピーして各要素に割り当てられたスペースの終わりをチェックするループになります。それは普通の std::memcpy よりもはるかに高価です 。

    一般に、アルゴリズムがアクセスしているデータ構造の内部構造についてより多くの情報を知っているほど、速くなります。 STLアルゴリズムは汎用的であり、その汎用性のコストは、コンテナー固有のアルゴリズムのコストよりもオーバーヘッドが大きくなる場合があります。

  • 前へ java - JPAクエリ:サブクエリをグループ化条件に結合する
  • 次へ java - Spring Boot OAuth2の `AbstractTokenGrantervalidateGrantType()`メソッドで何が起こっているのですか?