RFR: 8240829: Use a fast O(1) algorithm for exact_log2

[Andrew Haley]

On 3/10/20 5:54 PM, Claes Redestad wrote:
> did you consider implementing these as [63,31] -
> count_leading_zeros(foo)? Or (sizeof(T) * BitsPerByte - 1 - lz),
> as expressed in round_down_power_of_2. I've been meaning to try this
> out now that exact_log2 has been freed from globalDefinitions.
>
> count_leading_zeros use compiler intrinsics to use lzcnt and similar
> instructions which are actually O(1) on many platforms - with a fallback
> to a similar DeBruijn algorithm.

Sure, I know. I should have mentioned that.

TL/DR: prefer portable code when possible.

I didn't do so because AFAIK count_leading_zeros() isn't part of
Standard C++ and I had no desire to try to find out what non-GCC
compilers do. If someone cares enough to get the last nanosecond out
of this, I guess that's fair, but it's such a small gain over this
algorithm that it wouldn't be noticeable.

-- 
Andrew Haley  (he/him)
Java Platform Lead Engineer
Red Hat UK Ltd. <https://www.redhat.com>
https://keybase.io/andrewhaley
EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671