如何找出C++代码的运行效率

Question

如何找出C++代码的运行效率

c++algorithmperformancec++-chrono

19

我正在尝试查找我最近在stackoverflow上发布的程序的效率。

如何在给定另一个向量的情况下高效地删除向量中的元素

为了比较我的代码与其他答案的效率，我使用了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

- user3898160

2

阅读此内容以了解如何重新排序chrono调用，从而使测量无效。https://dev59.com/QloU5IYBdhLWcg3wIkeI - Niall

6

我认为执行相同的代码多次并取平均值会得到更好的结果。 - Neijwiert

2

为了正确地进行测量，您需要至少以下三点：1）热身（在测量之前执行许多类似的操作），2）找到许多调用的平均结果，3）避免编译器的超级优化（如果它能检测到您不使用计算结果，它可能会跳过它）。 - Ilya

4

性能测量并不容易。考虑使用像nonius这样的库，以更少的努力获得正确的结果。 - nwp

4

入侵式的测量框架在实际测量性能时效果不佳。你应该使用像Linux Perf或Intel Vtune这样的非入侵式工具来实际测量真实性能，而不会潜在地干扰编译器。 - Steve Cox

显示剩余3条评论

3个回答

6

你的方法存在以下问题： 1) 你测试的代码太短且可预测性太高。你需要运行它至少数千次，以便每个测试之间有至少几百毫秒的间隔，并且需要使数据集更大且不那么可预测。总的来说，CPU缓存实际上会使基于合成输入数据的准确测量变得非常困难。 2) 编译器可以重新排列你的代码。通常很难确保你正在计时的代码将在检查时间之间执行（就此而言，也没有其他内容）。一方面，你可以减小优化程度，但是另一方面，你想要测量被优化过的代码。

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

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

    std::atomic_thread_fence(std::memory_order_seq_cst);

（需要 #include <atomic> 和支持C++11的编译器）。

此外，您可能希望补充您的测量数据，以查看L1/2/3缓存的使用效率、内存瓶颈、指令退役率等等。不幸的是，Intel x86 上最好的工具是商业化的（vtune），但在 AMD x86 上有一个类似的免费工具（codeXL）。

- rustyx

2

您可以考虑使用基准测试库，例如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());    
}

- Tomasz Lewowski

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Sergey · Accepted Answer

以下是翻译的结果：

检查运行时效率的方法是否正确？

看起来不是最好的方法。我在你的方法中看到以下缺陷：

数值已排序。分支预测可能会在测试相同算法的排序和未排序值时暴露出荒谬的效果。可能的解决方法是对排序和未排序进行测试并比较结果。
数值是硬编码的。CPU缓存是一个棘手的问题，它可能会在硬编码值和实际值之间引入微妙的差异。在现实世界中，您不太可能对硬编码值执行这些操作，因此您可以从文件中读取它们或生成随机值。
数值太少。您的代码执行时间远小于计时器精度。
您只运行了一次代码。如果您修复了所有其他问题并运行代码两次，则第二次运行可能比第一次快得多，因为缓存预热：后续运行 tend to have less 缓存未命中 than the first one.
您仅在固定大小数据上运行代码。最好将否则正确的测试运行至少四次，以涵盖以下参数的笛卡尔积：
- 排序数据与未排序数据
- v3适合CPU缓存还是v3大小超过CPU缓存。还要考虑当(v1.length() + v3.length()) * sizeof(int)适合缓存或不适合，(v1.length() + v2.length() + v3.length()) * sizeof(int)适合缓存或不适合等所有组合的情况。