RFR: 8257815: Replace global log2 functions with efficient implementations [v10]

[Kim Barrett]

On Mon, 14 Dec 2020 12:07:33 GMT, Claes Redestad <redestad at openjdk.org> wrote:

>> This patch replaces the log2 functions in globalDefinitions.hpp with more efficient counterparts in utilities/powerOfTwo.hpp
>> 
>> Naming is hard, but I think the following scheme is reasonable:
>> 
>> - log2i: any integral type. 0-hostile
>> - log2i_allow_zero: any integral type. gracefully handles zero (adds a branch)
>> - exact_log2i: any integral type. value must be a power of two
>> 
>> I chose log2i rather than log2 to stand out from the log2 functions defined in various standard libraries.
>> 
>> Going through all usage, quite a few uses of log2_long et.c. could be replaced by exact_log2i since they take something that has been checked to be a power of two. Most of the remaining usage seem to be able to use the 0-hostile variant, which avoids a branch.
>> 
>> To sanity check that calculating log2 using count_leading_zeros gives better performance I added a couple of trivial and short-running microbenchmarks to test_powerOfTwo. For small values (<= 1025) the new impl is ~5x faster, with a larger speed-up for larger integer values:
>> 
>> [ RUN      ] power_of_2.log2_long_micro
>> [       OK ] power_of_2.log2_long_micro (3581 ms)
>> [ RUN      ] power_of_2.log2_long_small_micro
>> [       OK ] power_of_2.log2_long_small_micro (549 ms)
>> [ RUN      ] power_of_2.log2i_micro
>> [       OK ] power_of_2.log2i_micro (259 ms)
>> [ RUN      ] power_of_2.log2i_small_micro
>> [       OK ] power_of_2.log2i_small_micro (113 ms)
>> 
>> I'm not sure if this naive microbenchmark carries its own weight, but it just adds a few seconds and can be useful for quickly checking this performance assumption on other H/W
>> 
>> (Intending this for 17)
>
> Claes Redestad has updated the pull request with a new target base due to a merge or a rebase. The incremental webrev excludes the unrelated changes brought in by the merge/rebase. The pull request contains 26 additional commits since the last revision:
> 
>  - With JDK-8257985 fixed, use count_trailing_zeros to implement log2i_exact
>  - Merge branch 'master' into log2_template
>  - Merge branch 'master' of https://github.com/openjdk/jdk into log2_template
>  - More review comments adressed
>  - Issue with using count_trailing_zeros with 64-bit values on 32-bit, revert and add TODO
>  - Merge branch 'master' into log2_template
>  - Renaming, adress review comments
>  - x->value
>  - Rename log2i ilogi and make it only accept value > 0, rename log2i_allow_zero log2i_graceful, accepting any value
>  - Rename exact_log2i exact_ilog2, make it stricter
>  - ... and 16 more: https://git.openjdk.java.net/jdk/compare/ea3a3570...42b75337

src/hotspot/share/utilities/powerOfTwo.hpp line 78:

> 76:   assert(is_power_of_2(value),
> 77:                        "value must be a power of 2: " UINT64_FORMAT,
> 78:                        (uint64_t)static_cast<typename std::make_unsigned<T>::type>(value));

This looks strange and complicated for something that ought to be straightforward.  There was a comment in conversation suggesting this is working around some problem with some test.  Please explain, because I'd really like this to go back to just a cast to uint64_t if at all possible.  Sorry I didn't bring this up earlier.

-------------

PR: https://git.openjdk.java.net/jdk/pull/1663