8000 WiP Optimize RuntimeLong division and remainder. · scala-js/scala-js@3883616 · GitHub
[go: up one dir, main page]
Skip to content 8000

Commit 3883616

Browse files
sjrdsjrd
committed
WiP Optimize RuntimeLong division and remainder.
TODO: Check the case where the divisor is >= 2^62. TODO: Write down the proof.
1 parent d9184b9 commit 3883616

File tree

3 files changed

+82
-217
lines changed

3 files changed

+82
-217
lines changed

‎linker-private-library/src/main/scala/org/scalajs/linker/runtime/RuntimeLong.scala

Lines changed: 71 additions & 206 deletions
Original file line numberDiff line numberDiff line change
@@ -80,6 +80,7 @@ final class RuntimeLong(val lo: Int, val hi: Int) {
8080
@inline private def >>>(b: Int): RuntimeLong = RuntimeLong.shr(this, b)
8181
@inline private def +(b: RuntimeLong): RuntimeLong = RuntimeLong.add(this, b)
8282
@inline private def -(b: RuntimeLong): RuntimeLong = RuntimeLong.sub(this, b)
83+
@inline private def *(b: RuntimeLong): RuntimeLong = RuntimeLong.mul(this, b)
8384
}
8485

8586
object RuntimeLong {
@@ -916,37 +917,11 @@ object RuntimeLong {
916917
}
917918

918919
def divideImpl(alo: Int, ahi: Int, blo: Int, bhi: Int): Int = {
919-
if (isZero(blo, bhi))
920-
throw new ArithmeticException("/ by zero")
921-
922-
if (isInt32(alo, ahi)) {
923-
if (isInt32(blo, bhi)) {
924-
if (alo == Int.MinValue && blo == -1) {
925-
hiReturn = 0
926-
Int.MinValue
927-
} else {
928-
val lo = alo / blo
929-
hiReturn = lo >> 31
930-
lo
931-
}
932-
} else {
933-
// Either a == Int.MinValue && b == (Int.MaxValue + 1), or (abs(b) > abs(a))
934-
if (alo == Int.MinValue && (blo == 0x80000000 && bhi == 0)) {
935-
hiReturn = -1
936-
-1
937-
} else {
938-
// 0L, because abs(b) > abs(a)
939-
hiReturn = 0
940-
0
941-
}
942-
}
943-
} else {
944-
val aAbs = inline_abs(alo, ahi)
945-
val bAbs = inline_abs(blo, bhi)
946-
val absRLo = unsigned_/(aAbs.lo, aAbs.hi, bAbs.lo, bAbs.hi)
947-
if ((ahi ^ bhi) >= 0) absRLo // a and b have the same sign bit
948-
else inline_negate_hiReturn(absRLo, hiReturn)
949-
}
920+
val aAbs = inline_abs(alo, ahi)
921+
val bAbs = inline_abs(blo, bhi)
922+
val absRLo = unsigned_/(aAbs.lo, aAbs.hi, bAbs.lo, bAbs.hi)
923+
if ((ahi ^ bhi) >= 0) absRLo // a and b have the same sign bit
924+
else inline_negate_hiReturn(absRLo, hiReturn)
950925
}
951926

952927
@inline
@@ -955,52 +930,13 @@ object RuntimeLong {
955930
new RuntimeLong(lo, hiReturn)
956931
}
957932

958-
def divideUnsignedImpl(alo: Int, ahi: Int, blo: Int, bhi: Int): Int = {
959-
if (isZero(blo, bhi))
960-
throw new ArithmeticException("/ by zero")
933+
@inline
934+
def divideUnsignedImpl(alo: Int, ahi: Int, blo: Int, bhi: Int): Int =
935+
unsigned_/(alo, ahi, blo, bhi)
961936

962-
if (isUInt32(ahi)) {
963-
if (isUInt32(bhi)) {
964-
hiReturn = 0
965-
Integer.divideUnsigned(alo, blo)
966-
} else {
967-
// a < b
968-
hiReturn = 0
969-
0
970-
}
971-
} else {
972-
unsigned_/(alo, ahi, blo, bhi)
973-
}
974-
}
975-
976-
private def unsigned_/(alo: Int, ahi: Int, blo: Int, bhi: Int): Int = {
977-
// This method is not called if isInt32(alo, ahi) nor if isZero(blo, bhi)
978-
if (isUnsignedSafeDouble(ahi)) {
979-
if (isUnsignedSafeDouble(bhi)) {
980-
val aDouble = asUnsignedSafeDouble(alo, ahi)
981-
val bDouble = asUnsignedSafeDouble(blo, bhi)
982-
val rDouble = aDouble / bDouble
983-
hiReturn = unsignedSafeDoubleHi(rDouble)
984-
unsignedSafeDoubleLo(rDouble)
985-
} else {
986-
// 0L, because b > a
987-
hiReturn = 0
988-
0
989-
}
990-
} else {
991-
if (bhi == 0 && isPowerOfTwo_IKnowItsNot0(blo)) {
992-
val pow = log2OfPowerOfTwo(blo)
993-
hiReturn = ahi >>> pow
994-
(alo >>> pow) | (ahi << 1 << (31-pow))
995-
} else if (blo == 0 && isPowerOfTwo_IKnowItsNot0(bhi)) {
996-
val pow = log2OfPowerOfTwo(bhi)
997-
hiReturn = 0
998-
ahi >>> pow
999-
} else {
1000-
unsignedDivModHelper(alo, ahi, blo, bhi, askQuotient = true)
1001-
}
1002-
}
1003-
}
937+
@noinline
938+
private def unsigned_/(alo: Int, ahi: Int, blo: Int, bhi: Int): Int =
939+
unsignedDivModHelper(alo, ahi, blo, bhi, askQuotient = true)
1004940

1005941
@inline
1006942
def remainder(a: RuntimeLong, b: RuntimeLong): RuntimeLong = {
@@ -1009,38 +945,11 @@ object RuntimeLong {
1009945
}
1010946

1011947
def remainderImpl(alo: Int, ahi: Int, blo: Int, bhi: Int): Int = {
1012-
if (isZero(blo, bhi))
1013-
throw new ArithmeticException("/ by zero")
1014-
1015-
if (isInt32(alo, ahi)) {
1016-
if (isInt32(blo, bhi)) {
1017-
if (blo != -1) {
1018-
val lo = alo % blo
1019-
hiReturn = lo >> 31
1020-
lo
1021-
} else {
1022-
// Work around https://github.com/ariya/phantomjs/issues/12198
1023-
hiReturn = 0
1024-
0
1025-
}
1026-
} else {
1027-
// Either a == Int.MinValue && b == (Int.MaxValue + 1), or (abs(b) > abs(a))
1028-
if (alo == Int.MinValue && (blo == 0x80000000 && bhi == 0)) {
1029-
hiReturn = 0
1030-
0
1031-
} else {
1032-
// a, because abs(b) > abs(a)
1033-
hiReturn = ahi
1034-
alo
1035-
}
1036-
}
1037-
} else {
1038-
val aAbs = inline_abs(alo, ahi)
1039-
val bAbs = inline_abs(blo, bhi)
1040-
val absRLo = unsigned_%(aAbs.lo, aAbs.hi, bAbs.lo, bAbs.hi)
1041-
if (ahi < 0) inline_negate_hiReturn(absRLo, hiReturn)
1042-
else absRLo
1043-
}
948+
val aAbs = inline_abs(alo, ahi)
949+
val bAbs = inline_abs(blo, bhi)
950+
val absRLo = unsigned_%(aAbs.lo, aAbs.hi, bAbs.lo, bAbs.hi)
951+
if (ahi < 0) inline_negate_hiReturn(absRLo, hiReturn)
952+
else absRLo
1044953
}
1045954

1046955
@inline
@@ -1049,122 +958,74 @@ object RuntimeLong {
1049958
new RuntimeLong(lo, hiReturn)
1050959
}
1051960

1052-
def remainderUnsignedImpl(alo: Int, ahi: Int, blo: Int, bhi: Int): Int = {
1053-
if (isZero(blo, bhi))
1054-
throw new ArithmeticException("/ by zero")
1055-
1056-
if (isUInt32(ahi)) {
1057-
if (isUInt32(bhi)) {
1058-
hiReturn = 0
1059-
Integer.remainderUnsigned(alo, blo)
1060-
} else {
1061-
// a < b
1062-
hiReturn = ahi
1063-
alo
1064-
}
1065-
} else {
1066-
unsigned_%(alo, ahi, blo, bhi)
1067-
}
1068-
}
961+
@inline
962+
private def remainderUnsignedImpl(alo: Int, ahi: Int, blo: Int, bhi: Int): Int =
963+
unsigned_%(alo, ahi, blo, bhi)
1069964

1070-
private def unsigned_%(alo: Int, ahi: Int, blo: Int, bhi: Int): Int = {
1071-
// This method is not called if isInt32(alo, ahi) nor if isZero(blo, bhi)
1072-
if (isUnsignedSafeDouble(ahi)) {
1073-
if (isUnsignedSafeDouble(bhi)) {
1074-
val aDouble = asUnsignedSafeDouble(alo, ahi)
1075-
val bDouble = asUnsignedSafeDouble(blo, bhi)
1076-
val rDouble = aDouble % bDouble
1077-
hiReturn = unsignedSafeDoubleHi(rDouble)
1078-
unsignedSafeDoubleLo(rDouble)
1079-
} else {
1080-
// a, because b > a
1081-
hiReturn = ahi
1082-
alo
1083-
}
1084-
} else {
1085-
if (bhi == 0 && isPowerOfTwo_IKnowItsNot0(blo)) {
1086-
hiReturn = 0
1087-
alo & (blo - 1)
1088-
} else if (blo == 0 && isPowerOfTwo_IKnowItsNot0(bhi)) {
1089-
hiReturn = ahi & (bhi - 1)
1090-
alo
1091-
} else {
1092-
unsignedDivModHelper(alo, ahi, blo, bhi, askQuotient 57AE = false)
1093-
}
1094-
}
1095-
}
965+
@noinline
966+
private def unsigned_%(alo: Int, ahi: Int, blo: Int, bhi: Int): Int =
967+
unsignedDivModHelper(alo, ahi, blo, bhi, askQuotient = false)
1096968

1097969
/** Helper for `unsigned_/` and `unsigned_%`.
1098970
*
1099971
* If `askQuotient` is true, computes the quotient, otherwise computes the
1100972
* remainder. Stores the hi word of the result in `hiReturn`, and returns
1101973
* the lo word.
1102974
*/
975+
@inline
1103976
private def unsignedDivModHelper(alo: Int, ahi: Int, blo: Int, bhi: Int,
1104977
askQuotient: Boolean): Int = {
1105978

1106-
var shift =
1107-
inlineNumberOfLeadingZeros(blo, bhi) - inlineNumberOfLeadingZeros(alo, ahi)
1108-
val initialBShift = new RuntimeLong(blo, bhi) << shift
1109-
var bShiftLo = initialBShift.lo
1110-
var bShiftHi = initialBShift.hi
1111-
var remLo = alo
1112-
var remHi = ahi
1113-
var quotLo = 0
1114-
var quotHi = 0
1115-
1116-
/* Invariants:
1117-
* bShift == b << shift == b * 2^shift
1118-
* quot >= 0
1119-
* 0 <= rem < 2 * bShift
1120-
* quot * b + rem == a
1121-
*
1122-
* The loop condition should be
1123-
* while (shift >= 0 && !isUnsignedSafeDouble(remHi))
1124-
* but we manually inline isUnsignedSafeDouble because remHi is a var. If
1125-
* we let the optimizer inline it, it will first store remHi in a temporary
1126-
* val, which will explose the while condition as a while(true) + if +
1127-
* break, and we don't want that.
1128-
*/
1129-
while (shift >= 0 && (remHi & UnsignedSafeDoubleHiMask) != 0) {
1130-
if (inlineUnsigned_>=(remLo, remHi, bShiftLo, bShiftHi)) {
1131-
val newRem =
1132-
new RuntimeLong(remLo, remHi) - new RuntimeLong(bShiftLo, bShiftHi)
1133-
remLo = newRem.lo
1134-
remHi = newRem.hi
1135-
if (shift < 32)
1136-
quotLo |= (1 << shift)
1137-
else
1138-
quotHi |= (1 << shift) // == (1 << (shift - 32))
1139-
}
1140-
shift -= 1
1141-
val newBShift = new RuntimeLong(bShiftLo, bShiftHi) >>> 1
1142-
bShiftLo = newBShift.lo
1143-
bShiftHi = newBShift.hi
1144-
}
1145-
1146-
// Now rem < 2^53, we can finish with a double division
1147-
if (inlineUnsigned_>=(remLo, remHi, blo, bhi)) {
1148-
val remDouble = asUnsignedSafeDouble(remLo, remHi)
1149-
val bDouble = asUnsignedSafeDouble(blo, bhi)
979+
if (bhi == 0 && inlineUnsignedInt_<(blo, 1 << 21)) {
980+
// b < 2^21
1150981

982+
val quotHi = Integer.divideUnsigned(ahi, blo) // takes care of the division by zero check
983+
val k = ahi - quotHi * blo // remainder of the above division; k < blo
984+
// (alo, k) is exact because it uses at most 32 + 21 = 53 bits
985+
val remainingNum = asUnsignedSafeDouble(alo, k)
1151986
if (askQuotient) {
1152-
val rem_div_bDouble = fromUnsignedSafeDouble(remDouble / bDouble)
1153-
val newQuot = new RuntimeLong(quotLo, quotHi) + rem_div_bDouble
1154-
hiReturn = newQuot.hi
1155-
newQuot.lo
987+
hiReturn = quotHi
988+
rawToInt(remainingNum / blo.toDouble)
1156989
} else {
1157-
val rem_mod_bDouble = remDouble % bDouble
1158-
hiReturn = unsignedSafeDoubleHi(rem_mod_bDouble)
1159-
unsignedSafeDoubleLo(rem_mod_bDouble)
990+
hiReturn = 0
991+
rawToInt(remainingNum % blo.toDouble)
1160992
}
1161993
} else {
994+
// b >= 2^21
995+
996+
val longNum = new RuntimeLong(alo, ahi)
997+
val longDivisor = new RuntimeLong(blo, bhi)
998+
val approxDivisor = unsignedToDoubleApprox(blo, bhi)
999+
10000 val approxNum = unsignedToDoubleApprox(alo, ahi)
1000+
val approxQuot = fromUnsignedSafeDouble(approxNum / approxDivisor)
1001+
val approxRem = longNum - longDivisor * approxQuot
1002+
11621003
if (askQuotient) {
1163-
hiReturn = quotHi
1164-
quotLo
1004+
if (approxRem.hi < 0) {
1005+
val result = approxQuot - new RuntimeLong(1, 0)
1006+
hiReturn = result.hi
1007+
result.lo
1008+
} else if (geu(approxRem, longDivisor)) {
1009+
val result = approxQuot + new RuntimeLong(1, 0)
1010+
hiReturn = result.hi
1011+
result.lo
1012+
} else {
1013+
hiReturn = approxQuot.hi
1014+
approxQuot.lo
1015+
}
11651016
} else {
1166-
hiReturn = remHi
1167-
remLo
1017+
if (approxRem.hi < 0) {
1018+
val result = approxRem + longDivisor
1019+
hiReturn = result.hi
1020+
result.lo
1021+
} else if (geu(approxRem, longDivisor)) {
1022+
val result = approxRem - longDivisor
1023+
hiReturn = result.hi
1024+
result.lo
1025+
} else {
1026+
hiReturn = approxRem.hi
1027+
approxRem.lo
1028+
}
11681029
}
11691030
}
11701031
}
@@ -1215,6 +1076,10 @@ object RuntimeLong {
12151076
@inline def unsignedSafeDoubleHi(x: Double): Int =
12161077
rawToInt(x / TwoPow32)
12171078

1079+
/** Converts the unsigned long (lo, hi) to a Double, subject to rounding. */
1080+
@inline def unsignedToDoubleApprox(lo: Int, hi: Int): Double =
1081+
asUint(hi) * TwoPow32 + asUint(lo)
1082+
12181083
/** Interprets an `Int` as an unsigned integer and returns its value as a
12191084
* `Double`.
12201085
*/

‎linker/shared/src/test/scala/org/scalajs/linker/LibrarySizeTest.scala

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -70,8 +70,8 @@ class LibrarySizeTest {
7070
)
7171

7272
testLinkedSizes(
73-
expectedFastLinkSize = 148960,
74-
expectedFullLinkSizeWithoutClosure = 88111,
73+
expectedFastLinkSize = 145632,
74+
expectedFullLinkSizeWithoutClosure = 85305,
7575
expectedFullLinkSizeWithClosure = 20704,
7676
classDefs,
7777
moduleInitializers = MainTestModuleInitializers

‎project/Build.scala

Lines changed: 9 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -2053,32 +2053,32 @@ object Build {
20532053
case `default212Version` =>
20542054
if (!useMinifySizes) {
20552055
Some(ExpectedSizes(
2056-
fastLink = 625000 to 626000,
2056+
fastLink = 622000 to 623000,
20572057
fullLink = 94000 to 95000,
2058-
fastLinkGz = 75000 to 79000,
2058+
fastLinkGz = 75000 to 76000,
20592059
fullLinkGz = 24000 to 25000,
20602060
))
20612061
} else {
20622062
Some(ExpectedSizes(
2063-
fastLink = 425000 to 426000,
2064-
fullLink = 283000 to 284000,
2065-
fastLinkGz = 61000 to 62000,
2063+
fastLink = 423000 to 424000,
2064+
fullLink = 280000 to 281000,
2065+
fastLinkGz = 60000 to 61000,
20662066
fullLinkGz = 43000 to 44000,
20672067
))
20682068
}
20692069

20702070
case `default213Version` =>
20712071
if (!useMinifySizes) {
20722072
Some(ExpectedSizes(
2073-
fastLink = 443000 to 444000,
2073+
fastLink = 440000 to 441000,
20742074
fullLink = 90000 to 91000,
2075-
fastLinkGz = 57000 to 58000,
2075+
fastLinkGz = 56000 to 57000,
20762076
fullLinkGz = 24000 to 25000,
20772077
))
20782078
} else {
20792079
Some(ExpectedSizes(
2080-
fastLink = 301000 to 302000,
2081-
fullLink = 259000 to 260000,
2080+
fastLink = 299000 to 300000,
2081+
fullLink = 256000 to 257000,
20822082
fastLinkGz = 47000 to 48000,
20832083
fullLinkGz = 42000 to 43000,
20842084
))

0 commit comments

Comments
 (0)
0