8203279: Faster rounding up to nearest power of two
authorigerasim
Mon, 21 May 2018 12:49:03 -0700
changeset 50201 a2c92332c6ba
parent 50200 9ce050c4711b
child 50202 63c65528b1fe
8203279: Faster rounding up to nearest power of two Reviewed-by: martin, redestad
src/java.base/share/classes/java/util/ComparableTimSort.java
src/java.base/share/classes/java/util/HashMap.java
src/java.base/share/classes/java/util/TimSort.java
--- a/src/java.base/share/classes/java/util/ComparableTimSort.java	Mon May 21 12:27:21 2018 -0700
+++ b/src/java.base/share/classes/java/util/ComparableTimSort.java	Mon May 21 12:49:03 2018 -0700
@@ -883,12 +883,7 @@
     private Object[]  ensureCapacity(int minCapacity) {
         if (tmpLen < minCapacity) {
             // Compute smallest power of 2 > minCapacity
-            int newSize = minCapacity;
-            newSize |= newSize >> 1;
-            newSize |= newSize >> 2;
-            newSize |= newSize >> 4;
-            newSize |= newSize >> 8;
-            newSize |= newSize >> 16;
+            int newSize = -1 >>> Integer.numberOfLeadingZeros(minCapacity);
             newSize++;
 
             if (newSize < 0) // Not bloody likely!
--- a/src/java.base/share/classes/java/util/HashMap.java	Mon May 21 12:27:21 2018 -0700
+++ b/src/java.base/share/classes/java/util/HashMap.java	Mon May 21 12:49:03 2018 -0700
@@ -376,12 +376,7 @@
      * Returns a power of two size for the given target capacity.
      */
     static final int tableSizeFor(int cap) {
-        int n = cap - 1;
-        n |= n >>> 1;
-        n |= n >>> 2;
-        n |= n >>> 4;
-        n |= n >>> 8;
-        n |= n >>> 16;
+        int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
         return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
     }
 
--- a/src/java.base/share/classes/java/util/TimSort.java	Mon May 21 12:27:21 2018 -0700
+++ b/src/java.base/share/classes/java/util/TimSort.java	Mon May 21 12:49:03 2018 -0700
@@ -916,12 +916,7 @@
     private T[] ensureCapacity(int minCapacity) {
         if (tmpLen < minCapacity) {
             // Compute smallest power of 2 > minCapacity
-            int newSize = minCapacity;
-            newSize |= newSize >> 1;
-            newSize |= newSize >> 2;
-            newSize |= newSize >> 4;
-            newSize |= newSize >> 8;
-            newSize |= newSize >> 16;
+            int newSize = -1 >>> Integer.numberOfLeadingZeros(minCapacity);
             newSize++;
 
             if (newSize < 0) // Not bloody likely!