C++コードのランタイム効率を見つける方法

Question

私は最近stackoverflowに投稿したプログラムの効率を見出そうとしています。

How to efficiently delete elements from a vector given an another vector

私はchronoオブジェクトを使用している他の回答に私のコードの効率を比較します。

実行時の効率を確認する正しい方法はありますか？

もしそうでない場合は、例を挙げてそれを行う方法をお勧めします。

Code on Coliru

#include <iostream> 
#include <vector> 
#include <algorithm> 
#include <chrono> 
#include <ctime> 
using namespace std; 

void remove_elements(vector<int>& vDestination, const vector<int>& vSource) 
{ 
    if(!vDestination.empty() && !vSource.empty()) 
    { 
     for(auto i: vSource) { 
      vDestination.erase(std::remove(vDestination.begin(), vDestination.end(), i), vDestination.end()); 
     } 
    } 
} 

int main() { 
    vector<int> v1={1,2,3}; 
    vector<int> v2={4,5,6}; 
    vector<int> v3={1,2,3,4,5,6,7,8,9}; 
    std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now(); 
    remove_elements(v3,v1); 
    remove_elements(v3,v2); 
    std::chrono::steady_clock::time_point end= std::chrono::steady_clock::now(); 
    std::cout << "Time difference = " << std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin).count() <<std::endl; 
    for(auto i:v3) 
     cout << i << endl; 
    return 0; 
} 

出力

Time difference = 1472 
7 
8 
9 

Answer 1

は、それが実行時の効率をチェックするための正しい方法は何ですか？

これを行う最良の方法ではないようです。あなたの方法には次のような欠陥があります。

1. 値がソートされています。 Branch predictionは、ソートされた値とソートされていない値を同じアルゴリズムでテストするとばかばかしい結果をもたらす可能性があります。可能な修正：ソート済みとソート済みの両方のテストと結果の比較。
2. 値はハードコードされています。 CPUキャッシュはtricky thingであり、ハードコードされた値と実際の値のテストとの間に微妙な違いが生じることがあります。現実の世界では、ハードコーディングされた値に対してこれらの操作を実行する可能性は低いので、ファイルから読み込んだり、ランダムな値を生成したりすることができます。
3. 値が小さすぎます。コードの実行時間は、タイマーの精度よりもはるかに小さいです。
4. コードを1回だけ実行します。他のすべての問題を修正してコードを2回実行すると、キャッシュのウォームアップにより、2回目の実行が最初の実行よりもはるかに高速になることがあります：後続の実行では、最初の実行よりも少なくなる傾向があります。
5. 固定サイズのデータ​​に対してコードを一度実行します。ソートされていないデータ対
   • ソート
   • v3がv3サイズは、CPUのキャッシュを超えるCPUキャッシュ対に合った：次のパラメータのデカルト積をカバーするために少なくとも4回そうでない場合は、正しいテストを実行する方が良いだろう。また、(v1.length() + v3.length()) * sizeof(int)がキャッシュに適合するかどうかを考慮して、(v1.length() + v2.length() + v3.length()) * sizeof(int)がすべての組み合わせに対してキャッシュに適合するかどうかなどを検討します。あなたのアプローチと

Answer 2

最大の問題は、以下のとおりです。あなたがテストしている

1）コードが短すぎると、予測可能です。測定間隔は少なくとも数百ミリ秒になるように少なくとも数千回実行する必要があります。また、データセットを大きくして予測しにくくする必要があります。一般に、CPUキャッシュは実際にPITAの合成入力データに基づいて正確な測定を行います。

2）コンパイラは、コードを再注文することができます。一般的には、時間をチェックするための呼び出しの間にあなたが実行するコードを確実に実行することは非常に困難です（それ以外は何もありません）。一方ではダイヤルダウン最適化が可能ですが、他方では最適化されたコードを測定したいと考えています。

解決策の1つは、プログラム全体の最適化をオフにして、タイミング呼び出しを別のコンパイル単位に入れることです。

もう1つの解決策は、テストの周りにメモリフェンスを使用することです。

std::atomic_thread_fence(std::memory_order_seq_cst); 

（#include <atomic>とC++ 11対応コンパイラが必要です）。

さらに、L1/2/3キャッシュがどの程度効率的に使用されているか、メモリのボトルネック、命令のリタイア率などを調べるために、プロファイラデータを補足したいと思うかもしれません。 （vtune）が、AMD x86でも同様のツールは無料（codeXL）です。

Answer 3

Celeroのようなベンチマークライブラリを使用して、パフォーマンス測定の難しい部分を処理し、最適化しようとしているコードに焦点を当てながら、測定を行うことを検討することもできます。より複雑な例では、私はあなたの前の質問（How to efficiently delete elements from a vector given an another vector）への答えにリンクされたコードで使用できますが、簡単なユースケースは、次のようになります。

BENCHMARK(VectorRemoval, OriginalQuestion, 100, 1000) 
{ 
    std::vector destination(10000); 
    std::generate(destination.begin(), destination.end(), std::rand); 
    std::sample(destination.begin(), destination.end(), std::back_inserter(source), 
     100, std::mt19937{std::random_device{}()})  

    for (auto i: source) 
     destination.erase(std::remove(destination.begin(), destination.end(), i), 
      destination.end());  
}