WiP Optimize the worst case of RuntimeLong division and remainder.

sjrd · sjrd · commit 62238a6bbec2 · 2025-06-23T16:56:37.000+02:00
TODO: Check the case where the divisor is &gt;= 2^62.
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 {
@@ -1094,73 +1093,45 @@ 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))
-      }
-      shift -= 1
-      val newBShift = new RuntimeLong(bShiftLo, bShiftHi) >>> 1
-      bShiftLo = newBShift.lo
-      bShiftHi = newBShift.hi
-    }
-
-    // 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)
-
-      if (askQuotient) {
-        val rem_div_bDouble = fromUnsignedSafeDouble(remDouble / bDouble)
-        val newQuot = new RuntimeLong(quotLo, quotHi) + rem_div_bDouble
-        hiReturn = newQuot.hi
-        newQuot.lo
-      } else {
-        val rem_mod_bDouble = remDouble % bDouble
-        hiReturn = unsignedSafeDoubleHi(rem_mod_bDouble)
-        unsignedSafeDoubleLo(rem_mod_bDouble)
-      }
+    val result = if (bhi == 0 && inlineUnsignedInt_<(blo, 1 << 21)) {
+      // 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 (askQuotient) {
-        hiReturn = quotHi
-        quotLo
+      // b >= 2^21
+
+      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 {
-        hiReturn = remHi
-        remLo
+        if (askQuotient) approxQuot
+        else approxRem
       }
     }
+
+    hiReturn = result.hi
+    result.lo
   }
 
   @inline
@@ -1291,17 +1262,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 = 147932,
-      expectedFullLinkSizeWithoutClosure = 87506,
-      expectedFullLinkSizeWithClosure = 20696,
+      expectedFastLinkSize = 148748,
+      expectedFullLinkSizeWithoutClosure = 88261,
+      expectedFullLinkSizeWithClosure = 20680,
       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 = 625000 to 626000,
                   fullLink = 94000 to 95000,
                   fastLinkGz = 75000 to 79000,
                   fullLinkGz = 24000 to 25000,
               ))
             } else {
               Some(ExpectedSizes(
-                  fastLink = 425000 to 426000,
-                  fullLink = 282000 to 283000,
-                  fastLinkGz = 61000 to 62000,
+                  fastLink = 426000 to 427000,
+                  fullLink = 283000 to 284000,
+                  fastLinkGz = 60000 to 61000,
                   fullLinkGz = 43000 to 44000,
               ))
             }
 
           case `default213Version` =>
             if (!useMinifySizes) {
               Some(ExpectedSizes(
-                  fastLink = 442000 to 443000,
+                  fastLink = 443000 to 444000,
                   fullLink = 90000 to 91000,
                   fastLinkGz = 57000 to 58000,
                   fullLinkGz = 24000 to 25000,
               ))
             } else {
               Some(ExpectedSizes(
-                  fastLink = 301000 to 302000,
-                  fullLink = 258000 to 259000,
+                  fastLink = 302000 to 303000,
+                  fullLink = 259000 to 260000,
                   fastLinkGz = 47000 to 48000,
                   fullLinkGz = 42000 to 43000,
               ))

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 = 147932,`
`74`		`- expectedFullLinkSizeWithoutClosure = 87506,`
`75`		`- expectedFullLinkSizeWithClosure = 20696,`
	`73`	`+ expectedFastLinkSize = 148748,`
	`74`	`+ expectedFullLinkSizeWithoutClosure = 88261,`
	`75`	`+ expectedFullLinkSizeWithClosure = 20680,`
`76`	`76`	`classDefs,`
`77`	`77`	`moduleInitializers = MainTestModuleInitializers`
`78`	`78`	`)`