Optimize the worst case of RuntimeLong division and remainder.

sjrd · sjrd · commit 65fd9b047729 · 2025-07-16T23:34:15.000+02:00
TODO: Write down the proof.
diff --git a/linker-private-library/src/main/scala/org/scalajs/linker/runtime/RuntimeLong.scala b/linker-private-library/src/main/scala/org/scalajs/linker/runtime/RuntimeLong.scala
@@ -76,10 +76,9 @@ final class RuntimeLong(val lo: Int, val hi: Int) {
 
   // A few operator-friendly methods used by the division algorithms
 
-  @inline private def <<(b: Int): RuntimeLong = RuntimeLong.shl(this, b)
-  @inline private def >>>(b: Int): RuntimeLong = RuntimeLong.shr(this, b)
   @inline private def +(b: RuntimeLong): RuntimeLong = RuntimeLong.add(this, b)
   @inline private def -(b: RuntimeLong): RuntimeLong = RuntimeLong.sub(this, b)
+  @inline private def *(b: RuntimeLong): RuntimeLong = RuntimeLong.mul(this, b)
 }
 
 object RuntimeLong {
@@ -910,7 +909,7 @@ object RuntimeLong {
   }
 
   def divideImpl(alo: Int, ahi: Int, blo: Int, bhi: Int): Int = {
-    if (isZero(blo, bhi))
+    if (bothZero(blo, bhi))
       throw new ArithmeticException("/ by zero")
 
     if (isInt32(alo, ahi)) {
@@ -950,7 +949,7 @@ object RuntimeLong {
   }
 
   def divideUnsignedImpl(alo: Int, ahi: Int, blo: Int, bhi: Int): Int = {
-    if (isZero(blo, bhi))
+    if (bothZero(blo, bhi))
       throw new ArithmeticException("/ by zero")
 
     if (isUInt32(ahi)) {
@@ -968,7 +967,7 @@ object RuntimeLong {
   }
 
   private def unsigned_/(alo: Int, ahi: Int, blo: Int, bhi: Int): Int = {
-    // This method is not called if isInt32(alo, ahi) nor if isZero(blo, bhi)
+    // This method is not called if isInt32(alo, ahi) nor if bothZero(blo, bhi)
     if (isUnsignedSafeDouble(ahi)) {
       if (isUnsignedSafeDouble(bhi)) {
         val aDouble = asSafeDouble(alo, ahi)
@@ -1003,7 +1002,7 @@ object RuntimeLong {
   }
 
   def remainderImpl(alo: Int, ahi: Int, blo: Int, bhi: Int): Int = {
-    if (isZero(blo, bhi))
+    if (bothZero(blo, bhi))
       throw new ArithmeticException("/ by zero")
 
     if (isInt32(alo, ahi)) {
@@ -1038,7 +1037,7 @@ object RuntimeLong {
   }
 
   def remainderUnsignedImpl(alo: Int, ahi: Int, blo: Int, bhi: Int): Int = {
-    if (isZero(blo, bhi))
+    if (bothZero(blo, bhi))
       throw new ArithmeticException("/ by zero")
 
     if (isUInt32(ahi)) {
@@ -1056,7 +1055,7 @@ object RuntimeLong {
   }
 
   private def unsigned_%(alo: Int, ahi: Int, blo: Int, bhi: Int): Int = {
-    // This method is not called if isInt32(alo, ahi) nor if isZero(blo, bhi)
+    // This method is not called if isInt32(alo, ahi) nor if bothZero(blo, bhi)
     if (isUnsignedSafeDouble(ahi)) {
       if (isUnsignedSafeDouble(bhi)) {
         val aDouble = asSafeDouble(alo, ahi)
@@ -1088,71 +1087,97 @@ object RuntimeLong {
    *  remainder. Stores the hi word of the result in `hiReturn`, and returns
    *  the lo word.
    */
+  @inline // inlined twice; specializes for askQuotient
   private def unsignedDivModHelper(alo: Int, ahi: Int, blo: Int, bhi: Int,
       askQuotient: Boolean): Int = {
 
-    var shift =
-      inlineNumberOfLeadingZeros(blo, bhi) - inlineNumberOfLeadingZeros(alo, ahi)
-    val initialBShift = new RuntimeLong(blo, bhi) << shift
-    var bShiftLo = initialBShift.lo
-    var bShiftHi = initialBShift.hi
-    var remLo = alo
-    var remHi = ahi
-    var quotLo = 0
-    var quotHi = 0
-
-    /* Invariants:
-     *   bShift == b << shift == b * 2^shift
-     *   quot >= 0
-     *   0 <= rem < 2 * bShift
-     *   quot * b + rem == a
-     *
-     * The loop condition should be
-     *   while (shift >= 0 && !isUnsignedSafeDouble(remHi))
-     * but we manually inline isUnsignedSafeDouble because remHi is a var. If
-     * we let the optimizer inline it, it will first store remHi in a temporary
-     * val, which will explose the while condition as a while(true) + if +
-     * break, and we don't want that.
-     */
-    while (shift >= 0 && (remHi & SafeDoubleHiMask) != 0) {
-      if (inlineUnsigned_>=(remLo, remHi, bShiftLo, bShiftHi)) {
-        val newRem =
-          new RuntimeLong(remLo, remHi) - new RuntimeLong(bShiftLo, bShiftHi)
-        remLo = newRem.lo
-        remHi = newRem.hi
-        if (shift < 32)
-          quotLo |= (1 << shift)
-        else
-          quotHi |= (1 << shift) // == (1 << (shift - 32))
+    // scalastyle:off return
+
+    val result = if (bothZero(bhi, blo & 0xffe00000)) {
+      // b < 2^21
+
+      val quotHi = Integer.divideUnsigned(ahi, blo) // takes care of the division by zero check
+      val k = ahi - quotHi * blo // remainder of the above division; k < blo
+      // (alo, k) is exact because it uses at most 32 + 21 = 53 bits
+      val remainingNum = asSafeDouble(alo, k)
+      if (askQuotient)
+        new RuntimeLong(rawToInt(remainingNum / blo.toDouble), quotHi)
+      else
+        new RuntimeLong(rawToInt(remainingNum % blo.toDouble), 0)
+    } else if ((bhi & 0xc0000000) == 0) {
+      // 2^21 <= b < 2^62
+
+      val longNum = new RuntimeLong(alo, ahi)
+      val longDivisor = new RuntimeLong(blo, bhi)
+      val approxDivisor = unsignedToDoubleApprox(blo, bhi)
+      val approxNum = unsignedToDoubleApprox(alo, ahi)
+      val approxQuot = fromUnsignedSafeDouble(approxNum / approxDivisor)
+      val approxRem = longNum - longDivisor * approxQuot
+
+      if (approxRem.hi < 0) {
+        if (askQuotient) approxQuot - new RuntimeLong(1, 0)
+        else approxRem + longDivisor
+      } else if (geu(approxRem, longDivisor)) {
+        if (askQuotient) approxQuot + new RuntimeLong(1, 0)
+        else approxRem - longDivisor
+      } else {
+        if (askQuotient) approxQuot
+        else approxRem
       }
-      shift -= 1
-      val newBShift = new RuntimeLong(bShiftLo, bShiftHi) >>> 1
-      bShiftLo = newBShift.lo
-      bShiftHi = newBShift.hi
+    } else {
+      // 2^62 <= b
+      return unsignedDivModHugeDivisor(alo, ahi, blo, bhi, askQuotient)
     }
 
-    // Now rem < 2^53, we can finish with a double division
-    if (inlineUnsigned_>=(remLo, remHi, blo, bhi)) {
-      val remDouble = asSafeDouble(remLo, remHi)
-      val bDouble = asSafeDouble(blo, bhi)
+    hiReturn = result.hi
+    result.lo
+
+    // scalastyle:on return
+  }
+
+  private def unsignedDivModHugeDivisor(alo: Int, ahi: Int, blo: Int, bhi: Int,
+      askQuotient: Boolean): Int = {
+
+    /* Called for b >= 2^62.
+     * Such huge divisors are practically useless, but they defeat the
+     * correction code of the fast algorithm above.
+     * Since there are only 4 possible outcomes for the quotient, we perform
+     * a "binary search" among those.
+     */
+
+    val a = new RuntimeLong(alo, ahi)
+    val b = new RuntimeLong(blo, bhi)
 
-      if (askQuotient) {
-        val rem_div_bDouble = fromUnsignedSafeDouble(remDouble / bDouble)
-        val newQuot = new RuntimeLong(quotLo, quotHi) + rem_div_bDouble
-        hiReturn = newQuot.hi
-        newQuot.lo
+    var quot = 0
+
+    // Since b >= 2^62, we know that rem < 4*b (mathematically)
+
+    val rem1 = if (bhi >= 0) {
+      // Bit 63 is 0: 2*b does not overflow, and we need a 4-way search
+      val b2 = shl(b, 1)
+      if (geu(a, b2)) {
+        quot = 2
+        a - b2
       } else {
-        val rem_mod_bDouble = remDouble % bDouble
-        hiReturn = unsignedSafeDoubleHi(rem_mod_bDouble)
-        unsignedSafeDoubleLo(rem_mod_bDouble)
+        a
       }
     } else {
-      if (askQuotient) {
-        hiReturn = quotHi
-        quotLo
+      a
+    }
+
+    // Now rem < 2*b (mathematically)
+    val rem1LTUb = ltu(rem1, b) // compute once for code size
+    if (askQuotient) {
+      hiReturn = 0
+      if (rem1LTUb) quot else quot + 1
+    } else {
+      if (rem1LTUb) {
+        hiReturn = rem1.hi
+        rem1.lo
       } else {
-        hiReturn = remHi
-        remLo
+        val rem2 = rem1 - b
+        hiReturn = rem2.hi
+        rem2.lo
       }
     }
   }
@@ -1163,9 +1188,9 @@ object RuntimeLong {
     s.jsSubstring(start)
   }
 
-  /** Tests whether the long (lo, hi) is 0. */
-  @inline def isZero(lo: Int, hi: Int): Boolean =
-    (lo | hi) == 0
+  /** Tests whether `a == 0 && b == 0` with a single comparison. */
+  @inline def bothZero(a: Int, b: Int): Boolean =
+    (a | b) == 0
 
   /** Tests whether the long (lo, hi)'s mathematical value fits in a signed Int. */
   @inline def isInt32(lo: Int, hi: Int): Boolean =
@@ -1285,17 +1310,6 @@ object RuntimeLong {
   @inline def log2OfPowerOfTwo(i: Int): Int =
     31 - Integer.numberOfLeadingZeros(i)
 
-  /** Returns the number of leading zeros in the given long (lo, hi). */
-  @inline def inlineNumberOfLeadingZeros(lo: Int, hi: Int): Int =
-    if (hi != 0) Integer.numberOfLeadingZeros(hi)
-    else Integer.numberOfLeadingZeros(lo) + 32
-
-  /** Tests whether the unsigned long (alo, ahi) is >= (blo, bhi). */
-  @inline
-  def inlineUnsigned_>=(alo: Int, ahi: Int, blo: Int, bhi: Int): Boolean =
-    if (ahi == bhi) inlineUnsignedInt_>=(alo, blo)
-    else inlineUnsignedInt_>=(ahi, bhi)
-
   @inline
   def inlineUnsignedInt_<(a: Int, b: Int): Boolean =
     (a ^ 0x80000000) < (b ^ 0x80000000)
diff --git a/linker/shared/src/test/scala/org/scalajs/linker/LibrarySizeTest.scala b/linker/shared/src/test/scala/org/scalajs/linker/LibrarySizeTest.scala
@@ -70,9 +70,9 @@ class LibrarySizeTest {
     )
 
     testLinkedSizes(
-      expectedFastLinkSize = 147395,
-      expectedFullLinkSizeWithoutClosure = 87201,
-      expectedFullLinkSizeWithClosure = 20680,
+      expectedFastLinkSize = 150451,
+      expectedFullLinkSizeWithoutClosure = 89534,
+      expectedFullLinkSizeWithClosure = 20699,
       classDefs,
       moduleInitializers = MainTestModuleInitializers
     )
diff --git a/project/Build.scala b/project/Build.scala
@@ -2053,32 +2053,32 @@ object Build {
           case `default212Version` =>
             if (!useMinifySizes) {
               Some(ExpectedSizes(
-                  fastLink = 624000 to 625000,
+                  fastLink = 627000 to 628000,
                   fullLink = 94000 to 95000,
                   fastLinkGz = 75000 to 79000,
                   fullLinkGz = 24000 to 25000,
               ))
             } else {
               Some(ExpectedSizes(
-                  fastLink = 425000 to 426000,
-                  fullLink = 282000 to 283000,
-                  fastLinkGz = 60000 to 61000,
+                  fastLink = 427000 to 428000,
+                  fullLink = 284000 to 285000,
+                  fastLinkGz = 61000 to 62000,
                   fullLinkGz = 43000 to 44000,
               ))
             }
 
           case `default213Version` =>
             if (!useMinifySizes) {
               Some(ExpectedSizes(
-                  fastLink = 442000 to 443000,
+                  fastLink = 445000 to 446000,
                   fullLink = 90000 to 91000,
                   fastLinkGz = 57000 to 58000,
                   fullLinkGz = 24000 to 25000,
               ))
             } else {
               Some(ExpectedSizes(
-                  fastLink = 301000 to 302000,
-                  fullLink = 258000 to 259000,
+                  fastLink = 303000 to 304000,
+                  fullLink = 261000 to 262000,
                   fastLinkGz = 47000 to 48000,
                   fullLinkGz = 42000 to 43000,
               ))
diff --git a/test-suite/shared/src/test/scala/org/scalajs/testsuite/javalib/lang/LongTest.scala b/test-suite/shared/src/test/scala/org/scalajs/testsuite/javalib/lang/LongTest.scala
@@ -822,6 +822,53 @@ class LongTest {
     assertThrows(classOf[ArithmeticException], JLong.remainderUnsigned(5L, 0L))
   }
 
+  @Test def divideRemainderUnsignedHugeDivisors(): Unit = {
+    @inline def test(x: Long, y: Long, expectedQuot: Long, expectedRem: Long): Unit = {
+      assertEquals(expectedQuot, JLong.divideUnsigned(x, y))
+      assertEquals(expectedQuot, JLong.divideUnsigned(hideFromOptimizer(x), y))
+      assertEquals(expectedQuot, JLong.divideUnsigned(x, hideFromOptimizer(y)))
+      assertEquals(expectedQuot, JLong.divideUnsigned(hideFromOptimizer(x), hideFromOptimizer(y)))
+
+      assertEquals(expectedRem, JLong.remainderUnsigned(x, y))
+      assertEquals(expectedRem, JLong.remainderUnsigned(hideFromOptimizer(x), y))
+      assertEquals(expectedRem, JLong.remainderUnsigned(x, hideFromOptimizer(y)))
+      assertEquals(expectedRem, JLong.remainderUnsigned(hideFromOptimizer(x), hideFromOptimizer(y)))
+    }
+
+    test(-63003L, -2L, 0L, -63003L) // this particular case fails if we don't have the "huge" path at all
+    test(-3L, -2L, 0L, -3L)
+    test(-2L, -2L, 1L, 0L)
+    test(-1L, -2L, 1L, 1L)
+
+    test(0x7ffffffffffffffeL, 0x7fffffffffffffffL, 0L, 0x7ffffffffffffffeL)
+    test(0x7fffffffffffffffL, 0x7fffffffffffffffL, 1L, 0L)
+    test(0x8000000000000000L, 0x7fffffffffffffffL, 1L, 1L)
+    test(0xfffffffffffffffdL, 0x7fffffffffffffffL, 1L, 0x7ffffffffffffffeL)
+    test(0xfffffffffffffffeL, 0x7fffffffffffffffL, 2L, 0L)
+    test(0xffffffffffffffffL, 0x7fffffffffffffffL, 2L, 1L)
+
+    test(0x7ffffffffffffff8L, 0x7ffffffffffffffeL, 0L, 0x7ffffffffffffff8L)
+    test(0x7ffffffffffffffeL, 0x7ffffffffffffffeL, 1L, 0L)
+    test(0x8000000000000008L, 0x7ffffffffffffffeL, 1L, 0xaL)
+    test(0xffffffffffff09e5L, 0x7ffffffffffffffeL, 1L, 0x7fffffffffff09e7L)
+    test(0xfffffffffffffffbL, 0x7ffffffffffffffeL, 1L, 0x7ffffffffffffffdL)
+    test(0xfffffffffffffffcL, 0x7ffffffffffffffeL, 2L, 0L)
+    test(0xfffffffffffffffdL, 0x7ffffffffffffffeL, 2L, 1L)
+    test(0xffffffffffffffffL, 0x7ffffffffffffffeL, 2L, 3L)
+
+    test(0x3ffffffffffffff0L, 0x4000000000000001L, 0L, 0x3ffffffffffffff0L)
+    test(0x4000000000000000L, 0x4000000000000001L, 0L, 0x4000000000000000L)
+    test(0x4000000000000001L, 0x4000000000000001L, 1L, 0L)
+    test(0x4000000000000002L, 0x4000000000000001L, 1L, 1L)
+    test(0x8000000000000001L, 0x4000000000000001L, 1L, 0x4000000000000000L)
+    test(0x8000000000000002L, 0x4000000000000001L, 2L, 0L)
+    test(0x8000000000000003L, 0x4000000000000001L, 2L, 1L)
+    test(0xc000000000000002L, 0x4000000000000001L, 2L, 0x4000000000000000L)
+    test(0xc000000000000003L, 0x4000000000000001L, 3L, 0L)
+    test(0xc000000000000004L, 0x4000000000000001L, 3L, 1L)
+    test(0xffffffffffffffffL, 0x4000000000000001L, 3L, 0x3ffffffffffffffcL)
+  }
+
   @Test def toUnsignedString(): Unit = {
     def test(x: Long, s: String, radix: Int = 10): Unit = {
       assertEquals(s, JLong.toUnsignedString(x, radix))

Original file line number	Diff line number	Diff line change
`@@ -70,9 +70,9 @@ class LibrarySizeTest {`
`70`	`70`	`)`
`71`	`71`
`72`	`72`	`testLinkedSizes(`
`73`		`- expectedFastLinkSize = 147395,`
`74`		`- expectedFullLinkSizeWithoutClosure = 87201,`
`75`		`- expectedFullLinkSizeWithClosure = 20680,`
	`73`	`+ expectedFastLinkSize = 150451,`
	`74`	`+ expectedFullLinkSizeWithoutClosure = 89534,`
	`75`	`+ expectedFullLinkSizeWithClosure = 20699,`
`76`	`76`	`classDefs,`
`77`	`77`	`moduleInitializers = MainTestModuleInitializers`
`78`	`78`	`)`