在一个位置或更低位置计算设置位的有效方法是

Latency: Critical path from when the bitset is ready to when the result is: shl(2) -> popcnt(3) -> imul(3). Total 8 cycles. Or 9c from when pos is ready, because the not is an extra 1c latency for it.

最佳bitbroadcast 版本 将shr​​ 替换为sar(相同的性能)和imul 带有 和(1c 延迟而不是 3c，在任何端口上运行).因此，唯一的性能变化是将关键路径延迟减少到 6 个周期.前端的吞吐量仍然是瓶颈.and 能够在任何端口上运行并没有什么区别，除非您将其与在 port1 上出现瓶颈的代码混合在一起(而不是查看仅运行this 紧密循环的代码).

The optimal bitbroadcast version replaces shr with sar (same perf), and imul with and (1c latency instead of 3c, runs on any port). So the only perf change is reducing the critical path latency to 6 cycles. Throughput is still bottlenecked on the frontend. and being able to run on any port doesn't make a difference, unless you're mixing this with code that bottlenecks on port1 (instead of looking at the throughput for running just this code in a tight loop).

cmov(三元运算符)版本:11 个融合域 uops(前端:每 2.75c 一个).执行单元:仍然在每个 2c 一个的移位端口 (p0/p6) 上遇到瓶颈.延迟:从 bitset 到 result 为 7c，从 pos 到 result 为 8c.(cmov 是 2c 延迟，对于 p0/p1/p5/p6 中的任何一个都是 2 uops.)

cmov (ternary operator) version: 11 fused-domain uops (frontend: one per 2.75c). execution units: still bottlenecked on the shift ports (p0/p6) at one per 2c. Latency: 7c from bitset to result, 8c from pos to result. (cmov is 2c latency, 2 uops for any of p0/p1/p5/p6.)

Clang 有一些不同的技巧:代替 test/cmovs，它生成一个全一或全的掩码-zeros 通过使用算术右移将符号位广播到寄存器的所有位置.我喜欢它:在英特尔上使用 and 而不是 cmov 更有效.不过，它仍然具有数据依赖性，并为分支的两端工作(这是 cmov 的主要缺点).更新:如果源代码正确，gcc 也会使用这种方法.

Clang has some different tricks up its sleeve: Instead of test/cmovs, it generates a mask of either all-ones or all-zeros by using an arithmetic right-shift to broadcast the sign bit to all positions of a register. I love it: Using and instead of cmov is more efficient on Intel. It still has the data-dependency and does the work for both sides of the branch (which is the main downside to cmov in general), though. Update: with the right source code, gcc will use this method, too.

clang 3.7 -O3 -Wall -march=nehalem -mtune=haswell

popcount_subset(std::bitset<64ul>, int):
    mov     ecx, 63
    sub     ecx, esi      ; larger code size, but faster on CPUs without mov-elimination
    shl     rdi, cl       ; rdi << ((63-pos) & 63)
    popcnt  rax, rdi      ; doesn't start a fresh dep chain before this, like gcc does
    sar     rdi, 63       ; broadcast the sign bit
    and     eax, edi      ; eax = 0 or its previous value
    ret

sar/and 替换了 xor/test/cmov，并且 cmov 是 Intel CPU 上的 2-uop 指令，所以这真的很好.(对于三元运算符版本).

sar / and replaces xor / test / cmov, and cmov is a 2-uop instruction on Intel CPUs, so that's really nice. (For the ternary-operator version).

在使用乘法源版本或bitbroadcast"源版本时，

Clang 仍然使用 sar/和 技巧，而不是实际的 imul.所以那些帮助 gcc 而不伤害 clang.(sar/and 肯定比 shr​​/imul 好:关键路径上的延迟减少了 2c.)pow_of_two_sub 版本确实伤害了 clang(参见第一个godbolt链接:从这个答案中省略，以避免与没有成功的想法混淆).

