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

Question

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

8

我有一个56位的数字，可能有两个设置位，例如00000000 00000000 00000000 00000000 00000000 00000000 00000011。换句话说，56位中有两个位分布在其中，因此我们有bin(56,2)=1540个可能的排列。

我现在正在寻找一种无损映射，将这样一个56位的数字映射到一个可以承载2048并因此也可以承载1540的11位数字中。知道了这个结构，这个11位数字足以存储我的低密度（1的数量较少）的56位数字的值。

我想要最大化性能（如果可能的话，这个函数应该每秒运行数百万甚至数十亿次）。到目前为止，我只想到了一些循环：

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的数字。

但是，难道没有比使用这样的循环更快的版本吗？

- IceFire

2

由于只有1540个这样的56位数字，一个显式地进行此映射的哈希表可能不是一个糟糕的想法。但这与硬件非常接近，我认为您在没有对实际代码进行测量的情况下将无法得到任何有意义的答案。 - Quimby

2

@Quimby，我也觉得这可能是最好的选择。但在这里，最好的哈希函数是什么呢？ - IceFire

2

你可能会想从一个带有1540个标签的开关开始，返回唯一的[0,1540)数值（最好不要手写），让编译器发挥它的魔力。使用 std::unordered_map 甚至是 std::map 总是可以的，但是要再度衡量。我真的不知道哪个哈希函数最适合这个键分布。甚至可能有一些位运算的技巧可以更快。 - Quimby

3

https://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious - melpomene

4

你可以这样分离二进制数的两位：topbit = inputNumber & (inputNumber - 1); bottombit = inputNumber ^ topbit;。 - melpomene

@melpomene非常好，谢谢！它很完美，应该运行得非常快。我使用检查endianness的版本。检查也可以在编译时进行。如果我将“int”更改为“long long”，它也适用于64位。如果您愿意获得upvote和答案分，请将其放入答案中。 - IceFire

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter Cordes · Accepted Answer

大多数指令集体系结构（ISA）都具有对位扫描指令的硬件支持，该指令可找到设置位的位置。 如果您关心这个运行速度，请使用它来代替简单循环或 bithack。 https://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious 提供了一些技巧，虽然比没有好，但它们仍然远不如一个高效的汇编指令。

但是，ISO C++ 不能以可移植的方式公开 clz/ctz 操作; 它只能通过各种实现的内在函数/内建函数获得。（而且 x86 内在函数对所有零输入都有瑕疵，相应于 asm 指令的行为）。

对于某些 ISA，它是一个计算前导零的操作，给出 31 - highbit_index。对于其他一些 ISA，它是一个 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 手册。）

如果我们只有CLZ，使用high = 63-CLZ（n）和low = 63-CLZ（（-n）＆n）来隔离低位。请注意，x86的bsr指令实际上产生63-CLZ（），即位索引而不是前导零计数。因此，在x86上，63-__builtin_clzll（n）可以编译为单个指令；如果我记得正确的话，gcc确实会注意到这一点。或者如果GCC使用额外的xor清零以避免不方便的假依赖，则需要2条指令。

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

如果我们两者都有，则low = CTZ（n），high = 63-CLZ（n）。我不确定GCC在非x86 ISA上的情况，其中它们不是本地可用的。 GCC内置函数始终可用，即使针对没有它的HW。但是内部实现不能使用上述技巧，因为它不知道恰好有2个位设置。

所以，如果你只使用CTZ和CLZ，你可能会得到其中一个的慢速仿真。或者在ARM上具有快速模拟，使用rbit进行位反转以进行clz，这是完全可以的。

AVX512CD具有64位整数的SIMD VPLZCNTQ，因此您可以在最近的Intel CPU上并行编码2、4或8x 64位整数。对于SSSE3或AVX2，您可以通过使用pshufb _mm_shuffle_epi8字节重排作为4位LUT并与_mm_max_epu8组合来构建SIMD lzcnt。最近有一个关于此的问答，但我找不到它。（它可能仅适用于16位整数；更宽需要更多工作。）

通过这种方式，Skylake-X或Cascade Lake CPU可能每2或3个时钟周期压缩8个64位整数，一旦考虑到结果打包的吞吐量成本。 SIMD对于将12位或11位结果打包成连续的比特流肯定很有用，例如使用可变移位指令，如果这是您想要使用结果的方式。在大约3或4GHz的时钟速度下，使用单个线程可能每个时钟周期获得超过100亿次。但是只有在输入来自连续内存时才能实现。根据您想要使用结果的方式，可能需要花费更多的周期来执行除了将它们压缩成16位整数之外的更多操作。例如将其打包成比特流。但是SIMD对于具有可变移位指令的情况应该很好，可以将每个寄存器的11个或12个位从正确的位置对齐并进行重新排列后OR在一起。

编码效率和编码性能之间存在权衡。对两个6位索引（位位置）使用12位非常简单，无论是压缩还是解压缩，至少在拥有位扫描指令的硬件上如此。

