如何找到一个运行时效率的c++代码

Question

我正试图找到我最近在stackoverflow上发布的一个程序的效率。

如何有效地从给定另一个向量的vector中删除元素

为了比较我的代码与其他答案的效率，我使用chrono对象。

这是检查运行时效率的正确方法吗?

如果没有，请给出一个例子。

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. 值排序。当使用相同的算法测试排序值和未排序值时，分支预测可能会暴露出荒谬的效果。可能的修复:测试排序和未排序并比较结果。
2. 值是硬编码的。CPU缓存是一件棘手的事情，它可能会在硬编码值和实际值的测试之间引入微妙的差异。在现实世界中，您不太可能对硬编码的值执行这些操作，因此您可以从文件中读取它们或生成随机值。
3. 值太少。你的代码的执行时间比计时器精度要小得多。
4. 您只运行一次代码。如果你修复所有其他问题并运行代码两次，由于缓存预热，第二次运行可能比第一次运行快得多:后续运行往往比第一次运行有更少的缓存丢失。
5. 对固定大小的数据运行一次代码。最好至少运行四次其他正确的测试，以涵盖以下参数的笛卡尔积:
   • 排序数据与未排序数据
   • v3适合CPU缓存，v3大小超过CPU缓存。还要考虑(v1.length() + v3.length()) * sizeof(int)是否适合缓存，(v1.length() + v2.length() + v3.length()) * sizeof(int)是否适合缓存等所有组合的情况。

Answer 2

你的方法最大的问题是:

1)您正在测试的代码太短且可预测。您需要运行它至少几千次，以便在测量之间至少有几百毫秒的。你需要让数据集更大，更不可预测。一般来说，CPU缓存确实可以根据合成输入数据(PITA)进行精确测量。

2)编译器可以自由重新排序你的代码。一般来说，要确保计时的代码在调用之间执行以检查时间(仅此而已)是相当困难的。一方面，您可以减少优化，但另一方面，您希望度量优化后的代码。

一个解决方案是关闭整个程序优化，并将计时调用放在另一个编译单元中。

另一个可能的解决方案是在测试周围使用内存围栏，例如

    std::atomic_thread_fence(std::memory_order_seq_cst);

(需要#include <atomic>和支持c++ 11的编译器)。

此外，您可能希望用性能分析器数据来补充您的测量，以了解L1/2/3缓存的使用效率、内存瓶颈、指令退役率等。不幸的是，Intel x86上最好的工具是商业的(vtune)，但是在AMD x86上类似的工具是免费的(codeXL)。

Answer 3

您可以考虑使用像Celero这样的基准库来为您进行测量并处理性能测量中棘手的部分，而您仍然专注于您试图优化的代码。更复杂的例子可以在代码中链接到你之前的问题的答案(如何有效地从给定的另一个向量中删除元素)，但一个简单的用例看起来像这样:

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());    
}