C代码执行时间因源变化小而不同,不应引入任何额外的工作

前端之家收集整理的这篇文章主要介绍了C代码执行时间因源变化小而不同,不应引入任何额外的工作前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
在对某些代码进行基准测试时,我发现即使是最无害的代码更改,它的执行时间也会有所不同.

我试图将下面的代码归结为最小的测试用例,但它仍然相当冗长(为此我道歉).几乎任何改变都会影响基准测试结果.

#include <string>
#include <vector>
#include <iostream>
#include <random>
#include <chrono>
#include <functional>

constexpr double usec_to_sec = 1000000.0;

// Simple convenience timer
class Timer
{
    std::chrono::high_resolution_clock::time_point start_time;
public:
    Timer() : start_time(std::chrono::high_resolution_clock::now()) { }
    int64_t operator()() const {
        return static_cast<int64_t>(
        std::chrono::duration_cast<std::chrono::microseconds>(
            std::chrono::high_resolution_clock::now()-start_time).count()
        );
    }
};

// Convenience random number generator
template <typename T>
class RandGen
{
    mutable std::default_random_engine generator;
    std::uniform_int_distribution<T> distribution;

    constexpr unsigned make_seed() const {
        return static_cast<unsigned>(std::chrono::system_clock::now().time_since_epoch().count());
    }
public:
    RandGen(T min,T max) : generator(make_seed()),distribution(min,max) { }
    T operator ()() { return distribution(generator); }
};

// Printer class
class Printer
{
    std::string filename;
    template <class S>    
    friend Printer &operator<<(Printer &,S &&s);
public:
    Printer(const char *filename) : filename(filename) {}
};

template <class S>
Printer &operator<<(Printer &pm,S &&s) {
    std::cout << s;
    return pm;
}

// +------------+
// | Main Stuff |
// +------------+
void runtest(size_t run_length)
{
    static RandGen<size_t> word_sz_generator(10,20);
    static RandGen<int> rand_char_generator(0,25);

    size_t total_char_count = 0;
    std::vector<std::string> word_list;
    word_list.reserve(run_length);

    Printer printer("benchmark.dat");
    printer << "Running test... ";

    Timer timer; // start timer
    for (auto i = 0; i < run_length; i++) {

        size_t word_sz = word_sz_generator();
        std::string word;
        for (auto sz = 0; sz < word_sz; sz++) {
            word.push_back(static_cast<char>(rand_char_generator())+'a');
        }
        word_list.emplace_back(std::move(word));
        total_char_count += word_sz;
    }
    int64_t execution_time_usec = timer(); // stop timer

    printer << /*run_length*/ word_list.size() << " words,and " 
            << total_char_count << " total characters,were built in "
            << execution_time_usec/usec_to_sec << " seconds.\n";
}

int main(int argc,char **argv)
{
    constexpr size_t iterations = 30;
    constexpr size_t run_length = 50000000;

    for (auto i = 0; i < iterations; i++)
        runtest(run_length);

    return EXIT_SUCCESS;
}

第一类Timer,只是一个小的便利类(为了简洁而故意不是很好的功能),用于对代码进行计时.

我试着没有第二类RandGen(它只是生成随机值),但任何试图从测试代码中排除这一点都会使问题自动神奇地消失.所以,我怀疑这个问题与它有关.但我无法弄清楚如何.

对于这个问题,第三类打印机似乎完全没有必要,但再次,包括它似乎加剧了这个问题.

所以,现在我们归结为main()(只运行测试)和runtest().

runtest()是可怕的,所以请不要从“干净的代码”的角度来看待它.以任何方式更改它(例如将内部for循环移动到其自己的函数)会导致基准测试结果发生变化.最简单,最令人困惑的例子是最后一行:

printer << /*run_length*/ word_list.size() << " words,and " 
        << total_char_count << " total characters,were built in "
        << execution_time_usec/usec_to_sec << " seconds.\n";

在上面的行中,run_length和word_list.size()是相同的.矢量word_list的大小由run_length定义.但是,如果我按原样运行代码,我的平均执行时间为9.8秒,而如果我取消注释run_length并注释掉word_list.size(),则执行时间实际上会增加到平均10.6秒.我无法理解这种微不足道的代码变更如何影响整个程序的时间安排.

换一种说法…

9.8秒:

printer << /*run_length*/ word_list.size() << " words,were built in "
        << execution_time_usec/usec_to_sec << " seconds.\n";

10.6秒:

printer << run_length /*word_list.size()*/ << " words,were built in "
        << execution_time_usec/usec_to_sec << " seconds.\n";

我已经多次重复评论和取消注释上述变量,并多次重新运行基准测试.基准测试是可重复且一致的 – 即它们分别始终为9.8秒和10.6秒.

对于这两种情况,代码输出如下所示:

06004

任何有关导致这种差异的信息都将不胜感激.

笔记:

>即使从Printer类中删除未使用的std :: string文件名成员对象也会产生不同的基准测试结果 – 这样做可以消除(或减少不显着的比例)上面提供的两个基准测试之间的差异.
>使用g(在Ubuntu上)进行编译时,这似乎不是问题.虽然,我不能说明这一点;我在Ubuntu上的测试是在同一台Windows机器上的VM中,VM可能无法访问所有资源和处理器增强功能.
>我正在使用Visual Studio Community 2017(版本15.7.4)

