计算前导/尾随1/0的效率有什么不同吗

Question

我正在设计一个带前缀的可变长度整数。

Rust有计算前导和尾随1和0的方法：https://doc.rust-lang.org/std/primitive.u64.html#method.leading_zeros

这些方法在x86_64、arm32和arm64上的效率有什么不同吗？

例如，如果计算尾随1比尾随0快，我将使用xxxx0111而不是xxxx1000作为长度编码字节(在本例中，用于后面的三个字节(。

Answer 1

在所有3个ISA:x86*、ARM、AArch64上计算尾随的零比尾随的零快。它们都提供零计数指令，如x86bsf(查找最低设置位(或x86 BMI1tzcnt(尾随零计数(。计算运行时变量中的前导/尾随将需要否定输入。

ARM/AArch64提供前导零计数，但用于尾随零的最佳选项是rbit/clz到位反向(由于ARMv6t2或ARMv7(。https://godbolt.org/z/Yr7eac.在此之前，编译器必须用x & -x隔离最低集位，计算其前导零，并取31-clz(x&-x)。

---

(在x86上，使用BMI1计算前导零的效率最高。如果没有它，bsr可以给你最高集位的位置，所以编译器需要31-bsr(x)来实现clz。在AMD CPU上，bsf/bsr明显比tzcnt/lzcnt慢，因此如果可能的话，最好使用-march=native或Rust等效软件进行编译。(

在AMD Zen上，lzcnt是1uop，tzcnt是2uop。https://uops.info/据推测，额外的uop要么是比特反向的，要么与x & -x隔离最低设置比特，但无论哪种方式，都会生成一些东西来馈送到lzcnt硬件。

相关有趣的事实：循环设置比特以找到它们的位置通常最好使用x = blsr(x)，因为循环携带依赖项x &= x-1，并独立地对每个结果进行比特扫描以获得设置比特。因此，在循环的关键路径延迟中没有一点扫描和偏移。

相关：在历史x86 CPU上设置任意大小整数C++bsr/bsf和tzcnt性能的前导零位。

Answer 2

在amd64/x86_64上，最快到最慢的是：

• 尾随零
• 前导零/尾随一
• 领先的

在arm64/arch64上，最快到最慢的是：

• 前导零
• 前导1/尾随0(绑定(
• 尾随的

godbolt.org的测试结果：

pub fn lz(num: u64) -> u32 {
num.leading_zeros()
}
pub fn lo(num: u64) -> u32 {
num.leading_ones()
}
pub fn tz(num: u64) -> u32 {
num.trailing_zeros()
}
pub fn to(num: u64) -> u32 {
num.trailing_ones()
}

amd64/x86_64:

example::lz:
test    rdi, rdi
je      .LBB0_1
bsr     rax, rdi
xor     rax, 63
ret
.LBB0_1:
mov     eax, 64
ret
example::lo:
not     rdi
test    rdi, rdi
je      .LBB1_1
bsr     rax, rdi
xor     rax, 63
ret
.LBB1_1:
mov     eax, 64
ret
example::tz:
test    rdi, rdi
je      .LBB2_1
bsf     rax, rdi
ret
.LBB2_1:
mov     eax, 64
ret
example::to:
not     rdi
test    rdi, rdi
je      .LBB3_1
bsf     rax, rdi
ret
.LBB3_1:
mov     eax, 64
ret

arm64/arch64:

example::lz:
clz     x0, x0
ret
example::lo:
mvn     x8, x0
clz     x0, x8
ret
example::tz:
rbit    x8, x0
clz     x0, x8
ret
example::to:
mvn     x8, x0
rbit    x8, x8
clz     x0, x8
ret