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

Question

我在一个系统上观察到，与常值std::fill或动态值相比，设置常值0时，大型std::vector<int>上的0要慢得多：

5.8GIB/s对7.5GIB/s

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

​

​

使用多个线程，在4个GiB数据大小下，fill(1)显示出较高的斜率，但达到比fill(0)低得多的峰值(51 GiB/s对90 GiB/s)：

​

​

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

测试系统是一个双套接字英特尔Xeon 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上，内存性能是相同的，而缓存中的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)是一个rep stosb，它将在一个优化的微编码循环中使用256 b存储。(如果缓冲区对齐，可能至少与32B或64B对齐，效果最好)。
• fill(1)是一个简单的128位movaps矢量存储循环.只有一个存储可以执行每个核心时钟周期，无论宽度，高达256 b AVX。因此128 B存储只能填满Haswell的L1D缓存写入带宽的一半。这就是为什么fill(0) 的缓冲速度是~32 This的2倍。使用-march=haswell 或 -march=native 编译以修复。 Haswell几乎无法跟上循环开销，但它仍然可以运行每个时钟一个商店，即使它根本没有展开。但是每个时钟有4个融合域up，这在无序窗口中占据了大量的空间。一些展开可能会让TLB在商店发生之前就开始更远的解析，因为存储地址uop的吞吐量比存储数据的吞吐量要高。展开可能有助于弥补ERMSB与适合于L1D的缓冲区的向量循环之间的其余差异。(对此问题的评论称，-march=native只帮助了fill(1) for L1。)

请注意，rep movsd (可以用于为int元素实现fill(1) )可能会执行与Haswell上的rep stosb相同的操作。尽管只有官方文档才能保证ERMSB提供快速的rep stosb (而不是rep stosd)、rep stosd。对于IvyBridge有一些疑问，也许只有b才是最快的。有关此方面的更新，请参阅@BeeOnRope的优秀再培训局答覆。

gcc为字符串操作(-mmemset-strategy=strategy)提供了一些-mmemset-strategy=strategy调优选项，但如果它们中的任何一个，则会使其真正为fill(1)发出rep movsd。可能不会，因为我假设代码开始时是一个循环，而不是一个memset。

使用多个线程，在4 GiB数据大小下，fill(1)显示出较高的斜率，但达到一个比fill(0)低得多的峰值(51 GiB/s对90 GiB/s)：

普通的movaps 存储到冷缓存行触发 阅读所有权(RFO)。当movaps写入前16个字节时，大量的实际DRAM带宽用于从内存中读取缓存行。ERMSB存储使用非RFO协议作为存储，因此内存控制器只编写.(除了杂乱的读取之外，就像页面表，即使在L3缓存中，任何页面都会丢失，或者中断处理程序或其他方面的一些加载缺失)。

@BeeOnRope 在评论中解释：常规RFO存储与ERMSB使用的避免RFO的协议之间的差异，对服务器CPU上的某些缓冲区大小有不利影响，在uncore/L3缓存中存在很高的延迟。还可以看到更多关于RFO与非RFO的链接ERMSB答案，以及在多核Intel CPUs中的高延迟(l3/内存)是单核带宽的一个问题。

movntps (**_mm_stream_ps()**)存储是弱有序的，因此它们可以绕过缓存，一次直接存储整个缓存行，而无需将缓存行读入L1D。movntps像rep stos一样避免使用RFO。(rep stos存储可以彼此重新排序，但不能超出指令的范围。)

您的movntps结果在您更新的答案是令人惊讶的。

对于具有大缓冲区的单个线程，您的结果是movnt >>正则RFO > ERMSB。所以，奇怪的是，两个非RFO方法位于普通老商店的对立面，而ERMSB却远非最优。我目前对此没有任何解释。(编辑欢迎和解释+良好的证据)。

正如我们所预期的，movnt允许多个线程实现高聚合存储带宽，比如ERMSB。movnt总是直接进入行填充缓冲区，然后进入内存，所以对于缓存中的缓冲区大小来说，它要慢得多。每个时钟一个128 B矢量就足以使单个核的无RFO带宽很容易地饱和到DRAM。可能vmovntps ymm (256 B)在存储CPU范围内的AVX256b向量化计算的结果时，仅仅是vmovntps xmm (128 B)的一个可衡量的优势(也就是说，只有当它将解压缩的麻烦省去到128 B时)。

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

@osgx发布评论中的一些有趣的链接

• Agner的asm优化指南、指令表和微弓指南：http://agner.org/optimize/
• 英特尔优化指南：http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf。
• 努马窥探：http://frankdenneman.nl/2016/07/11/numa-deep-dive-part-3-cache-coherency/
• https://software.intel.com/en-us/articles/intelr-memory-latency-checker
• Intel Haswell-EP体系结构的缓存一致性协议及内存性能

还请参阅x86标记wiki中的其他内容。

Answer 2

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

编译器将fill(0)优化为内部memset。它不能对fill(1)做同样的事情，因为memset只在字节上工作。

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

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

手动循环编译到实际128位指令的位置：

add    $0x1,%rax                                                                                                       
add    $0x10,%rdx                                                                                                      
movaps %xmm0,-0x10(%rdx)                                                                                               
cmp    %rax,%r8                                                                                                        
ja     400f41

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

因为只有当代码实际在内存中工作而不是在缓存中工作时，才会发生这种情况，这使得Haswell-EP体系结构无法有效地合并单个字节写入。

我希望能更深入地了解这个问题和相关的微观体系结构细节。特别是，我不清楚为什么这在四个或更多线程中的行为如此不同，以及为什么memset在缓存中的速度要快得多。

更新：

以下是与

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

对于vmovnt 6线程，在内存中操作时，<= 比有2倍的优势。

单线程带宽：

​

​

内存中的总带宽：

​

​

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

void __attribute__ ((noinline)) fill1(vector& v) {
    std::fill(v.begin(), v.end(), 1);
}
┌─→add    $0x1,%rax
│  vmovdq %ymm0,(%rdx)
│  add    $0x20,%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    $0x4,%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    $0x10,%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    $0x20,%rdx
│  cmp    %rcx,%rdx
└──jb     40

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