8203279: Faster rounding up to nearest power of two
Reviewed-by: martin, redestad
--- 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!