8000 Remove all the fast paths from RuntimeLong division. · scala-js/scala-js@442e307 · GitHub
[go: up one dir, main page]
Skip to content

Commit 442e307

Browse files
sjrdsjrd
committed
Remove all the fast paths from RuntimeLong division.
Now that the worst case isn't so bad anymore, we remove the fast paths for small values of the numerator. It does make them slower. However, it also makes division more predictable: the time is now dependent only on the divisor, which should be more stable in most applications. It also reduces the overall code size.
1 parent 62238a6 commit 442e307

File tree

3 files changed

+46
-189
lines changed

3 files changed

+46
-189
lines changed

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

Lines changed: 39 additions & 182 deletions
Original file line numberDiff line numberDiff line change
@@ -908,38 +908,12 @@ object RuntimeLong {
908908
new RuntimeLong(lo, hiReturn)
909909
}
910910

911+
@noinline
911912
def divideImpl(alo: Int, ahi: Int, blo: Int, bhi: Int): Int = {
912-
if (isZero(blo, bhi))
913-
throw new ArithmeticException("/ by zero")
914-
915-
if (isInt32(alo, ahi)) {
916-
if (isInt32(blo, bhi)) {
917-
if (alo == Int.MinValue && blo == -1) {
918-
hiReturn = 0
919-
Int.MinValue
920-
} else {
921-
val lo = alo / blo
922-
hiReturn = lo >> 31
923-
lo
924-
}
925-
} else {
926-
// Either a == Int.MinValue && b == (Int.MaxValue + 1), or (abs(b) > abs(a))
927-
if (alo == Int.MinValue && (blo == 0x80000000 && bhi == 0)) {
928-
hiReturn = -1
929-
-1
930-
} else {
931-
// 0L, because abs(b) > abs(a)
932-
hiReturn = 0
933-
0
934-
}
935-
}
936-
} else {
937-
val aAbs = inline_abs(alo, ahi)
938-
val bAbs = inline_abs(blo, bhi)
939-
val absRLo = unsigned_/(aAbs.lo, aAbs.hi, bAbs.lo, bAbs.hi)
940-
if ((ahi ^ bhi) >= 0) absRLo // a and b have the same sign bit
941-
else inline_negate_hiReturn(absRLo, hiReturn)
942-
}
913+
val aAbs = inline_abs(alo, ahi)
914+
val bAbs = inline_abs(blo, bhi)
915+
val absR = unsignedDivRem(aAbs.lo, aAbs.hi, bAbs.lo, bAbs.hi, askQuotient = true)
916+
intoHiReturn(negateIfSign(absR, (ahi ^ bhi) >> 31)) // sign on if a and b have opposite signs
943917
}
944918

945919
@inline
@@ -948,51 +922,10 @@ object RuntimeLong {
948922
new RuntimeLong(lo, hiReturn)
949923
}
950924

925+
@noinline
951926
def divideUnsignedImpl(alo: Int, ahi: Int, blo: Int, bhi: Int): Int = {
952-
if (isZero(blo, bhi))
953-
throw new ArithmeticException("/ by zero")
954-
955-
if (isUInt32(ahi)) {
956-
if (isUInt32(bhi)) {
957-
hiReturn = 0
958-
Integer.divideUnsigned(alo, blo)
959-
} else {
960-
// a < b
961-
hiReturn = 0
962-
0
963-
}
964-
} else {
965-
unsigned_/(alo, ahi, blo, bhi)
966-
}
967-
}
968-
969-
private def unsigned_/(alo: Int, ahi: Int, blo: Int, bhi: Int): Int = {
970-
// This method is not called if isInt32(alo, ahi) nor if isZero(blo, bhi)
971-
if (isUnsignedSafeDouble(ahi)) {
972-
if (isUnsignedSafeDouble(bhi)) {
973-
val aDouble = asSafeDouble(alo, ahi)
974-
val bDouble = asSafeDouble(blo, bhi)
975-
val rDouble = aDouble / bDouble
976-
hiReturn = unsignedSafeDoubleHi(rDouble)
977-
unsignedSafeDoubleLo(rDouble)
978-
} else {
979-
// 0L, because b > a
980-
hiReturn = 0
981-
0
982- 8000
}
983-
} else {
984-
if (bhi == 0 && isPowerOfTwo_IKnowItsNot0(blo)) {
985-
val pow = log2OfPowerOfTwo(blo)
986-
hiReturn = ahi >>> pow
987-
(alo >>> pow) | (ahi << 1 << (31-pow))
988-
} else if (blo == 0 && isPowerOfTwo_IKnowItsNot0(bhi)) {
989-
val pow = log2OfPowerOfTwo(bhi)
990-
hiReturn = 0
991-
ahi >>> pow
992-
} else {
993-
unsignedDivModHelper(alo, ahi, blo, bhi, askQuotient = true)
994-
}
995-
}
927+
val r = unsignedDivRem(alo, ahi, blo, bhi, askQuotient = true)
928+
intoHiReturn(r)
996929
}
997930

