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 指令是不可能的，因为我实际上必须在阅读之前检查每个整数的大小。

标签： performanceassemblyx86-64endiannessmicro-optimization

Answer 1

在内存中对 64 位值进行字节交换的最快方法是什么？

大多数英特尔处理器上的mov/bswap/mov版本和版本movbe/mov大致相同。根据 µop 计数，它似乎movbe解码为mov + bswap，但在 Atom 上除外。对于锐龙，movbe可能会更好。手动交换字节要慢得多，除非在某些边缘情况下，大型加载/存储非常慢，例如当它跨越 Skylake 之前的 4K 边界时。

pshufb即使是替换单个bswap, 也是一个合理的选择，尽管这浪费了 shuffle 可以做的一半工作。

---

PS：我的真实情况有点复杂。我确实有一个大字节数组，但它包含不同大小的整数，而且都是密集的。

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

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

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

使用未打包（每个大小 1 个字节）表示将使提取更容易（只是未对齐的 dword 加载），但需要打包结果以使用例如pext. 这对于 Intel CPU 来说是合理的，但pext在 AMD Ryzen 上却非常慢。对 AMD 和 Intel 都适用的另一种方法是读取未对齐的 dword，然后使用乘法/移位技巧提取 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;
    }
}

例如，Clang 10 with-O3 -march=haswell将其变为

    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 个周期。