为什么一行代码会导致性能下降10倍？

Question

代码行

next += val;

性能下降到了10倍，我已经检查过汇编代码，但没有结果。

为什么这行代码会导致性能下降到10倍？

以下是结果：

➜  ~ clang-13 1.c -O3
➜  ~ ./a.out
rand_read_1
sum = 2624b18779c40, time = 0.19s
rand_read_2
sum = 2624b18779c40, time = 1.24s

中央处理器（CPU）：Intel(R) Xeon(R) Silver 4210 CPU @ 2.20GHz

以下是代码：

#include <stdio.h>
#include <time.h>
#include <stdint.h>
#include <unistd.h>
#include <string.h>
#include <assert.h>
#include <stdlib.h>

#define CCR_MULTIPLY_64           6364136223846793005
#define CCR_ADD_64                1
static inline uint64_t my_rand64(uint64_t *r)
{
    *r = *r * CCR_MULTIPLY_64 + CCR_ADD_64;
    return *r;
}

#define NUM 10000000UL

uint64_t rand_read_1(uint64_t *ptr, uint64_t nr_words)
{
    uint64_t i, next, val = 0;
    uint64_t sum;

    next = 0;
    sum = 0;
    for (i = 0; i < NUM; i++) {
        my_rand64(&next);
        next %= nr_words;
        val = ptr[next];
        sum += val ^ next;
        // printf("next1:%ld\n", next);
    }

    return sum;
}

uint64_t rand_read_2(uint64_t *ptr, uint64_t nr_words)
{
    uint64_t i, next, val ,next2 = 0;
    uint64_t sum;

    next = 0;
    sum = 0;
    for (i = 0; i < NUM; i++) {
        my_rand64(&next);
        next %= nr_words;
        val = ptr[next];
        sum += val ^ next;
        next += val;
    }

    return sum;
}

#define SIZE    (1024*1024*1024)

static uint64_t get_ns(void)
{
    struct timespec val;
    uint64_t v;
    int ret;

    ret = clock_gettime(CLOCK_REALTIME, &val);
    if (ret != 0) {
        perror("clock_gettime");
        exit(1);
    }
    v  = (uint64_t) val.tv_sec * 1000000000LL;
    v += (uint64_t) val.tv_nsec;
    return v;
}

int main(int argc, char *argv[])
{
    uint64_t *ptr;
    uint64_t sum;
    uint64_t t0, t1, td, t2;

    ptr = (uint64_t *)malloc(SIZE);
    assert(ptr);

    memset(ptr, 0, SIZE);

    t0 = get_ns();
    printf("rand_read_1\n");
    sum = rand_read_1(ptr, SIZE/8);
    t1 = get_ns();
    td = t1 - t0;
    printf("sum = %lx, time = %.2fs\n", sum, td/1E9);
    printf("rand_read_2\n");
    sum = rand_read_2(ptr, SIZE/8);
    t2 = get_ns();
    td = t2 - t1;
    printf("sum = %lx, time = %.2fs\n", sum, td/1E9);
    return 0;
}

- zhanglistar

---

首先不要计时打印语句。 - John3136

第一个较慢，因为它需要“热身”stdout/printf使用的缓存？如果您注释掉rand_read调用会发生什么？ - Lundin

malloc(SIZE); ... memset(ptr, 0, SIZE); 翻译为：使用 calloc。或者更好的方法是使用 volatile 访问将整个块默认初始化为一些随机的 goo，然后再将其清零。这样可以确保操作系统的后期堆分配本身不会影响基准测试。 - Lundin

@Casey 在编辑代码时，绝不能改变编码风格。你那些粗心的破坏性修改引入了代码中原本不存在的错误。 - Lundin

我会回滚破坏并正确编辑它，稍等一下... - Lundin

Answer 1

基准测试的方法有点靠不住，但这是一个真实的效果。

next += val; 改变了代码结构的某些基本特征：它使得每个内存读取都依赖于前一个读取的结果。如果没有这行代码，读取操作是独立的（通过 my_rand64 有一个更短的循环依赖链，而内存读取不是其中的一部分）。

