Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitb500b8f

Browse files
committed
WiP Optimize RuntimeLong division and remainder.
TODO: Check the case where the divisor is >= 2^62.TODO: Write down the proof.
1 parentd9184b9 commitb500b8f

File tree

3 files changed

+69
-247
lines changed

3 files changed

+69
-247
lines changed

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

Lines changed: 58 additions & 236 deletions
Original file line numberDiff line numberDiff line change
@@ -76,10 +76,9 @@ final class RuntimeLong(val lo: Int, val hi: Int) {
7676

7777
// A few operator-friendly methods used by the division algorithms
7878

79-
@inlineprivatedef<<(b:Int):RuntimeLong=RuntimeLong.shl(this, b)
80-
@inlineprivatedef>>>(b:Int):RuntimeLong=RuntimeLong.shr(this, b)
8179
@inlineprivatedef+(b:RuntimeLong):RuntimeLong=RuntimeLong.add(this, b)
8280
@inlineprivatedef-(b:RuntimeLong):RuntimeLong=RuntimeLong.sub(this, b)
81+
@inlineprivatedef*(b:RuntimeLong):RuntimeLong=RuntimeLong.mul(this, b)
8382
}
8483

8584
objectRuntimeLong {
@@ -916,37 +915,11 @@ object RuntimeLong {
916915
}
917916

918917
defdivideImpl(alo:Int,ahi:Int,blo:Int,bhi:Int):Int= {
919-
if (isZero(blo, bhi))
920-
thrownewArithmeticException("/ 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-
vallo= 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-
valaAbs= inline_abs(alo, ahi)
945-
valbAbs= inline_abs(blo, bhi)
946-
valabsRLo= 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-
}
918+
valaAbs= inline_abs(alo, ahi)
919+
valbAbs= inline_abs(blo, bhi)
920+
valabsRLo= unsigned_/(aAbs.lo, aAbs.hi, bAbs.lo, bAbs.hi)
921+
if ((ahi^ bhi)>=0) absRLo// a and b have the same sign bit
922+
else inline_negate_hiReturn(absRLo, hiReturn)
950923
}
951924

952925
@inline
@@ -955,52 +928,13 @@ object RuntimeLong {
955928
newRuntimeLong(lo, hiReturn)
956929
}
957930

958-
defdivideUnsignedImpl(alo:Int,ahi:Int,blo:Int,bhi:Int):Int= {
959-
if (isZero(blo, bhi))
960-
thrownewArithmeticException("/ by zero")
961-
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-
}
931+
@inline
932+
defdivideUnsignedImpl(alo:Int,ahi:Int,blo:Int,bhi:Int):Int=
933+
unsigned_/(alo, ahi, blo, bhi)
975934

976-
privatedefunsigned_/(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-
valaDouble= asUnsignedSafeDouble(alo, ahi)
981-
valbDouble= asUnsignedSafeDouble(blo, bhi)
982-
valrDouble= 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-
valpow= log2OfPowerOfTwo(blo)
993-
hiReturn= ahi>>> pow
994-
(alo>>> pow)| (ahi<<1<< (31-pow))
995-
}elseif (blo==0&& isPowerOfTwo_IKnowItsNot0(bhi)) {
996-
valpow= log2OfPowerOfTwo(bhi)
997-
hiReturn=0
998-
ahi>>> pow
999-
}else {
1000-
unsignedDivModHelper(alo, ahi, blo, bhi, askQuotient=true)
1001-
}
1002-
}
1003-
}
935+
@noinline
936+
privatedefunsigned_/(alo:Int,ahi:Int,blo:Int,bhi:Int):Int=
937+
unsignedDivModHelper(alo, ahi, blo, bhi, askQuotient=true)
1004938

