在优化内部循环的过程中，我遇到了奇怪的性能行为，我无法理解和纠正这些行为。

代码的简化版本如下；粗略地说，有一个巨大的数组，分为 16 个词 block ，我简单地把每个词 block 中的前导零的数量加起来。 (实际上我使用的是来自 Dan Luu 的 popcnt 代码，但在这里我选择了一个具有类似性能特征的更简单的指令以“简洁”。Dan Luu 的代码基于对 this SO question 的回答。虽然它有非常相似的奇怪结果，但似乎并没有在这里回答我的问题。)

// -*- compile-command: "gcc -O3 -march=native -Wall -Wextra -std=c99 -o clz-timing clz-timing.c" -*-
#include <stdint.h>
#include <time.h>
#include <stdlib.h>
#include <stdio.h>

#define ARRAY_LEN 16

// Return the sum of the leading zeros of each element of the ARRAY_LEN
// words starting at u.
static inline uint64_t clz_array(const uint64_t u[ARRAY_LEN]) {
    uint64_t c0 = 0;
    for (int i = 0; i < ARRAY_LEN; ++i) {
        uint64_t t0;
        __asm__ ("lzcnt %1, %0" : "=r"(t0) : "r"(u[i]));
        c0 += t0;
    }
    return c0;
}

// For each of the narrays blocks of ARRAY_LEN words starting at
// arrays, put the result of clz_array(arrays + i*ARRAY_LEN) in
// counts[i]. Return the time taken in milliseconds.
double clz_arrays(uint32_t *counts, const uint64_t *arrays, int narrays) {
    clock_t t = clock();
    for (int i = 0; i < narrays; ++i, arrays += ARRAY_LEN)
        counts[i] = clz_array(arrays);
    t = clock() - t;
    // Convert clock time to milliseconds
    return t * 1e3 / (double)CLOCKS_PER_SEC;
}

void print_stats(double t_ms, long n, double total_MiB) {
    double t_s = t_ms / 1e3, thru = (n/1e6) / t_s, band = total_MiB / t_s;
    printf("Time: %7.2f ms, %7.2f x 1e6 clz/s, %8.1f MiB/s\n", t_ms, thru, band);
}

int main(int argc, char *argv[]) {
    long n = 1 << 20;
    if (argc > 1)
        n = atol(argv[1]);

    long total_bytes = n * ARRAY_LEN * sizeof(uint64_t);
    uint64_t *buf = malloc(total_bytes);
    uint32_t *counts = malloc(sizeof(uint32_t) * n);
    double t_ms, total_MiB = total_bytes / (double)(1 << 20);

    printf("Total size: %.1f MiB\n", total_MiB);

    // Warm up
    t_ms = clz_arrays(counts, buf, n);
    //print_stats(t_ms, n, total_MiB);    // (1)
    // Run it
    t_ms = clz_arrays(counts, buf, n);    // (2)
    print_stats(t_ms, n, total_MiB);

    // Write something into buf
    for (long i = 0; i < n*ARRAY_LEN; ++i)
        buf[i] = i;

    // And again...
    (void) clz_arrays(counts, buf, n);    // (3)
    t_ms = clz_arrays(counts, buf, n);    // (4)
    print_stats(t_ms, n, total_MiB);

    free(counts);
    free(buf);
    return 0;
}

上面的代码有点奇怪的是，我第一次和第二次调用 clz_arrays 函数时，它是在未初始化的内存上。

这是典型运行的结果(编译器命令在源代码的开头):

$ ./clz-timing 10000000
Total size: 1220.7 MiB
Time:   47.78 ms,  209.30 x 1e6 clz/s,  25548.9 MiB/s
Time:   77.41 ms,  129.19 x 1e6 clz/s,  15769.7 MiB/s

