c++ - 将两位数转换为低内存表示的最快方法

大多数 ISA 都具有对位扫描指令的硬件支持，该指令用于查找设置位的位置。 对于您关心此快速运行的任何架构，请使用它而不是天真的循环或 bithack。 https://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious有一些总比没有好的技巧，但这些技巧仍然比单一的高效 asm 指令差得多。

但是 ISO C++ 并没有可移植地暴露clz/ctz操作；它只能通过内在函数/内置函数用于各种实现。（并且 x86 内在函数具有全零输入的怪癖，对应于 asm 指令行为）。

对于某些 ISA，它是一个 count-leading-zeros 给你31 - highbit_index。对于其他人来说，这是一个 CTZ 计数尾随零操作，为您提供低位的索引。x86 两者都有。（而且它的高位查找器实际上是直接找到高位索引，而不是前导零计数，除非您使用 BMI1lzcnt而不是传统的bsr） https://en.wikipedia.org/wiki/Find_first_set有一个表说明有什么不同ISA 有。

GCC 可移植地提供__builtin_clz和__builtin_ctz; 在没有硬件支持的 ISA 上，它们编译为对辅助函数的调用。 请参阅在 C 中查找整数中最高设置位 (msb) 的最快/最有效方法是什么？和__builtin_clz 的实现

（对于 64 位整数，您需要long long版本：如__builtin_ctzll GCC 手册。）

如果我们只有一个 CLZ，请使用high=63-CLZ(n)和隔离低位low= 63-CLZ((-n) & n)。请注意，x86 的bsr指令实际上会产生63-CLZ()，即位索引而不是前导零计数。所以63-__builtin_clzll(n)可以在 x86 上编译成单条指令；IIRC gcc 确实注意到了这一点。如果 GCC 使用额外的异或归零来避免不方便的错误依赖，则为 2 条指令。

如果我们只有 CTZ，请执行low = CTZ(n)并high = CTZ(n & (n - 1))清除最低设置位。 （保留高位，假设该数字恰好有 2 个设置位）。

如果我们两者都有，low = CTZ(n)并且high = 63-CLZ(n)。我不确定 GCC 在非 x86 ISA 上做了什么，因为它们不是原生可用的。即使针对没有它的硬件，GCC 内置程序也始终可用。但是内部实现不能使用上述技巧，因为它不知道总是有 2 位被设置。

（我写出了完整的公式；这个答案的早期版本在这部分中反转了 CLZ 和 CTZ。我发现这很容易发生在我身上，尤其是当我还必须跟踪 x86bsr和bsr（位扫描反向和正向）并记住那些分别领先和落后。）

因此，如果您同时使用 CTZ 和 CLZ，您最终可能会对其中一个进行缓慢的仿真。rbit或者在 ARM 上使用to bit-reverse for 进行快速仿真clz，这 100% 没问题。

AVX512CD 具有用于 64 位整数的SIMDVPLZCNTQ，因此您可以在最近的 Intel CPU 上并行编码 2、4 或 8 个 64 位整数。对于 SSSE3 或 AVX2，您可以使用pshufb _mm_shuffle_epi8byte-shuffle 作为 4 位 LUT 并结合_mm_max_epu8. 最近有一个关于此的问答，但我找不到。（它可能仅适用于 16 位整数；更宽需要更多工作。）

有了这个，一旦考虑到打包结果的吞吐量成本，Skylake-X 或 Cascade Lake CPU 可能每 2 或 3 个时钟周期压缩 8x 64 位整数。SIMD 对于将 12 位或 11 位结果打包成一个连续的比特流当然很有用，例如，如果您想对结果执行此操作，则可以使用可变移位指令。在约 3 或 4GHz 的时钟速度下，单线程每个时钟可能会使您超过 100 亿。但前提是输入来自连续内存。根据您想要对结果执行的操作，可能会花费更多的周期来完成更多操作，而不仅仅是将它们打包成 16 位整数。例如打包成比特流。但是 SIMD 应该适用于可变移位指令，该指令可以将每个寄存器的 11 位或 12 位排列到正确的位置，以便在改组后一起进行 OR 运算。

