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

[Raffaello Giulietti]

Hi,

here's a patch for [1], which is currently unassigned. Anybody willing 
to sponsor it?

The fix is based on "Hacker's Delight" (2nd ed), section 9.3 and makes 
use of longs only, no BigInteger, no garbage to collect. It is faster 
and "greener" than the current code.

Contrary to the dramatic plea in the subject, with this fix I think 
there's no pressing need for an intrinsic.

The fix should be back-portable to 11 and 8, where the methods first 
appeared, but I only tried on a current changeset [2].

Passes tier1.

If anybody needs the fix as attachment, just let me know.


Greetings
Raffaello

----

[1] https://bugs.openjdk.java.net/browse/JDK-8238669
[2] http://hg.openjdk.java.net/jdk/jdk/rev/2fc1acf9c894




# HG changeset patch
# User lello
# Date 1599044207 -7200
#      Wed Sep 02 12:56:47 2020 +0200
# Node ID 7a844bedebbc753c5dee265fba8fe7ed30a79d31
# Parent  2fc1acf9c89458a1d05915963961d7c780cb6ad3
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