有效地移位或大位向量

Question

我有一个大的内存数组作为一些指针uint64_t * arr（加上大小），它代表普通位。我需要非常有效（性能最高/速度最快）将这些位从 0 向右移动一定量到 63。

通过移动整个数组，我的意思是不移动每个元素（如a[i] <<= Shift），而是将其作为单个大位向量移动。换句话说，对于每个中间位置i（第一个和最后一个元素除外），我可以在循环中执行以下操作：

dst[i] = w | (src[i] << Shift);
w = src[i] >> (64 - Shift);

其中w是一些临时变量，保存前一个数组元素的右移值。

上面这个解决方案简单明了。但我需要更高效的东西，因为我有千兆字节的数据。

理想情况下，为此使用一些 SIMD 指令，因此我正在寻找专家的 SIMD 建议。我需要为所有四种类型的流行指令集实现移位代码 - SSE-SSE4.2 / AVX / AVX-2 / AVX-512。

但据我所知，例如 SSE2 只存在_mm_slli_si128()内在/指令，它仅移位 8 的倍数（换句话说，字节移位）。我需要按任意位大小进行移位，而不仅仅是字节移位。

如果没有 SIMD，我也可以通过 using 指令一次移位 128 位shld reg, reg, reg，这允许进行 128 位移位。它在 MSVC 中作为内部__shiftleft128()实现，并生成可以在此处看到的汇编代码。

顺便说一句，我需要所有 MSVC/GCC/CLang 的解决方案。

另外，在单循环迭代中，我可以在顺序操作中移位 4 或 8 个字，这将使用 CPU 流水线来加速多个指令的并行无序执行。

如果需要，我的位向量可以与内存中的任意数量的字节对齐，如果这有助于通过对齐读/写来提高 SIMD 速度等。源和目标位向量内存也不同（不重叠）。

换句话说，我正在寻找有关如何在不同的英特尔 CPU 上最有效（最具性能）地解决我的任务的所有建议。

请注意，为了澄清，我实际上必须进行多次换班或操作，而不仅仅是单次换班。我有大的位向量X和数百个移位大小s0, s1, ..., sN，其中每个移位大小都不同并且也可以很大（例如移位 100K 位），然后我想计算结果大位向量Y = (X << s0) | (X << s1) | ... | (X << sN)。我只是将 StackOverflow 的问题简化为移动单个向量。但关于原始任务的这个细节可能非常重要。

根据 @Jake'Alquimista'LEE 的要求，我决定实现一个现成的玩具最小可重复示例，即计算输入位向量的移位或src以生成或运算的最终dst位向量。这个例子根本没有优化，只是我的任务如何解决的一个简单的变体。为简单起见，此示例的输入向量较小，而不是像我的情况那样为千兆字节。这是一个玩具示例，我没有检查它是否正确解决任务，它可能包含小错误：

在线尝试一下！

dst[i] = w | (src[i] << Shift);
w = src[i] >> (64 - Shift);

我真实项目的当前代码与上面的玩具示例不同。该项目已经正确解决了现实世界的任务。我只需要做额外的优化。我已经做了一些优化，例如用于OpenMP在所有核心上并行化移位或操作。另外，正如评论中所述，我为每个移位大小创建了专门的模板函数，总共 64 个函数，并选择 64 个函数之一来执行实际的移位或操作。每个 C++ 函数都有移位大小的编译时值，因此编译器会考虑编译时值进行额外的优化。

Answer 1

您可以，甚至可能不需要显式使用 SIMD 指令。目标编译器 GCC、CLANG 和 MSVC 以及其他编译器（如 ICC）都支持自动向量化。虽然手动优化的汇编可以胜过编译器生成的向量化指令，但它通常更难实现，并且您可能需要针对不同体系结构的多个版本。产生高效自动向量化指令的通用代码是一种可以跨多个平台移植的解决方案。

例如一个简单的shiftvec版本