运行此程序的 CPU 是“Intel(R) Core(TM) i7-6700HQ CPU @ 2.60GHz”，具有 3.5GHz 的涡轮增压。 lzcnt 指令的延迟为 3 个周期，但它的吞吐量为每秒 1 次操作(请参阅 Agner Fog's Skylake instruction tables )，因此，对于 8 字节字(使用 uint64_t)， 3.5GHz 峰值带宽应为 3.5e9 cycles/sec x 8 bytes/cycle = 28.0 GiB/s，这与我们在第一个数字中看到的非常接近。即使在 2.6GHz，我们也应该接近 20.8GiB/s。

我的主要问题是，

Why is the bandwidth of call (4) always so far below the optimal value(s) obtained in call (2) and what can I do to guarantee optimal performance under a majority of circumstances?

关于我目前发现的一些要点:

• 根据 perf 的广泛分析，问题似乎是由 LLC 缓存加载未命中引起的出现在快的情况下。我的猜测是，也许我们正在执行计算的内存尚未初始化这一事实意味着编译器没有义务将任何特定值加载到内存中，但 objdump -d 的输出 清楚地表明每次都在运行相同的代码。就好像硬件预取器第一次处于事件状态而不是第二次处于事件状态，但在任何情况下，这个数组都应该是世界上最容易可靠预取的东西。
• (1) 和 (3) 处的“预热”调用始终与对应于调用 (4) 的第二个打印带宽一样慢。
• 我在台式机(“Intel(R) Xeon(R) CPU E5-2620 v3 @ 2.40GHz”)上获得了几乎相同的结果。
• GCC 4.9、7.0 和 Clang 4.0 的结果基本相同。所有测试均在 Debian 测试、内核 4.14 上运行。
• 所有这些结果和观察也可以通过将 clz_array 替换为 Dan Luu 帖子中的 builtin_popcnt_unrolled_errata_manual 进行必要的必要修改来获得。

如有任何帮助，我们将不胜感激!

最佳答案

The slightly peculiar thing about the code above is that the first and second times I call the clz_arrays function it is on uninitialised memory

未初始化的内存 malloc从内核获取 mmap最初都是写时复制映射到全为零的同一物理页面。

所以你会得到 TLB 未命中但不会缓存未命中。如果它使用 4k 页面，那么您将获得 L1D 命中。如果它使用 2M 大页面，那么您只会获得 L3 (LLC) 命中，但这仍然比 DRAM 带宽好得多。

单核内存带宽通常受限于 max_concurrency / latency ，并且通常不能使 DRAM 带宽饱和。 (有关更多信息，请参阅 Why is Skylake so much better than Broadwell-E for single-threaded memory throughput? 和 this answer 的“延迟限制平台”部分；在多核 Xeon 芯片上比在四核台式机/笔记本电脑上更糟糕。)

您的第一次预热运行将遇到页面错误和 TLB 未命中。此外，在启用了 Meltdown 缓解的内核上，任何系统调用都会刷新整个 TLB。如果您要添加额外的 print_stats以显示热身运行性能，这会使运行速度变慢。

您可能希望在计时运行中多次循环访问同一内存，这样您就不需要因为接触如此多的虚拟地址空间而进行如此多的页面遍历。

clock()不是衡量性能的好方法。它以秒为单位记录时间，而不是 CPU 核心时钟周期。如果您运行基准测试的时间足够长，则不需要非常高的精度，但您需要控制 CPU 频率以获得准确的结果。打电话clock()可能会导致系统调用(启用 Meltdown 和 Spectre 缓解措施)刷新 TLB 和分支预测。 Skylake 从 max turbo 时钟回落的速度可能足够慢。在那之后你不做任何热身工作，当然你不能因为第一个clock()之后的任何事情在时间间隔内。

基于挂钟时间的东西可以使用 RDTSC 作为时间源而不是切换到内核模式(如 gettimeofday() )会降低开销，尽管这样你会测量挂钟时间而不是 CPU 时间。如果机器处于空闲状态，那么这基本上是等价的，因此您的进程不会被取消调度。

对于不受内存限制的事物，计算核心时钟周期的 CPU 性能计数器可以非常准确，并且没有必须控制 CPU 频率的不便。 (尽管现在您不必重新启动即可暂时禁用 Turbo 并将调速器设置为 performance。)

但是对于内存受限的东西，改变内核频率会改变内核与内存的比率，从而使内存相对于 CPU 更快或更慢。

关于c++ - 如何在此循环中获得始终如一的高吞吐量？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/48981887/