poy*_*poy 1 c optimization simd bit-packing avx2
我需要从原始比特流中提取所有10位单词 ABACABACABAC...
它已经可以与天真的C实现一起使用，例如
for(uint8_t *ptr = in_packet; ptr < max; ptr += 5){
const uint64_t val =
(((uint64_t)(*(ptr + 4))) << 32) |
(((uint64_t)(*(ptr + 3))) << 24) |
(((uint64_t)(*(ptr + 2))) << 16) |
(((uint64_t)(*(ptr + 1))) << 8) |
(((uint64_t)(*(ptr + 0))) << 0) ;
*a_ptr++ = (val >> 0);
*b_ptr++ = (val >> 10);
*a_ptr++ = (val >> 20);
*c_ptr++ = (val >> 30);
}
但是性能对于我的应用程序来说是不够的，因此我想使用一些AVX2优化来改善它。
我访问了网站https://software.intel.com/sites/landingpage/IntrinsicsGuide/#，以找到可以提供帮助的任何功能，但似乎没有任何功能可用于10位字，只有8位或16位字。这似乎是合乎逻辑的，因为10位不是处理器固有的，但对我来说却很难。
有什么方法可以使用AVX2解决此问题？
标量循环无法有效地编译。编译器将其作为5个单独的字节加载来执行。您可以使用memcpy以下命令在C ++中表示未对齐的8字节负载：
#include <stdint.h>
#include <string.h>
// do an 8-byte load that spans the 5 bytes we want
// clang auto-vectorizes using an AVX2 gather for 4 qwords. Looks pretty clunky but not terrible
void extract_10bit_fields_v2calar(const uint8_t *__restrict src,
uint16_t *__restrict a_ptr, uint16_t *__restrict b_ptr, uint16_t *__restrict c_ptr,
const uint8_t *max)
{
for(const uint8_t *ptr = src; ptr < max; ptr += 5){
uint64_t val;
memcpy(&val, ptr, sizeof(val));
const unsigned mask = (1U<<10) - 1; // unused in original source!?!
*a_ptr++ = (val >> 0) & mask;
*b_ptr++ = (val >> 10) & mask;
*a_ptr++ = (val >> 20) & mask;
*c_ptr++ = (val >> 30) & mask;
}
}
ICC和clang自动矢量化您的1字节版本，但是做得很糟糕（很多单字节的插入/提取）。这是您的原始内容，以及Godbolt上的此功能（带有gcc和clang -O3 -march=skylake）
这三个编译器都没有真正接近我们可以手动完成的工作。
我当前的这个答案的AVX2版本忘记了一个细节：只有3种字段ABAC，而不是像10位RGBA像素那样的ABCD。因此，我有一个这样的版本，可以解压缩为4个单独的输出流（如果我为ABAC交织添加专用版本，则将由于打包的RGBA用例而将其保留）。
现有版本可用于vpunpcklwd交错两个A部分，而不是单独存储vmovq应适用于您的情况。IDK可能会更有效。
顺便说一句，我发现记住和键入指令助记符而不是固有名称更容易。英特尔在线内在函数指南可通过指令助记符进行搜索。
每个字段跨越一个字节边界，从不跨越两个边界，因此可以在一个包含4个完整字段的qword中组合任意4对字节。
或使用字节混洗来创建2字节的字，每个字在偏移处具有整个字段。（例如，用于AVX512BWvpsrlvw，或用于AVX2 2倍vpsrld。+字共混物），如AVX512甲字洗牌vpermw将不足够：个别字节需要与一个场的开始和结束的另一个被复制。也就是说，源位置并不是全部对齐的单词，尤其是当向量的相同16字节“通道”内有2x 5字节时。
00-07|08-15|16-23|24-31|32-39 byte boundaries (8-bit)
00...09|10..19|20...29|30..39 field boundaries (10-bit)
幸运的是，8和10的GCD为2，即> = 10-8 = 2。8 * 5 = 4 * 10，因此我们无法获得所有可能的开始位置，例如，永远不会有从1个字节的最后一位开始，跨越另一个字节并包括第3个字节的第一位的字段。
可能的AVX2策略：未对齐的32字节负载，在低通道顶部保留2x 5字节，在高通道底部保留2x 5字节。 然后vpshufb在车道内随机播放以设置2 vpsrlvd倍可变计数的班次和混合。
我尚未扩展新想法的快速摘要。
给定xxx a0B0A0C0 a1B1A1C1 | a2B2A2C2 a3B3A3C3来自我们未调整负载的输入，我们可以通过
a0 A0 a1 A1 B0 B1 C0 C1 | a2 A2 a3 A3 B2 B3 C2 C3正确选择vpshufb控制来获得结果。
然后，vpermd可以把所有那些32比特组的成正确的顺序，与所有的A在上半部（准备好一个元件vextracti128到存储器），以及B和C处于低一半（准备好vmovq/ vmovhps存储）。
vpermd对相邻的对使用不同的混洗，以便我们可以vpblendd将它们合并为128位B并C存储。
旧版本，可能比未对齐的load + vpshufb更糟糕。
使用AVX2时，一种选择是将包含64位的元素广播到向量中的所有位置，然后使用可变计数右移将这些位放到dword元素的底部。
您可能希望为每个组执行一个单独的64位广播负载（因此与前一组部分重叠），而不是尝试分离出一个__m256i连续的位。（广播负载便宜，混洗很昂贵。）
之后_mm256_srlvd_epi64，再进行AND运算以隔离每个qword中的低10位。
对于4个输入向量，重复该4次，然后使用_mm256_packus_epi32in-lane打包，先压缩到32位然后再压缩到16位元素。
那是简单的版本。交织的优化是可能的，例如通过使用向左或向右转移到设置为vpblendd代替像一个2输入洗牌vpackusdw或vshufps。 _mm256_blend_epi32在任何端口上运行的现有CPU上非常高效。
这也可以将AND延迟到第一个打包步骤之后，因为我们不需要避免高垃圾造成的饱和。
设计注意事项：
shown as 32-bit chunks after variable-count shifts
[0 d0 0 c0 | 0 b0 0 a0] # after an AND mask
[0 d1 0 c1 | 0 b1 0 a1]
[0 d1 0 c1 0 d0 0 c0 | 0 b1 0 a1 0 b0 0 a0] # vpackusdw
shown as 16-bit elements but actually the same as what vshufps can do
---------
[X d0 X c0 | X b0 X a0] even the top element is only garbage right shifted by 30, not quite zero
[X d1 X c1 | X b1 X a1]
[d1 c1 d0 c0 | b1 a1 b0 a0 ] vshufps (can't do d1 d0 c1 c0 unfortunately)
---------
[X d0 X c0 | X b0 X a0] variable-count >> qword
[d1 X c1 X | b1 X a1 0] variable-count << qword
[d1 d0 c1 c0 | b1 b0 a1 a0] vpblendd
最后一个技巧扩展到vpblendw，使我们能够使用交织混合来完成所有操作，根本没有洗牌指令，从而导致我们想要的输出是连续的，并且在a的qword中以正确的顺序排列__m256i。
对于所有元素，x86 SIMD可变计数移位只能是左移或右移，因此我们需要确保所有数据都在期望位置的左或右，而不是同一向量中的每个。我们可以使用立即计数移位来对此进行设置，但是更好的方法是只调整从中加载的字节地址。对于第一个位之后的加载，我们知道在想要的第一个位域之前加载一些字节是安全的（不触及未映射的页面）。
# as 16-bit elements
[X X X d0 X X X c0 | ...] variable-count >> qword
[X X d1 X X X c1 X | ...] variable-count >> qword from an offset load that started with the 5 bytes we want all to the left of these positions
[X d2 X X X c2 X X | ...] variable-count << qword
[d3 X X X c3 X X X | ...] variable-count << qword
[X d2 X d0 X c2 X c0 | ...] vpblendd
[d3 X d1 X c3 X c1 X | ...] vpblendd
[d3 d2 d1 d0 c3 c2 c1 c0 | ...] vpblendw (Same behaviour in both high and low lane)
Then mask off the high garbage inside each 16-bit word
注意：这会执行4个单独的输出，例如ABCD或RGBA-> planar，而不是ABAC。
// potentially unaligned 64-bit broadcast-load, hopefully vpbroadcastq. (clang: yes, gcc: no)
// defeats gcc/clang folding it into an AVX512 broadcast memory source
// but vpsllvq's ymm/mem operand is the shift count, not data
static inline
__m256i bcast_load64(const uint8_t *p) {
// hopefully safe with strict-aliasing since the deref is inside an intrinsic?
__m256i bcast = _mm256_castpd_si256( _mm256_broadcast_sd( (const double*)p ) );
return bcast;
}
// UNTESTED
// unpack 10-bit fields from 4x 40-bit chunks into 16-bit dst arrays
// overreads past the end of the last chunk by 1 byte
// for ABCD repeating, not ABAC, e.g. packed 10-bit RGBA
void extract_10bit_fields_4output(const uint8_t *__restrict src,
uint16_t *__restrict da, uint16_t *__restrict db, uint16_t *__restrict dc, uint16_t *__restrict dd,
const uint8_t *max)
{
// FIXME: cleanup loop for non-whole-vectors at the end
while( src<max ){
__m256i bcast = bcast_load64(src); // data we want is from bits [0 to 39], last starting at 30
__m256i ext0 = _mm256_srlv_epi64(bcast, _mm256_set_epi64x(30, 20, 10, 0)); // place at bottome of each qword
bcast = bcast_load64(src+5-2); // data we want is from bits [16 to 55], last starting at 30+16 = 46
__m256i ext1 = _mm256_srlv_epi64(bcast, _mm256_set_epi64x(30, 20, 10, 0)); // place it at bit 16 in each qword element
bcast = bcast_load64(src+10); // data we want is from bits [0 to 39]
__m256i ext2 = _mm256_sllv_epi64(bcast, _mm256_set_epi64x(2, 12, 22, 32)); // place it at bit 32 in each qword element
bcast = bcast_load64(src+15-2); // data we want is from bits [16 to 55], last field starting at 46
__m256i ext3 = _mm256_sllv_epi64(bcast, _mm256_set_epi64x(2, 12, 22, 32)); // place it at bit 48 in each qword element
__m256i blend20 = _mm256_blend_epi32(ext0, ext2, 0b10101010); // X d2 X d0 X c2 X c0 | X b2 ...
__m256i blend31 = _mm256_blend_epi32(ext1, ext3, 0b10101010); // d3 X d1 X c3 X c1 X | b3 X ...
__m256i blend3210 = _mm256_blend_epi16(blend20, blend31, 0b10101010); // d3 d2 d1 d0 c3 c2 c1 c0
__m256i res = _mm256_and_si256(blend3210, _mm256_set1_epi16((1U<<10) - 1) );
__m128i lo = _mm256_castsi256_si128(res);
__m128i hi = _mm256_extracti128_si256(res, 1);
_mm_storel_epi64((__m128i*)da, lo); // movq store of the lowest 64 bits
_mm_storeh_pi((__m64*)db, _mm_castsi128_ps(lo)); // movhps store of the high half of the low 128. Efficient: no shuffle uop needed on Intel CPUs
_mm_storel_epi64((__m128i*)dc, hi);
_mm_storeh_pi((__m64*)dd, _mm_castsi128_ps(hi)); // clang pessmizes this to vpextrq :(
da += 4;
db += 4;
dc += 4;
dd += 4;
src += 4*5;
}
}
这个编译（Godbolt）在每4组4个字段的循环约21前端微指令（上SKYLAKE微架构）。（包括一个无用的寄存器副本，_mm256_castsi256_si128而不是仅使用ymm0 = xmm0的下半部分）。这在Skylake上会非常好。不同端口上的微指令之间有很好的平衡，而SKL上p0或p1的可变计数移位为1微微指令（而以前价格更高）。瓶颈可能只是每个时钟4个融合域uops的前端限制。
由于未对齐的负载有时会越过64字节的缓存行边界，因此会发生缓存行拆分负载的重放。但这只是在后端，由于前端瓶颈（端口2和3的结果集有4个负载和4个存储，因此索引存储不能使用端口7），因此在端口2和3上我们有一些备用周期）。如果还必须重播依赖的ALU运维，我们可能会开始看到后端瓶颈。
尽管具有索引寻址模式，但不会分层，因为Haswell及其以后可以使索引存储保持微融合，并且广播负载仍然是单个纯uop，而不是微融合ALU +负载。
如果内存带宽不是瓶颈，在Skylake上，每5个时钟周期它可能接近4个40位组。（例如，具有良好的缓存阻塞。）一旦考虑了开销和缓存线分割负载导致偶尔的停顿的成本，在Skylake上，每40位输入可能需要1.5个周期，即每20个字节输入需要6个周期。
在其他CPU（Haswell和Ryzen）上，可变计数移位将成为瓶颈，但是您对此无能为力。我认为没有比这更好的了。在HSW上为3 oups：p5 + 2p0。在Ryzen上，它只有1个uop，但是每2个时钟吞吐量（对于128位版本）只有1个，对于256位版本（每2个时钟）只有4个时钟。
当心叮当声将_mm_storeh_pi商店贬值至vpextrq [mem], xmm, 1：2 uops ，随机播放+商店。（而不是vmovhps：Intel上的纯存储，没有ALU）。GCC按照书面形式进行编译。
我使用了_mm256_broadcast_sd即使我真的vpbroadcastq只是因为有一个使用指针操作数而不是指针的内在函数__m256i（因为对于AVX1，仅存在内存源版本。但是对于AVX2，存在所有广播指令的寄存器源版本）。要使用_mm256_set1_epi64，我必须编写不违反严格别名（例如，使用memcpy）的纯C语言来执行未对齐的uint64_t加载。不过，我认为在当前CPU上使用FP广播负载不会影响性能。
我希望_mm256_broadcast_sd允许其源操作数对任何别名都进行别名，而无需C ++严格混淆未定义的行为，就像这样_mm256_loadu_ps做一样。无论哪种方式，如果它没有内联到存储到中的函数中，*src甚至在那时，它都会在实践中起作用。因此，也许一个零散的未对齐负载会更有意义！
过去，让编译器pmovzxdw xmm0, [mem]从类似的代码中发出代码时，我取得了不好的结果_mm_cvtepu16_epi32( _mm_loadu_si64(ptr) )。您通常会得到实际的movq负载+ reg-reg pmovzx。这就是为什么我没有尝试的原因_mm256_broadcastq_epi64(__m128i)。
旧思想；如果我们已经需要字节改组，我们不妨使用普通字移位而不是vpmultishift。
使用AVX512VBMI（IceLake，CannonLake），您可能需要vpmultishiftqb。不必一次广播/移动一组，而是可以先将正确的字节放在正确的位置后，再对整个组的向量进行所有工作。
对于带有某些AVX512但没有AVX512VBMI的CPU（例如Skylake-avx512），您仍然需要/想要一个版本。大概vpermd+ vpshufb可以将所需的字节放入所需的128位通道中。
我认为我们不能仅使用dword粒度移动来允许合并屏蔽而不是在qword移位后进行dword混合。我们也许可以合并蒙版vpblendw，保存一个vpblendd
IceLake具有1个时钟vpermw和1个vpermb单时钟。（它在另一个端口上有一个第二混洗单元，可以处理一些混洗uops）。因此，我们可以加载包含4或8组4个元素的完整向量，并有效地将每个字节随机排列。我认为每个vpermb具有单CPU的CPU 。（但这只是冰湖和限量发行的坎农湖）。
vpermt2w（将2个向量中的16位元素组合成任意顺序）是每2个时钟吞吐量之一。（适用于IceLake-Y的InstLatx64），因此不幸的是，它的效率不如单矢量随机播放。
无论如何，您可以这样使用它：