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

Question

我在一个系统std::fill上观察到,与常量值或动态值相比,std::vector<int>设置常量值时,大型系统显着且持续地较慢:01

5.8 GiB/s vs 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)和英特尔编译器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)是一个ERMSBrep stosb,它将在优化的微编码循环中使用256b存储.(如果缓冲区对齐,则效果最佳,可能至少为32B或64B).

• fill(1)是一个简单的128位movaps向量存储循环.无论宽度如何,每个核心时钟周期只能执行一个存储,最高可达256b AVX.因此128b存储只能填充Haswell的L1D缓存写入带宽的一半. 这就是为什么fill(0)对于高达~32kiB的缓冲区来说,速度大约是2倍.编译-march=haswell或-march=native修复它.

  Haswell几乎无法跟上循环开销,但它仍然可以每个时钟运行1个存储,即使它根本没有展开.但是每个时钟有4个融合域uop,这就是很多填充占用了无序窗口的空间.一些展开可能会让TLB未命中开始在存储发生的地方之前进一步解决,因为存储地址微量的吞吐量比存储数据的吞吐量更多.对于适合L1D的缓冲区,展开可能有助于弥补ERMSB与此向量循环之间的其余差异.(对问题的评论说-march=native只fill(1)对L1有帮助.)

需要注意的是rep movsd(这可能被用来实现fill(1)的int元素)将可能执行相同的rep stosb上的Haswell.虽然只有官方文档只保证ERMSB提供快速rep stosb(但不是rep stosd),支持ERMSB的实际CPU使用类似的高效微码rep stosd.对IvyBridge有一些疑问,可能只有b快速.有关此更新,请参阅@ BeeOnRope的优秀ERMSB答案.

GCC有字符串OPS(一些86优化选项像-mstringop-strategy=ALG和-mmemset-strategy=strategy),但IDK如果任何人会得到它的实际发射rep movsd的fill(1).可能不是,因为我假设代码开始是一个循环,而不是一个memset.

对于多个线程,在4 GiB数据大小时,fill(1)显示更高的斜率,但达到比fill(0)更低的峰值(51 GiB/s vs 90 GiB/s):

movaps冷存储线的正常存储会触发读取所有权(RFO).在movaps写入前16个字节时,大量实际DRAM带宽用于从存储器读取高速缓存行.ERMSB存储为其存储使用无RFO协议,因此内存控制器仅写入.(除了杂项读取之外,如果任何页面遍历错误,甚至在L3缓存中也可能出现页面表,并且可能在中断处理程序中出现一些加载错误或其他情况).

@BeeOnRope 在评论中解释说,常规RFO存储和ERMSB使用的RFO避免协议之间的区别在于服务器CPU上某些缓冲区大小范围的缺点,其中uncore/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矢量足以轻松地将单核的无RFO带宽饱和到DRAM.当存储CPU绑定的AVX 256b矢量化计算的结果时(即,只有当它解除了解包到128b的麻烦时vmovntps ymm),可能(256b)仅比vmovntps xmm(128b)可测量的优势.

movnti 带宽很低,因为存储在每个时钟1个存储uop的4B块块瓶颈中将数据添加到行填充缓冲区,而不是将这些行满的缓冲区发送到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 snooping: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

有趣的是,虽然有一个模板/头优化来实现字节类型的std::fillvia memset,但在这种情况下,它是一个编译器优化来转换实际的循环.奇怪的是,对于a 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具有2倍的优势rep stos.

单线程带宽:

内存中的聚合带宽:

以下是用于各自热循环的附加测试的代码:

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

注意:我必须进行手动指针计算才能使循环变得如此紧凑.否则它会在循环内进行向量索引,可能是由于优化器内在混淆.