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

一级， Timer , 只是一个方便的小类(为了简洁起见，故意没有很好的功能)用于计时代码。

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

第三课 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()是相同的。 vector 的大小 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.
...

任何有关导致这种差异的原因的信息将不胜感激。

笔记:

甚至删除未使用的 std::string filename来自 Printer 的成员对象类产生不同的基准测试结果 - 在这样做的情况下，消除(或减少到微不足道的比例)上面提供的两个基准之间的差异。

使用 g++(在 Ubuntu 上)编译时，这似乎不是问题。虽然，我不能肯定地说。我在 Ubuntu 上的测试是在同一台 Windows 机器上的 VM 中进行的，其中 VM 可能无法访问所有资源和处理器增强功能。

我正在使用 Visual Studio Community 2017(版本 15.7.4)

编译器版本:19.14.26431

所有测试和报告的结果都是 发布版本 , 64 位

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

Answer 1

您可能会遇到某种代码对齐效果。大多数情况下，现代 x86-64 CPU 在对齐方面相当稳健，但对齐会影响分支预测器中的分支相互混淆(如提到的 @rcgldr)和各种前端效果。

见 https://agner.org/optimize/ ，以及 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?某处有一篇关于以不同顺序链接目标文件如何影响性能的文章(这是工具链的意外影响)，但我找不到它。

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

但不幸的是，您无能为力；微不足道的源差异，如果它们影响汇编，将改变一切的对齐方式。

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

您可以使用 SIMD 加快速度，例如使用矢量化的 PRNG，如 with an SSE2 or AVX2 xorshift+ 一次生成 16 个字节的随机字母。 (通过压缩字节操作有效地获得统一的 0..25 分布可能很棘手，但可能与我在 3.9GHz Skylake 上每 ~0.03 秒 generate 1GiB of space-separated random ASCII digits 使用的 0..9 分布相同的技术会很有用。但是，它不是完全均匀分布的，因为 65536 % 10 有余数(如 65536/25)，但您可能可以更改质量与速度的权衡，并且仍然运行得很快。)

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

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

我输入了 #ifdef所以我可以使用 -DUSE_RL有两个 MSVC 2017 输出，它们以不同的方式构建相同的源，并将这些 asm 输出提供给差异 Pane 。 ( 差异 Pane 位于我链接的凌乱布局的底部；单击其上的全屏框以仅显示 。)

整个功能的唯一区别是:

一些指令的订购和注册选择，如 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用于在函数底部附近的分支目标之前对齐(在 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删除了代码生成差异。那么该功能可能会随着这种变化而消失。 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 生成更糟糕的代码，或者如果您传递大量输入，它是否只是不安全。