RFR: 8238669: Long.divideUnsigned is extremely slow for certain values (Needs to be Intrinsic)

[Raffaello Giulietti]

Hi Joe,

I modified the values in method testDivideAndRemainder(), without 
touching the logic.

The values are odd and even dividends and divisors around 0, 2^31, 2^32, 
2^33, 2^63 and 2^64.

Is this OK?


Greetings
Raffaello



On 2020-09-02 23:26, Raffaello Giulietti wrote:
> will do in the next days, hopefully before the transition to Skara.
> 




# HG changeset patch
# User lello
# Date 1599145128 -7200
#      Thu Sep 03 16:58:48 2020 +0200
# Node ID 3b3304879831cb1e76e4edbc2303efcf620d63b8
# Parent  6ab9279c0e99bf28d813c54c3c2645df61e654e7
Patch to fix JDK-8238669
8238669: Long.divideUnsigned is extremely slow for certain values (Needs 
to be Intrinsic)
Reviewed-by: TBD
Contributed-by: Raffaello Giulietti <raffaello.giulietti at gmail.com>

diff --git a/src/java.base/share/classes/java/lang/Long.java 
b/src/java.base/share/classes/java/lang/Long.java
--- a/src/java.base/share/classes/java/lang/Long.java
+++ b/src/java.base/share/classes/java/lang/Long.java
@@ -1668,24 +1668,13 @@
       * @since 1.8
       */
      public static long divideUnsigned(long dividend, long divisor) {
-        if (divisor < 0L) { // signed comparison
-            // Answer must be 0 or 1 depending on relative magnitude
-            // of dividend and divisor.
-            return (compareUnsigned(dividend, divisor)) < 0 ? 0L :1L;
+        // See Hacker's Delight (2nd ed), section 9.3
+        if (divisor >= 0) {
+            final long q = (dividend >>> 1) / divisor << 1;
+            final long r = dividend - q * divisor;
+            return q + ((r | ~(r - divisor)) >>> Long.SIZE - 1);
          }
-
-        if (dividend > 0) //  Both inputs non-negative
-            return dividend/divisor;
-        else {
-            /*
-             * For simple code, leveraging BigInteger.  Longer and faster
-             * code written directly in terms of operations on longs is
-             * possible; see "Hacker's Delight" for divide and remainder
-             * algorithms.
-             */
-            return toUnsignedBigInteger(dividend).
-                divide(toUnsignedBigInteger(divisor)).longValue();
-        }
+        return (dividend & ~(dividend - divisor)) >>> Long.SIZE - 1;
      }

      /**
@@ -1701,15 +1690,13 @@
       * @since 1.8
       */
      public static long remainderUnsigned(long dividend, long divisor) {
-        if (dividend > 0 && divisor > 0) { // signed comparisons
-            return dividend % divisor;
-        } else {
-            if (compareUnsigned(dividend, divisor) < 0) // Avoid 
explicit check for 0 divisor
-                return dividend;
-            else
-                return toUnsignedBigInteger(dividend).
-                    remainder(toUnsignedBigInteger(divisor)).longValue();
+        // See Hacker's Delight (2nd ed), section 9.3
+        if (divisor >= 0) {
+            final long q = (dividend >>> 1) / divisor << 1;
+            final long r = dividend - q * divisor;
+            return r - (~(r - divisor) >> Long.SIZE - 1 & divisor);
          }
+        return dividend - ((dividend & ~(dividend - divisor)) >> 
Long.SIZE - 1 & divisor);
      }

      // Bit Twiddling
diff --git a/test/jdk/java/lang/Long/Unsigned.java 
b/test/jdk/java/lang/Long/Unsigned.java
--- a/test/jdk/java/lang/Long/Unsigned.java
+++ b/test/jdk/java/lang/Long/Unsigned.java
@@ -375,24 +375,54 @@

      private static int testDivideAndRemainder() {
          int errors = 0;
-        long MAX_UNSIGNED_INT = Integer.toUnsignedLong(0xffff_ffff);
+        long TWO_31 = 1L << Integer.SIZE - 1;
+        long TWO_32 = 1L << Integer.SIZE;
+        long TWO_33 = 1L << Integer.SIZE + 1;
+        BigInteger NINETEEN = BigInteger.valueOf(19L);
+        BigInteger TWO_63 = BigInteger.ONE.shiftLeft(Long.SIZE - 1);
+        BigInteger TWO_64 = BigInteger.ONE.shiftLeft(Long.SIZE);

          BigInteger[] inRange = {
-            BigInteger.valueOf(0L),
-            BigInteger.valueOf(1L),
-            BigInteger.valueOf(10L),
-            BigInteger.valueOf(2147483646L),   // Integer.MAX_VALUE - 1
-            BigInteger.valueOf(2147483647L),   // Integer.MAX_VALUE
-            BigInteger.valueOf(2147483648L),   // Integer.MAX_VALUE + 1
+            BigInteger.ZERO,
+            BigInteger.ONE,
+            BigInteger.TEN,
+            NINETEEN,
+
+            BigInteger.valueOf(TWO_31 - 19L),
+            BigInteger.valueOf(TWO_31 - 10L),
+            BigInteger.valueOf(TWO_31 - 1L),
+            BigInteger.valueOf(TWO_31),
+            BigInteger.valueOf(TWO_31 + 1L),
+            BigInteger.valueOf(TWO_31 + 10L),
+            BigInteger.valueOf(TWO_31 + 19L),

-            BigInteger.valueOf(MAX_UNSIGNED_INT - 1L),
-            BigInteger.valueOf(MAX_UNSIGNED_INT),
+            BigInteger.valueOf(TWO_32 - 19L),
+            BigInteger.valueOf(TWO_32 - 10L),
+            BigInteger.valueOf(TWO_32 - 1L),
+            BigInteger.valueOf(TWO_32),
+            BigInteger.valueOf(TWO_32 + 1L),
+            BigInteger.valueOf(TWO_32 + 10L),
+            BigInteger.valueOf(TWO_32 - 19L),

-            BigInteger.valueOf(Long.MAX_VALUE - 1L),
-            BigInteger.valueOf(Long.MAX_VALUE),
-            BigInteger.valueOf(Long.MAX_VALUE).add(BigInteger.ONE),
+            BigInteger.valueOf(TWO_33 - 19L),
+            BigInteger.valueOf(TWO_33 - 10L),
+            BigInteger.valueOf(TWO_33 - 1L),
+            BigInteger.valueOf(TWO_33),
+            BigInteger.valueOf(TWO_33 + 1L),
+            BigInteger.valueOf(TWO_33 + 10L),
+            BigInteger.valueOf(TWO_33 + 19L),

-            TWO.pow(64).subtract(BigInteger.ONE)
+            TWO_63.subtract(NINETEEN),
+            TWO_63.subtract(BigInteger.TEN),
+            TWO_63.subtract(BigInteger.ONE),
+            TWO_63,
+            TWO_63.add(BigInteger.ONE),
+            TWO_63.add(BigInteger.TEN),
+            TWO_63.add(NINETEEN),
+
+            TWO_64.subtract(NINETEEN),
+            TWO_64.subtract(BigInteger.TEN),
+            TWO_64.subtract(BigInteger.ONE),
          };

          for(BigInteger dividend : inRange) {