998931
@inline
@@ -1001,39 +934,12 @@ object RuntimeLong {
1001934
new RuntimeLong(lo, hiReturn)
1002935
}
1003936

937+
@noinline
1004938
def remainderImpl(alo: Int, ahi: Int, blo: Int, bhi: Int): Int = {
1005-
if (isZero(blo, bhi))
1006-
throw new ArithmeticException("/ by zero")
1007-
1008-
if (isInt32(alo, ahi)) {
1009-
if (isInt32(blo, bhi)) {
1010-
if (blo != -1) {
1011-
val lo = alo % blo
1012-
hiReturn = lo >> 31
1013-
lo
1014-
} else {
1015-
// Work around https://github.com/ariya/phantomjs/issues/12198
1016-
hiReturn = 0
1017-
0
1018-
}
1019-
} else {
1020-
// Either a == Int.MinValue && b == (Int.MaxValue + 1), or (abs(b) > abs(a))
1021-
if (alo == Int.MinValue && (blo == 0x80000000 && bhi == 0)) {
1022-
hiReturn = 0
1023-
0
1024-
} else {
1025-
// a, because abs(b) > abs(a)
1026-
hiReturn = ahi
1027-
alo
1028-
}
1029-
}
1030-
} else {
1031-
val aAbs = inline_abs(alo, ahi)
1032-
val bAbs = inline_abs(blo, bhi)
1033-
val absRLo = unsigned_%(aAbs.lo, aAbs.hi, bAbs.lo, bAbs.hi)
1034-
if (ahi < 0) inline_negate_hiReturn(absRLo, hiReturn)
1035-
else absRLo
1036-
}
939+
val aAbs = inline_abs(alo, ahi)
940+
val bAbs = inline_abs(blo, bhi)
941+
val absR = unsignedDivRem(aAbs.lo, aAbs.hi, bAbs.lo, bAbs.hi, askQuotient = false)
942+
intoHiReturn(negateIfSign(absR, ahi >> 31)) // the result should have the same sign as a
1037943
}
1038944

1039945
@inline
@@ -1042,62 +948,22 @@ object RuntimeLong {
1042948
new RuntimeLong(lo, hiReturn)
1043949
}
1044950

