performance - 在内存中交换未对齐的 64 位值的字节的最快方法是什么？

Question

我在内存中有大量 64 位值。不幸的是，它们可能不会与 64 位地址对齐。我的目标是改变所有这些值的字节序，即交换/反转它们的字节。

我知道 bswap交换 32 位或 64 位寄存器字节的指令。但是因为它需要一个寄存器参数，所以我不能将它传递给我的内存地址。当然我可以先将内存加载到寄存器中，然后交换，然后写回:

mov rax, qword [rsi]
bswap rax
mov qword [rsi], rax

但这是否正确，因为地址可能未对齐？

另一种可能性是手动进行交换:

mov al, byte [rsi + 0]
mov bl, byte [rsi + 7]
mov byte [rsi + 0], bl
mov byte [rsi + 7], al

mov al, byte [rsi + 1]
mov bl, byte [rsi + 6]
mov byte [rsi + 1], bl
mov byte [rsi + 6], al

mov al, byte [rsi + 2]
mov bl, byte [rsi + 5]
mov byte [rsi + 2], bl
mov byte [rsi + 5], al

mov al, byte [rsi + 3]
mov bl, byte [rsi + 4]
mov byte [rsi + 3], bl
mov byte [rsi + 4], al

这显然是更多的指令。但它也更慢吗？

但总而言之，我对 x86-64 仍然缺乏经验，所以我想知道: 在内存中字节交换 64 位值的最快方法是什么？我描述的两个选项之一是最佳选择吗？或者是否有一种完全不同的方法甚至更快？

PS:我的真实情况有点复杂。我确实有一个大字节数组，但它包含不同大小的整数，全部密集。其他一些数组告诉我接下来期望的整数大小。所以这个“描述”可以说“一个 32 位整数，两个 64 位整数，一个 16 位整数，然后又是一个 64 位整数”。我在这里提到这个只是为了告诉你(据我所知)，使用 SIMD 指令是不可能的，因为我实际上必须在阅读之前检查每个整数的大小。

Answer 1

What is the fastest way to byte swap a 64 bit value in memory?

mov/bswap/mov版本和 movbe/mov在大多数英特尔处理器上大致相同。根据 µop 计数，似乎 movbe解码为 mov + bswap ，除了在 Atom 上。对于锐龙， movbe可能更好。手动交换字节要慢得多，除非在大型加载/存储非常慢的某些边缘情况下，例如当它跨越 4K 边界 pre-Skylake 时。
pshufb即使替换单个 bswap 也是一个合理的选择，尽管这浪费了 shuffle 可以做的一半工作。

PS: My real situation is a bit more complicated. I do have a large byte array, but it contains differently sized integers, all densely packed.

在这种一般情况下，从其他数据流中动态获取大小，一个新的大问题是大小的分支。即使在可以避免的标量代码中，通过对 64 位块进行字节反转并将其右移 8 - size ，然后将其与未反转的字节合并，并前进 size .这可以解决，但尝试这样做是浪费时间，SIMD 版本会更好。

SIMD 版本可以使用 pshufb和一个由“大小模式”索引的混洗掩码表，例如一个 8 位整数，其中每 2 位表示一个元素的大小。 pshufb然后反转它正在查看的 16 字节窗口中完全包含的元素，并保留其余部分(尾部未更改的字节也将被写回，但没关系)。然后我们按照实际处理的字节数前进。

为了最大的方便，这些大小模式(以及相应的字节数)应该以这样一种方式提供，即实际的 Endianness Flipper 本身可以在每次迭代中只消耗其中的一个，而没有任何沉重的东西，例如 提取 一个字节未对齐的 8 位序列，并动态确定要消耗多少位。这也是可能的，但成本要高得多。在我的测试中大约慢 4 倍，受循环携带依赖的限制，通过“在当前位索引处提取 8 位”通过“通过表查找查找位索引增量”然后进入下一次迭代:每次迭代大约 16 个周期，尽管仍有 60% 的时间是等效的标量代码所花费的时间。

使用未打包(每个大小 1 个字节)表示会使提取更容易(只是未对齐的双字加载)，但需要打包结果以索引 shuffle 掩码表，例如使用 pext .这对于 Intel CPU 来说是合理的，但是 pext在 AMD Ryzen 上速度非常慢。对 AMD 和 Intel 都适用的替代方法是执行未对齐的双字读取，然后使用乘法/移位技巧提取 8 个有趣的位:

mov eax, [rdi]
imul eax, eax, 0x01041040
shr eax, 24

应该使用的一个额外技巧，至少在方便输入的情况下(否则无论如何我们都会遇到 5 倍差的性能并且这个技巧将不相关)，是在存储结果之前读取下一次迭代的数据当前迭代。如果没有这个技巧，存储通常会“踩到”下一次迭代的负载(因为我们前进的字节少于 16 个字节，因此负载读取存储保持不变但无论如何必须写入的一些字节)，强制它们之间存在内存依赖性，从而阻止下一次迭代。性能差异很大，大约3倍。

然后 Endianness Flipper 可能看起来像这样:

void flipEndiannessSSSE3(char* buffer, size_t totalLength, uint8_t* sizePatterns, uint32_t* lengths, __m128i* masks)
{
    size_t i = 0;
    size_t j = 0;
    __m128i data = _mm_loadu_si128((__m128i*)buffer);
    while (i < totalLength) {
        int sizepattern = sizePatterns[j];
        __m128i permuted = _mm_shuffle_epi8(data, masks[sizepattern]);
        size_t next_i = i + lengths[j++];
        data = _mm_loadu_si128((__m128i*)&buffer[next_i]);
        _mm_storeu_si128((__m128i*)&buffer[i], permuted);
        i = next_i;
    }
}

例如，带有 -O3 -march=haswell 的 Clang 10把它变成

    test    rsi, rsi
    je      .LBB0_3
    vmovdqu xmm0, xmmword ptr [rdi]
    xor     r9d, r9d
    xor     r10d, r10d
.LBB0_2:                            # =>This Inner Loop Header: Depth=1
    movzx   eax, byte ptr [rdx + r10]
    shl     rax, 4
    vpshufb xmm1, xmm0, xmmword ptr [r8 + rax]
    mov     eax, dword ptr [rcx + 4*r10]
    inc     r10
    add     rax, r9
    vmovdqu xmm0, xmmword ptr [rdi + rax]
    vmovdqu xmmword ptr [rdi + r9], xmm1
    mov     r9, rax
    cmp     rax, rsi
    jb      .LBB0_2
.LBB0_3:
    ret

LLVM-MCA 认为每次迭代大约需要 3.3 个周期，在我的 PC(4770K，使用 1、2、4 和 8 字节大小的元素的统一混合测试)上它有点慢，每次迭代接近 3.7 个周期，但就是这样仍然不错:每个元素不到 1.2 个周期。