RFR: 8155795: Optimize Integer/Long.reverse by using reverseBytes

Jaroslav Kameník jaroslav at kamenik.cz
Mon May 2 20:47:34 UTC 2016


Thanks for comments. I have changed tests as Aleksey suggested.

Btw. is not there some class used for utility methods as leftpad?

Ad performance of changed reverseBytes, I tried to compare
both reverseBytes alone, and it seems to be same, but differs
when inlined to reverse().

J.

2016-05-02 17:00 GMT+02:00 Claes Redestad <claes.redestad at oracle.com>:

> On 2016-05-02 16:48, Aleksey Shipilev wrote:
>
>> On 05/02/2016 05:07 PM, Claes Redestad wrote:
>>
>>> I'd like to sponsor this patch proposed by Jaroslav Kameník here:
>>>
>>> http://mail.openjdk.java.net/pipermail/core-libs-dev/2016-April/040660.html
>>>
>>> Bug https://bugs.openjdk.java.net/browse/JDK-8155795
>>> Webrev: http://cr.openjdk.java.net/~redestad/8155795/webrev.01/
>>>
>> *) I wonder if Integer.reverseBytes is better spelled as:
>>
>>   return (i >>> 24) |
>>          ((i & 0xFF0000) >> 8) |
>>          ((i & 0xFF00) << 8)   |
>>          (i << 24);
>>
>
> The reverseBytes changes were motivated by seeing slightly better
> performance on the micro with the suggested changes, but after
> discussing this a bit I think we should revert to the original code alone
> and investigate if there's some compiler quirk lurking here separately.
>
> I'll file a bug.
>
>
>> *) The test should probably follow the same randomized testing pattern
>> as other tests:
>>
>>   for (int i = 0; i < N; i++) {
>>     int x = rnd.nextInt();
>>
>>     String expected = new StringBuilder().
>>         .append(leftpad(Integer.toBinaryString(x), 32))
>>         .reverse().toString();
>>
>>     String actual   =
>>         leftpad(Integer.toBinaryString(Integer.reverse(x)), 32);
>>
>>     if (!expected.equals(actual)) {
>>         throw new RuntimeException("reverse: \n" +
>>                            expected + " \n" + actual);
>>     }
>>
>>   // That's how development looks like in 2016.
>>   private static String leftpad(String s, int width) {
>>     String r = s;
>>     for (int c = 0; c < width - s.length(); c++) {
>>       r = "0" + r;
>>     }
>>     return r;
>>   }
>>
>> ...and should probably precede any other test that uses reverse().
>>
>
> Seems reasonable.
>
> Jaroslav, do you mind improving the test as per Aleksey's
> suggestions?
>
> Thanks!
>
> /Claes
>
-------------- next part --------------
diff -r 2bf84670f079 src/java.base/share/classes/java/lang/Integer.java
--- a/src/java.base/share/classes/java/lang/Integer.java	Sat Apr 30 16:08:48 2016 -0700
+++ b/src/java.base/share/classes/java/lang/Integer.java	Mon May 02 22:09:54 2016 +0200
@@ -1790,9 +1790,8 @@
         i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;
         i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;
         i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;
-        i = (i << 24) | ((i & 0xff00) << 8) |
-            ((i >>> 8) & 0xff00) | (i >>> 24);
-        return i;
+
+        return reverseBytes(i);
     }
 
     /**
@@ -1820,10 +1819,10 @@
      */
     @HotSpotIntrinsicCandidate
     public static int reverseBytes(int i) {
-        return ((i >>> 24)           ) |
-               ((i >>   8) &   0xFF00) |
-               ((i <<   8) & 0xFF0000) |
-               ((i << 24));
+        return (i << 24)            |
+               ((i & 0xff00) << 8)  |
+               ((i >>> 8) & 0xff00) |
+               (i >>> 24);
     }
 
     /**
diff -r 2bf84670f079 src/java.base/share/classes/java/lang/Long.java
--- a/src/java.base/share/classes/java/lang/Long.java	Sat Apr 30 16:08:48 2016 -0700
+++ b/src/java.base/share/classes/java/lang/Long.java	Mon May 02 22:09:54 2016 +0200
@@ -1952,10 +1952,8 @@
         i = (i & 0x5555555555555555L) << 1 | (i >>> 1) & 0x5555555555555555L;
         i = (i & 0x3333333333333333L) << 2 | (i >>> 2) & 0x3333333333333333L;
         i = (i & 0x0f0f0f0f0f0f0f0fL) << 4 | (i >>> 4) & 0x0f0f0f0f0f0f0f0fL;
-        i = (i & 0x00ff00ff00ff00ffL) << 8 | (i >>> 8) & 0x00ff00ff00ff00ffL;
-        i = (i << 48) | ((i & 0xffff0000L) << 16) |
-            ((i >>> 16) & 0xffff0000L) | (i >>> 48);
-        return i;
+
+        return reverseBytes(i);
     }
 
     /**
diff -r 2bf84670f079 test/java/lang/Integer/BitTwiddle.java
--- a/test/java/lang/Integer/BitTwiddle.java	Sat Apr 30 16:08:48 2016 -0700
+++ b/test/java/lang/Integer/BitTwiddle.java	Mon May 02 22:09:54 2016 +0200
@@ -58,6 +58,21 @@
 
         for (int i = 0; i < N; i++) {
             int x = rnd.nextInt();
+
+            String expected = new StringBuilder()
+                .append(leftpad(toBinaryString(x), 32))
+                .reverse().toString();
+
+            String actual = leftpad(toBinaryString(reverse(x)), 32);
+
+            if (!expected.equals(actual)) {
+                throw new RuntimeException("reverse: \n" +
+                        expected + " \n" + actual);
+            }
+        }
+
+        for (int i = 0; i < N; i++) {
+            int x = rnd.nextInt();
             if (highestOneBit(x) != reverse(lowestOneBit(reverse(x))))
                 throw new RuntimeException("g: " + toHexString(x));
         }
@@ -136,4 +151,12 @@
                 throw new RuntimeException("z: " + toHexString(x));
         }
     }
+
+    private static String leftpad(String s, int width) {
+        String r = s;
+        for (int c = 0; c < width - s.length(); c++) {
+            r = "0" + r;
+        }
+        return r;
+    }
 }
diff -r 2bf84670f079 test/java/lang/Long/BitTwiddle.java
--- a/test/java/lang/Long/BitTwiddle.java	Sat Apr 30 16:08:48 2016 -0700
+++ b/test/java/lang/Long/BitTwiddle.java	Mon May 02 22:09:54 2016 +0200
@@ -58,6 +58,21 @@
 
         for (int i = 0; i < N; i++) {
             long x = rnd.nextLong();
+
+            String expected = new StringBuilder()
+                .append(leftpad(toBinaryString(x), 64))
+                .reverse().toString();
+
+            String actual = leftpad(toBinaryString(reverse(x)), 64);
+
+            if (!expected.equals(actual)) {
+                throw new RuntimeException("reverse: \n" +
+                        expected + " \n" + actual);
+            }
+        }
+
+        for (int i = 0; i < N; i++) {
+            long x = rnd.nextLong();
             if (highestOneBit(x) != reverse(lowestOneBit(reverse(x))))
                 throw new RuntimeException("g: " + toHexString(x));
         }
@@ -136,4 +151,12 @@
                 throw new RuntimeException("z: " + toHexString(x));
         }
     }
+
+    private static String leftpad(String s, int width) {
+        String r = s;
+        for (int c = 0; c < width - s.length(); c++) {
+            r = "0" + r;
+        }
+        return r;
+    }
 }


More information about the core-libs-dev mailing list