void shiftvec(uint64_t* dst, uint64_t* src, int size, int shift)
{
    for (int i = 0; i < size; ++i,++src,++dst)
    {
        *dst = ((*src)<<shift) | (*(src+1)>>(64-shift));
    }
}

使用最新的 GCC（或 CLANG 也可以）编译，并-O3 -std=c++11 -mavx2在汇编的核心循环中生成 SIMD 指令

.L5:
  vmovdqu ymm4, YMMWORD PTR [rsi+rax]
  vmovdqu ymm5, YMMWORD PTR [rsi+8+rax]
  vpsllq ymm0, ymm4, xmm2
  vpsrlq ymm1, ymm5, xmm3
  vpor ymm0, ymm0, ymm1
  vmovdqu YMMWORD PTR [rdi+rax], ymm0
  add rax, 32
  cmp rax, rdx
  jne .L5

请参阅godbolt.org：https://godbolt.org/z/5TxhqMhnK

如果您想在 dst 中组合多个班次，这也适用：

void shiftvec2(uint64_t* dst, uint64_t* src1, uint64_t* src2, int size1, int size2, int shift1, int shift2)
{
    int size = size1<size2 ? size1 : size2;
    for (int i = 0; i < size; ++i,++src1,++src2,++dst)
    {
        *dst = ((*src1)<<shift1) | (*(src1+1)>>(64-shift1));
        *dst |= ((*src2)<<shift2) | (*(src2+1)>>(64-shift2)); 
    }
    for (int i = size; i < size1; ++i,++src1,++dst)
    {
        *dst = ((*src1)<<shift1) | (*(src1+1)>>(64-shift1));        
    }
    for (int i = size; i < size2; ++i,++src2,++dst)
    {
        *dst = ((*src2)<<shift2) | (*(src2+1)>>(64-shift2));
    }
}

编译为核心循环：

.L38:
  vmovdqu ymm7, YMMWORD PTR [rsi+rcx]
  vpsllq ymm1, ymm7, xmm4
  vmovdqu ymm7, YMMWORD PTR [rsi+8+rcx]
  vpsrlq ymm0, ymm7, xmm6
  vpor ymm1, ymm1, ymm0
  vmovdqu YMMWORD PTR [rax+rcx], ymm1
  vmovdqu ymm7, YMMWORD PTR [rdx+rcx]
  vpsllq ymm0, ymm7, xmm3
  vmovdqu ymm7, YMMWORD PTR [rdx+8+rcx]
  vpsrlq ymm2, ymm7, xmm5
  vpor ymm0, ymm0, ymm2
  vpor ymm0, ymm0, ymm1
  vmovdqu YMMWORD PTR [rax+rcx], ymm0
  add rcx, 32
  cmp r10, rcx
  jne .L38

在一个循环中组合多个源将减少加载/写入目标所花费的内存带宽总量。当然，可以组合的数量受到可用寄存器的限制。请注意，xmm2和xmm3forshiftvec包含移位值，因此对于编译时已知移位值具有不同版本可能会释放这些寄存器。

另外，对每个指针使用__restrict（受 GCC、CLANG、MSVC 支持）将告诉编译器范围不重叠。

我最初在 MSVC 提供正确的自动向量化代码方面遇到了问题，但似乎添加更多类似 SIMD 的结构将使其适用于所有三个所需的编译器 GCC、CLANG 和 MSVC：

void shiftvec(uint64_t* __restrict dst, const uint64_t* __restrict src, int size, int shift)
{
    int i = 0;
    // MSVC: use steps of 2 for SSE, 4 for AVX2, 8 for AVX512
    for (; i+4 < size; i+=4,dst+=4,src+=4)
    {
        for (int j = 0; j < 4; ++j)
            *(dst+j) = (*(src+j))<<shift;
        for (int j = 0; j < 4; ++j)
            *(dst+j) |= (*(src+1)>>(64-shift));
    }
    for (; i < size; ++i,++src,++dst)
    {
        *dst = ((*src)<<shift) | (*(src+1)>>(64-shift));
    }    
}