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

Question

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

我知道bswap指令交换32位或64位寄存器的字节。但由于它需要一个register参数，我无法将内存地址传递给它。当然，我可以先将内存加载到寄存器中，然后交换，然后再写回：

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位int，两个64位int，一个16位int，然后再一个64位int”。我在这里提到这个只是为了告诉你（据我所知），使用SIMD指令是不可能的，因为我实际上必须在阅读之前检查每个整数的大小。

Answer 1

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

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

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

附言：我的实际情况有点复杂。我有一个大字节数组，但它包含大小不同的整数，都是密集的。

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

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

为方便起见，这些大小模式（以及相应的字节计数）的提供方式应确保实际的endpoint翻转器本身在每次迭代中可以使用其中一个模式，而无需任何繁重的操作，例如提取一个8位的字节未对齐序列，并动态确定要使用多少位。这也是可能的，但代价要高得多。在我的测试中，速度大约是原来的4倍，受循环相关性的限制，通过“在当前位索引中提取8位”通过“通过查表找到位索引增量”，然后进入下一个迭代：每个迭代大约16个周期，尽管仍然是等效标量代码所用时间的60%。

使用未打包（每个大小1个字节）表示将使提取更容易（只是未对齐的dword加载），但需要打包结果以索引无序掩码表，例如使用pext。这对于Intel CPU来说是合理的，但在AMD Ryzen上，pext的速度非常慢。对于AMD和Intel来说，另一种合适的方法是执行未对齐的dword读取，然后使用乘法/移位技巧提取8个有趣的位：

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

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

然后Endianness鳍状肢可以如下所示：

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;
    }
}

例如，将10与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个。