基于BitMask在数组中设置值的内在特性

Question

在输入数组中的所有位置，在所提供的BitMask中对应位置有1位的位置，是否有一个内部设置值？

10101010是位掩码

值为121

它将设置价值121的0、2、4、6的头寸。

Answer 1

和AVX512一起，是的。在AVX512，蒙面商店是一流的业务。

将位掩码用作向量存储到数组的AVX512掩码，使用_mm512_mask_storeu_epi8 (void* mem_addr, __mmask64 k, __m512i a) vmovdqu8。(AVX512BW.使用AVX512F，您只能使用32或64位的元素大小。)

#include <immintrin.h>
#include <stdint.h>

void set_value_in_selected_elements(char *array, uint64_t bitmask, uint8_t value) {
    __m512i broadcastv = _mm512_set1_epi8(value);
    // integer types are implicitly convertible to/from __mmask types
    // the compiler emits the KMOV instruction for you.
    _mm512_mask_storeu_epi8 (array, bitmask, broadcastv);
}

这会将)编译为：

    vpbroadcastb    zmm0, edx
    kmovq   k1, rsi
    vmovdqu8        ZMMWORD PTR [rdi]{k1}, zmm0
    vzeroupper
    ret

如果要在位图为零的元素中写入零，可以使用零掩蔽移动从掩码创建常量并将其存储，或者使用AVX512BW或DQ __m512i _mm512_movm_epi8(__mmask64 )创建0/ -1向量。其他元素大小也可用。但是，当数组大小不是向量宽度的倍数时，使用蒙面存储可以安全地使用它，因为未修改的元素不会被读取/重写或其他任何东西；它们确实没有被触摸。(不过，如果任何未触及的元素在真正的存储上发生故障，CPU可以获得缓慢的微码辅助。)

没有AVX512，您仍然需要“一个内在的”(单数)。

有pdep，您可以使用它将位图展开为字节映射。有关使用my AVX2 left-packing answer将mask中的每个位解压缩为一个字节的示例，请参阅_pdep_u64(mask, 0x0101010101010101);。这在uint64_t中给出了8个字节。在C中，如果在该数组和数组之间使用union，那么它将给出一个0/1元素的数组。(当然，索引数组需要编译器发出移位指令，如果它还没有先在某个地方溢出的话)。您可能只想将memcpy uint64_t放入一个永久数组中。)

但是在更一般的情况下(更大的位图)，甚至当您想要根据位掩码混合新的值时，也应该使用多个本质来实现pmovmskb的逆，并使用它来混合。(参见下面的无一节)

通常，如果数组适合64位(例如，8元素char数组)，则可以使用pdep。或者，如果它是一个4位小咬的数组，那么你可以做一个16位的掩码，而不是8位。

否则，就没有单一的指令，也就没有内在的指令。对于较大的位图，您可以将其处理为8位块，并将8字节块存储到数组中。

如果数组元素大于8位(而且您没有AVX512)，则可能仍然应该用pdep将位展开为字节，然后使用[v]pmovzx从字节扩展到dword或向量中的任何东西。例如：

// only the low 8 bits of the input matter
__m256i bits_to_dwords(unsigned bitmap) {
    uint64_t mask_bytes = _pdep_u64(bitmap, 0x0101010101010101);  // expand bits to bytes
    __m128i byte_vec = _mm_cvtsi64x_si128(mask_bytes);
    return _mm256_cvtepu8_epi32(byte_vec);
}

如果您想让元素不被修改，而不是将它们设置为零(位掩码在位掩码中为零--，或与前面的内容一起使用，而不是赋值/存储)，则为。

在C/ C++ (与asm相比)中表示这是相当不方便的。要将8个字节从uint64_t复制到char数组中，您可以(而且应该)只使用memcpy (以避免由于指针混叠或对齐uint64_t*而导致的任何未定义行为)。这将用现代编译器编译成一个8字节的存储区。

但是要将它们放入其中，则必须对uint64_t的字节编写一个循环，或者将char数组转换为uint64_t*。这通常很好，因为char*可以别名任何东西，这样以后读取char数组就不会有任何严格的别名UB了。但是，如果编译器假设uint64_t*在自动向量化时是对齐的，那么即使在x86上也会出现问题。Why does unaligned access to mmap'ed memory sometimes segfault on AMD64?

分配的值不是0/ 1

使用乘0xFF将0/1字节的掩码转换为0/ -1掩码，然后使用uint64_t将值广播到所有字节位置。

如果不想将元素设置为零或value=121，那么即使数组中有字节元素，也应该使用SSE2 / SSE4或AVX2。使用字节掩码作为控制向量加载旧内容vpblendvb和set1(121) .

vpblendvb只使用每个字节的高位，所以您的pdep常数可以是0x8080808080808080，将输入位分散到每个字节的高位，而不是低位。(所以你不需要被0xFF乘以就可以得到一个和掩码)。

如果元素是dword或更大，则可以使用_mm256_maskstore_epi32。(在将掩码从字节扩展到dword时，使用pmovsx而不是zx复制符号位)。这可能是对变量混合+总是读/重写的一个额外的胜利。Is it possible to use SIMD instruction for replace?。

无pdep

pdep在Ryzen上速度很慢，即使是英特尔，这也不是最好的选择。

另一种方法是将位掩码转换为矢量掩码：is there an inverse instruction to the movemask instruction in intel avx2?和

epi8 (VPMOVMSKB)?。

也就是说，将你的位图广播到向量的每一个位置(或者在对应的字节中对位图的正确位进行洗牌)，并使用SIMD并为该字节屏蔽适当的位。然后，对和掩码使用pcmpeqb/w/d来查找设置其位的元素。

如果不想在位图为零的地方存储零，则可能需要加载/混合/存储。

使用比较掩码在您的value上混合，例如与_mm_blendv_epi8或256位AVX2版本。您可以用16位块处理位图，只需一个pshufb就可以生成16字节的向量，将其字节发送到正确的元素。

但是，即使多线程的位图不相交，多个线程在同一数组上同时执行此操作也是不安全的，除非您使用蒙面存储。