logo标签列表

提高 C++ 内存读取速度

c++performancesimdapple-m1memory-bandwidth
3
我将创建一个包含10亿个32位元素的整数向量，具体操作如下：
std::vector<int> nums;
for (size_t i = 0; i < 1024 * 1024 * 1024; i++) {
   nums.push_back(rand() % 1024);
}

此时该向量包含4GB的随机数据。然后，我只是简单地将向量中所有元素相加，如下所示：

uint64_t total = 0;
for (auto cn = nums.begin(); cn < nums.end(); cn++) {
   total += *cn;
}

这需要约0.18秒，这意味着数据的处理速度大约为22.2 GB/s。我在M1上运行此代码，其内存带宽要高得多，约为60GB/s。有没有办法使上述代码在单核上运行更快？

编辑： 手动SIMD版本：

int32x4_t simd_total = vmovq_n_s32(0); 
for (auto cn = nums.begin(); cn < nums.end()-3; cn +=4) { 
    const int32_t v[4] = {cn[0], cn[1], cn[2], cn[3]} 
    simd_total = vaddq_s32(simd_total, vld1q_s32(v)); 
} 
return vaddvq_s32(simd_total);

SIMD 版本与非手动 SIMD 版本的性能相同。

编辑2： 好吧，我已经按建议将向量元素更改为 uint32_t，并将结果类型也更改为 uint32_t（来自 @Peter Cordes）：

uint32_t sum_ints_32(const std::vector<uint32_t>& nums) {
    uint32_t total = 0;
    for (auto cn = nums.begin(); cn < nums.end(); cn++) {
        total += *cn;
    }
    return total;
}

这个运行速度更快 (~45 GB/s)。这是反汇编：

