如何在此循环中获得始终如一的高吞吐量？

Question

在优化内循环的过程中,我遇到了奇怪的性能行为,我无法理解和纠正.

代码的精简版本如下; 粗略地说,有一个巨大的数组被分成16个字块,我简单地将每个块中字的前导零的数量加起来.(实际上我正在使用Dan Luu的popcnt代码,但是在这里我选择了一个具有类似性能特征的简单指令,用于"简洁".Dan Luu的代码基于这个SO问题的答案,虽然它具有诱人的类似奇怪的结果,似乎没有在这里回答我的问题.)

// -*- 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的Skylake指令表),因此,uint64_t在3.5GHz的8字节字(使用)时,峰值带宽应该是3.5e9 cycles/sec x 8 bytes/cycle = 28.0 GiB/s,这非常接近于我们在第一个数字中看到.即使在2.6GHz,我们也应该接近20.8 GiB/s.

我的主要问题是,

为什么call(4)的带宽总是远远低于call(2)中获得的最佳值,我该怎样做才能保证在大多数情况下的最佳性能？

关于我到目前为止所发现的一些观点:

• 根据广泛的分析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.
• 所有这些结果和观察结果也可以从Dan Luu职位clz_array取代builtin_popcnt_unrolled_errata_manual,经过必要的修正.

非常感激任何的帮助!

Answer 1

关于上面代码的一点点奇怪之处在于我第一次和第二次调用clz_arrays函数它是在未初始化的内存上

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

所以你得到TLB未命中而不是缓存未命中.如果它使用4k页面,那么你会得到L1D命中.如果它使用2M巨页,那么你只能获得L3(LLC)命中,但这仍然比DRAM显着更好的带宽.

单核内存带宽通常受到限制max_concurrency / latency,并且通常不能使DRAM带宽饱和.(请参阅为什么Skylake对Broadwell-E的单线程内存吞吐量要好得多？而且这个答案的"延迟限制平台"部分对此有更多的了解;它在多核Xeon芯片上要比四核处理器差得多 - 核心台式机/笔记本电脑.)

您的第一次热身运行将遭受页面错误以及TLB未命中.此外,在启用了Meltdown缓冲的内核上,任何系统调用都将刷新整个TLB.如果你要添加额外的print_stats以显示预热运行性能,那么这会使运行速度变慢.

您可能希望在计时运行中在同一内存上多次循环,因此您不需要这么多页面遍历来触摸这么多虚拟地址空间.

clock()不是衡量绩效的好方法.它以秒为单位记录时间,而不是CPU核心时钟周期.如果您运行足够长的基准测试,则不需要非常高的精度,但是您需要控制CPU频率以获得准确的结果.调用clock()可能会导致系统调用(启用Meltdown和Spectre缓解)刷新TLB和分支预测.它可能足够慢,让Skylake从最大涡轮增压时钟回落.之后你不做任何热身工作,当然你不能因为第一次之后的任何事情都在clock()定时间隔内.

基于挂钟时间可以使用RDTSC作为时间源而不是切换到内核模式(例如gettimeofday())的东西将是较低的开销,尽管那时你将测量挂钟时间而不是CPU时间.如果机器处于空闲状态,那么这基本上是等效的,因此您的过程不会被取消预定.

对于不受内存限制的内容,计算核心时钟周期的CPU性能计数器可以非常准确,并且不必为CPU频率控制带来不便.(虽然这些天您不必重新启动以暂时禁用turbo并将调控器设置为performance.)

但是对于内存限制的东西,改变核心频率会改变内核与内存的比例,使内存相对于CPU更快或更慢.