c++ - 为什么 std::fill(0) 比 std::fill(1) 慢？

Question

我在一个系统上观察到 std::fill在大 std::vector<int>设置常量值 0 时明显且始终较慢与常数值 1 相比或动态值:

5.8 GiB/s 对比 7.5 GiB/s

但是，对于较小的数据大小，结果是不同的，其中 fill(0)是比较快的:



具有多个线程，数据大小为 4 GiB，fill(1)显示更高的斜率，但达到比 fill(0) 低得多的峰值(51 GiB/s 对比 90 GiB/s):



这就提出了第二个问题，为什么fill(1)的峰值带宽？低得多。

对此的测试系统是一个双插槽 Intel Xeon CPU E5-2680 v3，频率设置为 2.5 GHz(通过 /sys/cpufreq)和 8x16 GiB DDR4-2133。我使用 GCC 6.1.0 ( -O3 ) 和 Intel 编译器 17.0.1 ( -fast ) 进行了测试，都得到了相同的结果。 GOMP_CPU_AFFINITY=0,12,1,13,2,14,3,15,4,16,5,17,6,18,7,19,8,20,9,21,10,22,11,23被设置。 Strem/add/24 个线程在系统上获得 85 GiB/s。

我能够在不同的 Haswell 双插槽服务器系统上重现这种效果，但不能在任何其他架构上重现。例如在 Sandy Bridge EP 上，内存性能是相同的，而在缓存中 fill(0)快得多。

这是要重现的代码:

#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <omp.h>
#include <vector>

using value = int;
using vector = std::vector<value>;

constexpr size_t write_size = 8ll * 1024 * 1024 * 1024;
constexpr size_t max_data_size = 4ll * 1024 * 1024 * 1024;

void __attribute__((noinline)) fill0(vector& v) {
    std::fill(v.begin(), v.end(), 0);
}

void __attribute__((noinline)) fill1(vector& v) {
    std::fill(v.begin(), v.end(), 1);
}

void bench(size_t data_size, int nthreads) {
#pragma omp parallel num_threads(nthreads)
    {
        vector v(data_size / (sizeof(value) * nthreads));
        auto repeat = write_size / data_size;
#pragma omp barrier
        auto t0 = omp_get_wtime();
        for (auto r = 0; r < repeat; r++)
            fill0(v);
#pragma omp barrier
        auto t1 = omp_get_wtime();
        for (auto r = 0; r < repeat; r++)
            fill1(v);
#pragma omp barrier
        auto t2 = omp_get_wtime();
#pragma omp master
        std::cout << data_size << ", " << nthreads << ", " << write_size / (t1 - t0) << ", "
                  << write_size / (t2 - t1) << "\n";
    }
}

int main(int argc, const char* argv[]) {
    std::cout << "size,nthreads,fill0,fill1\n";
    for (size_t bytes = 1024; bytes <= max_data_size; bytes *= 2) {
        bench(bytes, 1);
    }
    for (size_t bytes = 1024; bytes <= max_data_size; bytes *= 2) {
        bench(bytes, omp_get_max_threads());
    }
    for (int nthreads = 1; nthreads <= omp_get_max_threads(); nthreads++) {
        bench(max_data_size, nthreads);
    }
}

呈现的结果由 g++ fillbench.cpp -O3 -o fillbench_gcc -fopenmp 编译.

Answer 1

从您的问题 + 从您的答案编译器生成的 asm:

fill(0)是 ERMSB rep stosb 它将在优化的微编码循环中使用 256b 存储。 (如果缓冲区对齐，则效果最佳，可能至少为 32B 或 64B)。

fill(1)是一个简单的 128 位 movaps vector 存储循环。无论宽度如何，每个内核时钟周期只能执行一个存储，最高可达 256b AVX。所以128b存储只能填满Haswell的L1D缓存写入带宽的一半。 这就是为什么fill(0)对于高达 ~32kiB 的缓冲区，速度大约是其 2 倍。编译 -march=haswell或 -march=native解决这个问题 .

