在内存中交换未对齐的 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

\n

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

\n

\n\n

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

\n\n

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

\n\n\n\n

\n

PS：我的实际情况有点复杂。我确实有一个大字节数组，但它包含不同大小的整数，并且全部密集排列。

\n

\n\n

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

\n\n

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

\n\n

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

\n\n

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

\n\n

mov eax, [rdi]\nimul eax, eax, 0x01041040\nshr eax, 24\n

\n\n

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

\n\n

那么 Endianness Flipper 可能看起来像这样：

\n\n

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

\n\n

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

\n\n

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

\n\n

LLVM-MCA 认为每次迭代大约需要 3.3 个周期，在我的 PC（4770K，使用 1、2、4 和 8 字节大小元素的统一混合进行测试）上，它有点慢，每次迭代接近 3.7 个周期，但是仍然不错：每个元素的周期略低于 1.2 个周期。

\n