我有一个大型的内存数组，表示为某些指针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，只存在可移位8的倍数（换句话说是字节移位）的_mm_slli_si128() 内嵌/指令。我需要任意位大小的移位，而不仅仅是字节移位。
如果没有SIMD，我也可以通过使用shld reg，reg，reg 指令一次性移位128位来实现，该指令允许进行128位移位。在MSVC中，它以内嵌形式__shiftleft128()实现，并生成汇编代码，可以在此处查看。
顺便说一下，我需要解决MSVC / GCC / CLang的所有问题。
此外，在单个循环迭代内，我可以通过连续操作移位4或8个字，利用CPU流水线加速并行无序执行多个指令。
如果需要，我的位向量可以对齐到内存中的任意字节数，如果这将有助于通过进行对齐读写来提高SIMD的速度。此外源和目标位向量内存是不同的（非重叠）。
换句话说，我正在寻找有关如何在不同的Intel CPU上最有效地解决我的任务的所有建议（最高效）。
注意，为了澄清，实际上我必须执行多个移位或运算，而不仅仅是单个移位。我有一个大的位向量X，以及若干个移位大小s0，s1，...，sN，其中每个移位大小都不同，也可能很大（例如100K位的移位），然后我想计算出结果大的位向量Y = (X << s0) | (X << s1) | ... | (X << sN)。我只是将我的问题简化为堆栈溢出以移动单个向量。但这个关于原始任务的细节可能非常重要。
src的移位或结果并生成dst位向量。该示例未进行任何优化，只是如何解决我的任务的简单直接变体。为了简单起见，此示例的输入向量大小很小，而不是像我的情况那样以千兆字节为单位。这是一个玩具示例，我没有检查它是否正确解决了任务，可能包含轻微的错误：在此在线尝试！
#include <cstdint>
#include <vector>
#include <random>
#define bit_sizeof(x) (sizeof(x) * 8)
using u64 = uint64_t;
using T = u64;
int main() {
std::mt19937_64 rng{123};
// Random generate source bit vector
std::vector<T> src(100'000);
for (size_t i = 0; i < src.size(); ++i)
src[i] = rng();
size_t const src_bitsize = src.size() * bit_sizeof(T);
// Destination bit vector, for example twice bigger in size
std::vector<T> dst(src.size() * 2);
// Random generate shifts
std::vector<u64> shifts(200);
for (size_t i = 0; i < shifts.size(); ++i)
shifts[i] = rng() % src_bitsize;
// Right-shift that handles overflow
auto Shr = [](auto x, size_t s) {
return s >= bit_sizeof(x) ? 0 : (x >> s);
};
// Do actual Shift-Ors
for (auto orig_shift: shifts) {
size_t const
word_off = orig_shift / bit_sizeof(T),
bit_off = orig_shift % bit_sizeof(T);
if (word_off >= dst.size())
continue;
size_t const
lim = std::min(src.size(), dst.size() - word_off);
T w = 0;
for (size_t i = 0; i < lim; ++i) {
dst[word_off + i] |= w | (src[i] << bit_off);
w = Shr(src[i], bit_sizeof(T) - bit_off);
}
// Special case of handling for last word
if (word_off + lim < dst.size())
dst[word_off + lim] |= w;
}
}
我的真实项目的当前代码与上面的玩具示例不同。这个项目已经正确地解决了一个真实世界中的任务。我只需要进行额外的优化。我已经做了一些优化，比如使用OpenMP在所有核心上并行化shift-or操作。另外，正如评论中所说，我为每个移位大小创建了专门的模板函数，共计64个函数，并选择其中一个函数来执行实际的shift-or操作。每个C++函数都有编译时值的移位大小，因此编译器会根据编译时值进行额外的优化。
Y = (X << s0) | (X << s1) | ... | (X << sN)，其中X是大型输入位向量，Y是大型输出位向量，而s0, ..., sN是从 0 到 1M 的一百个移位大小。我在两个循环中进行这个计算，外部循环遍历所有的sK，内部循环执行实际的移位或操作，就像我在问题开头展示的代码中所示。除此之外没有别的了。这不是最优解决方案。因此，我正在寻求所有关于如何优化它的建议。 - Arty__builtin_assume_aligned。 - Marc Stevens