Haswell 只能勉强跟上循环开销，但它仍然可以在每个时钟运行 1 个存储，即使它根本没有展开。但是每个时钟有 4 个融合域 uops，在乱序窗口中占据了大量空间。一些展开可能会让 TLB 未命中在存储发生的位置之前开始解决，因为存储地址 uop 的吞吐量比存储数据的吞吐量要大。对于适合 L1D 的缓冲区，展开可能有助于弥补 ERMSB 和此 vector 循环之间的其余差异。 (对该问题的评论说 -march=native 仅对 L1 有帮助 fill(1)。)

请注意 rep movsd (可用于为 fill(1) 元素实现 int)可能与 rep stosb 执行相同在哈斯韦尔。
虽然只有官方文档只保证ERMSB给出快速 rep stosb (但不是 rep stosd )， actual CPUs that support ERMSB use similarly efficient microcode for rep stosd . IvyBridge 有一些疑问，可能只有 b很快。查看@BeeOnRope 的精彩 ERMSB answer更新。

gcc 有一些用于字符串操作的 x86 调整选项( like -mstringop-strategy= alg and -mmemset-strategy=strategy )，但 IDK(如果有的话)会让它实际发出 rep movsd为 fill(1) .可能不是，因为我假设代码以循环开始，而不是 memset .

With more than one thread, at 4 GiB data size, fill(1) shows a higher slope, but reaches a much lower peak than fill(0) (51 GiB/s vs 90 GiB/s):

正常 movaps存储到冷缓存行会触发 Read For Ownership (RFO) .当 movaps 时，大量实际 DRAM 带宽用于从内存中读取缓存行。写入前 16 个字节。 ERMSB 存储对其存储使用无 RFO 协议(protocol)，因此内存 Controller 仅进行写入。 (除了杂项读取，比如页表，即使在 L3 缓存中也有任何页面遍历未命中，并且可能在中断处理程序中出现一些加载未命中等等)。

@BeeOnRope explains in comments常规 RFO 存储与 ERMSB 使用的 RFO 避免协议(protocol)之间的差异对服务器 CPU 上的某些缓冲区大小范围存在不利影响，其中非核心/L3 缓存中存在高延迟。 另请参阅链接的 ERMSB 答案，了解有关 RFO 与非 RFO 的更多信息，以及多核 Intel CPU 中非核心(L3/内存)的高延迟是单核带宽的问题。

movntps ( _mm_stream_ps() ) 商店 是弱排序的，因此它们可以绕过缓存并一次直接进入整个缓存行的内存，而无需将缓存行读入 L1D。 movntps避免 RFO，例如 rep stos做。 ( rep stos 存储可以相互重新排序，但不能超出指令的边界。)

您的 movntps结果你更新的答案令人惊讶。
对于具有大缓冲区的单个线程，您的结果是 movnt >> 常规 RFO > ERMSB .因此，这两种非 RFO 方法位于普通旧商店的相反两侧真的很奇怪，而且 ERMSB 远非最佳。我目前没有对此的解释。 (欢迎编辑并提供解释 + 良好的证据)。

正如我们所料， movnt允许多个线程实现高聚合存储带宽，如 ERMSB。 movnt总是直接进入行填充缓冲区，然后进入内存，因此适合缓存的缓冲区大小要慢得多。每个时钟一个 128b vector 足以轻松地将单个内核的无 RFO 带宽饱和到 DRAM。大概 vmovntps ymm (256b) 仅比 vmovntps xmm 具有可衡量的优势(128b) 在存储受 CPU 限制的 AVX 256b 向量化计算的结果时(即仅当它省去解包到 128b 的麻烦时)。
movnti带宽很低，因为存储在 4B 块中的瓶颈是每个时钟 1 个存储 uop 将数据添加到行填充缓冲区，而不是将这些行满缓冲区发送到 DRAM(直到您有足够的线程来饱和内存带宽)。

@osgx 发布 some interesting links in comments :

Agner Fog 的 asm 优化指南、指令表和微架构指南:http://agner.org/optimize/

英特尔优化指南:http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf .

NUMA 窥探:http://frankdenneman.nl/2016/07/11/numa-deep-dive-part-3-cache-coherency/

https://software.intel.com/en-us/articles/intelr-memory-latency-checker

Cache Coherence Protocol and MemoryPerformance of the Intel Haswell-EP Architecture

另请参阅 x86 中的其他内容标记维基。