编码效率和编码性能之间存在权衡。将 12 位用于两个 6 位索引（位位置）对于压缩和解压缩都非常简单，至少在具有位扫描指令的硬件上是这样。

或者代替位索引，一个或两个可能是前导零计数，因此解码将是(1ULL << 63) >> a。 1ULL>>63是一个固定常量，您实际上可以右移，或者编译器可以将其转换为1ULL << (63-a)IIRC1 << (-a)在汇编中针对 x86 等 ISA 优化的左移，其中移位指令屏蔽移位计数（仅查看低 6 位） .

此外，2x 12 位是字节的整数，但如果要打包它们，11 位只会为每 8 个输出提供整数字节。所以索引一个位压缩数组更简单。

0 仍然是一个特殊情况：可能通过使用全为位索引（即索引 = 位 63，它在低 56 位之外）来处理。在解码/解压缩时，您设置 2 位位置(1ULL<<a) | (1ULL<<b)，然后&屏蔽以清除高位。或偏向您的位索引并解码右移 1。

如果我们不必处理零，那么现代 x86 CPU 可以每秒执行 1 或 20 亿次编码，前提是它不需要执行任何其他操作。例如，Skylake 的位扫描指令每个时钟吞吐量为 1，并且应该能够以每 2 个时钟 1 个数字进行编码，这只是瓶颈。（或者使用 SIMD 可能会更好）。只需 4 条标量指令，我们就可以获得低位和高位索引（64 位tzcnt+ bsr），移位 6 位，然后或一起。¹ 或在 AMD 上，避免bsr/bsf并手动执行 63- lzcnt。

input == 0不过，将最终结果设置为任何硬编码常量（如）的分支或无分支检查63 , 63应该很便宜。

像 AArch64 这样的其他 ISA 的压缩也很便宜。它有clz但没有ctz。可能你最好的选择是使用一个内在的 forrbit来位反转一个数字（所以clz位反转的数字直接给你低位的位索引。现在是反转版本的高位。）假设rbit是与add/一样快sub，这比使用多条指令清除低位便宜。

如果您真的想要 11 位，那么您需要避免 2x 6 位的冗余能够使任一索引大于另一个。比如可能有 6-bita和 5-bit b，并且有a<=b一些特别的意思，比如b+=32. 我还没有完全考虑到这一点。您需要能够对靠近寄存器顶部或底部的 2 个相邻位进行编码，或者如果我们考虑像 56 位循环一样在边界处回绕，则 2 个设置位可能相距 28 位。

Melpomene 提出的隔离低位和高位设置的建议可能作为其他东西的一部分有用，但仅适用于在只有一个位扫描方向可用的目标上进行编码，而不是两者兼有。即便如此，您实际上也不会同时使用这两种表达方式。前导零计数不需要您隔离低位，您只需清除它即可获得高位。

脚注 1：x86 上的解码也很便宜： x |= (1<<a)是 1 条指令：bts. 但是许多编译器错过了优化并且没有注意到这一点，而是实际上将1. bts reg, reg自 PPro 以来，Intel 上的延迟为 1 uop / 1 周期延迟，有时在 AMD 上为 2 uop。（只有内存目标版本很慢。） https://agner.org/optimize/

AMD CPU 上的最佳编码性能需要 BMI1 tzcnt/lzcnt因为bsr并且bsf速度较慢（6 uops 而不是 1 https://agner.org/optimize/）。在 Ryzen 上，lzcnt是 1 uop，1c 延迟，每时钟 4 吞吐量。但是tzcnt是2微秒。

使用 BMI1，编译器可以blsr用来清除寄存器的最低设置位（并复制它）。即现代 x86 有一条指令，dst = (SRC-1) bitwiseAND ( SRC );在 Intel 上是单 uop，而在 AMD 上是 2 uop。

