基于 BitMask 在数组中设置值的本质

Question

是否有一个内在函数可以在输入数组中的所有位置设置单个值，其中相应位置在提供的 BitMask 中具有 1 位？

10101010 是位掩码

值为 121

它将设置位置 0,2,4,6 值为 121

Answer 1

对于 AVX512，是的。蒙面商店是 AVX512 中的一流操作。

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

#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);
}

这编译（使用 gcc7.3 -O3 -march=skylake-avx512）为：

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

如果要在位图为零的元素中写入零，请使用零掩码移动从掩码创建常量并将其存储，或者使用 AVX512BW 或 DQ 创建 0 / -1 向量__m512i _mm512_movm_epi8(__mmask64 )。其他元件尺寸可供选择。但是，当数组大小不是向量宽度的倍数时，使用屏蔽存储可以安全地使用它，因为未修改的元素不会被读取/重写或任何其他操作；他们确实原封不动。（不过，如果任何未触及的元素在真实存储上出现故障，CPU 可能会采取缓慢的微代码协助。）

如果没有 AVX512，您仍然要求“内在的”（单数）。

有pdep，您可以使用它将位图扩展为字节图。有关使用将每个位解包为一个字节的示例，请参阅我的 AVX2 left-packing 答案。这为您提供了 8 个字节。在 C 中，如果您在该数组和数组之间使用 a，那么它会为您提供一个包含 0 / 1 个元素的数组。（但是当然，索引数组将要求编译器发出移位指令，如果它没有首先将其溢出到某个地方。您可能只想将其放入永久数组中。）_pdep_u64(mask, 0x0101010101010101);maskuint64_tunionmemcpyuint64_t

但在更一般的情况下（较大的位图），或者即使有 8 个元素，当您想要基于位掩码混合新值时，您应该使用多个内在函数来实现 的逆pmovmskb，并使用它来混合。（参见下面的无pdep部分）

一般来说，如果您的数组适合 64 位（例如 8 元素字符数组），您可以使用pdep. 或者，如果它是 4 位半字节数组，那么您可以使用 16 位掩码而不是 8 位掩码。

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

如果您的数组元素比 8 位宽（并且您没有 AVX512），您可能仍然应该使用 将位扩展为字节pdep，但然后使用[v]pmovzx将字节扩展为双字或向量中的任何内容。例如

// 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 个字节从 a 复制uint64_t到 char 数组中，您可以（并且应该）只使用memcpy(以避免由于指针别名或未对齐而导致任何未定义的行为uint64_t*)。这将使用现代编译器编译为单个 8 字节存储。

但要对它们进行“或”操作，您要么必须在 的字节上编写一个循环uint64_t，要么将 char 数组转换为uint64_t*。这通常工作得很好，因为char*可以为任何内容设置别名，因此稍后读取 char 数组不会有任何严格别名 UB。但是，如果编译器在自动向量化时 假设它是对齐的，那么即使在 x86 上，未对齐也uint64_t* 可能会导致问题。为什么在 AMD64 上对 mmap 内存的未对齐访问有时会出现段错误？

指定 0 / 1 以外的值

使用乘以0xFF将 0/1 字节的掩码转换为 0 / -1 掩码，然后与将uint64_t您的值广播到所有字节位置的 a 进行 AND 运算。

如果您想保持元素不被修改而不是将它们设置为零或value=121，则即使您的数组具有字节元素，您也应该使用 SSE2 / SSE4 或 AVX2 。加载旧内容，vpblendvb使用set1(121)字节掩码作为控制向量。

vpblendvb仅使用每个字节的高位，因此您的pdep常量可以是0x8080808080808080将输入位分散到每个字节的高位，而不是低位。（所以你不需要乘以0xFF得到 AND 掩码）。

如果您的元素是双字或更大，您可以使用_mm256_maskstore_epi32. （将pmovsx掩码从字节扩展为双字时，使用而不是 zx 来复制符号位）。这可能是优于变量混合 + 始终读取/重写的性能优势。 是否可以使用SIMD指令进行替换？。

没有pdep

pdep在 Ryzen 上速度非常慢，即使在 Intel 上它也可能不是最佳选择。

另一种方法是将位掩码转换为向量掩码： intel avx2 中是否有与 movemask 指令相反的指令？以及
如何执行 _mm256_movemask_epi8 (VPMOVMSKB) 的逆操作？。

即，将位图广播到向量的每个位置（或对其进行洗牌，以便将位图的正确位放入相应的字节中），并使用 SIMD AND 来屏蔽该字节的相应位。然后使用pcmpeqb/w/dAND 掩码来查找已设置位的元素。

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

使用比较掩码来混合您的value，例如_mm_blendv_epi8256 位 AVX2 版本。您可以处理 16 位块中的位图，生成 16 字节向量，只需pshufb将其字节发送到正确的元素。

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