C++代码执行时间随着源代码的变化而变化,不应引入任何额外的工作

Question

在对一些代码进行基准测试时,我发现即使是最无害的代码更改,它的执行时间也会有所不同.

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

#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;
}

1 ^第一类,Timer是只用于定时的码的小便利类(故意没有很好功能,为了简洁).

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

3 ^次类Printer似乎完全没有必要对这个问题,但同样,包括它似乎加剧了这一问题.

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

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

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, and " 
        << total_char_count << " total characters, were built in "
        << execution_time_usec/usec_to_sec << " seconds.\n";

10.6秒:

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

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

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

Running test... 50000000 words, and 750000798 total characters, were built in 9.83379 seconds.
Running test... 50000000 words, and 749978210 total characters, were built in 9.84541 seconds.
Running test... 50000000 words, and 749996688 total characters, were built in 9.87418 seconds.
Running test... 50000000 words, and 749995415 total characters, were built in 9.85704 seconds.
Running test... 50000000 words, and 750017699 total characters, were built in 9.86186 seconds.
Running test... 50000000 words, and 749998680 total characters, were built in 9.83395 seconds.
...

Running test... 50000000 words, and 749988517 total characters, were built in 10.604 seconds.
Running test... 50000000 words, and 749958011 total characters, were built in 10.6283 seconds.
Running test... 50000000 words, and 749994387 total characters, were built in 10.6374 seconds.
Running test... 50000000 words, and 749995242 total characters, were built in 10.6445 seconds.
Running test... 50000000 words, and 749988379 total characters, were built in 10.6543 seconds.
Running test... 50000000 words, and 749969532 total characters, were built in 10.6722 seconds.
...

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

笔记:

1. 即使std::string filename从Printer类中删除未使用的成员对象也会产生不同的基准测试结果 - 这样做可以消除(或减少不显着的比例)上面提供的两个基准测试之间的差异.
2. 在使用g ++编译时(在Ubuntu上),这似乎不是问题.虽然,我不能说明这一点; 我在Ubuntu上的测试是在同一台Windows机器上的VM中,VM可能无法访问所有资源和处理器增强功能.
3. 我正在使用Visual Studio Community 2017(版本15.7.4)
   • 编译器版本:19.14.26431
   • 所有测试和报告的结果都是Release Build,64位
4. 系统:Win10,i7-6700K @ 4.00 GHz,32 GB RAM

Answer 1

您可能会遇到某种代码对齐效果。大多数时候，现代 x86-64 CPU 在对齐方面相当稳健，但对齐会影响分支预测器中相互别名的分支（如@rcgldr 提到的）以及各种前端效果。

请参阅https://agner.org/optimize/以及x86 标签 wiki中的性能链接。但老实说，我认为这里没有任何有用的解释，除了您发现循环对来自前端或分支预测的对齐效果敏感之外。这意味着即使主程序中不同对齐的相同机器代码也可能具有不同的性能。

这是众所周知的现象。关于“一个目标文件中的代码对齐正在影响另一个目标文件中的函数的性能”的答案有一些关于对齐如何重要的一般性评论，另请参阅为什么引入无用的 MOV 指令会加速 x86_64 程序集中的紧密循环？ 有一篇文章介绍了以不同顺序链接对象文件如何影响性能（这是工具链的意外影响），但我找不到它。

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

但不幸的是，你无能为力。微小的源差异，如果它们完全影响汇编，将改变所有内容的对齐方式。

有时，您可以通过用无分支代码替换分支来重新设计事物，使其对分支预测不太敏感。例如，始终生成 16 字节的随机字母，并将其截断为随机长度。（复制时在大小上进行一些分支可能是不可避免的，除非创建 16 字节std::string然后截断它可以是无分支的。）

您可以使用 SIMD 加快速度，例如使用矢量化 PRNG（如SSE2 或 AVX2）xorshift+一次生成 16 字节的随机字母。（通过打包字节操作有效地获得统一的 0..25 分布可能很棘手，但也许与我用来在 3.9 上每约 0.03 秒生成 1GiB 空格分隔的随机 ASCII 数字的 0..9分布相同的技术GHz Skylake 会很有用。不过，它并不是完全均匀分布的，因为 65536 % 10 有余数（如 65536/25），但您可能可以更改质量与速度的权衡，并且仍然运行得很快。）

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

函数中两个版本的内部循环的 asmruntest本质上是相同的，至少如果我们在 Godbolt 编译器资源管理器上看到的编译器 asm输出与您在 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]寻址模式。

• 不同的code-gen与实际源码的区别：

        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 之前运行一次。

• 在上述代码差异之后，npad 7在函数底部附近的分支目标之前（在 a 之后）额外的对齐。call _Xtime_get_ticks

有很大的红色/绿色差异，但这些差异仅来自不同编号的标签，除了函数开头的那三个指令之外。

但在此之前runtest，该word_list.size()版本包含的??$?6_K@@YAAEAVPrinter@@AEAV0@$QEA_K@Z PROC函数代码在使用 的版本中没有出现在任何地方run_length。（C++ 名称修饰将类型转换为函数的 asm 名称中的时髦字符。）这正在为class Printer.

您说删除未使用的内容std::string filename删除Printer了代码生成差异。好吧，这个功能可能会随着这个变化而消失。我不知道为什么MSVC 决定发布它，更不用说只在一个版本与另一个版本中发布它了。

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

顺便说一句，海湾合作委员会警告

<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 的代码生成更糟糕，或者如果传递大量输入，是否会变得不安全。