0000000100002218 <__Z11sum_ints_32RKNSt3__16vectorIjNS_9allocatorIjEEEE>:
   100002218:   a940200c    ldp x12, x8, [x0]
   10000221c:   eb08019f    cmp x12, x8
   100002220:   54000102    b.cs    100002240 <__Z11sum_ints_32RKNSt3__16vectorIjNS_9allocatorIjEEEE+0x28>  // b.hs, b.nlast
   100002224:   aa2c03e9    mvn x9, x12
   100002228:   8b090109    add x9, x8, x9
   10000222c:   f1006d3f    cmp x9, #0x1b
   100002230:   540000c8    b.hi    100002248 <__Z11sum_ints_32RKNSt3__16vectorIjNS_9allocatorIjEEEE+0x30>  // b.pmore
   100002234:   52800000    mov w0, #0x0                    // #0
   100002238:   aa0c03e9    mov x9, x12
   10000223c:   14000016    b   100002294 <__Z11sum_ints_32RKNSt3__16vectorIjNS_9allocatorIjEEEE+0x7c>
   100002240:   52800000    mov w0, #0x0                    // #0
   100002244:   d65f03c0    ret
   100002248:   d342fd29    lsr x9, x9, #2
   10000224c:   9100052a    add x10, x9, #0x1
   100002250:   927ded4b    and x11, x10, #0x7ffffffffffffff8
   100002254:   8b0b0989    add x9, x12, x11, lsl #2
   100002258:   9100418c    add x12, x12, #0x10
   10000225c:   6f00e400    movi    v0.2d, #0x0
   100002260:   aa0b03ed    mov x13, x11
   100002264:   6f00e401    movi    v1.2d, #0x0
   100002268:   ad7f8d82    ldp q2, q3, [x12, #-16]
   10000226c:   4ea08440    add v0.4s, v2.4s, v0.4s
   100002270:   4ea18461    add v1.4s, v3.4s, v1.4s
   100002274:   9100818c    add x12, x12, #0x20
   100002278:   f10021ad    subs    x13, x13, #0x8
   10000227c:   54ffff61    b.ne    100002268 <__Z11sum_ints_32RKNSt3__16vectorIjNS_9allocatorIjEEEE+0x50>  // b.any
   100002280:   4ea08420    add v0.4s, v1.4s, v0.4s
   100002284:   4eb1b800    addv    s0, v0.4s
   100002288:   1e260000    fmov    w0, s0
   10000228c:   eb0b015f    cmp x10, x11
   100002290:   540000a0    b.eq    1000022a4 <__Z11sum_ints_32RKNSt3__16vectorIjNS_9allocatorIjEEEE+0x8c>  // b.none
   100002294:   b840452a    ldr w10, [x9], #4
   100002298:   0b000140    add w0, w10, w0
   10000229c:   eb08013f    cmp x9, x8
   1000022a0:   54ffffa3    b.cc    100002294 <__Z11sum_ints_32RKNSt3__16vectorIjNS_9allocatorIjEEEE+0x7c>  // b.lo, b.ul, b.last
   1000022a4:   d65f03c0    ret

我还重写了Manual-SIMD版本：

uint32_t sum_ints_simd_2(const std::vector<uint32_t>& nums) {
    uint32x4_t  simd_total = vmovq_n_u32(0);
    for (auto cn = nums.begin(); cn < nums.end()-3; cn +=4) {
        const uint32_t v[4] = { cn[0], cn[1], cn[2], cn[3] };
        simd_total = vaddq_u32(simd_total, vld1q_u32(v));
    }
    return vaddvq_u32(simd_total);
}

仍然比非手动SIMD版本慢2倍，并导致以下反汇编结果：
0000000100002464 <__Z15sum_ints_simd_2RKNSt3__16vectorIjNS_9allocatorIjEEEE>:
   100002464:   a9402408    ldp x8, x9, [x0]
   100002468:   d1003129    sub x9, x9, #0xc
   10000246c:   6f00e400    movi    v0.2d, #0x0
   100002470:   eb09011f    cmp x8, x9
   100002474:   540000c2    b.cs    10000248c <__Z15sum_ints_simd_2RKNSt3__16vectorIjNS_9allocatorIjEEEE+0x28>  // b.hs, b.nlast
   100002478:   6f00e400    movi    v0.2d, #0x0
   10000247c:   3cc10501    ldr q1, [x8], #16
   100002480:   4ea08420    add v0.4s, v1.4s, v0.4s
   100002484:   eb09011f    cmp x8, x9
   100002488:   54ffffa3    b.cc    10000247c <__Z15sum_ints_simd_2RKNSt3__16vectorIjNS_9allocatorIjEEEE+0x18>  // b.lo, b.ul, b.last
   10000248c:   4eb1b800    addv    s0, v0.4s
   100002490:   1e260000    fmov    w0, s0
   100002494:   d65f03c0    ret

为了达到与自动向量化版本相同的速度，我们可以在手动SIMD版本中使用uint32x4x2而不是uint32x4：
uint32_t sum_ints_simd_3(const std::vector<uint32_t>& nums) {
    uint32x4x2_t simd_total;
    simd_total.val[0] = vmovq_n_u32(0);
    simd_total.val[1] = vmovq_n_u32(0);
    for (auto cn = nums.begin(); cn < nums.end()-7; cn +=8) {
        const uint32_t v[4] = { cn[0], cn[1], cn[2], cn[3] };
        const uint32_t v2[4] = { cn[4], cn[5], cn[6], cn[7] };
        simd_total.val[0] = vaddq_u32(simd_total.val[0], vld1q_u32(v));
        simd_total.val[1] = vaddq_u32(simd_total.val[1], vld1q_u32(v2));
    }
    return vaddvq_u32(simd_total.val[0]) + vaddvq_u32(simd_total.val[1]);
}

为了获得更高的速度，我们可以利用uint32x4x4（从而获得约53 GB/s）：

uint32_t sum_ints_simd_4(const std::vector<uint32_t>& nums) {
    uint32x4x4_t simd_total;
    simd_total.val[0] = vmovq_n_u32(0);
    simd_total.val[1] = vmovq_n_u32(0);
    simd_total.val[2] = vmovq_n_u32(0);
    simd_total.val[3] = vmovq_n_u32(0);
    for (auto cn = nums.begin(); cn < nums.end()-15; cn +=16) {
        const uint32_t v[4] = { cn[0], cn[1], cn[2], cn[3] };
        const uint32_t v2[4] = { cn[4], cn[5], cn[6], cn[7] };
        const uint32_t v3[4] = { cn[8], cn[9], cn[10], cn[11] };
        const uint32_t v4[4] = { cn[12], cn[13], cn[14], cn[15] };
        simd_total.val[0] = vaddq_u32(simd_total.val[0], vld1q_u32(v));
        simd_total.val[1] = vaddq_u32(simd_total.val[1], vld1q_u32(v2));
        simd_total.val[2] = vaddq_u32(simd_total.val[2], vld1q_u32(v3));
        simd_total.val[3] = vaddq_u32(simd_total.val[3], vld1q_u32(v4));
    }
    return vaddvq_u32(simd_total.val[0])
        + vaddvq_u32(simd_total.val[1])
        + vaddvq_u32(simd_total.val[2])
        + vaddvq_u32(simd_total.val[3]);
}

我们得到以下反汇编代码：

0000000100005e34 <__Z15sum_ints_simd_4RKNSt3__16vectorIjNS_9allocatorIjEEEE>:
   100005e34:   a9402408    ldp x8, x9, [x0]
   100005e38:   d100f129    sub x9, x9, #0x3c
   100005e3c:   6f00e403    movi    v3.2d, #0x0
   100005e40:   6f00e402    movi    v2.2d, #0x0
   100005e44:   6f00e401    movi    v1.2d, #0x0
   100005e48:   6f00e400    movi    v0.2d, #0x0
   100005e4c:   eb09011f    cmp x8, x9
   100005e50:   540001c2    b.cs    100005e88 <__Z15sum_ints_simd_4RKNSt3__16vectorIjNS_9allocatorIjEEEE+0x54>  // b.hs, b.nlast
   100005e54:   6f00e400    movi    v0.2d, #0x0
   100005e58:   6f00e401    movi    v1.2d, #0x0
   100005e5c:   6f00e402    movi    v2.2d, #0x0
   100005e60:   6f00e403    movi    v3.2d, #0x0
   100005e64:   ad401504    ldp q4, q5, [x8]
   100005e68:   ad411d06    ldp q6, q7, [x8, #32]
   100005e6c:   4ea38483    add v3.4s, v4.4s, v3.4s
   100005e70:   4ea284a2    add v2.4s, v5.4s, v2.4s
   100005e74:   4ea184c1    add v1.4s, v6.4s, v1.4s
   100005e78:   4ea084e0    add v0.4s, v7.4s, v0.4s
   100005e7c:   91010108    add x8, x8, #0x40
   100005e80:   eb09011f    cmp x8, x9
   100005e84:   54ffff03    b.cc    100005e64 <__Z15sum_ints_simd_4RKNSt3__16vectorIjNS_9allocatorIjEEEE+0x30>  // b.lo, b.ul, b.last
   100005e88:   4eb1b863    addv    s3, v3.4s
   100005e8c:   1e260068    fmov    w8, s3
   100005e90:   4eb1b842    addv    s2, v2.4s
   100005e94:   1e260049    fmov    w9, s2
   100005e98:   0b080128    add w8, w9, w8
   100005e9c:   4eb1b821    addv    s1, v1.4s
   100005ea0:   1e260029    fmov    w9, s1
   100005ea4:   0b090108    add w8, w8, w9
   100005ea8:   4eb1b800    addv    s0, v0.4s
   100005eac:   1e260009    fmov    w9, s0
   100005eb0:   0b090100    add w0, w8, w9
   100005eb4:   d65f03c0    ret

疯狂的东西

2
你必须记住，其他任务和硬件设备需要共享数据总线和地址总线。当其他设备正在使用数据和地址总线时，CPU 的取指可能需要等待。 - Thomas Matthews
你可以尝试展开 for 循环。处理器不喜欢分支语句，因此你消除的分支越多，它就会越高兴。例如，在循环中可以有 4、16 或更多次加法运算，然后再绕回来进行分支。一些编译器可能会在更高的优化级别下执行此操作。 - Thomas Matthews
另一种技术是使用多个寄存器。例如，有4个变量，并读取它们。然后使用这4个变量进行求和。这将有助于缓存访问，因为4个访问将紧密相邻，没有分支语句。 - Thomas Matthews
@PeterCordes 非常感谢您的想法，将 int64_t 值改为 summing int32_t 确实可以大大提高性能。现在它的速度已经达到了约 45 GB/s。我还尝试使用 neon intrinsics，但奇怪的是速度回到了原始的 22GB/s 速度：int32x4_t simd_total = vmovq_n_s32(0); for (auto cn = nums.begin(); cn < nums.end()-3; cn +=4) { const int32_t v[4] = {cn[0], cn[1], cn[2], cn[3]} simd_total = vaddq_s32(simd_total, vld1q_s32(v)); } return vaddvq_s32(simd_total); - user2403221
1
@Peter Cordes，是的，你说得对，我想保持一致，但第一个版本已经自动向量化了，所以不太准确。我的意思是非手动SIMD版本;) 顺便说一句，使用uint32x4x4_t手动SIMD版本甚至比自动向量化版本更快（~53 GB/s）。 - user2403221
显示剩余9条评论
3个回答
2
“-march=native”是否有帮助？我不确定苹果clang是否已经利用了第一代AArch64 MacOS CPU上的任何SIMD特性，但是clang可能只是在一般情况下采用基线AArch64。如果使用“uint32_t”求和，编译器就不必在加法之前扩展每个元素，这样每个SIMD指令只能从内存中处理一半大小的数据，与相同大小的累加器相比速度会更快。链接https://godbolt.org/z/7c19913jE显示Thomas Matthews的展开建议确实可以让clang11 -O3 -march=apple-a13展开它所生成的SIMD向量化汇编循环。这种源代码更改通常不是一个优势，在x86-64 clang -O3 -march=haswell中表现得更差，但在这里确实有帮助。
另一种可能性是单个核心无法饱和内存带宽。但例如Anandtech发布的基准测试结果似乎排除了这种可能性：他们发现即使单个核心也可以达到59GB/s，尽管这可能是运行了一个优化的memcpy函数。
（他们说：“单个Firestorm核心几乎可以饱和内存控制器，这是我们以前从未见过的设计。”听起来有点奇怪；桌面/笔记本电脑的Intel CPU已经非常接近了，不像他们的“服务器”芯片。也许不像苹果那么接近？
与现代x86相比，M1的内存延迟非常低，因此这可能有助于单个核心能够跟踪传入的负载，保持必要的延迟x带宽乘积在飞行中，即使其具有高内存带宽。
好的，让我们把讨论移到这里，我又更新了问题。 - user2403221
@user2403221：在你的编辑中，你提到了“非SIMD版本”。但实际上那是自动向量化版本！看一下汇编代码：ldp加载两个16字节的q寄存器，用于uint32_t循环的两个add v0.4s ...指令，而你手动循环每次只有一个指令。 （通过优化掉局部数组的复制，而是从std::vector进行矢量加载，否则速度会慢得多）。 - Peter Cordes
是的，那不太清楚，我又编辑了一下！非常感谢，我想今天我们能得到的速度就这么多了！ - user2403221
1
也许值得添加 Optimizing AMD Opteron Memory Bandwidth 这篇文章是一篇不错的阅读材料。DRAM与交错页面的额外并行性对于读取操作有一些显著的影响，特别是在北通道频率高于任何银行可以在新的DRAM上产生的情况下。 - Noah
1
@Noah：在这里转发你分享的链接：Apple M1 微架构逆向工程（PDF），作者是 Maynard Handley。其中包括一些实验细节，以便了解事物如何运作，以及一些很好的通用计算机架构内容。(reddit 线程，有人将其链接并归功于 Maynard 的大部分工作，还包括 Travis Downs（BeeOnRope）、Dougall J、Andrei Frumusanu 等人的贡献。) - Peter Cordes
1

这里是一些技术。

循环展开

uint64_t total = 0;
for (auto cn = nums.begin(); cn < nums.end(); cn += 4)
{
    total += cn[0];
    total += cn[1];
    total += cn[2];
    total += cn[3];
}

注册预取

uint64_t total = 0;
for (auto cn = nums.begin(); cn < nums.end(); cn += 4)
{
    const uint64 n0 = cn[0];
    const uint64 n1 = cn[1];
    const uint64 n2 = cn[2];
    const uint64 n3 = cn[3];
    total += n0;
    total += n1;
    total += n2;
    total += n3;
}

你应该使用高优化级别打印每个的汇编语言，并进行比较。

此外，您的处理器可能具有一些专门的指令，例如 ARM 处理器可以使用一条指令从内存中加载多个寄存器。

同时，请查询 SIMD 指令或在互联网上搜索“C++ SIMD read memory”。

我曾与编译器（在嵌入式系统上）争论过，发现编译器的优化策略可能比指令专业化或其他技术更好或相等（使用测试点和示波器进行计时）。

请记住，在单核机器上，您的任务很可能会比拥有多个核心或专用（嵌入式）系统的系统更经常被换出。

2
不是我的 DV，而是你的“寄存器预取”版本应该与现代 C++ 编译器编译成相同的汇编代码。(并且使用 clang -O3 -mcpu=apple-a13 https://godbolt.org/z/7c19913jE，可能类似于 M1 上的 MacOS 上的 Apple clang)。如果没有这样做，那么对于任何一个不是最优的版本来说，这将是一种错失的优化。(实际上，这就是编译器已经擅长的优化类型；它们已经将您的 C++ 源代码编译成 SSA 形式，在这种情况下，值是否具有 C++ 变量名称并不重要。) - Peter Cordes
2
如果您的循环包含通过指针进行赋值，则提前进行大量操作可能会很有用：这可以节省编译器检查别名以维护精确的C++语义的时间，如果您重新读取刚刚存储的内容。但是在这里，您没有获取n0..3的地址，因此它们将根据编译器内部的通常设计轻松地进行优化。有趣的是，当自动矢量化时，clang没有为您展开原始源代码。如果不是使用更广泛的总和，它可能会这样做。clang喜欢展开，至少对于x86来说是这样。也许对于AArch64不是这样。 - Peter Cordes
1
请注意，手动进行标量展开并不总是一件好事！对于使用clang的x86相同代码，展开的源代码会使SSE2自动向量化失败（其中64位向量元素的符号扩展是一个痛点）。https://godbolt.org/z/oo31sYYeh显示clang自动向量化（和展开）简单循环，但仅使用标量（展开4次）进行循环。或者，如果有AVX2可用，则可以将n0..3作为一个向量的元素，并在循环内部进行水平求和！与保持4个向量累加器的简单源代码相比，这样做的汇编代码要好得多。 - Peter Cordes
使用多个累加器（单独的 total0 ... total3 变量）展开源代码可能会有所帮助。但通常仅适用于浮点数，因为编译器无法为您完成此操作（没有 -ffast-math 或至少 -fassociative-math 和其他选项）。但是，对于整数来说，这通常不是一个因素，因为它是可结合的，所以如果有用的话，编译器可以发明更多的向量累加器来隐藏 SIMD 整数加法延迟。 - Peter Cordes
嗨@ThomasMatthews，非常感谢您的贡献！看起来编译器已经自行应用了这些优化（我刚刚测试过）。 - user2403221
显示剩余2条评论
0
考虑尽可能预先计算并使用内置STL函数，这将在尝试SIMD或汇编方法之前产生尽可能优化的代码。如果仍然太慢，则尝试SIMD/汇编版本：
避免在未预留std :: vector的情况下调用push_back：当达到容量限制时，这会导致系统分配更多空间。由于您事先知道数组的大小，请提前保留空间：（对于非内置类型，还要考虑emplace_back）。
此外，STL函数可以将样板代码减少到两个函数调用。
另外，避免使用rand()。
const std::size_t GB = 1024 * 1024 * 1024;
std::vector<int> nums(4 * GB);
std::generate(std::begin(nums), std::end(nums), [](){ return rand() % 1024; });

//...

const auto sum = std::accumulate(std::begin(nums), std::end(nums), 0);
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接