RFR 8203279 : Faster calculation of power of two

[David Holmes]

On 17/05/2018 12:55 PM, Martin Buchholz wrote:
> Hello Ivan,
> 
> I've wondered about this myself.
> Probably the performance is architecture dependent.
> Probably a new method should be added to Integer and Long with
> @HotspotIntrinsicCandidate.
> That gives David another chance to practice his blind aarch64 assembly
> language coding skills.

Ha! :)

> It's hard to give a good name for this.  Hacker's delight calls it dclp2
> and we can probably do better than that.
> http://www.hackersdelight.org/hdcodetxt/clp2.c.txt
> But I approve either way.

Interesting that the existing code is almost, but not quite clp2.

And numberOfLeadingZeroes also comes from HD.

If both forms get optimally compiled I'm very surprised that we would 
see such a performance difference.

David

> 
> On Wed, May 16, 2018 at 5:32 PM, Ivan Gerasimov <ivan.gerasimov at oracle.com>
> wrote:
> 
>> Hello!
>>
>> In a few places we have code that rounds an integer up to the nearest
>> power of two.
>>
>> It is done with a series of RSHOTFs and ORs, but it can possibly be done
>> faster with the use of Integer.numberOfLeadingZeros (assuming it is
>> intrinsified).
>>
>> Would you please help review this trivial optimization:
>>
>> BUGURL: https://bugs.openjdk.java.net/browse/JDK-8203279
>> WEBREV: http://cr.openjdk.java.net/~igerasim/8203279/00/webrev/
>>
>> For HashMap.tableSizeFor() I created a simple test with a loop from
>> Integer.MIN_VALUE to Integer.MAX_VALUE (including), to make sure the result
>> is the same.
>>
>> For TimSort.ensureCapacity() I checked all positive values of minCapacity.
>>
>> --
>> With kind regards,
>> Ivan Gerasimov
>>
>>