AVX2 什么是最有效的基于掩码打包的方法？
AVX2 what is the most efficient way to pack left based on a mask?
如果您有一个输入数组和一个输出数组，但您只想写入满足特定条件的那些元素，那么在 AVX2 中执行此操作的最有效方法是什么？
我在 SSE 看到过这样的操作：
（来自：https://deplinenoise.files.wordpress.com/2015/03/gdc2015_afredriksson_simd.pdf）
__m128i LeftPack_SSSE3(__m128 mask, __m128 val)
{
// Move 4 sign bits of mask to 4-bit integer value.
int mask = _mm_movemask_ps(mask);
// Select shuffle control data
__m128i shuf_ctrl = _mm_load_si128(&shufmasks[mask]);
// Permute to move valid values to front of SIMD register
__m128i packed = _mm_shuffle_epi8(_mm_castps_si128(val), shuf_ctrl);
return packed;
}
这对于 4 宽的 SSE 来说似乎没问题，因此只需要 16 个条目的 LUT，但是对于 8 宽的 AVX，LUT 变得相当大（256 个条目，每个 32 字节，或 8k）。
令我惊讶的是，AVX 似乎没有简化此过程的说明，例如带包装的蒙版商店。
我认为通过一些改组来计算设置在左侧的符号位的数量，您可以生成必要的排列 table，然后调用 _mm256_permutevar8x32_ps。但是我认为这也是相当多的说明..
有人知道使用 AVX2 执行此操作的任何技巧吗？或者什么是最有效的方法？
以下是上述文档中左包装问题的说明：
谢谢
如果您的目标是 AMD Zen，则此方法可能是首选，因为 ryzen 上的 pdep 和 pext 非常慢（每个 18 个周期）。
我想出了这个方法，它使用压缩的 LUT，它是 768（+1 填充）字节，而不是 8k。它需要广播单个标量值，然后在每个通道中将其移位不同的量，然后屏蔽到较低的 3 位，从而提供 0-7 LUT。
这是内在函数版本，以及构建 LUT 的代码。
//Generate Move mask via: _mm256_movemask_ps(_mm256_castsi256_ps(mask)); etc
__m256i MoveMaskToIndices(u32 moveMask) {
u8 *adr = g_pack_left_table_u8x3 + moveMask * 3;
__m256i indices = _mm256_set1_epi32(*reinterpret_cast<u32*>(adr));//lower 24 bits has our LUT
// __m256i m = _mm256_sllv_epi32(indices, _mm256_setr_epi32(29, 26, 23, 20, 17, 14, 11, 8));
//now shift it right to get 3 bits at bottom
//__m256i shufmask = _mm256_srli_epi32(m, 29);
//Simplified version suggested by wim
//shift each lane so desired 3 bits are a bottom
//There is leftover data in the lane, but _mm256_permutevar8x32_ps only examines the first 3 bits so this is ok
__m256i shufmask = _mm256_srlv_epi32 (indices, _mm256_setr_epi32(0, 3, 6, 9, 12, 15, 18, 21));
return shufmask;
}
u32 get_nth_bits(int a) {
u32 out = 0;
int c = 0;
for (int i = 0; i < 8; ++i) {
auto set = (a >> i) & 1;
if (set) {
out |= (i << (c * 3));
c++;
}
}
return out;
}
u8 g_pack_left_table_u8x3[256 * 3 + 1];
void BuildPackMask() {
for (int i = 0; i < 256; ++i) {
*reinterpret_cast<u32*>(&g_pack_left_table_u8x3[i * 3]) = get_nth_bits(i);
}
}
这里是 MSVC 生成的程序集：
lea ecx, DWORD PTR [rcx+rcx*2]
lea rax, OFFSET FLAT:unsigned char * g_pack_left_table_u8x3 ; g_pack_left_table_u8x3
vpbroadcastd ymm0, DWORD PTR [rcx+rax]
vpsrlvd ymm0, ymm0, YMMWORD PTR __ymm@00000015000000120000000f0000000c00000009000000060000000300000000
请参阅我对没有 LUT 的 AVX2+BMI2 的其他回答。
既然您提到了对 AVX512 可扩展性的担忧：别担心，AVX512F 指令正是针对此:
VCOMPRESSPS — Store Sparse Packed Single-Precision Floating-Point Values into Dense Memory。 （还有用于双精度和 32 或 64 位整数元素 (vpcompressq) 的版本，但不是字节或字（16 位））。类似于 BMI2 pdep / pext，但对于向量元素而不是整数 reg.
中的位
目标可以是向量寄存器或内存操作数，而源是向量和掩码寄存器。使用寄存器目标，它可以合并或清零高位。有了内存dest，"Only the contiguous vector is written to the destination memory location".
要计算下一个向量的指针前进多远，弹出掩码。
假设您想从数组中过滤掉除值 >= 0 以外的所有内容：
#include <stdint.h>
#include <immintrin.h>
size_t filter_non_negative(float *__restrict__ dst, const float *__restrict__ src, size_t len) {
const float *endp = src+len;
float *dst_start = dst;
do {
__m512 sv = _mm512_loadu_ps(src);
__mmask16 keep = _mm512_cmp_ps_mask(sv, _mm512_setzero_ps(), _CMP_GE_OQ); // true for src >= 0.0, false for unordered and src < 0.0
_mm512_mask_compressstoreu_ps(dst, keep, sv); // clang is missing this intrinsic, which can't be emulated with a separate store
src += 16;
dst += _mm_popcnt_u64(keep); // popcnt_u64 instead of u32 helps gcc avoid a wasted movsx, but is potentially slower on some CPUs
} while (src < endp);
return dst - dst_start;
}
这编译（使用 gcc4.9 或更高版本）为 (Godbolt Compiler Explorer):
# Output from gcc6.1, with -O3 -march=haswell -mavx512f. Same with other gcc versions
lea rcx, [rsi+rdx*4] # endp
mov rax, rdi
vpxord zmm1, zmm1, zmm1 # vpxor xmm1, xmm1,xmm1 would save a byte, using VEX instead of EVEX
.L2:
vmovups zmm0, ZMMWORD PTR [rsi]
add rsi, 64
vcmpps k1, zmm0, zmm1, 29 # AVX512 compares have mask regs as a destination
kmovw edx, k1 # There are some insns to add/or/and mask regs, but not popcnt
movzx edx, dx # gcc is dumb and doesn't know that kmovw already zero-extends to fill the destination.
vcompressps ZMMWORD PTR [rax]{k1}, zmm0
popcnt rdx, rdx
## movsx rdx, edx # with _popcnt_u32, gcc is dumb. No casting can get gcc to do anything but sign-extend. You'd expect (unsigned) would mov to zero-extend, but no.
lea rax, [rax+rdx*4] # dst += ...
cmp rcx, rsi
ja .L2
sub rax, rdi
sar rax, 2 # address math -> element count
ret
性能：256 位向量在 Skylake-X / Cascade Lake 上可能更快
理论上，加载位图并将一个数组过滤到另一个数组的循环应该 运行 在 SKX / CSLX 上每 3 个时钟 1 个向量，无论向量宽度如何，在端口 5 上成为瓶颈。（kmovb/w/d/q k1, eax 运行s 在 p5 上，vcompressps 进入内存是 2p5 + 存储，根据 IACA 和 http://uops.info/ 测试）。
@ZachB 在评论中报告说，在实践中，使用 ZMM _mm512_mask_compressstoreu_ps 的循环比真正的 CSLX 硬件上的 _mm256_mask_compressstoreu_ps 稍慢。（我我不确定那是否是允许 256 位版本脱离“512 位矢量模式”并提高时钟频率的微基准测试，或者是否有周围的 512 位代码。）
我怀疑未对齐的存储正在损害 512 位版本。 vcompressps 可能有效地进行了掩蔽的 256 位或 512 位向量存储，如果它跨越缓存行边界，那么它必须做额外的工作。由于输出指针通常不是 16 个元素的倍数，因此整行 512 位存储几乎总是未对齐。
由于某些原因，未对齐的 512 位存储可能比缓存行拆分 256 位存储更糟糕，而且发生得更频繁；我们已经知道其他事物的 512 位矢量化似乎对对齐更敏感。这可能只是因为 运行 每次都发生拆分加载缓冲区，或者处理缓存行拆分的回退机制对于 512 位向量来说效率较低。
将 vcompressps 基准化到寄存器中会很有趣，具有单独的全向量重叠存储 。这可能是相同的 uops，但是当它是一个单独的指令时，商店可以微融合。如果屏蔽商店与重叠商店之间存在一些差异，这将揭示它。
下面评论中讨论的另一个想法是使用 vpermt2ps 为对齐的商店建立完整的向量。这个 和我们填充向量时的分支可能会预测错误，除非位掩码具有非常规则的模式，或者大 运行 的全 0 和全 1。
一个无分支的实现，带有一个循环携带的依赖链，通过正在构建的向量有 4 或 6 个循环，用 vpermt2ps 和一个混合或其他东西来替换它，当它是 "full".使用对齐的向量存储每次迭代，但仅在向量已满时才移动输出指针。
这可能比当前 Intel CPU 上未对齐存储的 vcompressps 慢。
AVX2 + BMI2。请参阅我对 AVX512 的其他回答。 （更新：在 64 位版本中保存了 pdep。）
我们可以使用 AVX2 vpermps (_mm256_permutevar8x32_ps)（或等价的整数 vpermd）来进行跨车道变量随机播放。
我们可以即时生成掩码，因为 BMI2 pext (Parallel Bits Extract) 为我们提供了所需操作的按位版本。
注意 pdep/pext 在 Zen 3 之前的 AMD CPU 上 非常 慢，例如 6 微指令/18 周期延迟Ryzen Zen 1 和 Zen 2 的吞吐量。这种实现在那些 AMD CPU 上的表现会非常糟糕。对于 AMD，您可能最好使用 pshufb 或 vpermilps LUT 或评论中讨论的一些 AVX2 变量移位建议来使用 128 位向量。特别是如果您的掩码输入是矢量掩码（不是内存中已经打包的位掩码）。
Zen2之前的AMD反正只有128位的向量执行单元，256位的跨车道shuffle很慢。所以 128 位向量在 Zen 1 上对此非常有吸引力。但是 Zen 2 有 256 位 load/store 和执行单元。 （而且微编码仍然很慢 pext/pdep。）
对于具有 32 位或更宽元素的整数向量： 1) _mm256_movemask_ps(_mm256_castsi256_ps(compare_mask)).
或者 2) 使用 _mm256_movemask_epi8 然后将第一个 PDEP 常量从 0x0101010101010101 更改为 0x0F0F0F0F0F0F0F0F 以分散 4 个连续位的块。将乘以 0xFFU 更改为 expanded_mask |= expanded_mask<<4; 或 expanded_mask *= 0x11;（未测试）。无论哪种方式，使用带 VPERMD 的洗牌掩码而不是 VPERMPS。
对于 64 位整数或 double 元素，一切仍然正常；比较掩码恰好总是具有相同的 32 位元素对，因此生成的混洗将每个 64 位元素的两半放在正确的位置。 （所以您仍然使用 VPERMPS 或 VPERMD，因为 VPERMPD 和 VPERMQ 仅适用于立即控制操作数。）
对于 16 位元素，您可以使用 128 位向量进行调整。
对于 8 位元素，请参阅 了解不同的技巧，将结果存储在多个可能重叠的块中。
算法：
从压缩的 3 位索引常量开始，每个位置都有自己的索引。即 [ 7 6 5 4 3 2 1 0 ] 其中每个元素为 3 位宽。 0b111'110'101'...'010'001'000.
使用pext将我们想要的索引提取到整数寄存器底部的连续序列中。例如如果我们想要索引 0 和 2，我们 pext 的控制掩码应该是 0b000'...'111'000'111。 pext 将获取与选择器中的 1 位对齐的 010 和 000 索引组。选定的组被打包到输出的低位，因此输出将为 0b000'...'010'000。 （即 [ ... 2 0 ]）
有关如何从输入向量掩码为 pext 生成 0b111000111 输入的注释代码。
现在我们与压缩 LUT 在同一条船上：解压缩多达 8 个压缩索引。
当你把所有的部分放在一起时，共有三个 pext/pdeps。我从我想要的东西开始倒退，所以从那个方向理解它可能也是最容易的。 （即从洗牌线开始，然后从那里向后工作。）
如果我们使用每个字节一个索引而不是压缩的 3 位组，我们可以简化解包。由于我们有 8 个索引，这仅适用于 64 位代码。
参见 this and a 32bit-only version on the Godbolt Compiler Explorer。我使用了 #ifdefs，因此它可以使用 -m64 或 -m32 进行最佳编译。 gcc 浪费了一些指令，但 clang 的代码非常好。
#include <stdint.h>
#include <immintrin.h>
// Uses 64bit pdep / pext to save a step in unpacking.
__m256 compress256(__m256 src, unsigned int mask /* from movmskps */)
{
uint64_t expanded_mask = _pdep_u64(mask, 0x0101010101010101); // unpack each bit to a byte
expanded_mask *= 0xFF; // mask |= mask<<1 | mask<<2 | ... | mask<<7;
// ABC... -> AAAAAAAABBBBBBBBCCCCCCCC...: replicate each bit to fill its byte
const uint64_t identity_indices = 0x0706050403020100; // the identity shuffle for vpermps, packed to one index per byte
uint64_t wanted_indices = _pext_u64(identity_indices, expanded_mask);
__m128i bytevec = _mm_cvtsi64_si128(wanted_indices);
__m256i shufmask = _mm256_cvtepu8_epi32(bytevec);
return _mm256_permutevar8x32_ps(src, shufmask);
}
这会编译成没有从内存加载的代码，只有立即常量。 （参见 godbolt link 和 32 位版本）。
# clang 3.7.1 -std=gnu++14 -O3 -march=haswell
mov eax, edi # just to zero extend: goes away when inlining
movabs rcx, 72340172838076673 # The constants are hoisted after inlining into a loop
pdep rax, rax, rcx # ABC -> 0000000A0000000B....
imul rax, rax, 255 # 0000000A0000000B.. -> AAAAAAAABBBBBBBB..
movabs rcx, 506097522914230528
pext rax, rcx, rax
vmovq xmm1, rax
vpmovzxbd ymm1, xmm1 # 3c latency since this is lane-crossing
vpermps ymm0, ymm1, ymm0
ret
（后来 clang 像 GCC 一样编译，用 mov/shl/sub 而不是 imul，见下文。）
因此，根据 Agner Fog's numbers and https://uops.info/，这是 6 微指令（不包括常量，或内联时消失的零扩展 mov）。在 Intel Haswell 上，它是 16c 延迟（vmovq 为 1，每个 pdep/imul/pext / vpmovzx / vpermps 为 3）。没有指令级并行性。但是，在一个循环中，这不是循环携带依赖的一部分（就像我在 Godbolt link 中包含的那个），瓶颈可能只是吞吐量，同时保持多次迭代.
这也许可以管理每 4 个周期一个的吞吐量，瓶颈在端口 1 上 pdep/pext/imul 加上循环中的 popcnt。当然，由于 loads/stores 和其他循环开销（包括比较和 movmsk），uop 总吞吐量也很容易成为问题。
例如我的 Godbolt link 中的过滤器循环是 14 微指令，带有 clang，-fno-unroll-loops 使其更易于阅读。它可能每 4c 维持一次迭代，跟上前端，如果我们幸运的话。
clang 6 和更早版本使用 popcnt's false dependency on its output 创建了一个循环承载依赖项，因此它将在 compress256 函数延迟的 3/5 处成为瓶颈。 clang 7.0 及更高版本使用 xor-zeroing 来打破错误的依赖（而不是仅仅使用 popcnt edx,edx 或类似 GCC 的东西：/）。
gcc（以及后来的 clang）使用多条指令乘以 0xFF，使用左移 8 和 sub，而不是 imul 乘以 255。这总共需要 3 uops vs . 1 用于前端，但延迟仅为 2 个周期，低于 3 个。（Haswell 在寄存器重命名阶段以零延迟处理 mov。）最重要的是，imul 只能运行 在端口 1 上，与 pdep/pext/popcnt 竞争，因此最好避免该瓶颈。
由于所有支持 AVX2 的硬件也都支持 BMI2，因此提供没有 BMI2 的 AVX2 版本可能没有意义。
如果您需要在一个很长的循环中执行此操作，那么如果初始缓存未命中被分摊到足够多的迭代中并且仅解压缩 LUT 条目的开销较低，那么 LUT 可能是值得的。你仍然需要 movmskps，所以你可以 popcnt 掩码并将其用作 LUT 索引，但是你保存了 pdep/imul/pext.
您可以使用我使用的相同整数序列解压 LUT 条目，但是当 LUT 条目在内存中开始并且不在内存中时，@Froglegs 的 set1() / vpsrlvd / vpand首先需要进入整数寄存器。 （32 位广播负载在 Intel CPU 上不需要 ALU uop）。但是，Haswell 上的可变移位是 3 微指令（但 Skylake 上只有 1 微指令）。
如果有人对此感兴趣，这里有一个 SSE2 的解决方案，它使用指令 LUT 而不是数据 LUT，也就是跳转 table。不过，使用 AVX 这将需要 256 个案例。
每次调用下面的 LeftPack_SSE2 时，它基本上使用三个指令：jmp、shufps、jmp。十六种情况中有五种不需要修改向量。
static inline __m128 LeftPack_SSE2(__m128 val, int mask) {
switch(mask) {
case 0:
case 1: return val;
case 2: return _mm_shuffle_ps(val,val,0x01);
case 3: return val;
case 4: return _mm_shuffle_ps(val,val,0x02);
case 5: return _mm_shuffle_ps(val,val,0x08);
case 6: return _mm_shuffle_ps(val,val,0x09);
case 7: return val;
case 8: return _mm_shuffle_ps(val,val,0x03);
case 9: return _mm_shuffle_ps(val,val,0x0c);
case 10: return _mm_shuffle_ps(val,val,0x0d);
case 11: return _mm_shuffle_ps(val,val,0x34);
case 12: return _mm_shuffle_ps(val,val,0x0e);
case 13: return _mm_shuffle_ps(val,val,0x38);
case 14: return _mm_shuffle_ps(val,val,0x39);
case 15: return val;
}
}
__m128 foo(__m128 val, __m128 maskv) {
int mask = _mm_movemask_ps(maskv);
return LeftPack_SSE2(val, mask);
}
将为@PeterCordes 的精彩回答添加更多信息：。
我用它实现了 std::remove from C++ standard 的整数类型。一旦可以进行压缩，该算法就相对简单：加载寄存器、压缩、存储。首先，我将展示变体，然后展示基准。
我最终对提议的解决方案做出了两个有意义的变体：
__m128i 寄存器，任何元素类型，使用 _mm_shuffle_epi8 指令__m256i寄存器，元素类型至少4个字节，使用_mm256_permutevar8x32_epi32
当 256 位寄存器的类型小于 4 个字节时，我将它们分成两个 128 位寄存器并且 compress/store 每个分开。
Link 到编译器资源管理器，您可以在其中看到完整的程序集（底部有一个 using type 和 width（每个包中的元素），您可以将其插入得到不同的变化）：https://gcc.godbolt.org/z/yQFR2t
注意：我的代码是在 C++17 中使用的自定义 simd 包装器，所以我不知道它的可读性如何。如果你想阅读我的代码 -> 大部分都在 godbolt 顶部包含的 link 后面。或者，所有代码都在 github.
@PeterCordes 对两种情况的回答的实现
注意：连同掩码，我还使用 popcount 计算剩余元素的数量。可能有不需要的情况，但是我还没见过
_mm_shuffle_epi8
的掩码
- 将每个字节的索引写成半字节：
0xfedcba9876543210
- 将索引对放入 8 条短裤中，打包成
__m128i
- 使用
x << 4 | x & 0x0f0f
分散它们
展开索引的例子。假设选择了第 7 个和第 6 个元素。
这意味着相应的短是：0x00fe。在 << 4 和 | 之后我们会得到 0x0ffe。然后我们清除第二个f.
完整掩码：
// helper namespace
namespace _compress_mask {
// mmask - result of `_mm_movemask_epi8`,
// `uint16_t` - there are at most 16 bits with values for __m128i.
inline std::pair<__m128i, std::uint8_t> mask128(std::uint16_t mmask) {
const std::uint64_t mmask_expanded = _pdep_u64(mmask, 0x1111111111111111) * 0xf;
const std::uint8_t offset =
static_cast<std::uint8_t>(_mm_popcnt_u32(mmask)); // To compute how many elements were selected
const std::uint64_t compressed_idxes =
_pext_u64(0xfedcba9876543210, mmask_expanded); // Do the @PeterCordes answer
const __m128i as_lower_8byte = _mm_cvtsi64_si128(compressed_idxes); // 0...0|compressed_indexes
const __m128i as_16bit = _mm_cvtepu8_epi16(as_lower_8byte); // From bytes to shorts over the whole register
const __m128i shift_by_4 = _mm_slli_epi16(as_16bit, 4); // x << 4
const __m128i combined = _mm_or_si128(shift_by_4, as_16bit); // | x
const __m128i filter = _mm_set1_epi16(0x0f0f); // 0x0f0f
const __m128i res = _mm_and_si128(combined, filter); // & 0x0f0f
return {res, offset};
}
} // namespace _compress_mask
template <typename T>
std::pair<__m128i, std::uint8_t> compress_mask_for_shuffle_epi8(std::uint32_t mmask) {
auto res = _compress_mask::mask128(mmask);
res.second /= sizeof(T); // bit count to element count
return res;
}
_mm256_permutevar8x32_epi32
的掩码
这几乎是一对一的@PeterCordes 解决方案 - 唯一的区别是 _pdep_u64 位（他建议将此作为注释）。
我选择的面具是0x5555'5555'5555'5555。这个想法是——我有 32 位的 mmask，8 个整数中的每一个有 4 位。我想要得到 64 位 => 我需要将 32 位的每一位转换为 2 => 因此 0101b = 5.The 乘数也从 0xff 变为 3 因为我将为每个整数得到 0x55，而不是 1 .
完整掩码：
// helper namespace
namespace _compress_mask {
// mmask - result of _mm256_movemask_epi8
inline std::pair<__m256i, std::uint8_t> mask256_epi32(std::uint32_t mmask) {
const std::uint64_t mmask_expanded = _pdep_u64(mmask, 0x5555'5555'5555'5555) * 3;
const std::uint8_t offset = static_cast<std::uint8_t(_mm_popcnt_u32(mmask)); // To compute how many elements were selected
const std::uint64_t compressed_idxes = _pext_u64(0x0706050403020100, mmask_expanded); // Do the @PeterCordes answer
// Every index was one byte => we need to make them into 4 bytes
const __m128i as_lower_8byte = _mm_cvtsi64_si128(compressed_idxes); // 0000|compressed indexes
const __m256i expanded = _mm256_cvtepu8_epi32(as_lower_8byte); // spread them out
return {expanded, offset};
}
} // namespace _compress_mask
template <typename T>
std::pair<__m256i, std::uint8_t> compress_mask_for_permutevar8x32(std::uint32_t mmask) {
static_assert(sizeof(T) >= 4); // You cannot permute shorts/chars with this.
auto res = _compress_mask::mask256_epi32(mmask);
res.second /= sizeof(T); // bit count to element count
return res;
}
基准测试
处理器：Intel Core i7 9700K（现代消费者级别 CPU，不支持 AVX-512）
编译器：clang，从版本 10 版本附近的主干构建
编译器选项：--std=c++17 --stdlib=libc++ -g -Werror -Wall -Wextra -Wpedantic -O3 -march=native -mllvm -align-all-functions=7
微基准库：google benchmark
控制代码对齐：
如果您不熟悉这个概念，请阅读 this or watch this
基准测试二进制文件中的所有函数都与 128 字节边界对齐。每个基准测试函数被复制 64 次，在函数的开头（进入循环之前）有一个不同的 noop 幻灯片。我显示的主要数字是每次测量的最小值。我认为这是可行的，因为该算法是内联的。我也得到了非常不同的结果这一事实的验证。在答案的最底部，我展示了代码对齐的影响。
注：benchmarking code。 BENCH_DECL_ATTRIBUTES 只是 noinline
Benchmark 从数组中删除一定百分比的 0。我用 {0, 5, 20, 50, 80, 95, 100} 百分比的零测试数组。
我测试了 3 种大小：40 字节（看看这是否适用于非常小的数组）、1000 字节和 10'000 字节。我按大小分组，因为 SIMD 取决于数据的大小而不是元素的数量。元素计数可以从元素大小得出（1000 字节是 1000 个字符，但 500 个短裤和 250 个整数）。由于非 simd 代码所需的时间主要取决于元素数量，因此字符的胜利应该更大。
绘图：x - 零的百分比，y - 以纳秒为单位的时间。 padding : min 表示这是所有对齐中的最小值。
40 字节数据，40 个字符
对于 40 字节，即使对于字符，这也没有意义 - 当在非 simd 代码上使用 128 位寄存器时，我的实现速度大约慢 8-10 倍。因此，例如，编译器在执行此操作时应小心。
1000 字节数据，1000 个字符
显然，非 simd 版本主要由分支预测决定：当我们得到少量零时，我们得到的加速较小：对于没有 0 的情况 - 大约 3 倍，对于 5% 的零 - 大约 5-6 倍的速度向上。当分支预测器无法帮助非 simd 版本时 - 大约有 27 倍的加速。这是一个有趣的 属性 simd 代码，它的性能往往不太依赖于数据。使用 128 和 256 寄存器几乎没有区别，因为大部分工作仍然分为 2 128 个寄存器。
1000 字节数据，500 条短裤
短裤的结果相似，只是增益小得多 - 最多 2 倍。
我不知道为什么短裤比非 simd 代码的字符要好得多：我希望短裤快两倍，因为只有 500 条短裤，但差异实际上高达 10 倍。
1000 字节数据，250 个整数
对于 1000，只有 256 位版本是有意义的 - 20-30% 获胜，不包括任何 0 以删除所有内容（完美的分支预测，非 simd 代码不删除）。
10'000 个字节的数据，10'000 个字符
与 1000 个字符相同的数量级获胜：分支预测器有帮助时快 2-6 倍，无帮助时快 27 倍。
同样的剧情，只有simd版本：
在这里我们可以看到使用 256 位寄存器并将它们分成 2 128 位寄存器大约有 10% 的优势：大约快 10%。它的大小从 88 条指令增加到 129 条指令，这不是很多，因此根据您的用例可能有意义。对于基线 - 非 simd 版本是 79 条指令（据我所知 - 虽然这些指令比 SIMD 指令小）。
10'000 字节数据，5'000 条短裤
从 20% 到 9 次获胜，具体取决于数据分布。未显示 256 位和 128 位寄存器之间的比较 - 它与字符的汇编几乎相同，并且 256 位的相同赢取了大约 10%。
10'000 个字节的数据，2'500 个整数
似乎使用 256 位寄存器很有意义，这个版本比 128 位寄存器快大约 2 倍。与非 simd 代码进行比较时 - 从 20% 的胜率和完美的分支预测到 3.5 - 4 倍，如果不是的话。
结论：当你有足够的数据量（至少 1000 字节）时，这对于没有 AVX-512[=54= 的现代处理器来说是一个非常值得的优化]
PS:
要删除的元素百分比
一方面，过滤一半的元素并不常见。另一方面，在排序过程中可以在分区中使用类似的算法 => 实际上预计会有 ~50% 的分支选择。
代码对齐影响
问题是：如果代码恰好对齐不好，值多少钱
（一般来说 - 对此无能为力）。
我只显示 10'000 字节。
对于每个百分比点，图中有两条线表示最小值和最大值（意思是 - 它不是一个 best/worst 代码对齐 - 它是给定百分比的最佳代码对齐）。
代码对齐影响 - 非 simd
字符数：
从分支预测差的 15-20% 到分支预测有很大帮助的 2-3 倍。 （已知分支预测器会受到代码对齐的影响）。
短裤：
出于某种原因 - 0% 完全不受影响。可以解释为 std::remove 首先进行线性搜索以找到要删除的第一个元素。显然，对短裤的线性搜索不受影响。
除此之外 - 从 10% 到 1.6-1.8 倍价值
整数：
与短裤相同 - 没有 0 不受影响。一旦我们进入删除部分，它就会从 1.3 倍增加到 5 倍，然后是最佳情况对齐。
代码对齐影响 - simd 版本
不显示短裤和整数 128，因为它与字符的汇编几乎相同
Chars - 128 位寄存器
大约慢 1.2 倍
Chars - 256 位寄存器
大约慢 1.1 - 1.24 倍
Ints - 256 位寄存器
慢 1.25 - 1.35 倍
我们可以看到，对于算法的 simd 版本，与非 simd 版本相比，代码对齐的影响要小得多。我怀疑这是因为实际上没有分支。
这可能有点晚了，尽管我最近 运行 解决了这个确切的问题并找到了一个使用严格 AVX 实现的替代解决方案。如果您不关心解压缩的元素是否与每个向量的最后一个元素交换，这也可以。以下为AVX版本：
inline __m128 left_pack(__m128 val, __m128i mask) noexcept
{
const __m128i shiftMask0 = _mm_shuffle_epi32(mask, 0xA4);
const __m128i shiftMask1 = _mm_shuffle_epi32(mask, 0x54);
const __m128i shiftMask2 = _mm_shuffle_epi32(mask, 0x00);
__m128 v = val;
v = _mm_blendv_ps(_mm_permute_ps(v, 0xF9), v, shiftMask0);
v = _mm_blendv_ps(_mm_permute_ps(v, 0xF9), v, shiftMask1);
v = _mm_blendv_ps(_mm_permute_ps(v, 0xF9), v, shiftMask2);
return v;
}
本质上，val 中的每个元素都使用位域向左移动一次，0xF9 以便与其未移位的变体混合。接下来，将移位和未移位版本与输入掩码混合（第一个非零元素广播到其余元素 3 和 4）。再重复此过程两次，在每次迭代中将 mask 的第二个和第三个元素广播到其后续元素，这应该提供 _pdep_u32() BMI2 指令的 AVX 版本。
如果您没有 AVX，您可以轻松地将每个 _mm_permute_ps() 替换为 _mm_shuffle_ps() 以获得 SSE4.1 兼容版本。
如果您使用的是双精度，这里是 AVX2 的附加版本：
inline __m256 left_pack(__m256d val, __m256i mask) noexcept
{
const __m256i shiftMask0 = _mm256_permute4x64_epi64(mask, 0xA4);
const __m256i shiftMask1 = _mm256_permute4x64_epi64(mask, 0x54);
const __m256i shiftMask2 = _mm256_permute4x64_epi64(mask, 0x00);
__m256d v = val;
v = _mm256_blendv_pd(_mm256_permute4x64_pd(v, 0xF9), v, shiftMask0);
v = _mm256_blendv_pd(_mm256_permute4x64_pd(v, 0xF9), v, shiftMask1);
v = _mm256_blendv_pd(_mm256_permute4x64_pd(v, 0xF9), v, shiftMask2);
return v;
}
另外_mm_popcount_u32(_mm_movemask_ps(val))可以用来判断left-packing后剩余的元素个数
如果您有一个输入数组和一个输出数组，但您只想写入满足特定条件的那些元素，那么在 AVX2 中执行此操作的最有效方法是什么？
我在 SSE 看到过这样的操作： （来自：https://deplinenoise.files.wordpress.com/2015/03/gdc2015_afredriksson_simd.pdf）
__m128i LeftPack_SSSE3(__m128 mask, __m128 val)
{
// Move 4 sign bits of mask to 4-bit integer value.
int mask = _mm_movemask_ps(mask);
// Select shuffle control data
__m128i shuf_ctrl = _mm_load_si128(&shufmasks[mask]);
// Permute to move valid values to front of SIMD register
__m128i packed = _mm_shuffle_epi8(_mm_castps_si128(val), shuf_ctrl);
return packed;
}
这对于 4 宽的 SSE 来说似乎没问题，因此只需要 16 个条目的 LUT，但是对于 8 宽的 AVX，LUT 变得相当大（256 个条目，每个 32 字节，或 8k）。
令我惊讶的是，AVX 似乎没有简化此过程的说明，例如带包装的蒙版商店。
我认为通过一些改组来计算设置在左侧的符号位的数量，您可以生成必要的排列 table，然后调用 _mm256_permutevar8x32_ps。但是我认为这也是相当多的说明..
有人知道使用 AVX2 执行此操作的任何技巧吗？或者什么是最有效的方法？
以下是上述文档中左包装问题的说明：
谢谢
如果您的目标是 AMD Zen，则此方法可能是首选，因为 ryzen 上的 pdep 和 pext 非常慢（每个 18 个周期）。
我想出了这个方法，它使用压缩的 LUT，它是 768（+1 填充）字节，而不是 8k。它需要广播单个标量值，然后在每个通道中将其移位不同的量，然后屏蔽到较低的 3 位，从而提供 0-7 LUT。
这是内在函数版本，以及构建 LUT 的代码。
//Generate Move mask via: _mm256_movemask_ps(_mm256_castsi256_ps(mask)); etc
__m256i MoveMaskToIndices(u32 moveMask) {
u8 *adr = g_pack_left_table_u8x3 + moveMask * 3;
__m256i indices = _mm256_set1_epi32(*reinterpret_cast<u32*>(adr));//lower 24 bits has our LUT
// __m256i m = _mm256_sllv_epi32(indices, _mm256_setr_epi32(29, 26, 23, 20, 17, 14, 11, 8));
//now shift it right to get 3 bits at bottom
//__m256i shufmask = _mm256_srli_epi32(m, 29);
//Simplified version suggested by wim
//shift each lane so desired 3 bits are a bottom
//There is leftover data in the lane, but _mm256_permutevar8x32_ps only examines the first 3 bits so this is ok
__m256i shufmask = _mm256_srlv_epi32 (indices, _mm256_setr_epi32(0, 3, 6, 9, 12, 15, 18, 21));
return shufmask;
}
u32 get_nth_bits(int a) {
u32 out = 0;
int c = 0;
for (int i = 0; i < 8; ++i) {
auto set = (a >> i) & 1;
if (set) {
out |= (i << (c * 3));
c++;
}
}
return out;
}
u8 g_pack_left_table_u8x3[256 * 3 + 1];
void BuildPackMask() {
for (int i = 0; i < 256; ++i) {
*reinterpret_cast<u32*>(&g_pack_left_table_u8x3[i * 3]) = get_nth_bits(i);
}
}
这里是 MSVC 生成的程序集：
lea ecx, DWORD PTR [rcx+rcx*2]
lea rax, OFFSET FLAT:unsigned char * g_pack_left_table_u8x3 ; g_pack_left_table_u8x3
vpbroadcastd ymm0, DWORD PTR [rcx+rax]
vpsrlvd ymm0, ymm0, YMMWORD PTR __ymm@00000015000000120000000f0000000c00000009000000060000000300000000
请参阅我对没有 LUT 的 AVX2+BMI2 的其他回答。
既然您提到了对 AVX512 可扩展性的担忧：别担心，AVX512F 指令正是针对此:
VCOMPRESSPS — Store Sparse Packed Single-Precision Floating-Point Values into Dense Memory。 （还有用于双精度和 32 或 64 位整数元素 (vpcompressq) 的版本，但不是字节或字（16 位））。类似于 BMI2 pdep / pext，但对于向量元素而不是整数 reg.
目标可以是向量寄存器或内存操作数，而源是向量和掩码寄存器。使用寄存器目标，它可以合并或清零高位。有了内存dest，"Only the contiguous vector is written to the destination memory location".
要计算下一个向量的指针前进多远，弹出掩码。
假设您想从数组中过滤掉除值 >= 0 以外的所有内容：
#include <stdint.h>
#include <immintrin.h>
size_t filter_non_negative(float *__restrict__ dst, const float *__restrict__ src, size_t len) {
const float *endp = src+len;
float *dst_start = dst;
do {
__m512 sv = _mm512_loadu_ps(src);
__mmask16 keep = _mm512_cmp_ps_mask(sv, _mm512_setzero_ps(), _CMP_GE_OQ); // true for src >= 0.0, false for unordered and src < 0.0
_mm512_mask_compressstoreu_ps(dst, keep, sv); // clang is missing this intrinsic, which can't be emulated with a separate store
src += 16;
dst += _mm_popcnt_u64(keep); // popcnt_u64 instead of u32 helps gcc avoid a wasted movsx, but is potentially slower on some CPUs
} while (src < endp);
return dst - dst_start;
}
这编译（使用 gcc4.9 或更高版本）为 (Godbolt Compiler Explorer):
# Output from gcc6.1, with -O3 -march=haswell -mavx512f. Same with other gcc versions
lea rcx, [rsi+rdx*4] # endp
mov rax, rdi
vpxord zmm1, zmm1, zmm1 # vpxor xmm1, xmm1,xmm1 would save a byte, using VEX instead of EVEX
.L2:
vmovups zmm0, ZMMWORD PTR [rsi]
add rsi, 64
vcmpps k1, zmm0, zmm1, 29 # AVX512 compares have mask regs as a destination
kmovw edx, k1 # There are some insns to add/or/and mask regs, but not popcnt
movzx edx, dx # gcc is dumb and doesn't know that kmovw already zero-extends to fill the destination.
vcompressps ZMMWORD PTR [rax]{k1}, zmm0
popcnt rdx, rdx
## movsx rdx, edx # with _popcnt_u32, gcc is dumb. No casting can get gcc to do anything but sign-extend. You'd expect (unsigned) would mov to zero-extend, but no.
lea rax, [rax+rdx*4] # dst += ...
cmp rcx, rsi
ja .L2
sub rax, rdi
sar rax, 2 # address math -> element count
ret
性能：256 位向量在 Skylake-X / Cascade Lake 上可能更快
理论上，加载位图并将一个数组过滤到另一个数组的循环应该 运行 在 SKX / CSLX 上每 3 个时钟 1 个向量，无论向量宽度如何，在端口 5 上成为瓶颈。（kmovb/w/d/q k1, eax 运行s 在 p5 上，vcompressps 进入内存是 2p5 + 存储，根据 IACA 和 http://uops.info/ 测试）。
@ZachB 在评论中报告说，在实践中，使用 ZMM _mm512_mask_compressstoreu_ps 的循环比真正的 CSLX 硬件上的 _mm256_mask_compressstoreu_ps 稍慢。（我我不确定那是否是允许 256 位版本脱离“512 位矢量模式”并提高时钟频率的微基准测试，或者是否有周围的 512 位代码。）
我怀疑未对齐的存储正在损害 512 位版本。 vcompressps 可能有效地进行了掩蔽的 256 位或 512 位向量存储，如果它跨越缓存行边界，那么它必须做额外的工作。由于输出指针通常不是 16 个元素的倍数，因此整行 512 位存储几乎总是未对齐。
由于某些原因，未对齐的 512 位存储可能比缓存行拆分 256 位存储更糟糕，而且发生得更频繁；我们已经知道其他事物的 512 位矢量化似乎对对齐更敏感。这可能只是因为 运行 每次都发生拆分加载缓冲区，或者处理缓存行拆分的回退机制对于 512 位向量来说效率较低。
将 vcompressps 基准化到寄存器中会很有趣，具有单独的全向量重叠存储 。这可能是相同的 uops，但是当它是一个单独的指令时，商店可以微融合。如果屏蔽商店与重叠商店之间存在一些差异，这将揭示它。
下面评论中讨论的另一个想法是使用 vpermt2ps 为对齐的商店建立完整的向量。这个
一个无分支的实现，带有一个循环携带的依赖链，通过正在构建的向量有 4 或 6 个循环，用 vpermt2ps 和一个混合或其他东西来替换它，当它是 "full".使用对齐的向量存储每次迭代，但仅在向量已满时才移动输出指针。
这可能比当前 Intel CPU 上未对齐存储的 vcompressps 慢。
AVX2 + BMI2。请参阅我对 AVX512 的其他回答。 （更新：在 64 位版本中保存了 pdep。）
我们可以使用 AVX2 vpermps (_mm256_permutevar8x32_ps)（或等价的整数 vpermd）来进行跨车道变量随机播放。
我们可以即时生成掩码，因为 BMI2 pext (Parallel Bits Extract) 为我们提供了所需操作的按位版本。
注意 pdep/pext 在 Zen 3 之前的 AMD CPU 上 非常 慢，例如 6 微指令/18 周期延迟Ryzen Zen 1 和 Zen 2 的吞吐量。这种实现在那些 AMD CPU 上的表现会非常糟糕。对于 AMD，您可能最好使用 pshufb 或 vpermilps LUT 或评论中讨论的一些 AVX2 变量移位建议来使用 128 位向量。特别是如果您的掩码输入是矢量掩码（不是内存中已经打包的位掩码）。
Zen2之前的AMD反正只有128位的向量执行单元，256位的跨车道shuffle很慢。所以 128 位向量在 Zen 1 上对此非常有吸引力。但是 Zen 2 有 256 位 load/store 和执行单元。 （而且微编码仍然很慢 pext/pdep。）
对于具有 32 位或更宽元素的整数向量： 1) _mm256_movemask_ps(_mm256_castsi256_ps(compare_mask)).
或者 2) 使用 _mm256_movemask_epi8 然后将第一个 PDEP 常量从 0x0101010101010101 更改为 0x0F0F0F0F0F0F0F0F 以分散 4 个连续位的块。将乘以 0xFFU 更改为 expanded_mask |= expanded_mask<<4; 或 expanded_mask *= 0x11;（未测试）。无论哪种方式，使用带 VPERMD 的洗牌掩码而不是 VPERMPS。
对于 64 位整数或 double 元素，一切仍然正常；比较掩码恰好总是具有相同的 32 位元素对，因此生成的混洗将每个 64 位元素的两半放在正确的位置。 （所以您仍然使用 VPERMPS 或 VPERMD，因为 VPERMPD 和 VPERMQ 仅适用于立即控制操作数。）
对于 16 位元素，您可以使用 128 位向量进行调整。
对于 8 位元素，请参阅
算法：
从压缩的 3 位索引常量开始，每个位置都有自己的索引。即 [ 7 6 5 4 3 2 1 0 ] 其中每个元素为 3 位宽。 0b111'110'101'...'010'001'000.
使用pext将我们想要的索引提取到整数寄存器底部的连续序列中。例如如果我们想要索引 0 和 2，我们 pext 的控制掩码应该是 0b000'...'111'000'111。 pext 将获取与选择器中的 1 位对齐的 010 和 000 索引组。选定的组被打包到输出的低位，因此输出将为 0b000'...'010'000。 （即 [ ... 2 0 ]）
有关如何从输入向量掩码为 pext 生成 0b111000111 输入的注释代码。
现在我们与压缩 LUT 在同一条船上：解压缩多达 8 个压缩索引。
当你把所有的部分放在一起时，共有三个 pext/pdeps。我从我想要的东西开始倒退，所以从那个方向理解它可能也是最容易的。 （即从洗牌线开始，然后从那里向后工作。）
如果我们使用每个字节一个索引而不是压缩的 3 位组，我们可以简化解包。由于我们有 8 个索引，这仅适用于 64 位代码。
参见 this and a 32bit-only version on the Godbolt Compiler Explorer。我使用了 #ifdefs，因此它可以使用 -m64 或 -m32 进行最佳编译。 gcc 浪费了一些指令，但 clang 的代码非常好。
#include <stdint.h>
#include <immintrin.h>
// Uses 64bit pdep / pext to save a step in unpacking.
__m256 compress256(__m256 src, unsigned int mask /* from movmskps */)
{
uint64_t expanded_mask = _pdep_u64(mask, 0x0101010101010101); // unpack each bit to a byte
expanded_mask *= 0xFF; // mask |= mask<<1 | mask<<2 | ... | mask<<7;
// ABC... -> AAAAAAAABBBBBBBBCCCCCCCC...: replicate each bit to fill its byte
const uint64_t identity_indices = 0x0706050403020100; // the identity shuffle for vpermps, packed to one index per byte
uint64_t wanted_indices = _pext_u64(identity_indices, expanded_mask);
__m128i bytevec = _mm_cvtsi64_si128(wanted_indices);
__m256i shufmask = _mm256_cvtepu8_epi32(bytevec);
return _mm256_permutevar8x32_ps(src, shufmask);
}
这会编译成没有从内存加载的代码，只有立即常量。 （参见 godbolt link 和 32 位版本）。
# clang 3.7.1 -std=gnu++14 -O3 -march=haswell
mov eax, edi # just to zero extend: goes away when inlining
movabs rcx, 72340172838076673 # The constants are hoisted after inlining into a loop
pdep rax, rax, rcx # ABC -> 0000000A0000000B....
imul rax, rax, 255 # 0000000A0000000B.. -> AAAAAAAABBBBBBBB..
movabs rcx, 506097522914230528
pext rax, rcx, rax
vmovq xmm1, rax
vpmovzxbd ymm1, xmm1 # 3c latency since this is lane-crossing
vpermps ymm0, ymm1, ymm0
ret
（后来 clang 像 GCC 一样编译，用 mov/shl/sub 而不是 imul，见下文。）
因此，根据 Agner Fog's numbers and https://uops.info/，这是 6 微指令（不包括常量，或内联时消失的零扩展 mov）。在 Intel Haswell 上，它是 16c 延迟（vmovq 为 1，每个 pdep/imul/pext / vpmovzx / vpermps 为 3）。没有指令级并行性。但是，在一个循环中，这不是循环携带依赖的一部分（就像我在 Godbolt link 中包含的那个），瓶颈可能只是吞吐量，同时保持多次迭代.
这也许可以管理每 4 个周期一个的吞吐量，瓶颈在端口 1 上 pdep/pext/imul 加上循环中的 popcnt。当然，由于 loads/stores 和其他循环开销（包括比较和 movmsk），uop 总吞吐量也很容易成为问题。
例如我的 Godbolt link 中的过滤器循环是 14 微指令，带有 clang，-fno-unroll-loops 使其更易于阅读。它可能每 4c 维持一次迭代，跟上前端，如果我们幸运的话。
clang 6 和更早版本使用 popcnt's false dependency on its output 创建了一个循环承载依赖项，因此它将在 compress256 函数延迟的 3/5 处成为瓶颈。 clang 7.0 及更高版本使用 xor-zeroing 来打破错误的依赖（而不是仅仅使用 popcnt edx,edx 或类似 GCC 的东西：/）。
gcc（以及后来的 clang）使用多条指令乘以 0xFF，使用左移 8 和 sub，而不是 imul 乘以 255。这总共需要 3 uops vs . 1 用于前端，但延迟仅为 2 个周期，低于 3 个。（Haswell 在寄存器重命名阶段以零延迟处理 mov。）最重要的是，imul 只能运行 在端口 1 上，与 pdep/pext/popcnt 竞争，因此最好避免该瓶颈。
由于所有支持 AVX2 的硬件也都支持 BMI2，因此提供没有 BMI2 的 AVX2 版本可能没有意义。
如果您需要在一个很长的循环中执行此操作，那么如果初始缓存未命中被分摊到足够多的迭代中并且仅解压缩 LUT 条目的开销较低，那么 LUT 可能是值得的。你仍然需要 movmskps，所以你可以 popcnt 掩码并将其用作 LUT 索引，但是你保存了 pdep/imul/pext.
您可以使用我使用的相同整数序列解压 LUT 条目，但是当 LUT 条目在内存中开始并且不在内存中时，@Froglegs 的 set1() / vpsrlvd / vpand首先需要进入整数寄存器。 （32 位广播负载在 Intel CPU 上不需要 ALU uop）。但是，Haswell 上的可变移位是 3 微指令（但 Skylake 上只有 1 微指令）。
如果有人对此感兴趣，这里有一个 SSE2 的解决方案，它使用指令 LUT 而不是数据 LUT，也就是跳转 table。不过，使用 AVX 这将需要 256 个案例。
每次调用下面的 LeftPack_SSE2 时，它基本上使用三个指令：jmp、shufps、jmp。十六种情况中有五种不需要修改向量。
static inline __m128 LeftPack_SSE2(__m128 val, int mask) {
switch(mask) {
case 0:
case 1: return val;
case 2: return _mm_shuffle_ps(val,val,0x01);
case 3: return val;
case 4: return _mm_shuffle_ps(val,val,0x02);
case 5: return _mm_shuffle_ps(val,val,0x08);
case 6: return _mm_shuffle_ps(val,val,0x09);
case 7: return val;
case 8: return _mm_shuffle_ps(val,val,0x03);
case 9: return _mm_shuffle_ps(val,val,0x0c);
case 10: return _mm_shuffle_ps(val,val,0x0d);
case 11: return _mm_shuffle_ps(val,val,0x34);
case 12: return _mm_shuffle_ps(val,val,0x0e);
case 13: return _mm_shuffle_ps(val,val,0x38);
case 14: return _mm_shuffle_ps(val,val,0x39);
case 15: return val;
}
}
__m128 foo(__m128 val, __m128 maskv) {
int mask = _mm_movemask_ps(maskv);
return LeftPack_SSE2(val, mask);
}
将为@PeterCordes 的精彩回答添加更多信息：
我用它实现了 std::remove from C++ standard 的整数类型。一旦可以进行压缩，该算法就相对简单：加载寄存器、压缩、存储。首先，我将展示变体，然后展示基准。
我最终对提议的解决方案做出了两个有意义的变体：
__m128i寄存器，任何元素类型，使用_mm_shuffle_epi8指令__m256i寄存器，元素类型至少4个字节，使用_mm256_permutevar8x32_epi32
当 256 位寄存器的类型小于 4 个字节时，我将它们分成两个 128 位寄存器并且 compress/store 每个分开。
Link 到编译器资源管理器，您可以在其中看到完整的程序集（底部有一个 using type 和 width（每个包中的元素），您可以将其插入得到不同的变化）：https://gcc.godbolt.org/z/yQFR2t
注意：我的代码是在 C++17 中使用的自定义 simd 包装器，所以我不知道它的可读性如何。如果你想阅读我的代码 -> 大部分都在 godbolt 顶部包含的 link 后面。或者，所有代码都在 github.
@PeterCordes 对两种情况的回答的实现
注意：连同掩码，我还使用 popcount 计算剩余元素的数量。可能有不需要的情况，但是我还没见过
_mm_shuffle_epi8
- 将每个字节的索引写成半字节：
0xfedcba9876543210 - 将索引对放入 8 条短裤中，打包成
__m128i - 使用
x << 4 | x & 0x0f0f 分散它们
展开索引的例子。假设选择了第 7 个和第 6 个元素。
这意味着相应的短是：0x00fe。在 << 4 和 | 之后我们会得到 0x0ffe。然后我们清除第二个f.
完整掩码：
// helper namespace
namespace _compress_mask {
// mmask - result of `_mm_movemask_epi8`,
// `uint16_t` - there are at most 16 bits with values for __m128i.
inline std::pair<__m128i, std::uint8_t> mask128(std::uint16_t mmask) {
const std::uint64_t mmask_expanded = _pdep_u64(mmask, 0x1111111111111111) * 0xf;
const std::uint8_t offset =
static_cast<std::uint8_t>(_mm_popcnt_u32(mmask)); // To compute how many elements were selected
const std::uint64_t compressed_idxes =
_pext_u64(0xfedcba9876543210, mmask_expanded); // Do the @PeterCordes answer
const __m128i as_lower_8byte = _mm_cvtsi64_si128(compressed_idxes); // 0...0|compressed_indexes
const __m128i as_16bit = _mm_cvtepu8_epi16(as_lower_8byte); // From bytes to shorts over the whole register
const __m128i shift_by_4 = _mm_slli_epi16(as_16bit, 4); // x << 4
const __m128i combined = _mm_or_si128(shift_by_4, as_16bit); // | x
const __m128i filter = _mm_set1_epi16(0x0f0f); // 0x0f0f
const __m128i res = _mm_and_si128(combined, filter); // & 0x0f0f
return {res, offset};
}
} // namespace _compress_mask
template <typename T>
std::pair<__m128i, std::uint8_t> compress_mask_for_shuffle_epi8(std::uint32_t mmask) {
auto res = _compress_mask::mask128(mmask);
res.second /= sizeof(T); // bit count to element count
return res;
}
_mm256_permutevar8x32_epi32
这几乎是一对一的@PeterCordes 解决方案 - 唯一的区别是 _pdep_u64 位（他建议将此作为注释）。
我选择的面具是0x5555'5555'5555'5555。这个想法是——我有 32 位的 mmask，8 个整数中的每一个有 4 位。我想要得到 64 位 => 我需要将 32 位的每一位转换为 2 => 因此 0101b = 5.The 乘数也从 0xff 变为 3 因为我将为每个整数得到 0x55，而不是 1 .
完整掩码：
// helper namespace
namespace _compress_mask {
// mmask - result of _mm256_movemask_epi8
inline std::pair<__m256i, std::uint8_t> mask256_epi32(std::uint32_t mmask) {
const std::uint64_t mmask_expanded = _pdep_u64(mmask, 0x5555'5555'5555'5555) * 3;
const std::uint8_t offset = static_cast<std::uint8_t(_mm_popcnt_u32(mmask)); // To compute how many elements were selected
const std::uint64_t compressed_idxes = _pext_u64(0x0706050403020100, mmask_expanded); // Do the @PeterCordes answer
// Every index was one byte => we need to make them into 4 bytes
const __m128i as_lower_8byte = _mm_cvtsi64_si128(compressed_idxes); // 0000|compressed indexes
const __m256i expanded = _mm256_cvtepu8_epi32(as_lower_8byte); // spread them out
return {expanded, offset};
}
} // namespace _compress_mask
template <typename T>
std::pair<__m256i, std::uint8_t> compress_mask_for_permutevar8x32(std::uint32_t mmask) {
static_assert(sizeof(T) >= 4); // You cannot permute shorts/chars with this.
auto res = _compress_mask::mask256_epi32(mmask);
res.second /= sizeof(T); // bit count to element count
return res;
}
基准测试
处理器：Intel Core i7 9700K（现代消费者级别 CPU，不支持 AVX-512）
编译器：clang，从版本 10 版本附近的主干构建
编译器选项：--std=c++17 --stdlib=libc++ -g -Werror -Wall -Wextra -Wpedantic -O3 -march=native -mllvm -align-all-functions=7
微基准库：google benchmark
控制代码对齐：
如果您不熟悉这个概念，请阅读 this or watch this
基准测试二进制文件中的所有函数都与 128 字节边界对齐。每个基准测试函数被复制 64 次，在函数的开头（进入循环之前）有一个不同的 noop 幻灯片。我显示的主要数字是每次测量的最小值。我认为这是可行的，因为该算法是内联的。我也得到了非常不同的结果这一事实的验证。在答案的最底部，我展示了代码对齐的影响。
注：benchmarking code。 BENCH_DECL_ATTRIBUTES 只是 noinline
Benchmark 从数组中删除一定百分比的 0。我用 {0, 5, 20, 50, 80, 95, 100} 百分比的零测试数组。
我测试了 3 种大小：40 字节（看看这是否适用于非常小的数组）、1000 字节和 10'000 字节。我按大小分组，因为 SIMD 取决于数据的大小而不是元素的数量。元素计数可以从元素大小得出（1000 字节是 1000 个字符，但 500 个短裤和 250 个整数）。由于非 simd 代码所需的时间主要取决于元素数量，因此字符的胜利应该更大。
绘图：x - 零的百分比，y - 以纳秒为单位的时间。 padding : min 表示这是所有对齐中的最小值。
40 字节数据，40 个字符
对于 40 字节，即使对于字符，这也没有意义 - 当在非 simd 代码上使用 128 位寄存器时，我的实现速度大约慢 8-10 倍。因此，例如，编译器在执行此操作时应小心。
1000 字节数据，1000 个字符
显然，非 simd 版本主要由分支预测决定：当我们得到少量零时，我们得到的加速较小：对于没有 0 的情况 - 大约 3 倍，对于 5% 的零 - 大约 5-6 倍的速度向上。当分支预测器无法帮助非 simd 版本时 - 大约有 27 倍的加速。这是一个有趣的 属性 simd 代码，它的性能往往不太依赖于数据。使用 128 和 256 寄存器几乎没有区别，因为大部分工作仍然分为 2 128 个寄存器。
1000 字节数据，500 条短裤
短裤的结果相似，只是增益小得多 - 最多 2 倍。 我不知道为什么短裤比非 simd 代码的字符要好得多：我希望短裤快两倍，因为只有 500 条短裤，但差异实际上高达 10 倍。
1000 字节数据，250 个整数
对于 1000，只有 256 位版本是有意义的 - 20-30% 获胜，不包括任何 0 以删除所有内容（完美的分支预测，非 simd 代码不删除）。
10'000 个字节的数据，10'000 个字符
与 1000 个字符相同的数量级获胜：分支预测器有帮助时快 2-6 倍，无帮助时快 27 倍。
同样的剧情，只有simd版本：
在这里我们可以看到使用 256 位寄存器并将它们分成 2 128 位寄存器大约有 10% 的优势：大约快 10%。它的大小从 88 条指令增加到 129 条指令，这不是很多，因此根据您的用例可能有意义。对于基线 - 非 simd 版本是 79 条指令（据我所知 - 虽然这些指令比 SIMD 指令小）。
10'000 字节数据，5'000 条短裤
从 20% 到 9 次获胜，具体取决于数据分布。未显示 256 位和 128 位寄存器之间的比较 - 它与字符的汇编几乎相同，并且 256 位的相同赢取了大约 10%。
10'000 个字节的数据，2'500 个整数
似乎使用 256 位寄存器很有意义，这个版本比 128 位寄存器快大约 2 倍。与非 simd 代码进行比较时 - 从 20% 的胜率和完美的分支预测到 3.5 - 4 倍，如果不是的话。
结论：当你有足够的数据量（至少 1000 字节）时，这对于没有 AVX-512[=54= 的现代处理器来说是一个非常值得的优化]
PS:
要删除的元素百分比
一方面，过滤一半的元素并不常见。另一方面，在排序过程中可以在分区中使用类似的算法 => 实际上预计会有 ~50% 的分支选择。
代码对齐影响
问题是：如果代码恰好对齐不好，值多少钱
（一般来说 - 对此无能为力）。
我只显示 10'000 字节。
对于每个百分比点，图中有两条线表示最小值和最大值（意思是 - 它不是一个 best/worst 代码对齐 - 它是给定百分比的最佳代码对齐）。
代码对齐影响 - 非 simd
字符数：
从分支预测差的 15-20% 到分支预测有很大帮助的 2-3 倍。 （已知分支预测器会受到代码对齐的影响）。
短裤：
出于某种原因 - 0% 完全不受影响。可以解释为 std::remove 首先进行线性搜索以找到要删除的第一个元素。显然，对短裤的线性搜索不受影响。
除此之外 - 从 10% 到 1.6-1.8 倍价值
整数：
与短裤相同 - 没有 0 不受影响。一旦我们进入删除部分，它就会从 1.3 倍增加到 5 倍，然后是最佳情况对齐。
代码对齐影响 - simd 版本
不显示短裤和整数 128，因为它与字符的汇编几乎相同
Chars - 128 位寄存器
Chars - 256 位寄存器
Ints - 256 位寄存器
我们可以看到，对于算法的 simd 版本，与非 simd 版本相比，代码对齐的影响要小得多。我怀疑这是因为实际上没有分支。
这可能有点晚了，尽管我最近 运行 解决了这个确切的问题并找到了一个使用严格 AVX 实现的替代解决方案。如果您不关心解压缩的元素是否与每个向量的最后一个元素交换，这也可以。以下为AVX版本：
inline __m128 left_pack(__m128 val, __m128i mask) noexcept
{
const __m128i shiftMask0 = _mm_shuffle_epi32(mask, 0xA4);
const __m128i shiftMask1 = _mm_shuffle_epi32(mask, 0x54);
const __m128i shiftMask2 = _mm_shuffle_epi32(mask, 0x00);
__m128 v = val;
v = _mm_blendv_ps(_mm_permute_ps(v, 0xF9), v, shiftMask0);
v = _mm_blendv_ps(_mm_permute_ps(v, 0xF9), v, shiftMask1);
v = _mm_blendv_ps(_mm_permute_ps(v, 0xF9), v, shiftMask2);
return v;
}
本质上，val 中的每个元素都使用位域向左移动一次，0xF9 以便与其未移位的变体混合。接下来，将移位和未移位版本与输入掩码混合（第一个非零元素广播到其余元素 3 和 4）。再重复此过程两次，在每次迭代中将 mask 的第二个和第三个元素广播到其后续元素，这应该提供 _pdep_u32() BMI2 指令的 AVX 版本。
如果您没有 AVX，您可以轻松地将每个 _mm_permute_ps() 替换为 _mm_shuffle_ps() 以获得 SSE4.1 兼容版本。
如果您使用的是双精度，这里是 AVX2 的附加版本：
inline __m256 left_pack(__m256d val, __m256i mask) noexcept
{
const __m256i shiftMask0 = _mm256_permute4x64_epi64(mask, 0xA4);
const __m256i shiftMask1 = _mm256_permute4x64_epi64(mask, 0x54);
const __m256i shiftMask2 = _mm256_permute4x64_epi64(mask, 0x00);
__m256d v = val;
v = _mm256_blendv_pd(_mm256_permute4x64_pd(v, 0xF9), v, shiftMask0);
v = _mm256_blendv_pd(_mm256_permute4x64_pd(v, 0xF9), v, shiftMask1);
v = _mm256_blendv_pd(_mm256_permute4x64_pd(v, 0xF9), v, shiftMask2);
return v;
}
另外_mm_popcount_u32(_mm_movemask_ps(val))可以用来判断left-packing后剩余的元素个数