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

Question

我试图找到我最近在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

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缓存的使用效率,内存瓶颈,指令退出率等.不幸的是,英特尔x86的最佳工具是商业(vtune),但在AMD x86上,类似的工具是免费的(codeXL).