assembly - 在 x86 程序集中存储大量布尔值的最佳方法是什么？

对于稀疏位集（除了少数例外，全部为真或全部为假），您可以使用任何集合数据结构（包括哈希表）存储一组索引。您当然可以在 asm 中手动实现任何算法，就像在 C 中一样。可能有一些更专业的数据结构适用于各种目的/用例。

对于“正常”的布尔数组，您的两个主要选项是

每个字节解压 1 个布尔值，值 0 / 1 像 C 一样bool arr[size]
（在.bss或动态分配的，无论你想放在哪里，与任何字节数组相同）。

占用压缩位数组的 8 倍空间（因此缓存占用空间），但非常易于使用。对于随机访问特别有效，尤其是写入，因为您可以存储一个字节而不会干扰其邻居。（不必读取/修改/写入包含的字节或双字）。

如果缓存占用空间加上其余数据不适合任何级别的缓存，则会导致更多缓存未命中，此外，较低的密度也不利于搜索、弹出计数、复制或设置/清除一系列元素。

如果可以在写入数组的代码中保存指令，则可以允许 0 / 非 0 而不是 0 / 1。但是，如果你想比较两个元素，或者计算真实值或其他什么，这可能会在阅读时花费说明。请注意，大多数 C/C++ ABI 严格使用 0 / 1 字节bool，并且将 abool保存 a传递2给 C 函数可能会使其崩溃。
每比特打包 1 个 bool ，如 C++std::vector<bool>。（除了你当然可以将它存储在任何你想要的地方，不像 std::vector 总是动态分配）。

Howard Hinnant 的文章Onvector<bool>讨论了位数组擅长的一些事情（通过适当优化的实现），例如搜索 atrue可以一次检查整个块，例如使用 qword 搜索一次 64 位，或 256 位一次与 AVX vptest。（然后tzcnt或bsf当您找到一个非零块时，或多或少与字节元素相同：有效地找到大数组中的最低有效位？）。因此，比使用字节数组快 8 倍（即使假设缓存命中相同），除了使用 SIMD 进行向量化时的一些额外工作，以在向量中找到正确的字节或 dword 后找到元素中的位。与字节数组相比，只是vpslld $7, %ymm0, %ymm0和vpmovmskb %ymm0, %eax/bsf %eax,%eax将字节转换为位图并进行搜索。

x86位数组又名位串指令：mem操作数慢

x86确实有位数组指令，例如bt(Bit Test) 和bts(Bit Test and Set)，还有 Reset (clear) 和 Complement (flip)，但是它们在内存目标和寄存器位索引方面很慢；实际上，手动索引正确的字节或双字并加载它，然后使用bts %reg,%reg并存储结果会更快。使用 bts 汇编指令和 gcc 编译器

# fast version:
# set the bit at index n (RSI) in bit-array at RDI
   mov  %esi, %edx           # save the original low bits of the index
   shr  $5, %rsi             # dword index = bit-index / 8 / 4
   mov  (%rdi, %rsi, 4), %eax   # load the dword containing the bit
   bts  %edx, %eax           # eax |= 1 << (n&31)   BTS reg,reg masks the bit-index like shifts
   mov  %eax, (%rdi, %rsi)   # and store it back

这有效地将位索引拆分为双字索引和双字内位索引。dword 索引是通过移位显式计算的（并使用缩放索引寻址模式转换回对齐 dword 的字节偏移量）。bit-within-dword 索引是隐式计算的，作为bts %reg,%reg掩码计数的一部分。

（如果您的位数组肯定小于 2^32 位（512 MiB），您可以通过使用来节省一个字节的代码大小shr $5, %esi，丢弃位索引的高 32 位。）

这会在 CF 中留下旧位的副本，以防万一。 bts reg,reg在 Intel 上是单 uop，在 AMD 上是 2 uop，因此绝对值得与手动执行mov $1, %reg/ shl/相比or。

这在现代英特尔 CPU（https://uops.info/和https://agner.org/optimize/）上只有 5 微指令，而 10 微指令的bts %rsi, (%rdi)作用完全相同（但不需要任何 tmp 寄存器）。

你会注意到我只使用了 dword 块，不像在 C 中你经常看到代码使用unsigned long或uint64_t块，所以搜索可以快速进行。但是在 asm 中，使用不同大小的访问相同的内存是零问题，除了存储转发停顿，如果你先做一个窄存储然后再做一个宽负载。更窄的 RMW 操作实际上更好，因为它意味着不同位上的操作可以更接近，而不会实际创建错误的依赖关系。如果这是一个主要问题，您甚至可以使用字节访问，但bts朋友只能降低到 16 位word操作数大小，因此您必须手动and $7, %reg从位索引中提取位内字节。

例如像这样阅读：

# byte chunks takes more work:
   mov  %esi, %edx      # save the original low bits
   shr  $3, %rsi        # byte index = bit-index / 8
   movzbl (%rdi, %rsi), %eax   # load the byte containing the bit
   and  $7, %edx
   bt   %edx, %eax      # CF = eax & 1 << (n&7)
   # mov  %al, (%rdi, %rsi)   if you used BTS, BTR, or BTC

字节加载最好使用movzx（aka AT&T movzbl）来避免写入部分寄存器。

如果您需要自动设置一些位（例如在多线程程序中），您可以lock bts %reg, mem，或者您可以1<<(n&31)在寄存器中生成，lock or %reg, mem如果您不关心旧值是什么。 lock bts无论如何都是缓慢和微编码的，所以如果你需要原子性，你可以只使用它而不是试图避免疯狂的 CISC 位数组语义。

在多线程的情况下，有更多理由考虑每个字节使用 1 个 bool，这样您就可以使用普通movb $1, (%rdi, %rsi)的（保证原子并且不会干扰其邻居：现代 x86 硬件可以不将单个字节存储到内存吗？），而不是原子 RMW。

assembly - 在 x86 程序集中存储大量布尔值的最佳方法是什么？

问题描述

解决方案

x86位数组又名位串指令：mem操作数慢

推荐阅读