或者，可以将一个或两个替换为前导零计数，因此解码将成为(1ULL << 63) >> a。1ULL>>63是一个固定的常量，您实际上可以将其右移，或者编译器可以将其转换为左移1ULL << (63-a)，我IRC优化为在像x86这样的ISA中的汇编中掩码移位指令（仅查看低6位）。

此外，2个12位组成了一个完整的字节，但是11位只能让你在每8个输出时得到完整的字节数，如果您将它们打包。因此，索引比特打包的数组更简单。

0仍然是一个特殊情况：可以通过使用全为1的位索引（即索引=位63，该位超出了低56位）来处理。在解码/解压缩时，您设置2个位位置

(1ULL<，然后使用&掩码清除高位。或者将您的位索引偏差，并使解码右移1位。
如果不需要处理零，现代的x86 CPU可以每秒编码10-20亿个数字，例如Skylake每个时钟节拍的位扫描指令吞吐量为1，应该能够以每2个时钟节拍编码1个数字，只是受到瓶颈限制。（或者使用SIMD更好）。只需4个标量指令，我们就可以得到低位和高位索引（64位 tzcnt+ bsr），将其向左移6位并进行OR操作。¹ 在AMD上，避免使用bsr/bsf，手动进行63-lzcnt。
分支或无分支检查输入是否为0，将最终结果设置为硬编码常量（如63, 63）应该很便宜。
其他ISA上的压缩（如AArch64）也很便宜。它有clz但没有ctz。在这种情况下，你最好使用一个内在函数来反转一个数的位（因此在反转后的数上直接使用clz给出了低位的位索引，这现在是反转版本的高位）。假设rbit与add/sub一样快，这比使用多个指令来清除低位更便宜。
如果你真的想要11位，那么你需要避免2x 6位具有任一索引大于另一个索引的冗余。例如，使用6位a和5位b，并且让a <= b表示像b += 32这样的特殊含义。我还没有完全思考这个问题。你需要能够将2个相邻位编码在寄存器的顶部或底部，否则这2个设置的位可能相距28个位，如果我们像56位旋转一样考虑边界包装的话。
Melpomene提出的分离低位和高位设置位的建议可能对其他东西有用，但仅在你只有一个方向的位扫描可用时才对编码目标有用，而不是两个方向都有。即使如此，你也不会实际上同时使用这两个表达式。前导零计数不需要你隔离低位，你只需要清除它以获取高位即可。
注1：在x86上解码也很便宜：x |= (1<<a)是1个指令：bts。但许多编译器都错过了优化，没有注意到这一点，而是实际移位1。bts reg，reg是Intel自PPro以来的1个uop / 1个周期延迟，或者在AMD上有时是2个uops。（只有内存目标版本较慢）。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个uops。
使用BMI1，编译器可以使用blsr清除寄存器中的最低设置位（并将其复制）。即现代x86具有以下指令dst = (SRC-1) bitwiseAND ( SRC );在Intel上是单个uop，但在AMD上是2个uops。
但是，在AMD Ryzen上，lzcnt比tzcnt更高效，因此最好的asm不使用它。
或者可能像这样（假设恰好有2位）。
（这个汇编语言是您想让编译器发出的。请不要实际使用内联汇编！）
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 uops 的情况下，这比每2个时钟周期更好。

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)上，bitscan指令需要3个周期，而在AMD上只需要1个。SHL + OR每个指令都会增加1个周期。

就吞吐量而言，我们只会在每个周期中出现一个位扫描（执行端口1）的瓶颈，因此我们可以每2个周期做一次编码，并且还剩下4个前端带宽的微操作可用于加载、存储和循环开销（或其他任务），假设我们有多个独立的编码要完成。

（但对于多个独立编码的情况，如果存在廉价的“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


这段代码有三个位移操作（包括bts），在Skylake处理器上只能使用端口0或端口6运行。因此，在Intel上，前端仅需4个微操作（每个时钟周期1个），但如果只运行此操作，每1.5个时钟周期只能解码1次，受到了位移吞吐量的瓶颈限制。

在4GHz的CPU上，每秒可解码26.66亿个指令，所以我们很好地达到了您的目标：）

而对于Ryzen处理器，bts reg,reg是2个微操作，吞吐量为0.5c，但是shr可以在任何端口上运行。 因此，它不会从bts获取吞吐量，整个操作需要6个微操作（与Ryzen内核最窄处5单元相比）。所以每1.2个时钟周期可进行1次编码，只受到前端成本的限制。



如果有BMI2指令集，可以使用shlx rax, rbx, rdi在寄存器中将一个带有1的位替换掉xor清零+第一个BTS，并假定可以在循环中重复使用寄存器中的1。

（这种优化完全依赖于编译器的发现；无标志位移只是更有效的复制和移位方法，可以在-march=haswell或-march=znver1或具有BMI2的其他目标上使用。）

无论如何，您只需编写retval = 1ULL << (packed & 63)以解码第一个位。但如果您想知道哪些编译器会产生良好的代码，请查看以下内容。