1045-
def remainderUnsignedImpl(alo: Int, ahi: Int, blo: Int, bhi: Int): Int = {
1046-
if (isZero(blo, bhi))
1047-
throw new ArithmeticException("/ by zero")
1048-
1049-
if (isUInt32(ahi)) {
1050-
if (isUInt32(bhi)) {
1051-
hiReturn = 0
1052-
Integer.remainderUnsigned(alo, blo)
1053-
} else {
1054-
// a < b
1055-
hiReturn = ahi
1056-
alo
1057-
}
1058-
} else {
1059-
unsigned_%(alo, ahi, blo, bhi)
1060-
}
1061-
}
1062-
1063-
private def unsigned_%(alo: Int, ahi: Int, blo: Int, bhi: Int): Int = {
1064-
// This method is not called if isInt32(alo, ahi) nor if isZero(blo, bhi)
1065-
if (isUnsignedSafeDouble(ahi)) {
1066-
if (isUnsignedSafeDouble(bhi)) {
1067-
val aDouble = asSafeDouble(alo, ahi)
1068-
val bDouble = asSafeDouble(blo, bhi)
1069-
val rDouble = aDouble % bDouble
1070-
hiReturn = unsignedSafeDoubleHi(rDouble)
1071-
unsignedSafeDoubleLo(rDouble)
1072-
} else {
1073-
// a, because b > a
1074-
hiReturn = ahi
1075-
alo
1076-
}
1077-
} else {
1078-
if (bhi == 0 && isPowerOfTwo_IKnowItsNot0(blo)) {
1079-
hiReturn = 0
1080-
alo & (blo - 1)
1081-
} else if (blo == 0 && isPowerOfTwo_IKnowItsNot0(bhi)) {
1082-
hiReturn = ahi & (bhi - 1)
1083-
alo
1084-
} else {
1085-
unsignedDivModHelper(alo, ahi, blo, bhi, askQuotient = false)
1086-
}
1087-
}
951+
@noinline
952+
private def remainderUnsignedImpl(alo: Int, ahi: Int, blo: Int, bhi: Int): Int = {
953+
val r = unsignedDivRem(alo, ahi, blo, bhi, askQuotient = false)
954+
intoHiReturn(r)
1088955
}
1089956

1090-
/** Helper for `unsigned_/` and `unsigned_%`.
957+
/** Common implementation of the four division operations.
1091958
*
1092959
* If `askQuotient` is true, computes the quotient, otherwise computes the
1093-
* remainder. Stores the hi word of the result in `hiReturn`, and returns
1094-
* the lo word.
960+
* remainder.
1095961
*/
1096-
@inline // inlined twice; specializes for askQuotient
1097-
private def unsignedDivModHelper(alo: Int, ahi: Int, blo: Int, bhi: Int,
1098-
askQuotient: Boolean): Int = {
962+
@inline // inlined 4 times and specialized by askQuotient, so we get 2 copies of each
963+
private def unsignedDivRem(alo: Int, ahi: Int, blo: Int, bhi: Int,
964+
askQuotient: Boolean): RuntimeLong = {
1099965

1100-
val result = if (bhi == 0 && inlineUnsignedInt_<(blo, 1 << 21)) {
966+
if (bhi == 0 && inlineUnsignedInt_<(blo, 1 << 21)) {
1101967
// b < 2^21
1102968

1103969
val quotHi = Integer.divideUnsigned(ahi, blo) // takes care of the division by zero check
@@ -1129,9 +995,6 @@ object RuntimeLong {
1129995
else approxRem
1130996
}
1131997
}
1132-
1133-
hiReturn = result.hi
1134-
result.lo
1135998
}
1136999

11371000
@inline
@@ -1140,18 +1003,10 @@ object RuntimeLong {
11401003
s.jsSubstring(start)
11411004
}
11421005

1143-
/** Tests whether the long (lo, hi) is 0. */
1144-
@inline def isZero(lo: Int, hi: Int): Boolean =
1145-
(lo | hi) == 0
1146-
11471006
/** Tests whether the long (lo, hi)'s mathematical value fits in a signed Int. */
11481007
@inline def isInt32(lo: Int, hi: Int): Boolean =
11491008
hi == (lo >> 31)
11501009

1151-
/** Tests whether the long (_, hi)'s mathematical value fits in an unsigned Int. */
1152-
@inline def isUInt32(hi: Int): Boolean =
1153-
hi == 0
1154-
11551010
/** Tests whether an unsigned long (lo, hi) is a safe Double.
11561011
* This test is in fact slightly stricter than necessary, as it tests
11571012
* whether `x < 2^53`, although x == 2^53 would be a perfectly safe
@@ -1254,14 +1109,6 @@ object RuntimeLong {
12541109
(x | 0).asInstanceOf[Int]
12551110
}
12561111

1257-
/** Tests whether the given non-zero unsigned Int is an exact power of 2. */
1258-
@inline def isPowerOfTwo_IKnowItsNot0(i: Int): Boolean =
1259-
(i & (i - 1)) == 0
1260-
1261-
/** Returns the log2 of the given unsigned Int assuming it is an exact power of 2. */
1262-
@inline def log2OfPowerOfTwo(i: Int): Int =
1263-
31 - Integer.numberOfLeadingZeros(i)
1264-
12651112
@inline
12661113
def inlineUnsignedInt_<(a: Int, b: Int): Boolean =
12671114
(a ^ 0x80000000) < (b ^ 0x80000000)
@@ -1279,14 +1126,25 @@ object RuntimeLong {
12791126
(a ^ 0x80000000) >= (b ^ 0x80000000)
12801127

12811128
@inline
1282-
def inline_negate_hiReturn(lo: Int, hi: Int): Int = {
1283-
val n = sub(new RuntimeLong(0, 0), new RuntimeLong(lo, hi))
1284-
hiReturn = n.hi
1285-
n.lo
1129+
def intoHiReturn(x: RuntimeLong): Int = {
1130+
hiReturn = x.hi
1131+
x.lo
12861132
}
12871133

12881134
@inline
1289-
def inline_abs(lo: Int, hi: Int): RuntimeLong = {
1135+
def inline_abs(lo: Int, hi: Int): RuntimeLong =
1136+
negateIfSign(lo, hi, hi >> 31)
1137+
1138+
@inline
1139+
def negateIfSign(x: RuntimeLong, sign: Int): RuntimeLong =
1140+
negateIfSign(x.lo, x.hi, sign)
1141+
1142+
/** Returns (lo, hi) if sign == 0, or -(lo, hi) if sign == -1.
1143+
*
1144+
* The function assumes that `sign` is either 0 or -1.
1145+
*/
1146+
@inline
1147+
def negateIfSign(lo: Int, hi: Int, sign: Int): RuntimeLong = {
12901148
/* The algorithm here is inspired by Hacker's Delight formula for `abs`.
12911149
* However, a naive application of that formula does not give good code for
12921150
* our RuntimeLong implementation.
@@ -1370,7 +1228,6 @@ object RuntimeLong {
13701228
* imagine" step. We inline the rhs of xhi at the only place where it is
13711229
* used, and we get the final algorithm.
13721230
*/
1373-
val sign = hi >> 31
13741231
val xlo = lo ^ sign
13751232
val rlo = xlo - sign
13761233
val rhi = (hi ^ sign) + ((xlo & ~rlo) >>> 31)

‎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 = 148748,
74-
expectedFullLinkSizeWithoutClosure = 88261,
73+
expectedFastLinkSize = 147372,
74+
expectedFullLinkSizeWithoutClosure = 87808,
7575
expectedFullLinkSizeWithClosure = 20680,
7676
classDefs,
7777
moduleInitializers = MainTestModuleInitializers

‎project/Build.scala

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -2053,15 +2053,15 @@ object Build {
20532053
case `default212Version` =>
20542054
if (!useMinifySizes) {
20552055
Some(ExpectedSizes(
2056-
fastLink = 625000 to 626000,
2056+
fastLink = 624000 to 625000,
20572057
fullLink = 94000 to 95000,
20582058
fastLinkGz = 75000 to 79000,
20592059
fullLinkGz = 24000 to 25000,
20602060
))
20612061
} else {
20622062
Some(ExpectedSizes(
2063-
fastLink = 426000 to 427000,
2064-
fullLink = 283000 to 284000,
2063+
fastLink = 425000 to 426000,
2064+
fullLink = 282000 to 283000,
20652065
fastLinkGz = 60000 to 61000,
20662066
fullLinkGz = 43000 to 44000,
20672067
))
@@ -2070,14 +2070,14 @@ object Build {
20702070
case `default213Version` =>
20712071
if (!useMinifySizes) {
20722072
Some(ExpectedSizes(
2073-
fastLink = 443000 to 444000,
2073+
fastLink = 441000 to 442000,
20742074
fullLink = 90000 to 91000,
20752075
fastLinkGz = 57000 to 58000,
20762076
fullLinkGz = 24000 to 25000,
20772077
))
20782078
} else {
20792079
Some(ExpectedSizes(
2080-
fastLink = 302000 to 303000,
2080+
fastLink = 301000 to 302000,
20812081
fullLink = 259000 to 260000,
20822082
fastLinkGz = 47000 to 48000,
20832083
fullLinkGz = 42000 to 43000,

0 commit comments

Comments
 (0)
0