如何进一步优化这段关于数组操作的代码？

Question

在下面的代码中，我对两个数组 result 和 DB 执行 XOR 运算，在下面的名为rotate1的偏移量之后访问结果。如您所见，我已经在进行 AVX2、循环展开和预取。我想知道我是否遗漏了任何可能导致速度缓慢的东西。在下面的 else 部分中，每次调用函数时仅访问一次分支。我注意到 50% 的时间花在异或上，其余 40% 的时间花在数据存储上。我仍然有负载。

void perform_array_xor(uint32_t partindex, uint32_t offset, uint64_t *result, uint32_t EntrySize, uint32_t PartSize)
{
    auto B = 1;

    assert(EntrySize/8==B);

    // Ensure that PartSize is a multiple of 32 for this example
    if (PartSize % 8 != 0)
    {
        // Handle this case
        return;
    }

     __m256i a,b,r;

     unsigned int rotate1_1;
     int k;
    
    for (int i = 0; i < PartSize; i += 8)
    {
        rotate1_1 = (i + offset) & (PartSize - 1);


        _mm_prefetch(result + rotate1_1, _MM_HINT_T2);
        k = 0;
        if(rotate1_1 + 7 < PartSize){
            a = _mm256_loadu_si256((__m256i*)(result + rotate1_1));
            b = _mm256_loadu_si256((__m256i*)(DB + partindex + i));
            r = _mm256_xor_si256(a, b);
            _mm256_storeu_si256((__m256i*)(result + rotate1_1), r);
            //std::memcpy(result + rotate1_1, &r, sizeof(__m256i));
            
            k = 4 ;
            a = _mm256_loadu_si256((__m256i*)(result + rotate1_1 + k));
            b = _mm256_loadu_si256((__m256i*)(DB + partindex + i + k));
            r = _mm256_xor_si256(a, b);
            _mm256_storeu_si256((__m256i*)(result + rotate1_1 + k), r);
            //std::memcpy(result + rotate1_1 + k, &r, sizeof(__m256i));
            
        }
        else{
        result[(rotate1_1 + 0) & (PartSize - 1)] ^= DB[partindex + (i + 0)];
        result[(rotate1_1 + 1) & (PartSize - 1)] ^= DB[partindex + (i + 1)];
        result[(rotate1_1 + 2) & (PartSize - 1)] ^= DB[partindex + (i + 2)];
        result[(rotate1_1 + 3) & (PartSize - 1)] ^= DB[partindex + (i + 3)];
        result[(rotate1_1 + 4) & (PartSize - 1)] ^= DB[partindex + (i + 4)];
        result[(rotate1_1 + 5) & (PartSize - 1)] ^= DB[partindex + (i + 5)];
        result[(rotate1_1 + 6) & (PartSize - 1)] ^= DB[partindex + (i + 6)];
        result[(rotate1_1 + 7) & (PartSize - 1)] ^= DB[partindex + (i + 7)];
        }
        
    }
}

更新： 以下是有关该功能的更多实现细节

• DB 数组的大小为 2^28，因此总共 2GB 数据
• 结果是一个大小为 2^14 的数组，总共 128KB
• 函数调用的结果是相同的
• 每次函数调用时，都会访问数据库中连续的 2^14 个条目
• 目前，我看到所有数据库的处理时间为 143 毫秒，约为 13 GB/s
• 针对 i7、第 9 代和 clang 编译器进行优化

Answer 1

每次调用函数时，分支的其他部分仅访问一次

通常，您会将其编写为循环之后的代码，而不是在主循环内编写

if

，即使这意味着您必须在循环外部的作用域中声明

i

。或者，如果您可以计算最终迭代的正确数组索引，而不需要矢量化迭代中的最终

i

，那么就这样做。

---

i7-9xxx 仍然源自 Skylake，因此具有 256KiB 二级缓存。人们可能希望 128KiB

result

在具有不同

part

的调用中能够在二级缓存中保持热状态，但请检查性能计数器来找出答案。

可能查看

l2_lines_out.non_silent

来查看 L2 的脏写回率，而不是干净逐出您仅读取的未修改数据。也许还有

l2_rqsts.rfo_hit

与

l2_rqsts.rfo_miss

，但不，这可能总是很低，因为

result ^=

负载侧的需求缺失将首先出现。因此，存储是在同一地址上的请求加载之后进行的，这意味着您可能不会看到许多 RFO 未命中（因为没有其他线程访问同一行，初始加载将获得 MESI 独占所有权。）这意味着您可能不会看到“也看不到

resource_stalls.sb

的计数（存储缓冲区已满）。

对于具有双通道内存的 i7-9xxx 而言，

13 GiB/s 的速度低得令人失望。 （除非循环内的

if

会减慢速度。但可能不会。 使用 32 字节向量和每个向量操作 2 个加载 + 1 个存储，CPU 吞吐量比 DRAM 带宽高得多，即使编译器不执行 loop unswitching 或剥离最终结果，循环中也存在一些低效率的空间特殊迭代，或任何适用于此优化的名称。）

如果结果在 L2 缓存中保持热状态，您希望更接近最大 DRAM 带宽，例如在具有 DDR4-2666 的系统上超过 30GiB/s，理论最大值为 41.6 GiB/s。 （英特尔“客户端”（非服务器）CPU 通常对 DRAM 具有足够低的延迟，以至于一个核心几乎可以使内存控制器饱和：为什么 Skylake 在单线程内存吞吐量方面比 Broadwell-E 好得多？）

---

也许值得尝试缓存阻塞。对

partindex

的前 32 或 64KiB 执行每个

result

，因此即使来自

DB

的数据流过 L2，它也有望保持热状态。然后循环

result

的其余部分。您仍然只接触

DB

的每个字节（您完全访问）一次，并且块大小为 4KiB 的倍数，如果

DB

和您的部件是 4K 对齐的，您希望避免无用的硬件预取。 （尽管错误推测的负载可能会进入这些页面。）

如果您仅针对某个特定 CPU 进行调整，您还可以使用 NT 预取来绕过 L2，仅预取到 L1（也是 L3 的一种方式，因为它包含在 Intel 客户端 CPU 中）。 （预取距离对 CPU 和条件非常敏感，尤其是 NT 预取。太早的话，数据会在加载之前再次被逐出，这对 NT 预取来说尤其糟糕，因为它甚至不在 L2 中。太晚了，您仍然会得到一个需求负载，这可能会将其拉入 L2，从而阻止使用 NT 预取的尝试。）

除了 NT 预取之外，预取指令通常对现代 CPU（尤其是 Intel）上的顺序访问没有帮助；硬件预取和乱序执行就足够了。 （“每个程序员应该了解的内存知识”有多少仍然有效？）。尽管

gcc -mtune=znver2

或类似的 AMD CPU 在自动矢量化时有时会生成 IIRC 预取指令。如果你的循环没有太多其他事情要做，那么通常运行预取指令不会有什么坏处，除了在 Ivy Bridge 上，这显然存在某种软件预取吞吐量错误。