C++优化内存读取速度

Question

我正在创建一个包含 1024 * 1024 * 1024 个元素的 int(32 位) vector ，如下所示:

std::vector<int> nums;
for (size_t i = 0; i < 1024 * 1024 * 1024; i++) {
   nums.push_back(rand() % 1024);
}

此时包含 4 GB 的随机数据。然后我简单地总结 vector 中的所有元素，如下所示:

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

这大约需要 0.18 秒，这意味着数据的处理速度约为 22.2 GB/秒。我在 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:好的，所以我将 vector 元素更改为 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

疯狂的东西

Answer 1

-march=native 有帮助吗？ IDK 如果有任何 SIMD 特性是 Apple clang 尚未在第一代 AArch64 MacOS CPU 上利用的，但 clang 可能只是一般采用基线 AArch64。

如果使用 uint32_t 总和，编译器不必在添加之前加宽每个元素，是否可以更快？这意味着每条 SIMD 指令只能处理来自内存的数据量是相同大小的累加器的一半。

https://godbolt.org/z/7c19913jE显示 Thomas Matthews 的展开建议实际上确实让 clang11 -O3 -march=apple-a13 展开它制作的 SIMD 向量化 asm 循环。这种来源的改变并不是一般的胜利，例如很多对于 x86-64 clang -O3 -march=haswell 更糟糕，但它在这里确实有帮助。

---

另一种可能性是单核无法使内存带宽饱和。但基准测试结果公布by Anandtech for example似乎排除了这一可能性:他们发现即使是单个内核也可以达到 59GB/s，尽管这可能是在运行优化的 memcpy 函数。

(他们说单个 Firestorm 核心几乎可以使内存 Controller 饱和这一事实令人震惊，这是我们以前在设计中从未见过的。这听起来有点奇怪；台式机/笔记本电脑英特尔CPU 非常接近，unlike their "server" chips。也许不像 Apple 那样接近？

与现代 x86 相比，M1 具有相当低的内存延迟，因此这可能有助于单核能够跟踪传入的负载，以保持必要的延迟 x 带宽乘积在运行中，即使它具有高内存带宽也是如此。