I'm designing a prefixed variable length integer.
Rust has methods for counting leading and trailing ones and zeros: https://doc.rust-lang.org/std/primitive.u64.html#method.leading_zeros
Is there any difference in the efficiency of these methods on x86_64, arm32 and arm64?
e.g. If counting trailing ones is faster than trailing zeros, I will use xxxx0111 instead of xxxx1000 for the length encoding byte (for three following bytes, in this example).
Counting trailing zeros is faster than trailing ones on all 3 ISAs: x86*, ARM, AArch64. They all provide zero-counting instructions like x86 bsf (find the lowest set bit) or x86 BMI1 tzcnt (Trailing Zero Count). Counting leading/trailing ones in a runtime-variable would require negating the input.
ARM / AArch64 provide a leading-zero count, but the best option for trailing-zero is rbit / clz to bit-reverse (since ARMv6t2 or ARMv7). https://godbolt.org/z/Yr7eac. Before that, compilers have to isolate the lowest set bit with x & -x, count leading zeros of that, and take 31-clz(x&-x).
(On x86, counting leading zeros is most efficient with BMI1. Without it, bsr can give you position of the highest set bit, so the compiler needs 31-bsr(x) to implement clz. On AMD CPUs, bsf / bsr are significantly slower than their tzcnt / lzcnt counterparts, so if possible it's good to compile with -march=native or whatever the Rust equivalent is.)
On AMD Zen, lzcnt is 1 uop, tzcnt is 2 uops. https://uops.info/ Presumably the extra uop is either bit-reverse or isolate lowest set bit with x & -x, but either way generating something to feed to the lzcnt hardware.
Related fun fact: looping over the set bits to find their positions is often best done with x = blsr(x) as the loop-carried dependency, x &= x-1, and independently bit-scan each result for the set bit. So there isn't a bit-scan and shift in the critical path latency of the loop.
Related: Set the leading zero bits in any size integer C++ bsr/bsf and tzcnt performance on historical x86 CPUs.
On amd64 / x86_64, fastest to slowest are:
On arm64 / aarch64, fastest to slowest are:
Test results from 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 / aarch64:
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