但是lzcnt由于比tzcntAMD Ryzen 更高效，AMD 最好的 asm 可能不会使用它。

或者可能是这样的（假设正好是 2 位，显然我们可以做到）。

（这个 asm 是你想让你的编译器发出的。实际上不要使用内联 asm！）

Ryzen_encode_scalar:    ; input in RDI, output in EAX
   lzcnt    rcx, rdi       ; 63-high bit index
   tzcnt    rdx, rdi       ; low bit

   mov      eax, 63
   sub      eax, ecx

   shl      edx, 6
   or       eax, edx       ; (low_bit << 6) | high_bit

   ret                     ; goes away with inlining.

移动低位索引可以平衡关键路径的长度，如果我们需要63-CLZ高位，则可以实现更好的指令级并行性。

吞吐量：总共 7 微指令，并且没有执行单元瓶颈。因此，在每个时钟流水线宽度为 5 uop 时，这比每 2 个时钟 1 个要好。

Skylake_encode_scalar:    ; input in RDI, output in EAX
   tzcnt    rax, rdi       ; low bit.  No false dependency on Skylake.  GCC will probably xor-zero RAX because there is on Broadwell and earlier.
   bsr      rdi, rdi       ; high bit index.  same,same reg avoids false dep
   shl      eax, 6
   or       eax, edx

   ret                     ; goes away with inlining.

这从输入到输出有 5 个周期延迟：位扫描指令在 Intel 上是 3 个周期，而在 AMD 上是 1 个周期。SHL + OR 每加 1 个循环。

对于吞吐量，我们仅在每个周期（执行端口 1）进行一次位扫描的瓶颈，因此我们可以每 2 个周期进行一次编码，并为加载、存储和循环开销（或其他东西）留出 4 uop 的前端带宽)，假设我们有多个独立的编码要做。

（但是对于多个独立编码的情况，如果存在廉价的仿真vplzcntq并且数据来自内存，那么 SIMD 对 AMD 和 Intel 来说可能仍然更好。）

标量解码可以是这样的：

decode:    ;; input in EDI, output in RAX
    xor   eax, eax           ; RAX=0
    bts   rax, rdi           ; RAX |= 1ULL << (high_bit_idx & 63)

    shr   edi, 6             ; extract low_bit_idx
    bts   rax, rdi           ; RAX |= 1ULL << low_bit_idx

    ret

这有 3 个班次（包括bts），在 Skylake 上只能在端口 0 或端口 6 上运行。所以在英特尔上，前端只需要 4 微秒（所以每个时钟 1 微秒作为做其他事情的一部分）。但如果只这样做，它会成为每 1.5 个时钟周期 1 次解码的移位吞吐量的瓶颈。

在 4GHz CPU 上，每秒解码 26.66 亿次，所以是的，我们在达到您的目标方面做得很好:)

或者 Ryzen，bts reg,reg是 2 uop，吞吐量为 0.5c，但shr可以在任何端口上运行。所以它不会从中窃取吞吐量bts，整件事是 6 微秒（而 Ryzen 的管道在最窄处是 5 宽）。所以每 1.2 个时钟周期 1 次编码，只是前端成本的瓶颈。

在 BMI2 可用的情况下，从1寄存器中的 a 开始并使用shlx rax, rbx, rdi可以用单个 uop 替换 xor-zeroing + first BTS，假设1寄存器中的 in 可以在循环中重复使用。

（此优化完全取决于您的编译器来查找；无标志移位只是更有效的复制和移位方法，可用于-march=haswellor-march=znver1或其他具有 BMI2 的目标。）

无论哪种方式，您都只是retval = 1ULL << (packed & 63)为了解码第一位而编写。但是，如果您想知道哪些编译器在这里编写了不错的代码，那么这就是您要寻找的。

c++ - 将两位数转换为低内存表示的最快方法

问题描述

解决方案

推荐阅读