Clang still does the sar / and trick instead of an actual imul when using the multiply source version, or the "bitbroadcast" source version. So those help gcc without hurting clang. (sar/and is definitely better than shr/imul: 2c less latency on the critical path.) The pow_of_two_sub version does hurt clang (see the first godbolt link: omitted from this answer to avoid clutter with ideas that didn't pan out).

mov ecx, 63/sub ecx, esi 实际上在 CPU 上更快，无需消除 reg,reg 移动(零延迟和无执行端口，由寄存器重命名处理).这包括 Intel IvyBridge 之前的版本，但不包括更新的 Intel 和 AMD CPU.

The mov ecx, 63 / sub ecx, esi is actually faster on CPUs without mov-elimination for reg,reg moves (zero latency and no execution port, handled by register renaming). This includes Intel pre-IvyBridge, but not more recent Intel and AMD CPUs.

Clang 的 mov imm/sub 方法只将 pos 的一个周期延迟放到关键路径上(超出 bitset->result 延迟)，而不是 mov ecx, esi/not ecx 在 mov r,r 具有 1c 延迟的 CPU 上的两个.

Clang's mov imm / sub method puts only one cycle of latency for pos onto the critical path (beyond the bitset->result latency), instead of two for a mov ecx, esi / not ecx on CPUs where mov r,r has 1c latency.

使用 BMI2(Haswell 及更高版本)，最佳 ASM 版本可以将 mov 保存到 ecx.其他一切都一样，因为 shlx 将其移位​​计数输入寄存器屏蔽到操作数大小，就像 shl 一样.

With BMI2 (Haswell and later), an optimal ASM version can save a mov to ecx. Everything else works the same, because shlx masks its shift-count input register down to the operand-size, just like shl.

x86 移位指令具有疯狂的 CISC 语义，如果移位计数为零，则标志不受影响.因此，可变计数移位指令对标志的旧值具有(潜在的)依赖性.普通"x86 shl r, cl 在 Haswell 上解码为 3 uops，但 BMI2 shlx r, r, r 仅为 1.所以 gcc 仍然发出 sal 与 -march=haswell 一起使用，而不是使用 shlx(它确实在其他一些情况下使用).

x86 shift instructions have crazy CISC semantics where if the shift count is zero, the flags aren't affected. So variable-count shift instructions have a (potential) dependency on the old value of the flags. "Normal" x86 shl r, cl decodes to 3 uops on Haswell, but BMI2 shlx r, r, r is only 1. So it's too bad that gcc still emits sal with -march=haswell, instead of using shlx (which it does use in some other cases).

// hand-tuned BMI2 version using the NOT trick and the bitbroadcast
popcount_subset(std::bitset<64ul>, int):
    not     esi           ; The low 6 bits hold 63-pos.  gcc's two-s complement trick
    xor     eax, eax      ; break false dependency on Intel.  maybe not needed when inlined.
    shlx    rdi, rdi, rsi ; rdi << ((63-pos) & 63)
    popcnt  rax, rdi
    sar     rdi, 63       ; broadcast the sign bit: rdi=0 or -1
    and     eax, edi      ; eax = 0 or its previous value
    ret

英特尔 Haswell 的性能分析:6 个融合域 uops(前端:每 1.5c 一个).执行单元:2 p0/p6 shift uops.1 p1 uop.2 个任意端口 uops:(从总执行端口限制中每 1.25c 一个).关键路径延迟:shlx(1) -> popcnt(3) -> and(1) = 5c bitset->result.(或来自 pos->result 的 6c).

Perf analysis for Intel Haswell: 6 fused-domain uops (frontend: one per 1.5c). Execution units: 2 p0/p6 shift uops. 1 p1 uop. 2 any-port uops: (one per 1.25c from total execution port limits). Critical path latency: shlx(1) -> popcnt(3) -> and(1) = 5c bitset->result. (or 6c from pos->result).

请注意，内联时，人类(或智能编译器)可以避免对 xor eax, eax 的需要.它只是因为 popcnt 对输出寄存器的错误依赖(在 Intel 上)，我们需要 eax 中的输出(调用者可能最近使用了很长时间)链).使用 -mtune=bdver2 或其他东西，gcc 不会将用于 popcnt 输出的寄存器清零.

