交换内存中未对齐的 64 位值的字节的最快方法是什么？
What is the fastest way to swap the bytes of an unaligned 64 bit value in memory?
我的内存中有大量的 64 位值。不幸的是，它们可能不会与 64 位地址对齐。我的目标是更改所有这些值的字节序，即 swapping/reversing 它们的字节。
我知道 bswap 指令可以交换 32 位或 64 位寄存器的字节。但由于它需要一个寄存器参数，我无法将我的内存地址传递给它。当然我可以先把内存加载到寄存器，然后swap，再写回去：
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：我的真实情况比较复杂。我确实有一个大字节数组，但它包含不同大小的整数，而且都是密集排列的。其他一些数组告诉我接下来期望的整数大小。所以这个 "description" 可以说 "one 32 bit int, two 64 bit ints, one 16 bit int, then one 64 bit int again"。我在这里提到这个只是为了告诉你（据我所知），使用 SIMD 指令是不可能的，因为我实际上必须在读取之前检查每个整数的大小。
What is the fastest way to byte swap a 64 bit value in memory?
mov/bswap/mov 版本和 movbe/mov 在大多数 Intel 处理器上大致相同。根据 µop 计数，似乎 movbe 解码为 mov + bswap，Atom 除外。对于 Ryzen，movbe 可能更好。手动交换字节要慢得多，除非在某些边缘情况下大 load/store 非常慢，例如当它跨越 Skylake 之前的 4K 边界时。
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 和由 "size pattern" 索引的洗牌掩码的 table，例如一个 8 位整数，其中每 2 位表示大小的一个元素。 pshufb 然后反转它正在查看的 16 字节 window 中完全包含的元素，并保留其余部分（尾部未更改的字节也会被写回，但没关系） .然后我们按实际处理的字节数前进。
为了最大程度的方便，这些大小模式（以及相应的字节数）应该以这样一种方式提供，即实际的 Endianness Flipper 本身可以在每次迭代中恰好使用其中一个，而没有任何沉重的东西，例如 提取 一个字节未对齐的 8 位序列并动态确定要消耗多少位。这也是可能的，但成本要高得多。在我的测试中慢了大约 4 倍，受到从 "extract 8 bits at current bit-index" 到 "find bit-index increment by table lookup" 的循环携带依赖性的限制，然后进入下一次迭代：每次迭代大约 16 个周期，尽管仍然有 60% 的时间是等效的标量代码。
使用未打包的（每个大小 1 个字节）表示会使提取更容易（只是一个未对齐的双字加载），但需要打包结果以索引混洗掩码 table，例如 pext。这对于 Intel CPU 来说是合理的，但是 pext 在 AMD Ryzen 上非常慢。对 AMD 和 Intel 都适用的替代方法是读取未对齐的双字，然后使用 multiply/shift 技巧提取 8 个有趣的位：
mov eax, [rdi]
imul eax, eax, 0x01041040
shr eax, 24
至少在方便输入的情况下应该使用一个额外的技巧（否则无论如何我们都会遇到 5 倍更差的性能并且这个技巧将不相关），正在读取下一次迭代的数据before 存储当前迭代的结果。如果没有这个技巧，存储通常会 "step on the toes" 下一次迭代的负载（因为我们前进不到 16 个字节，所以负载读取存储保持不变但无论如何都必须写入的一些字节），迫使它们之间的内存依赖关系会阻止下一次迭代。性能差异较大，大约是 3x。
那么 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 个周期。
我的内存中有大量的 64 位值。不幸的是，它们可能不会与 64 位地址对齐。我的目标是更改所有这些值的字节序，即 swapping/reversing 它们的字节。
我知道 bswap 指令可以交换 32 位或 64 位寄存器的字节。但由于它需要一个寄存器参数，我无法将我的内存地址传递给它。当然我可以先把内存加载到寄存器，然后swap，再写回去：
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：我的真实情况比较复杂。我确实有一个大字节数组，但它包含不同大小的整数，而且都是密集排列的。其他一些数组告诉我接下来期望的整数大小。所以这个 "description" 可以说 "one 32 bit int, two 64 bit ints, one 16 bit int, then one 64 bit int again"。我在这里提到这个只是为了告诉你（据我所知），使用 SIMD 指令是不可能的，因为我实际上必须在读取之前检查每个整数的大小。
What is the fastest way to byte swap a 64 bit value in memory?
mov/bswap/mov 版本和 movbe/mov 在大多数 Intel 处理器上大致相同。根据 µop 计数，似乎 movbe 解码为 mov + bswap，Atom 除外。对于 Ryzen，movbe 可能更好。手动交换字节要慢得多，除非在某些边缘情况下大 load/store 非常慢，例如当它跨越 Skylake 之前的 4K 边界时。
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 和由 "size pattern" 索引的洗牌掩码的 table，例如一个 8 位整数，其中每 2 位表示大小的一个元素。 pshufb 然后反转它正在查看的 16 字节 window 中完全包含的元素，并保留其余部分（尾部未更改的字节也会被写回，但没关系） .然后我们按实际处理的字节数前进。
为了最大程度的方便，这些大小模式（以及相应的字节数）应该以这样一种方式提供，即实际的 Endianness Flipper 本身可以在每次迭代中恰好使用其中一个，而没有任何沉重的东西，例如 提取 一个字节未对齐的 8 位序列并动态确定要消耗多少位。这也是可能的，但成本要高得多。在我的测试中慢了大约 4 倍，受到从 "extract 8 bits at current bit-index" 到 "find bit-index increment by table lookup" 的循环携带依赖性的限制，然后进入下一次迭代：每次迭代大约 16 个周期，尽管仍然有 60% 的时间是等效的标量代码。
使用未打包的（每个大小 1 个字节）表示会使提取更容易（只是一个未对齐的双字加载），但需要打包结果以索引混洗掩码 table，例如 pext。这对于 Intel CPU 来说是合理的，但是 pext 在 AMD Ryzen 上非常慢。对 AMD 和 Intel 都适用的替代方法是读取未对齐的双字，然后使用 multiply/shift 技巧提取 8 个有趣的位：
mov eax, [rdi]
imul eax, eax, 0x01041040
shr eax, 24
至少在方便输入的情况下应该使用一个额外的技巧（否则无论如何我们都会遇到 5 倍更差的性能并且这个技巧将不相关），正在读取下一次迭代的数据before 存储当前迭代的结果。如果没有这个技巧，存储通常会 "step on the toes" 下一次迭代的负载（因为我们前进不到 16 个字节，所以负载读取存储保持不变但无论如何都必须写入的一些字节），迫使它们之间的内存依赖关系会阻止下一次迭代。性能差异较大，大约是 3x。
那么 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 个周期。