我有一个大型的内存数组,表示为某些指针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