本质上，有了这行代码，它就是一个延迟基准测试；没有这行代码，它就是一个吞吐量基准测试。内存读取的延迟和吞吐量相差10倍是合理的。

在汇编级别上，如果使用Clang编译，没有这行代码时，汇编代码如下：

.LBB2_3:                                # =>This Inner Loop Header: Depth=1
    imul    rcx, r15
    add     rcx, 1
    mov     edx, ecx
    and     edx, 134217727
    xor     rdx, qword ptr [r14 + 8*rdx]
    mov     esi, r15d
    imul    esi, ecx
    add     rdx, rbx
    add     esi, 1
    and     esi, 134217727
    mov     rbx, qword ptr [r14 + 8*rsi]
    xor     rbx, rsi
    add     rbx, rdx
    mov     rcx, rsi
    add     rax, -2
    jne     .LBB2_3

uiCA 估计每次迭代需要9.16个周期（循环展开了2倍，因此相当于原始循环每次迭代需要约4.5个周期），但它没有考虑缓存未命中的情况。

通过这条指令，汇编代码看起来几乎相同，但这并不意味着它们运行方式也几乎相同：

.LBB2_6:                                # =>This Inner Loop Header: Depth=1
    imul    ecx, r15d
    add     ecx, 1
    and     ecx, 134217727
    mov     rdx, qword ptr [r14 + 8*rcx]
    mov     rsi, rcx
    xor     rsi, rdx
    add     rsi, rbx
    add     edx, ecx
    imul    edx, r15d
    add     edx, 1
    and     edx, 134217727
    mov     rcx, qword ptr [r14 + 8*rdx]
    mov     rbx, rdx
    xor     rbx, rcx
    add     rbx, rsi
    add     rdx, rcx
    mov     rcx, rdx
    add     rax, -2
    jne     .LBB2_6

现在 uiCA 估计 每次迭代需要 24.11 个周期（此循环也展开了 2 倍），但仍未考虑缓存失效的影响。

- harold

---

谢谢，我也怀疑这行代码会降低CPU流水线的吞吐量。 - zhanglistar

有没有其他工具可以分析代码？ - zhanglistar

@zhanglistar дҫӢеҰӮпјҢIntel VTuneжҲ–LinuxдёҠзҡ„perfеҸҜд»ҘеңЁд»Јз ҒиҝҗиЎҢж—¶иҝӣиЎҢеҲҶжһҗпјҢеӣ жӯӨе®ғ们еҸҜд»ҘжҳҫзӨәLLVM-MCAжҲ–uiCAзӯүе·Ҙе…·ж— жі•еҲҶжһҗзҡ„ж•ҲжһңгҖӮ - harold

你是如何生成这段汇编代码的？我有不同的汇编代码。此外，从汇编代码来看，修改变量next是寄存器操作而非内存操作。我仍然有些困惑。谢谢。 - zhanglistar

@zhanglistar，你可以阅读《数据流图简介》（https://fgiesen.wordpress.com/2018/03/05/a-whirlwind-introduction-to-dataflow-graphs/）作为我所说的那些依赖和等待其他指令的指令的参考。 - harold

Answer 2

关于如何不要进行基准测试的一些注意事项（基准测试非常困难）：

• malloc非常昂贵，你在这里分配了很多内存。然而，操作系统可能在注意到内存被使用之前并没有实际分配它。因此，除非你强制操作系统在基准测试开始之前实际分配内存，否则你将测试malloc的速度而不是其他任何东西，这对于你的小算法来说是一个巨大的性能杀手。

  此外，你可能为操作系统分配了太多的内存，而且你也不一定分配了sizeof(uint64_t)的对齐倍数，这是一个错误。

  你可以尝试像这样做（可能需要先减少SIZE）：

  ptr = (uint64_t *)malloc(SIZE * sizeof(uint64_t));
  assert(ptr);
  for(size_t i=0; i<SIZE; i++)
  {
    volatile uint64_t tmp = 123; // 一些垃圾值
    ptr[i] = tmp; // 编译器必须从堆栈加载123到堆中
  }
  // 实际的堆分配现在应该完成了
  