1005939
@inline
1006940
defremainder(a:RuntimeLong,b:RuntimeLong):RuntimeLong= {
@@ -1009,38 +943,11 @@ object RuntimeLong {
1009943
}
1010944

1011945
defremainderImpl(alo:Int,ahi:Int,blo:Int,bhi:Int):Int= {
1012-
if (isZero(blo, bhi))
1013-
thrownewArithmeticException("/ by zero")
1014-
1015-
if (isInt32(alo, ahi)) {
1016-
if (isInt32(blo, bhi)) {
1017-
if (blo!=-1) {
1018-
vallo= 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-
valaAbs= inline_abs(alo, ahi)
1039-
valbAbs= inline_abs(blo, bhi)
1040-
valabsRLo= unsigned_%(aAbs.lo, aAbs.hi, bAbs.lo, bAbs.hi)
1041-
if (ahi<0) inline_negate_hiReturn(absRLo, hiReturn)
1042-
else absRLo
1043-
}
946+
valaAbs= inline_abs(alo, ahi)
947+
valbAbs= inline_abs(blo, bhi)
948+
valabsRLo= unsigned_%(aAbs.lo, aAbs.hi, bAbs.lo, bAbs.hi)
949+
if (ahi<0) inline_negate_hiReturn(absRLo, hiReturn)
950+
else absRLo
1044951
}
1045952

1046953
@inline
@@ -1049,123 +956,61 @@ object RuntimeLong {
1049956
newRuntimeLong(lo, hiReturn)
1050957
}
1051958

1052-
defremainderUnsignedImpl(alo:Int,ahi:Int,blo:Int,bhi:Int):Int= {
1053-
if (isZero(blo, bhi))
1054-
thrownewArithmeticException("/ 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-
}
959+
@inline
960+
privatedefremainderUnsignedImpl(alo:Int,ahi:Int,blo:Int,bhi:Int):Int=
961+
unsigned_%(alo, ahi, blo, bhi)
1069962

1070-
privatedefunsigned_%(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-
valaDouble= asUnsignedSafeDouble(alo, ahi)
1075-
valbDouble= asUnsignedSafeDouble(blo, bhi)
1076-
valrDouble= 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-
}elseif (blo==0&& isPowerOfTwo_IKnowItsNot0(bhi)) {
1089-
hiReturn= ahi& (bhi-1)
1090-
alo
1091-
}else {
1092-
unsignedDivModHelper(alo, ahi, blo, bhi, askQuotient=false)
1093-
}
1094-
}
1095-
}
963+
@noinline
964+
privatedefunsigned_%(alo:Int,ahi:Int,blo:Int,bhi:Int):Int=
965+
unsignedDivModHelper(alo, ahi, blo, bhi, askQuotient=false)
1096966

1097967
/** Helper for `unsigned_/` and `unsigned_%`.
1098968
*
1099969
* If `askQuotient` is true, computes the quotient, otherwise computes the
1100970
* remainder. Stores the hi word of the result in `hiReturn`, and returns
1101971
* the lo word.
1102972
*/
973+
@inline
1103974
privatedefunsignedDivModHelper(alo:Int,ahi:Int,blo:Int,bhi:Int,
1104975
askQuotient:Boolean):Int= {
1105976

1106-
varshift=
1107-
inlineNumberOfLeadingZeros(blo, bhi)- inlineNumberOfLeadingZeros(alo, ahi)
1108-
valinitialBShift=newRuntimeLong(blo, bhi)<< shift
1109-
varbShiftLo= initialBShift.lo
1110-
varbShiftHi= initialBShift.hi
1111-
varremLo= alo
1112-
varremHi= ahi
1113-
varquotLo=0
1114-
varquotHi=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-
valnewRem=
1132-
newRuntimeLong(remLo, remHi)-newRuntimeLong(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-
valnewBShift=newRuntimeLong(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-
valremDouble= asUnsignedSafeDouble(remLo, remHi)
1149-
valbDouble= asUnsignedSafeDouble(blo, bhi)
977+
if (bhi==0&& inlineUnsignedInt_<(blo,1<<21)) {
978+
// b < 2^21
1150979

980+
valquotHi=Integer.divideUnsigned(ahi, blo)// takes care of the division by zero check
981+
valk= ahi- quotHi* blo// remainder of the above division; k < blo
982+
// (alo, k) is exact because it uses at most 32 + 21 = 53 bits
983+
valremainingNum= asUnsignedSafeDouble(alo, k)
1151984
if (askQuotient) {
1152-
valrem_div_bDouble= fromUnsignedSafeDouble(remDouble/ bDouble)
1153-
valnewQuot=newRuntimeLong(quotLo, quotHi)+ rem_div_bDouble
1154-
hiReturn= newQuot.hi
1155-
newQuot.lo
985+
hiReturn= quotHi
986+
rawToInt(remainingNum/ blo.toDouble)
1156987
}else {
1157-
valrem_mod_bDouble= remDouble% bDouble
1158-
hiReturn= unsignedSafeDoubleHi(rem_mod_bDouble)
1159-
unsignedSafeDoubleLo(rem_mod_bDouble)
988+
hiReturn=0
989+
rawToInt(remainingNum% blo.toDouble)
1160990
}
1161991
}else {
1162-
if (askQuotient) {
1163-
hiReturn= quotHi
1164-
quotLo
992+
// b >= 2^21
993+
994+
vallongNum=newRuntimeLong(alo, ahi)
995+
vallongDivisor=newRuntimeLong(blo, bhi)
996+
valapproxDivisor= unsignedToDoubleApprox(blo, bhi)
997+
valapproxNum= unsignedToDoubleApprox(alo, ahi)
998+
valapproxQuot= fromUnsignedSafeDouble(approxNum/ approxDivisor)
999+
valapproxRem= longNum- longDivisor* approxQuot
1000+
1001+
valresult=if (approxRem.hi<0) {
1002+
if (askQuotient) approxQuot-newRuntimeLong(1,0)
1003+
else approxRem+ longDivisor
1004+
}elseif (geu(approxRem, longDivisor)) {
1005+
if (askQuotient) approxQuot+newRuntimeLong(1,0)
1006+
else approxRem- longDivisor
11651007
}else {
1166-
hiReturn= remHi
1167-
remLo
1008+
if (askQuotient) approxQuot
1009+
else approxRem
11681010
}
1011+
1012+
hiReturn= result.hi
1013+
result.lo
11691014
}
11701015
}
11711016

@@ -1175,18 +1020,10 @@ object RuntimeLong {
11751020
s.jsSubstring(start)
11761021
}
11771022

1178-
/** Tests whether the long (lo, hi) is 0.*/
1179-
@inlinedefisZero(lo:Int,hi:Int):Boolean=
1180-
(lo| hi)==0
1181-
11821023
/** Tests whether the long (lo, hi)'s mathematical value fits in a signed Int.*/
11831024
@inlinedefisInt32(lo:Int,hi:Int):Boolean=
11841025
hi== (lo>>31)
11851026

1186-
/** Tests whether the long (_, hi)'s mathematical value fits in an unsigned Int.*/
1187-
@inlinedefisUInt32(hi:Int):Boolean=
1188-
hi==0
1189-
11901027
/** Tests whether an unsigned long (lo, hi) is a safe Double.
11911028
* This test is in fact slightly stricter than necessary, as it tests
11921029
* whether `x < 2^53`, although x == 2^53 would be a perfectly safe
@@ -1215,6 +1052,10 @@ object RuntimeLong {
12151052
@inlinedefunsignedSafeDoubleHi(x:Double):Int=
12161053
rawToInt(x/TwoPow32)
12171054

1055+
/** Converts the unsigned long (lo, hi) to a Double, subject to rounding.*/
1056+
@inlinedefunsignedToDoubleApprox(lo:Int,hi:Int):Double=
1057+
asUint(hi)*TwoPow32+ asUint(lo)
1058+
12181059
/** Interprets an `Int` as an unsigned integer and returns its value as a
12191060
* `Double`.
12201061
*/
@@ -1229,25 +1070,6 @@ object RuntimeLong {
12291070
(x|0).asInstanceOf[Int]
12301071
}
12311072

1232-
/** Tests whether the given non-zero unsigned Int is an exact power of 2.*/
1233-
@inlinedefisPowerOfTwo_IKnowItsNot0(i:Int):Boolean=
1234-
(i& (i-1))==0
1235-
1236-
/** Returns the log2 of the given unsigned Int assuming it is an exact power of 2.*/
1237-
@inlinedeflog2OfPowerOfTwo(i:Int):Int=
1238-
31-Integer.numberOfLeadingZeros(i)
1239-
1240-
/** Returns the number of leading zeros in the given long (lo, hi).*/
1241-
@inlinedefinlineNumberOfLeadingZeros(lo:Int,hi:Int):Int=
1242-
if (hi!=0)Integer.numberOfLeadingZeros(hi)
1243-
elseInteger.numberOfLeadingZeros(lo)+32
1244-
1245-
/** Tests whether the unsigned long (alo, ahi) is >= (blo, bhi).*/
1246-
@inline
1247-
definlineUnsigned_>=(alo:Int,ahi:Int,blo:Int,bhi:Int):Boolean=
1248-
if (ahi== bhi) inlineUnsignedInt_>=(alo, blo)
1249-
else inlineUnsignedInt_>=(ahi, bhi)
1250-
12511073
@inline
12521074
definlineUnsignedInt_<(a:Int,b:Int):Boolean=
12531075
(a^0x80000000)< (b^0x80000000)

‎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

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp