ファニースタートまたはC ++とSTL：誰が速いですか？

問題の声明

多数の要素（ループ、STLアルゴリズム、反復子、ポインターなど）で同様の操作を実行するためのさまざまな標準C ++ツールの速度に関心があります。 単純化するために、最初のタスクは多数の整数の合計を計算することであると想定しています。 （読みたくないが見たい人のためのリンク 。）

準備する

最初に、サイクルの速度を評価するコードを記述します。

#include <iostream> #include <sys/time.h> #include <iomanip> using namespace std; const int COUNT = 1000 * 1000 * 1000; int main () { struct timespec tm1, tm2; clock_gettime(CLOCK_REALTIME, &tm1); // Our code to estimate clock_gettime(CLOCK_REALTIME, &tm2); double t1 = 1000.0 * tm1.tv_sec + tm1.tv_nsec / (1000.0 * 1000); double t2 = 1000.0 * tm2.tv_sec + tm2.tv_nsec / (1000.0 * 1000); cout << "t=" << setprecision(5) << t2 -t1 << " ms" << endl; return 0; };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

あまり正確ではありませんが、シンプルでわかりやすいです。



STLの要素の順次列挙では、要素が順次配置されるため、最速のコンテナーはベクトルです。 したがって、COUNTベクトルを作成し、（ほぼ）ランダムな整数値で埋めます。

 #include <vector> #include <algorithm> … int RandomNumber () { static int s = 0; return (s++ % 100); } int main () { vector<int> vec(COUNT); generate(vec.begin(), vec.end(), RandomNumber); ... // Our code to estimate
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

蓄積する

問題を解決する最も適切な方法は、 accumulate関数を使用することです。

 #include <numeric> … // Our code to estimate accumulate(vec.begin(), vec.end(), 0, [](int sum, int i) { return sum + i; });
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

コンパイルして実行します：

 $ g++ -std=c++11 main.cpp -o test && ./test $ duration 349.29 mseconds
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

少なからず...

for_each

for_eachを試してみましょう。

 // Our code to estimate int sum = 0; for_each(vec.begin(), vec.end(), [&sum](int i) { sum += i; });
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

私たちは見ます：

 $ g++ -std=c++11 main.cpp -o test && ./test $ duration 417.64 mseconds
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

興味深いことに、状態を持つオブジェクトを使用すると、少し速くなります： ラムダへのリンクを渡すと、少し遅くなります：

 class Sum { int sum; public: Sum() : sum(0) {} inline void operator()(int i) { sum += i; } inline operator int() { return sum; } }; … // Our code to estimate for_each(vec.begin(), vec.end(), Sum());
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ドラムロール...

 $ g++ -std=c++11 main.cpp -o test && ./test $ duration 371.64 mseconds
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

状態を持つラムダを作成して、 accumulateに匹敵する結果を得ることができますが、ゲームはろうそくの価値がありません：結果はまだ私たちに合わないでしょう。

のために

古き良きサイクルに戻りましょう。

 // Our code to estimate int sum = 0; for(auto i = vec.begin(); i != vec.end(); i++) { sum += *i; };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

それで何？

 $ g++ -std=c++11 main.cpp -o test && ./test $ duration 520.66 mseconds
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

さて、コードを少し変更する理由は理解できます。

 auto end = vec.end(); for(auto i = vec.begin(); i != end; i++) {
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

コンパイルして再実行します。

 $ g++ -std=c++11 main.cpp -o test && ./test $ duration 403.68 mseconds
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

もういい！ また、 接頭辞の増分が接尾辞の増分よりもわずかに速いこともわかっています 。

 for(auto i = vec.begin(); i != end; ++i) {
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これは、後置インクリメント操作が一時オブジェクト+コピーを使用するためです。



コンパイルして実行します：

 $ g++ -std=c++11 main.cpp -o test && ./test $ duration 327.05 mseconds
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

今日の最高の結果！ しかし、まだ夕方ではありません...

サイクルが少し速くなったのはなぜですか？ これは主に、関数呼び出しがなく、オブジェクト（この場合は整数）の余分なコピーがないためです。

イテレータかどうか

一般的にイテレータから拒否します：

 for(int i = 0; i < COUNT; ++i) { sum += vec[i]; };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

コンパイルして実行：

 $ g++ -std=c++11 main.cpp -o test && ./test $ duration 110.52 mseconds
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これが結果です。



ここでは、一度に2つの操作で勝ちました。intの増分は反復子の増分演算子よりも速く 、逆参照演算子はインデックスによるアクセスよりも遅くなります。

配列

しかし、通常の配列を使用するとどうなりますか？ より正確には、インデックスではなく、ポインタのオフセットによって要素を取得します（ベクトルを配列で置き換えることは無意味です-ベクトルはそのデータを配列に格納します）。

 int *array = &vec[0]; for(int i = 0; i < COUNT; ++i) { sum += array[i]; };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そして、それは価値がありました：

 $ g++ -std=c++11 main.cpp -o test && ./test $ duration 81.219 mseconds
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ポインターによるアクセスははるかに高速です！

そして、インデックスなしでポインタをすぐに反復すると、はるかに高速になります：

 auto end = &vec[vec.size () - 1]; for(int *i = &vec[0]; i != end; ++i) { sum += *i; };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

 $ g++ -std=c++11 main.cpp -o test && ./test $ duration 24.494 mseconds
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ハードコア

ループで他に何ができるでしょうか？ 正確に-「登録」：

 register int *array = &vec[0]; register int sum = 0; for(register int i = 0; i != COUNT; ++i) { sum += array[i]; };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そして、私たちは何を得ますか？

 $ g++ -std=c++11 main.cpp -o test && ./test $ duration 10.456 mseconds
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

結果は楽しいですが、レジスタ修飾子の乱用はそれを無効にすることを覚えておく必要があります：コンパイラは十分なレジスタがないときに注意を払うのを停止しますが、常に欠落しています）したがって、上記の結果は実用的というよりも学術的な関心のあるものです。



このような変更など、アルゴリズムを試すことができます。

 sum += array[i] + array[++i];
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

コードはさらに2つ高速化されます。

 $ g++ -std=c++11 main.cpp -o test && ./test $ duration 4.8562 mseconds
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

更新 ：そして未定義の動作につながります！ コメントをくれたalexacに感謝します。

コンパイラーの最適化も記事の範囲を超えており、使用していません。 しかし、これは別の記事のトピックです...

おわりに

私たちのサイクルの速度は桁違いに増加しました ！ 同時に、マルチスレッドアルゴリズム（および一般的なアルゴリズム）についても考えませんでした。 また、ネイティブC ++以外は使用しませんでした。標準に厳密に従って動作し、サードパーティのライブラリは使用しませんでした。







したがって、サイクルの速度が重要な場合、 STLアルゴリズムは適切ではありません 。 イテレータは柔軟ですが、速すぎません-最速の方法は通常のポインタを使用することです。