Skip to contentSkip to conversation

Faster generic_fls

RFC PATCH Chuck Ebbert 1 participant 1 message May 1, 2003

lore
Share & tools
lore
#0 lore raw
Quoted 10 lines · Linus Torvalds
Quoted 4 lines

BTW, has someone benchmarked BSF/BSR on x86 ? It should be
faster, it it's also possible that a poor microcode implements it with a one bit/cycle algo, which will result in one instruction not being as fast as your code.

I think the original i386 did it with a one-bit-per-cycle algorithm, anything since should be fine. In particular, on a P4 where I just tested, the bsf seems to be 4 cycles over the whole input set (actually, my whole loop was 4 cycles per iteration, so 4 cycles is worst-case. I'm assuming the rest could have been done in parallell).

Just for comparison, the Pentium (Classic) manual says 6-43 clocks for
bsfl and 7-72 (!) for bsrl.

------
Chuck