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

[Claes Redestad]

Hi Andrew,

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.

Thanks!

/Claes

On 2020-03-10 18:29, Andrew Haley wrote:
> exact_log2() is used a great deal in HotSpot, especially at
> startup. exact_log2() uses a naive iterative algorithm. We should do
> better, and in particular we should use an algorithm that compilers
> commonly optimize well, so that constant expressions that use
> exact_log2 are computed at compilation time.
> 
> GCC reliably does the constant propagation so that exact_log2(const)
> calculations are always treated as constants, and even if the argument
> is not a constant the runtime effort is no more than a multiplication,
> a shift, and a load.
> 
> I also added a test. This is one of those few algorithms that can be
> exhaustively tested, so I have very high confidence that it is correct.
> 
> OK?
> 
> http://cr.openjdk.java.net/~aph/8240829-1/
>