dav*_*erd 2 c++ sse bit-manipulation simd vectorization
我正在尝试编写 BSF 的矢量化实现作为练习，但我陷入困境，它不起作用。
算法：
short bitScanForward(int16_t bb)
{
constexpr uint16_t two = static_cast<uint16_t>(2);
constexpr uint16_t zero = static_cast<uint16_t>(0);
uint16_t lsb;
bb &= -bb;
lsb = (unsigned short)bb
| (unsigned short)(bb >> short(8));
return static_cast<short>(((((((unsigned short)(bb >>
short(8)) != zero) * two)
+ ((lsb & unsigned short(0xf0f0)) != zero)) * two)
+ ((lsb & unsigned short(0xcccc)) != zero)) * two)
+ ((lsb & unsigned short(0xaaaa)) != zero);
}
我的矢量代码：
[[nodiscard]] inline __m128i _mm_cmpneq_epi16(const __m128i& a, const __m128i& b) noexcept
{
const __m128i _NEG_ONE = _mm_set1_epi16(static_cast<int16_t>(-1));
__m128i _mask = _mm_setzero_si128();
_mask = _mm_cmpeq_epi16(a, b);
_mask = _mm_xor_si128(_mask, _NEG_ONE);//Not Equal
return _mask;
}//End of _mm_neq_epi16
[[nodiscard]] inline __m128i _mm_bsf_epi16(__m128i x) noexcept
{
__m128i _lsb = _mm_setzero_si128();
__m128i _temp1 = _mm_setzero_si128();
__m128i _temp2 = _mm_setzero_si128();
__m128i _result = _mm_setzero_si128();
const __m128i _zero = _mm_setzero_si128();
const __m128i _one = _mm_set1_epi16(static_cast<uint16_t>(1));
const __m128i _two = _mm_set1_epi16(static_cast<uint16_t>(2));
const __m128i _hex2 = _mm_set1_epi16(static_cast<uint16_t>(0xf0f0));
const __m128i _hex3 = _mm_set1_epi16(static_cast<uint16_t>(0xcccc));
const __m128i _hex4 = _mm_set1_epi16(static_cast<uint16_t>(0xaaaa));
x = _mm_and_si128(x, _mm_sub_epi16(_zero, x));
_lsb = _mm_or_si128(x, _mm_srli_epi16(x, 8));
_temp1 = _mm_mullo_epi16(_mm_abs_epi16(_mm_cmpneq_epi16(_mm_srli_epi16(x, 8), _zero)), _two);
_temp2 = _mm_abs_epi16(_mm_cmpneq_epi16(_mm_and_si128(_lsb, _hex2), _zero));
_result = _mm_add_epi16(_temp1, _temp2);
_result = _mm_mullo_epi16(_result, _two);
_temp1 = _mm_abs_epi16(_mm_cmpneq_epi16(_mm_and_si128(_lsb, _hex3), _zero));
_temp2 = _mm_abs_epi16(_mm_cmpneq_epi16(_mm_and_si128(_lsb, _hex4), _zero));
_result = _mm_add_epi16(_result, _temp1);
_result = _mm_add_epi16(_result, _temp2);
return _result;
}//End of _mm_bsf_epi16
这是我得到的 const 向量的结果：
-32,768 1000000000000000 bsf: 15
8,192 0010000000000000 bsf: 13
2,048 0000100000000000 bsf: 11
8,704 0010001000000000 bsf: 9
8,832 0010001010000000 bsf: 7
-24,544 1010000000100000 bsf: 5
-24,568 1010000000001000 bsf: 3
-8,190 1110000000000010 bsf: 1
好吧，我成功了，事实证明我严重误读了上面乱七八糟的括号，并且把算法搞乱了。
至于性能，该版本确实优于常见算法，例如：
x = x & -x;
if ((x & 0xff00ff00) != 0) index += 8;
if ((x & 0xf0f0f0f0) != 0) index += 4;
if ((x & 0xcccccccc) != 0) index += 2;
if ((x & 0xaaaaaaaa) != 0) index += 1;
return index;
x86 上没有用于 16 位整数的 BSF 指令。
我的 SIMD 版本需要 138 毫秒才能在 10 亿个 int16_t 上交换 ffs（使用多线程），而上面的另一个版本需要 374 毫秒（使用多线程）。
您选择的 SIMD BSF 策略效率不高。利用 CPU 可以作为单个指令执行的其他原始操作会更好。即使该策略的最佳情况实现也需要许多不同的掩码常量，以及每个向量的大量指令。
您选择使用*2with_mm_mullo_epi16而不是_mm_slli_epi16by 1 来实现是特别不幸的。（或者_mm_add_epi16(same,same)）。幸运的是，一些编译器会为您将常量优化mullo为 add，但整个策略仍然需要比必要的指令多得多的指令。但像 MSVC 和 ICC 这样的其他软件则相当字面地理解内在函数，并且实际上会使用硬件乘法，而其延迟相对较高。
有多种好的策略，最佳选择取决于 SIMD 元素宽度和可用 ISA 扩展级别（许多需要 SSSE3 pshufb）。实现细节中的一些微观优化可能取决于英特尔与 AMD 或同一供应商各代产品之间的微架构差异。
使用 AVX-512vpopcntb/w/d/q可用：(vpopcnt(~v & (v-1))
/ vpadd -1/ vpandn) vpopcnt，即制作一个掩码，直到但不包括最低设置位，然后对其进行 popcount。 ~v & (v-1)输入为零时给出全 1，因此它可以为 16 位输入产生 17 个不同的输出值，不需要任何修复即可完全工作0。
3 个说明，其中两个非常便宜。（并且在支持它的 CPUvpopcnt 、Ice Lake 及更高版本（Alder Lake 除外）和 Zen 4上价格便宜。AVX-512 VPOPCNTDQ 和 BITALG（对于黑白版本）。）如果在循环中使用它，Clang 会以这种方式进行矢量化。__tzcnt_u16
请注意，v ^ (v-1)要获得直到并包含类似标量的掩码blsmsk，就会计数太多，并且无法与;区分开0来。0x8000两者都产生0xffff.
带有 AVX-512 的 32 或 64 位元素：vplzcntd/q始终可用（所有 AVX-512 CPU 都有 AVX-512CD）。 tzcntd = 31-lzcntd(v&-v)对于非零输入。这会给你一个-1全零元素。（因此，如果您需要的话，最后一个vpminud(tz, set1(32))会将 UINT_MAX 限制为 32。）
具有 SSSE3 的 16 位元素：DeBruijn 序列相乘以生成 LUT 的 4 位值pshufb：非常好，特别是如果您不关心输入 = 0 的情况。此策略不适用于 32 位或 64 位元素，如果没有用于vpermb更广泛 LUT 的 AVX-512 VBMI，在这种情况下，您通常还会有vpopcnt.
每个向量 5 个单 uop 指令（使用 AVX），2 个向量常量。（或者 7 或 8 条指令，如果您想要完整的tzcnt行为，则生成16。input=0如果-1适合这种情况，则稍微便宜一些。）pmullw( _mm_mullo_epi16) 在现代 CPU 上是单微指令，与pmulld
我认为这个策略比 aqrit 将pshufb结果与pminub（9 个指令与 gcc 或 clang）相结合的聪明策略更好。
32 位元素：@Soonts 的 FP 策略非常好，特别是如果您只想假设 SSE2。转换为 FP 以利用执行此操作的硬件来计算指数字段。32 位是打包 SIMD int->float 转换的自然宽度。如果输入设置了 MSB，则必须处理设置的符号位，即and向下移动指数后的额外指令。
@aqrit 使用 2xpshufb作为原始整数的每个半字节的 4 位 LUT 的策略也很有趣，但我认为它需要额外的合并步骤，而 @Soonts 需要更少的步骤，不需要分割低/高并合并。
@aqrit 的 SSE2-only 策略_mm_avg_epu16(r, _mm_cmpeq_epi16(_mm_and_si128(x3333, v), x0000));看起来比 FP 策略慢，特别是对于 32 位，它需要更多的工作，但 FP 策略每个向量需要更少的工作。
64 位元素：打包 64 位整数 -> FP 转换在 AVX-512 之前不可用。Skylake-X 有 AVX-512，但没有 AVX-512VPOPCNTDQ。
即使没有直接支持 SIMD popcount，这个popcnt(~v & (v-1))想法也可能是好的。SIMD popcnt是已知技术，例如分成2x的低/高半字节vpshufb作为4位LUT。然后将_mm_add_epi8这些高/低半部分放在一起，并对qword 块内的字节进行psadbw求和0。
（这基本上就是 clang 自动矢量化的方式sum += __tzcnt_u16(arr[i])，即使没有 -march=icelake-client`，但也有一些浪费的洗牌和低效的求和。）
设置的最低有效位位置的答案可以适应 16 位，然后可以使用 SSSE3 对 8 位值的 16 项查找表进行矢量化pshufb。
De Bruijn 序列的每个4 位位模式都在某处重叠。将其乘以 2 的幂（单个位集）会将这些序列之一移至顶部n位，右移会将type_width - n它们移至底部。因此，我们在字节底部得到一个 4 位值，准备用作 LUT 索引。
SSE2pmullw在所有现代 CPU 上速度都很快，甚至 Alder Lake E 核也是如此。单 uop，尽管 P 核 Haswell/Skylake/Ice Lake 上的延迟为 5 个周期。但自 SKL 以来，它具有 2/时钟吞吐量，在端口 0 或 1 上运行。在 Zen 2 上也很快，例如，1/时钟吞吐量，3 个周期延迟。 https://uops.info/。
SIMD 整数移位 ( psrlw) 与 竞争相同的端口pmullw，但幸运的是，2/时钟吞吐量应该足以避免瓶颈。 pshufb在 Intel 的端口 5 上运行，不与 shift / pmul 竞争。
__m128i bsf_epi16_debruijn(__m128i v)
{
const __m128i debruijn_magic = _mm_set1_epi16( 0x09AF );
const __m128i bit_table = _mm_setr_epi8(
0, 1, 2, 5, 3, 9, 6, 11,
15, 4, 8, 10, 14, 7, 13, 12 );
__m128i blsi = _mm_sub_epi16(_mm_setzero_si128(), v);
blsi = _mm_and_si128(blsi, v); // v &= -v; a power of 2; multiplying by it is like a shift
__m128i idx = _mm_mullo_epi16(blsi, debruijn_magic);
idx = _mm_srli_epi16(idx, 12); // leaving a 4-bit index from the selected position in the DeBruijn sequence
// maybe TODO: avoid the shift with PMULHW with a debruijn sequence and table crafted to use the bits "shifted" into the high half?
// But then would need to mask before pshufb without AVX-512VBMI vpermb xmm
// And if we have that (Ice Lake) we normally have AVX-512 BITALG for vpopcntw(~v & (v-1)) or vpopcntw(pandn(v, v-1)) (vpaddw / vpandn)
__m128i bsf = _mm_shuffle_epi8(bit_table, idx); // high half of each word looks up to 0 so no fixup needed
// input = 0 produces output = 0, same as input=1, unless we fixup the result
#if 1
// optional: produce -1 or 16 for input==0, instead of 0
__m128i was_zero = _mm_cmpeq_epi16(v, _mm_setzero_si128());
//bsf = _mm_blendv_epi8(bsf, _mm_set1_epi16(16), was_zero); // single-uop on AMD, 2 uops on Intel; 3 on Alder Lake P and 4 on E cores. Single uop for the legacy SSE version, though.
// was_zero = _mm_and_si128(was_zero, _mm_set1_epi16(16));
bsf = _mm_or_si128(bsf, was_zero); // return -1 for v==0 . (Or with the &16, return 16
// alternative: bsf = _mm_sub_epi16(bsf, _mm_slli_epi16(was_zero,4)); // subtract (-1<<4) or (0). Avoids a constant.
#endif
return bsf;
}
我使用https://sites.google.com/site/sydfhd/articles-tutorials/de-bruijn-sequence-generator中的程序生成了 16 位 De Bruijn 序列和查找表，并通过注释掉修复了编译错误2 行涉及if，is_mulshift因为程序中未定义。还g++ -O2 -fpermissive可以消除其他警告。
Godbolt与这个，原来的，和（我的调整）Soonts 的答案，加上 aqrit 的答案。还有一个 clang 自动矢量化的标量循环。
bsf_epi16_debruijn(long long __vector(2)): # @bsf_epi16_debruijn(long long __vector(2))
vpxor xmm1, xmm1, xmm1 # constant can be hoisted out of loops
vpsubw xmm2, xmm1, xmm0
vpand xmm2, xmm2, xmm0
vpmullw xmm2, xmm2, xmmword ptr [rip + .LCPI5_0]
vpsrlw xmm2, xmm2, 12
vmovdqa xmm3, xmmword ptr [rip + .LCPI5_1] # xmm3 = [0,1,2,5,3,9,6,11,15,4,8,10,14,7,13,12]
vpshufb xmm2, xmm3, xmm2
vpcmpeqw xmm0, xmm0, xmm1 # fixup for v==0
vpor xmm0, xmm2, xmm0 # fixup for v==0
ret
因此，不计算将寄存器设置为常量的指令（因为可以使用 AVX 将这些指令提升出循环以允许非破坏性地使用它们），这是主要工作的 5 条指令。两个用于乘法/移位端口，两个可以在任何端口上运行的简单整数，以及一个英特尔 CPU 仅在端口 5 上运行的 shuffle。
对于此修复策略，还有 2 个说明，其中给出-1的元素是0，而不是0没有修复的输出 = 。（这就是为什么我们可以只进行 OR in 而不是 Even，vpblendvb即使我们想将其设置为 16，而不仅仅是设置为-1。 -1 | anything == -1因此，即使 LUT 对于输入 0 没有产生 0，这也是有效的。）
这很容易扩展到 256 位向量 (AVX2) 或 512 位向量 (AVX-512BW)。我还没有尝试将其写入标量来查看 GCC 或 clang 是否会自动矢量化移位和 LUT 查找；我并不乐观，但也不排除这种可能性。
x86 上没有用于 16 位整数的 BSF 指令。
不正确：bsf允许操作数大小为 16、32 或 64 位。BMI1 也相同tzcnt。 BSF 的内在函数和内置函数在编译器之间没有很好地标准化（据我所知，没有 16 位的内在函数bsf），但英特尔确实记录了_tzcnt_u16. GCC 只支持__tzcnt_u16（两个前导下划线），不支持 Intel 的名称，但 clang 支持这两个名称（一个和两个下划线）。
没关系; bsf零输入会产生垃圾值（它的内在特性不会暴露使目标寄存器保持不变的 asm 行为；AMD 记录的行为，但 Intel 和 AMD 都实现了）。对于非零 16 位输入，低 16 位以上的位不会影响该值。因此，拥有 16 位bsf不会有帮助，但 16 位tzcnt确实可以让您16在输入为零时得到 a，而不必_tzcnt_u32(0x10000 | x)让 32 位 tzcnt 在您想要的位置找到设置位。