为什么 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) 的峰值带宽要低得多。

此测试系统是双插槽英特尔至强 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

我将分享我的初步发现，希望鼓励更详细的答案。我只是觉得这作为问题本身的一部分太过分了。

编译器将fill(0)优化为内部memset。它不能对 fill(1) 执行相同的操作，因为 memset 仅适用于字节。

具体来说，glibcs __memset_avx2 和 __intel_avx_rep_memset 都是用一条热指令实现的：

rep    stos %al,%es:(%rdi)

手动循环在哪里编译成实际的 128 位指令：

add    [=11=]x1,%rax                                                                                                       
add    [=11=]x10,%rdx                                                                                                      
movaps %xmm0,-0x10(%rdx)                                                                                               
cmp    %rax,%r8                                                                                                        
ja     400f41

有趣的是，虽然有一个 template/header 优化来通过 memset 为字节类型实现 std::fill，但在这种情况下，它是一个编译器优化来转换实际循环。奇怪的是，对于 std::vector<char>，gcc 也开始优化 fill(1)。尽管有 memset 模板规范，但英特尔编译器没有。

由于这种情况仅在代码实际在内存而不是缓存中运行时才会发生，因此 Haswell-EP 架构似乎无法有效地整合单字节写入。

我会感谢对问题和相关微体系结构细节的任何进一步见解。特别是我不清楚为什么这对四个或更多线程的行为如此不同以及为什么 memset 在缓存中如此快。

更新：

这是与

对比的结果

fill(1) 使用 -march=native (avx2 vmovdq %ymm0) - 它在 L1 中工作得更好，但与其他内存级别的 movaps %xmm0 版本相似。
32、128 和 256 位非临时存储的变体。无论数据大小如何，它们都以相同的性能一致地执行。所有这些都优于内存中的其他变体，特别是对于少量线程。 128 位和 256 位的性能完全相似，对于少量线程，32 位的性能明显更差。

对于 <= 6 线程，vmovnt 在内存中运行时比 rep stos 有 2 倍的优势。

单线程带宽：

内存中的总带宽：

这是用于附加测试及其各自热循环的代码：

void __attribute__ ((noinline)) fill1(vector& v) {
    std::fill(v.begin(), v.end(), 1);
}
┌─→add    [=12=]x1,%rax
│  vmovdq %ymm0,(%rdx)
│  add    [=12=]x20,%rdx
│  cmp    %rdi,%rax
└──jb     e0


void __attribute__ ((noinline)) fill1_nt_si32(vector& v) {
    for (auto& elem : v) {
       _mm_stream_si32(&elem, 1);
    }
}
┌─→movnti %ecx,(%rax)
│  add    [=12=]x4,%rax
│  cmp    %rdx,%rax
└──jne    18


void __attribute__ ((noinline)) fill1_nt_si128(vector& v) {
    assert((long)v.data() % 32 == 0); // alignment
    const __m128i buf = _mm_set1_epi32(1);
    size_t i;
    int* data;
    int* end4 = &v[v.size() - (v.size() % 4)];
    int* end = &v[v.size()];
    for (data = v.data(); data < end4; data += 4) {
        _mm_stream_si128((__m128i*)data, buf);
    }
    for (; data < end; data++) {
        *data = 1;
    }
}
┌─→vmovnt %xmm0,(%rdx)
│  add    [=12=]x10,%rdx
│  cmp    %rcx,%rdx
└──jb     40


void __attribute__ ((noinline)) fill1_nt_si256(vector& v) {
    assert((long)v.data() % 32 == 0); // alignment
    const __m256i buf = _mm256_set1_epi32(1);
    size_t i;
    int* data;
    int* end8 = &v[v.size() - (v.size() % 8)];
    int* end = &v[v.size()];
    for (data = v.data(); data < end8; data += 8) {
        _mm256_stream_si256((__m256i*)data, buf);
    }
    for (; data < end; data++) {
        *data = 1;
    }
}
┌─→vmovnt %ymm0,(%rdx)
│  add    [=12=]x20,%rdx
│  cmp    %rcx,%rdx
└──jb     40

