6 ms·
Dude, your case statement will compile into a bunch of test and branch instructions, implementing a binary search if you're lucky, and a linear search if you're
by drfuchs 11y ago
Dude, your case statement will compile into a bunch of test and branch instructions, implementing a binary search if you're lucky, and a linear search if you're not. Better to use __builtin_clz() or similar, so your function will just take a few cycles with no (expensive) branching. Extra bonus: with care, it can work for all inputs, giving a truncated or rounded result.
- scott_s 11y agoDude, this outperformed log2 by a large margin, which is what I cared about. Cycles mattered in this code, but after this optimization, that's not where most cycles were being spent. edit: Investigating further, this intrinsic was introduced into gcc around 2006, which means I'm not sure it would have been available to me at the time.
- uxcn 11y agoOn x86, it could also compile down to just a jmp. A bsr would still be faster, but it would probably be worth checking that __builtin_clz actually compiles down to bsr. For portability reasons, it might be better just using bit tricks and letting the compiler try to optimize it though. Clang and GCC do pretty well here.