fastest way to convert two-bit number to low-memory representation

Question

I have a 56-bit number with potentially two set bits, e.g., 00000000 00000000 00000000 00000000 00000000 00000000 00000011. In other words, two bits are distributed among 56 bits, so that we have bin(56,2)=1540 possible permutations.

I now look for a loss-free mapping of such an 56 bit number to an 11-bit number that can carry 2048 and therefore also 1540. Knowing the structure, this 11-bit number is enough to store the value of my low-density (of ones) 56 bit number.

我想最大化性能（如果可能，此功能每秒应运行数百万甚至数十亿次）。到目前为止，我只想出了一些循环：

int inputNumber = 24; // 11000
int bitMask = 1;
int bit1 = 0, bit2 = 0;    
for(int n = 0; n < 54; ++n, bitMask *= 2)
{
    if((inputNumber & bitMask) != 0)
    {
        if(bit1 != 0)
            bit1 = n;
        else
        {
            bit2 = n;
            break;
        }
    }
}

并使用这两位，我可以轻松生成最大1540个数字。

但是，没有比使用这种循环更快的版本了吗？

Answer 1

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

但是，ISO C ++并没有公开地公开clz/ ctz操作。它只能通过内部函数/内置函数用于各种实现。（x86内部函数对于全零输入具有怪癖，这与asm指令行为相对应）。

对于某些ISA，这是给您带来计数领先的零31 - highbit_index。对于其他人来说，这是CTZ计数尾随零操作，为您提供低位的索引。x86兼有。（而且，除非您使用BMI1 lzcnt而不是传统的方法，否则它的高位查找程序实际上直接查找高位索引，而不是前导零计数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 manual。）

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

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

如果我们同时拥有low = CTZ(n)和high = 63-CLZ(n)。我不确定在非x86 ISA上GCC怎么做，而这两个ISA都不都是本地可用的。即使针对不具备此功能的硬件，GCC内置函数始终可用。但是内部实现无法使用上述技巧，因为它不知道总是总是设置了2位。

（我写出了完整的公式；该答案的较早版本在这一部分中将CLZ和CTZ颠倒了。我发现这很容易发生，特别是当我还必须跟踪x86 bsr和bsr（bitscan反向和前进）并记住分别是领先和落后。）

因此，如果仅同时使用CTZ和CLZ，则可能会对其中之一进行缓慢的仿真。或在ARM上rbit进行快速仿真，以进行位反转clz，这是100％好的。

AVX512CD具有针对64位整数的SIMDVPLZCNTQ，因此您可以与最近的Intel CPU并行地对2、4或8x 64位整数进行编码。对于SSSE3或AVX2，您可以通过将pshufb _mm_shuffle_epi8byte-shuffle用作4位LUT并与组合来构建SIMD lzcnt _mm_max_epu8。最近对此进行了问答，但我找不到。（它可能只适用于16位整数；更宽的内容需要更多的工作。）

这样，一旦考虑到打包结果的吞吐成本，Skylake-X或Cascade Lake CPU可能每2或3个时钟周期压缩8x 64位整数。如果您要对结果进行处理，则SIMD对于将12位或11位结果打包到连续的位流中非常有用，例如使用可变移位指令。以大约3或4GHz的时钟速度，单线程可能使您每个时钟超过100亿。但仅当输入来自连续内存时。根据您要对结果进行的处理，可能需要花费更多的时间来完成更多的工作，而不仅仅是将它们压缩为16位整数。例如打包成一个比特流。但是，SIMD应当具有可变移位指令，该指令可以在改组后将每个寄存器的11位或12位对齐到正确的位置或在一起。

在编码效率和编码性能之间需要权衡。至少在具有位扫描指令的硬件上，对两个6位（位位置）的索引使用12位非常容易压缩和解压缩。

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

同样，2 x 12位是一个整数字节，但是如果要打包它们，则每8个输出11个位只能给出一个整数字节。因此，对位压缩数组进行索引更简单。

0仍然是一种特殊情况：可以通过使用全1的位索引来处理该问题（即，索引=位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）的分支或无分支检查应该很便宜。

在其他ISA（如AArch64）上的压缩也很便宜。它有clz但没有ctz。可能是你最好的赌注有使用固有的rbit对位反转的一些（这样clz的位反转数直接给你低位的位索引。现在哪家的反向版本的高位。）假设rbit是与add/ 一样快sub，这比使用多条指令清除低位便宜。

如果您确实想要11位，则需要避免2x 6位的冗余，使其中一个索引大于另一个索引。例如可能具有6位a和5位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处理器最佳编码性能需要BMI1 tzcnt/ lzcnt因为bsr和bsf较慢（6个微指令而不是1 https://agner.org/optimize/）。在Ryzen上lzcnt为1 uop，1c延迟，每时钟吞吐量4。但是tzcnt是2微妙。

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

但是，lzcnt由于效率比tzcntAMD Ryzen 更高，可能不适合AMD的最佳组件。

或者也许是这样（假设恰好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 uops，没有执行单元瓶颈。因此，在每时钟流水线宽度为5微秒的情况下，优于每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 +或每个加1个周期。

对于吞吐量，我们每个周期只对一个位扫描（执行端口1）进行瓶颈处理，因此我们可以每2个周期进行一次编码，并留有4 oups的前端带宽用于负载，存储和循环开销（或其他处理） ），假设我们有多个独立的编码要做。

（但对于多重独立编码的情况，如果存在廉价的模拟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上只能在port0或port6上运行。因此，在Intel上，前端仅需花费4 uop（因此，每时钟1时钟作为其他操作的一部分）。但是，如果仅执行此操作，则它会阻塞移位吞吐量，即每1.5个时钟周期进行1次解码。

在4GHz CPU上，每秒26.66亿次解码，因此，对您的目标，我们做得很好：)

或Ryzen bts reg,reg是2 uops，吞吐量为0.5c，但shr可以在任何端口上运行。因此，它不会从中窃取吞吐量bts，整个过程为6微秒（与Ryzen的管道在最窄点处的宽度为5倍）有关。因此，每1.2个时钟周期1个编码，只是前端成本的瓶颈。

有了BMI2 ，假设寄存器中的in可以在循环中重用，则从1寄存器中的a 开始并使用shlx rax, rbx, rdi可以用一个uop 替换异或归零+第一个BTS 1。

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

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