在AVX2或更早的版本中,没有单独的指令。(AVX512可以直接使用位图形式的掩码,并且有一条指令将掩码扩展为向量)。
8位 -> 8字节或者没有AVX2的字(word):
如何高效地将8位位图转换为0/1整数数组,使用x86 SIMD非常便宜,尽管没有SSSE3的8位或16位掩码广播可能会导致多次洗牌。
请注意使用
_mm_min_epu8(v, _mm_set1_epi8(1))
这个技巧
而不是使用
_mm_cmpeq_epi8
来获得0/1而不是0/FF。
16位 -> 使用SSE2或SSSE3转换为16字节,或者
AVX-512:
将16位掩码转换为16字节掩码。
(还有用于
unsigned __int128
的BMI2,纯C++乘法位操作技巧,以及用于获得0/1而不是0/-1的AVX-512示例)
8位 -> 8字节:如果您只需要每次处理8位,那么标量乘法技巧可能更好:
如何通过8个布尔值创建一个字节(反之亦然)。
对于您的情况,如果您从内存中加载位图,则直接将其加载到矢量寄存器中以进行ALU策略应该效果很好,即使是4位掩码也可以。
如果您将位图作为计算结果,则它将在整数寄存器中,您可以轻松地将其用作LUT索引,因此如果您的目标是64位元素,那么这是一个不错的选择。否则,对于32位元素或更小的情况,可能仍然选择ALU,而不是使用巨大的LUT或执行多个块。
我们将不得不等待AVX-512的掩码寄存器,才能实现从整数位屏蔽转换为矢量屏蔽的廉价方法。(使用
kmovw k1, r/m16
,编译器会隐式为
int => __mmask16
生成)。有一个AVX512指令可以根据掩码设置矢量(
VPMOVM2D zmm1, k1
,具体信息请参考
_mm512_movm_epi8/16/32/64
,针对不同元素大小也有其他版本),但通常您不需要它,因为以前使用掩码矢量的所有内容现在都使用掩码寄存器。也许如果您想计算符合某个比较条件的元素数量?(这里可以使用
pcmpeqd
/
psubd
来生成和累加0或-1元素的矢量)。但是,在掩码结果上使用标量
popcnt
可能更好。
但请注意,vpmovm2d需要将掩码放在AVX512的k0..7掩码寄存器中。除非来自矢量比较结果,否则将其放置在那里将需要额外的指令,并且移动到掩码寄存器的指令需要Intel Skylake-X和类似CPU上端口5的uop,因此这可能成为一个瓶颈(特别是如果进行任何洗牌操作)。尤其是如果它起始于内存(加载位图)且您只需要每个元素的高位,则即使有256位和512位的AVX512指令可用,使用广播加载+可变移位仍然更好。
另外,还有一种可能性(对于0/1的结果而不是0/-1),可以从常量进行零掩码加载,例如_mm_maskz_mov_epi8(mask16, _mm_set1_epi8(1))。https://godbolt.org/z/1sM8hY8Tj
对于64位元素,掩码只有4位,所以使用查找表是合理的。您可以通过使用`VPMOVSXBQ ymm1, xmm2/m32`(`_mm256_cvtepi8_epi64`)来压缩LUT。这将使LUT的大小为(1<<4) = 16 * 4字节 = 64B = 1个缓存行。不幸的是,`pmovsx`在使用内部函数时不方便使用窄加载。
特别是如果您已经将位图存储在整数寄存器中(而不是内存中),则在64位元素的内部循环中使用`vpmovsxbq` LUT应该非常好。或者,如果指令吞吐量或洗牌吞吐量成为瓶颈,可以使用未压缩的LUT。这样可以让您(或编译器)将掩码向量用作其他操作数的内存操作数,而无需单独的指令来加载它。
32位元素的查找表(LUT):可能不是最优解,但以下是你可以实现的方法。
对于32位元素,8位掩码可以给出256个可能的向量,每个向量包含8个元素。256 * 8B = 2048字节,即使对于压缩版本(使用
vpmovsxbd ymm, m64
加载),这也是一个相当大的缓存占用。
为了解决这个问题,你可以将LUT分成4位块。将一个8位整数拆分成两个4位整数需要大约3条整数指令(
mov/and/shr
)。然后,对于128位向量的未压缩LUT(适用于32位元素大小),使用
vmovdqa
加载低半部分,再使用
vinserti128
加载高半部分。你仍然可以压缩LUT,但我不建议这样做,因为你将需要
vmovd
/
vpinsrd
/
vpmovsxbd
,这涉及2次洗牌操作(所以你可能会受到uop吞吐量的限制)。
或者2倍 vpmovsxbd xmm, [lut + rsi*4]
+ vinserti128
在英特尔上可能更糟糕。
ALU替代方案:适用于16/32/64位元素
当整个位图适合每个元素时:广播它,与选择器掩码相与,并对同一常数进行VPCMPEQ比较(该常数可以在循环中的多次使用中保留在寄存器中)。
vpbroadcastd ymm0, dword [mask] ; _mm256_set1_epi32
vpand ymm0, ymm0, setr_epi32(1<<0, 1<<1, 1<<2, 1<<3, ..., 1<<7)
vpcmpeqd ymm0, ymm0, [same constant] ; _mm256_cmpeq_epi32
; ymm0 = (mask & bit) == bit
; where bit = 1<<element_number
掩码可以来自带有vmovd + vpbroadcastd的整数寄存器,但如果它已经在内存中,广播加载是廉价的,例如从一个掩码数组应用于一个元素数组。实际上,我们只关心该双字的低8位,因为8个32位元素= 32字节(例如,您从vmovmaskps获得的)。对于16个16位元素的16位掩码,您需要vpbroadcastw。要首先从16位整数向量获取这样的掩码,您可以将两个向量一起vpacksswb(保留每个元素的符号位),然后vpermq将元素放入顺序后的in-lane pack,然后vpmovmskb。
对于8位元素,您需要使用
vpshufb
将
vpbroadcastd
的结果进行重排,以便将相关位放入每个字节中。请参阅
如何执行_mm256_movemask_epi8(VPMOVMSKB)的逆操作?。但是对于16位及更宽的元素,元素数量≤元素宽度,因此广播加载可以免费完成。(与32位和64位广播加载完全在加载端口中处理不同,16位广播加载会产生一个微融合ALU洗牌微操作成本。)
vpbroadcastd/q
甚至不需要任何ALU uops, 它直接在加载端口完成。 (b
和w
是加载+洗牌)。即使您的掩码紧凑地放在一起(每个字节对应32位或64位元素),与其使用vpbroadcastb
,使用vpbroadcastd
可能更高效。在广播之后,x & mask == mask
检查不关心每个元素高字节中的垃圾数据。唯一需要担心的是缓存行/页面分割。
变量位移(Skylake 上更便宜),如果只需要符号位
变量混合和掩码加载/存储只关心掩码元素的符号位。
一旦将 8 位掩码广播到双字元素,这只是 1 个微操作(在 Skylake 上)。
vpbroadcastd ymm0, dword [mask]
vpsllvd ymm0, ymm0, [vec of 24, 25, 26, 27, 28, 29, 30, 31] ; high bit of each element = corresponding bit of the mask
;vpsrad ymm0, ymm0, 31 ; broadcast the sign bit of each element to the whole element
;vpsllvd + vpsrad has no advantage over vpand / vpcmpeqb, so don't use this if you need all the bits set.
vpbroadcastd
与从内存加载一样廉价(在Intel CPU和Ryzen上完全没有ALU uop)。较窄的广播,例如vpbroadcastb y,mem
在Intel上需要一个ALU洗牌uop,但可能不需要在Ryzen上。
变量移位在Haswell/Broadwell上稍微昂贵(3个uop,受限执行端口),但在Skylake上与立即数移位一样廉价!(在端口0或1上的1个uop。)在Zen 3之前的AMD上,它们不会额外消耗uop,但速度较慢(3周期延迟,吞吐量为正常移位uop的四分之一)。在Zen 1上,这是额外糟糕的,因为256位操作通常作为2个uop运行。但这并不是灾难,尤其是如果其他uop可以在它们占用额外周期时使用同一端口上的其他执行单元(我不知道是否可能)。在Zen 3及更高版本上,它们的性能与Skylake相当,1个周期延迟,0.5个周期吞吐量。
请参阅
x86标签维基以获取性能信息,尤其是
Agner Fog的指令表和
https://uops.info/。
对于64位元素,请注意算术右移仅适用于16位和32位元素大小。如果您希望将整个元素集设置为全零/全一以进行4位-> 64位元素的操作,请使用不同的策略。
使用内部函数:
// AVX2, most efficient on Skylake and Zen 3 and later
// if you just need the MSBs set. Otherwise still use and/cmpeq
__m256i bitmap2vecmask(int m) {
const __m256i vshift_count = _mm256_set_epi32(24, 25, 26, 27, 28, 29, 30, 31)
__m256i bcast = _mm256_set1_epi32(m)
__m256i shifted = _mm256_sllv_epi32(bcast, vshift_count)
return shifted
// use _mm256_and and _mm256_cmpeq if you need all bits set, not two shifts.
// would work but not worth it: return _mm256_srai_epi32(shifted, 31)
}
在循环内部,根据循环中的指令组合,查找表(LUT)可能值得占用缓存空间。特别是对于64位元素大小,其缓存占用不多,但甚至对于32位也可能如此。
另一个选择,而不是使用变量移位,是使用BMI2将每个位解包到一个字节中,并在高位使用该掩码元素,然后使用vpmovsx。
; 8bit mask bitmap in eax, constant in rdi
pdep rax, rax, rdi ; rdi = 0b1000000010000000... repeating
vmovq xmm0, rax
vpmovsxbd ymm0, xmm0 ; each element = 0xffffff80 or 0
; optional
;vpsrad ymm0, ymm0, 8 ; arithmetic shift to get -1 or 0
如果您已经将掩码存储在整数寄存器中(无论如何,您都需要单独进行
vmovq
/
vpbroadcastd
),那么即使在Skylake上变量计数移位很便宜,这种方式可能更好。
如果您的掩码起始于内存中,则另一种ALU方法(直接
vpbroadcastd
到向量中)可能更好,因为广播加载非常便宜。
请注意,在Zen 1和Zen 2上,
pdep
是6个相关的微操作(18个周期延迟,18个周期吞吐量,或者取决于位数而更差),因此即使您的掩码确实起始于整数寄存器,这种方法在Ryzen上效果很差。 Zen 3及更高版本具有专用的
pext
/
pdep
硬件,并将它们像Intel一样高效地执行,作为单个微操作。
(未来的读者可以随意编辑这个版本的内部函数。使用汇编语言编写更容易,因为打字较少,汇编助记符更易读(不会在各处弄乱
_mm256_
之类的愚蠢字符)。)