• memset为零可能不算作“触摸”堆内存，潜在地编译器甚至可能通过交换到calloc来优化掉它。当我检查优化后的代码（gcc x86_64 Linux）时，这确实是发生的。因此，这并没有实现上述“触摸堆”的目的。

• printf和stdout缓冲区是性能重的函数，不应该放在基准测试代码中。你可能最终只会测试printf的速度。例如，将你的代码更改为

  printf("rand_read_1\n");
  t0 = get_ns();
  sum = rand_read_1(ptr, SIZE/8);
  t1 = get_ns();
  

  结果差异很大。

• 最后一个td = t2 - t1;是无意义的，因为它测量了自上次测量以来与你的算法无关的所有垃圾，包括操作系统的任何数量的上下文切换...

应用了所有这些错误修复后，main() 可能会像这样：

int main(int argc, char *argv[])
{
    uint64_t *ptr;
    uint64_t sum;
    uint64_t t0, t1, td, t2;

    ptr = malloc(SIZE * sizeof(uint64_t));
    assert(ptr);
    for(size_t i=0; i<SIZE; i++)
    {
      volatile uint64_t tmp = 123; // some garbage value
      ptr[i] = tmp; // the compiler has to load 123 from stack to heap
    }

    printf("rand_read_1\n");
    t0 = get_ns();
    sum = rand_read_1(ptr, SIZE/8);
    t1 = get_ns();
    td = t1 - t0;
    printf("sum = %lx, time = %.2fs\n", sum, td/1E9);
    printf("rand_read_2\n");
    
    t0 = get_ns();
    sum = rand_read_2(ptr, SIZE/8);
    t1 = get_ns();
    td = t1 - t0;
    printf("sum = %lx, time = %.2fs\n", sum, td/1E9);
    return 0;
}

此外，我建议先执行方法1，然后执行方法2，再执行方法1和方法2，以确保基准测试不会偏向于第一个算法将值加载到缓存中，第二个算法重复使用它们，或者偏向于启动程序后x时间单位发生的上下文切换。从那里开始，您可以开始测量和考虑实际算法的性能，这不是您当前正在做的事情。我建议您发布一个单独的问题来讨论这个问题。

- Lundin

---

代码假设 sizeof(uint64_t) = 8，这在他们进行基准测试的系统上是正确的。虽然它不太可移植，但它实际上并没有读取超出分配大小：rand_read_1(ptr, SIZE/8);，而且该除法是截断的，在分配了部分 uint64_t 的情况下向下舍入。此外，如果 sizeof 更小，则会使用分配大小的较少部分，我认为 sizeof(uint64_t) 不可能大于 8；CHAR_BIT 至少保证为 8，而 uint64_t 保证为 64 个值位而没有填充。 - Peter Cordes

你说的没错，GCC会将malloc+memset(0)优化为calloc，实际上并不会首先访问内存，因此每组页面的第一次访问将会支付一个页错误。这将在1GiB（256K 4k页面或512x 2M大页面）上进行10M次访问，因此平均而言（如果LCG PRNG触及每个页面），每个页错误最多分摊到38.1个页错误（无故障环绕的4k页面），或者对于2M大页面而言是19.5k个页错误。 - Peter Cordes

不知道，也许我误读了代码；我没有尝试过。我只是在我的x86-64 Linux系统上使用clang -O3进行了尝试，并且它可以运行而不会崩溃。（在i7-6700k Skylake上分别为0.02和0.14秒。我不知道OP如何得到这么高的数字，尽管Skylake-server的内存延迟已知要高得多。我的stdout是一个KDE“konsole”终端窗口；定时区域内的printf很糟糕，但仍然比0.03秒微不足道。） - Peter Cordes

还有一些小问题，因为方法1和方法2中哪一个先执行对结果有很大的影响。 - Lundin

我没有点踩。不过这里肯定存在一个真实的影响，而你的回答似乎在说唯一的影响是糟糕的基准测试方法，所以我没有点赞。像你这样更好设计的基准测试会让原始问题变得更好，但这个影响足够大，仍然存在一个真正的问题；就像我说的，在我的机器上，我可以通过原始糟糕的基准测试和你修复后的版本得到类似的结果。 - Peter Cordes