>编译器版本:19.14.26431
>所有测试和报告的结果都是Release Build,64位

>系统:Win10,i7-6700K @ 4.00 GHz,32 GB RAM

解决方法

您可能正在遇到某种代码对齐效果.现代x86-64 cpu在大多数情况下在对齐方面相当稳健,但是对齐会影响分支预测变量中的分支别名(如提到的@rcgldr)和各种前端效果.

请参阅@L_404_1@和the x86 tag wiki中的性能链接.但老实说,我认为这里没有任何有用的解释,除了你发现你的循环对前端或分支预测的对齐效果很敏感.这意味着即使主程序中不同路线的相同机器代码也可能具有不同的性能.

这是一种已知现象.关于Code alignment in one object file is affecting the performance of a function in another object file的答案有一些关于对齐如何重要的一般性评论,另请参阅Why would introducing useless MOV instructions speed up a tight loop in x86_64 assembly?有一篇关于如何以不同的顺序链接目标文件会影响性能文章(这是工具链的意外效果),但我无法找不到它.

您可以使用硬件性能计数器来测量分支错误预测率,以查看这是否解释了为什么一个版本比另一个版本慢.或者,如果还有其他一些前端效应.

但不幸的是,你无能为力;微不足道的源差异,如果它们完全影响asm,将改变一切的对齐.

通过用无分支代码替换分支,有时可以重新设计对分支预测不太敏感的东西.例如总是生成16个字节的随机字母,并将其截断为随机长度. (复制时大小分支的大小可能是不可避免的,除非创建一个16字节的std :: string然后截断它可以是无分支的.)

您可以使用SIMD加快速度,例如:使用像with an SSE2 or AVX2 xorshift+这样的矢量化PRNG一次生成16个字节的随机字母. (使用压缩字节操作有效地获得统一的0..25分布可能很棘手,但可能与我在3.9GHz Skylake上每隔0.03秒使用的0 … 9分布相同的技术将是有用的.它不是但是,完全均匀分布,因为65536%10有一个余数(如65536/25),但你可以改变质量与速度的权衡并仍然快速运行.)

比较两个版本的编译器输出

runtest函数中内部循环的两个版本的asm基本相同,至少如果编译器asm输出我们看到on the Godbolt compiler explorer与MSVC中可执行文件中实际获得的内容相匹配. (与gcc / clang不同,它的asm输出不一定能组装成一个工作对象文件.)如果你的真实版本构建做了任何可以内联一些库代码链接时优化,它可能会在最终版本中做出不同的优化选择.可执行文件.

我输入#ifdef所以我可以使用-DUSE_RL来获得两个MSVC 2017输出,它们以不同的方式构建相同的源,并将这些asm输出提供给diff窗格. (差异窗格位于我链接的凌乱布局的底部;单击其上的全屏框以显示内容.)

整个功能的唯一区别是:

>命令和注册选择一些指令,如mov edx,DWORD PTR _tls_index和mov QWORD PTR run_length $GSCopy $1 $[rbp-121],rcx位于仅运行一次的函数顶部. (但不是代码大小,因此以后不会影响对齐).这应该对以后的代码没有影响,并且他们最终对架构状态进行相同的更改,只使用不再使用的不同临时注册.
>堆栈布局(局部变量相对于RBP的位置).但是所有偏移都低于127,因此它们仍然可以使用[rbp disp8]寻址模式.
>来自实际来源差异的不同代码

mov     rdx,QWORD PTR word_list$[rbp-113]
      sub     rdx,QWORD PTR word_list$[rbp-121]  ; word_list.size() = end - start 
      ...
      sar     rdx,5               ; >> 5   arithmetic right shift

mov     rdx,rsi             ; copy run_length from another register

不,这些指令本身无法解释速度差异.它们仅在每个定时间隔运行一次,在某些I / O之前运行.
>在上述代码差异之后,在函数底部附近(在调用_Xtime_get_ticks之后)的分支目标之前进行对齐的额外npad 7.

有一大块红色/绿色差异,但这些只是来自不同数量标签,除了功能开始时的那三个指令.

但是在运行测试之前,word_list.size()版本包含一个?? $?6_K @@ YAAEAVPrinter @@ AEAV0 @ $QEA_K @ Z PROC函数代码,该函数在使用run_length的版本中没有出现. (C名称修改将类型转换为函数的asm名称中的时髦字符.)这是为类Printer做的事情.

你说从Printer中删除未使用的std :: string文件删除代码差异.那个功能可能随着这种变化而消失. IDK为什么MSVC决定发射它,更不用说只有一个版本而不是另一个版本.

可能g -O3没有代码差异,这就是为什么你没有看到差异. (假设您的VM是硬件虚拟化,g生成的机器代码仍然在cpu上本地运行.从操作系统获取新的内存页面可能需要更长的时间在VM中,但在循环中花费的主要时间可能是在此代码中的用户空间中.)

顺便说一下,gcc警告说

<source>:72:24: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]

     for (auto i = 0; i < run_length; i++) {
                      ~~^~~~~~~~~~~~

我没有密切关注asm输出,看看是否会导致更糟糕的代码与gcc或MSVC,或者如果你传递大量输入它只是不安全.

猜你在找的C&C++相关文章