Note that when inlining, a human (or smart compiler) could avoid the need for the xor eax, eax. It's only there because of popcnt's false dependency on the output register (on Intel), and we need the output in eax (which the caller may have used recently for a long dep chain). With -mtune=bdver2 or something, gcc won't zero the register it's going to use for popcnt output.

内联时，我们可以使用一个输出寄存器，该寄存器至少早在 popcnt 的源代码中就已经准备好了，以避免出现问题.当以后不需要源时，编译器将执行就地 popcnt rdi,rdi ，但这里不是这种情况.相反，我们可以选择另一个在源之前已经准备好的寄存器.popcnt的输入依赖于63-pos，我们可以破坏它，所以popcnt rsi,rdi对rsi的依赖不能延迟它.或者如果我们在寄存器中有 63，我们可以 popcnt rsi,rdi/sarx rax, rsi, reg_63/ and eax,esi.或者 BMI2 3 操作数移位指令也可以让我们不破坏输入，以防以后需要它们.

When inlining, we could use an output register that already has to be ready at least as early as popcnt's source reg to avoid the problem. Compilers will do an in-place popcnt rdi,rdi when the source isn't needed later, but that's not the case here. Instead, we can pick another register that already has to be ready before the source. popcnt's input depends on 63-pos, and we can clobber it, so popcnt rsi,rdi's dependency on rsi can't delay it. Or if we had 63 in a register, we could popcnt rsi,rdi / sarx rax, rsi, reg_63 / and eax, esi. Or BMI2 3-operand shift instructions would also let us not clobber inputs in case they're needed afterwards.

这太轻了，以至于循环开销和设置输入操作数/存储结果将成为主要因素.(并且 63-pos 可以使用编译时常量进行优化，或者优化到变量计数的来源.)

This is so light-weight that loop overhead and setting up the input operands / storing the results are going to be major factors. (And the 63-pos can optimize away with a compile-time constant, or into wherever a variable count comes from.)

英特尔编译器很有趣，它没有利用 A[63] 是符号位这一事实.shl/bt rdi, 63/jc.它甚至以一种非常愚蠢的方式设置了分支.它可以将 eax 归零，然后根据 shl 设置的符号标志跳过 popcnt 或不跳过.

The Intel compiler amusingly shoots itself in the foot and doesn't take advantage of the fact that A[63] is the sign bit. shl / bt rdi, 63 / jc. It even sets up the branches in a really dumb way. It could zero eax, and then jump over popcnt or not based on the sign flag set by shl.

最佳分支实现，从 Godbolt 上 -O3 -march=corei7 的 ICC13 输出开始:

An optimal branching implementation, starting from ICC13 output from -O3 -march=corei7 on godbolt:

   // hand-tuned, not compiler output
        mov       ecx, esi    ; ICC uses neg/add/mov :/
        not       ecx
        xor       eax, eax    ; breaks the false dep, or is the return value in the taken-branch case
        shl       rdi, cl
        jns    .bit_not_set
        popcnt    rax, rdi
.bit_not_set:
        ret

这几乎是最优的:A[pos] == true 情况有一个未被采用的分支.不过，与无分支方法相比，它并没有节省多少.

That's pretty much optimal: The A[pos] == true case has one not-taken branch. It doesn't save very much over the branchless method, though.

如果 A[pos] == false 情况更常见:跳过 ret 指令，到 popcnt/>ret.(或在内联之后:跳转到执行 popcnt 并跳回的末尾块).

If the A[pos] == false case is more common: jump over a ret instruction, to a popcnt / ret. (Or after inlining: jump to a block at the end that does the popcnt and jumps back).

这篇关于在一个位置或更低位置计算设置位的有效方法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持编程学习网！