注意：为了使循环如此紧凑，我不得不进行手动指针计算。否则它会在循环内进行向量索引，这可能是由于优化器的内在混淆。

Answer 2

根据您的问题 + 根据您的回答编译器生成的 asm：

fill(0) 是一个，它将在优化的微编码循环中使用 256b 存储。（如果缓冲区对齐，效果最好，可能至少为 32B 或 64B）。
fill(1) 是一个简单的 128 位 movaps 向量存储循环。无论宽度如何，每个内核时钟周期只能执行一个存储，最高 256b AVX。所以 128b 的存储只能填满 Haswell 的 L1D 缓存写入带宽的一半。 这就是为什么 fill(0) 对于高达 ~32kiB 的缓冲区来说大约快 2 倍。使用 -march=haswell 或 -march=native 编译以修复 .

Haswell 只能勉强跟上循环开销，但它仍然可以运行每个时钟存储 1 个，即使它根本没有展开。但是每个时钟有 4 个融合域 uops，在无序 window 中占用了很多填充符 space。一些展开可能会让 TLB 未命中在存储发生之前更早地开始解决，因为存储地址微指令的吞吐量比存储数据的吞吐量大。展开可能有助于弥补 ERMSB 与适用于 L1D 的缓冲区的矢量循环之间的其余差异。（对该问题的评论说 -march=native 只对 L1 有帮助 fill(1)。）

请注意，rep movsd（可用于为 int 元素实现 fill(1)）可能与 Haswell 上的 rep stosb 执行相同。虽然只有官方文档只保证 ERMSB 给出快速rep stosb（而不是rep stosd），. There is some doubt about IvyBridge, where maybe only b is fast. See the @BeeOnRope's excellent 对此进行更新

gcc 有一些用于字符串操作的 x86 调整选项 (like -mstringop-strategy=alg and -mmemset-strategy=strategy)，但 IDK 如果其中任何一个将使它实际为 fill(1) 发出 rep movsd。可能不是，因为我假设代码开始时是一个循环，而不是 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 写入前 16 个字节时，大量实际 DRAM 带宽用于从内存读取缓存行。 ERMSB 存储对其存储使用无 RFO 协议，因此内存控制器仅进行写入。（除了杂项读取，例如页表，如果任何页面遍历甚至在 L3 缓存中都未命中，并且可能在中断处理程序或其他内容中有一些加载未命中）。

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

movntps (_mm_stream_ps()) 存储 是弱排序的，因此它们可以绕过缓存并直接进入内存中的整个缓存行有一段时间没有将缓存行读入 L1D。 movntps 避免 RFO，就像 rep stos 那样。（rep stos 商店可以相互重新排序，但不能超出指令范围。）

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

如我们所料，movnt 允许多个线程实现高聚合存储带宽，如 ERMSB。 movnt 总是直接进入行填充缓冲区，然后进入内存，因此对于适合缓存的缓冲区大小来说要慢得多。每个时钟一个 128b 矢量足以轻松地将单个内核的无 RFO 带宽饱和到 DRAM。在存储 CPU 绑定的 AVX 256b 向量化计算的结果时，vmovntps ymm (256b) 可能仅比 vmovntps xmm (128b) 具有可测量的优势（即仅当它节省了麻烦时解包到 128b).

movnti 带宽很低，因为在 4B 块中存储瓶颈是每个时钟 1 个存储 uop 将数据添加到行填充缓冲区，而不是将那些行满缓冲区发送到 DRAM（直到你有足够的线程来饱和内存带宽）。

@osgx 发布 :

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
缓存一致性协议和内存英特尔 Haswell-EP 架构的性能

另请参阅 x86 标签 wiki 中的其他内容。

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

Why is std::fill(0) slower than std::fill(1)?

c++

performance

x86

memset

compiler-optimization