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

Commit3883616

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 commit3883616

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
@inlineprivatedef>>>(b:Int):RuntimeLong=RuntimeLong.shr(this, b)
8181
@inlineprivatedef+(b:RuntimeLong):RuntimeLong=RuntimeLong.add(this, b)
8282
@inlineprivatedef-(b:RuntimeLong):RuntimeLong=RuntimeLong.sub(this, b)
83+
@inlineprivatedef*(b:RuntimeLong):RuntimeLong=RuntimeLong.mul(this, b)
8384
}
8485

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

918919
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-
}
920+
valaAbs= inline_abs(alo, ahi)
921+
valbAbs= inline_abs(blo, bhi)
922+
valabsRLo= 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
newRuntimeLong(lo, hiReturn)
956931
}
957932

958-
defdivideUnsignedImpl(alo:Int,ahi:Int,blo:Int,bhi:Int):Int= {
959-
if (isZero(blo, bhi))
960-
thrownewArithmeticException("/ by zero")
933+
@inline
934+
defdivideUnsignedImpl(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-
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-
}
937+
@noinline
938+
privatedefunsigned_/(alo:Int,ahi:Int,blo:Int,bhi:Int):Int=
939+
unsignedDivModHelper(alo, ahi, blo, bhi, askQuotient=true)
1004940

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

1011947
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-
}
948+
valaAbs= inline_abs(alo, ahi)
949+
valbAbs= inline_abs(blo, bhi)
950+
valabsRLo= 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
newRuntimeLong(lo, hiReturn)
1050959
}
1051960

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-
}
961+
@inline
962+
privatedefremainderUnsignedImpl(alo:Int,ahi:Int,blo:Int,bhi:Int):Int=
963+
unsigned_%(alo, ahi, blo, bhi)
1069964

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-
}
965+
@noinline
966+
privatedefunsigned_%(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
privatedefunsignedDivModHelper(alo:Int,ahi:Int,blo:Int,bhi:Int,
1104977
askQuotient:Boolean):Int= {
1105978

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)
979+
if (bhi==0&& inlineUnsignedInt_<(blo,1<<21)) {
980+
// b < 2^21
1150981

982+
valquotHi=Integer.divideUnsigned(ahi, blo)// takes care of the division by zero check
983+
valk= 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+
valremainingNum= asUnsignedSafeDouble(alo, k)
1151986
if (askQuotient) {
1152-
valrem_div_bDouble= fromUnsignedSafeDouble(remDouble/ bDouble)
1153-
valnewQuot=newRuntimeLong(quotLo, quotHi)+ rem_div_bDouble
1154-
hiReturn= newQuot.hi
1155-
newQuot.lo
987+
hiReturn= quotHi
988+
rawToInt(remainingNum/ blo.toDouble)
1156989
}else {
1157-
valrem_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+
vallongNum=newRuntimeLong(alo, ahi)
997+
vallongDivisor=newRuntimeLong(blo, bhi)
998+
valapproxDivisor= unsignedToDoubleApprox(blo, bhi)
999+
valapproxNum= unsignedToDoubleApprox(alo, ahi)
1000+
valapproxQuot= fromUnsignedSafeDouble(approxNum/ approxDivisor)
1001+
valapproxRem= longNum- longDivisor* approxQuot
1002+
11621003
if (askQuotient) {
1163-
hiReturn= quotHi
1164-
quotLo
1004+
if (approxRem.hi<0) {
1005+
valresult= approxQuot-newRuntimeLong(1,0)
1006+
hiReturn= result.hi
1007+
result.lo
1008+
}elseif (geu(approxRem, longDivisor)) {
1009+
valresult= approxQuot+newRuntimeLong(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+
valresult= approxRem+ longDivisor
1019+
hiReturn= result.hi
1020+
result.lo
1021+
}elseif (geu(approxRem, longDivisor)) {
1022+
valresult= 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
@inlinedefunsignedSafeDoubleHi(x:Double):Int=
12161077
rawToInt(x/TwoPow32)
12171078

1079+
/** Converts the unsigned long (lo, hi) to a Double, subject to rounding.*/
1080+
@inlinedefunsignedToDoubleApprox(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 to626000,
2056+
fastLink=622000 to623000,
20572057
fullLink=94000 to95000,
2058-
fastLinkGz=75000 to79000,
2058+
fastLinkGz=75000 to76000,
20592059
fullLinkGz=24000 to25000,
20602060
))
20612061
}else {
20622062
Some(ExpectedSizes(
2063-
fastLink=425000 to426000,
2064-
fullLink=283000 to284000,
2065-
fastLinkGz=61000 to62000,
2063+
fastLink=423000 to424000,
2064+
fullLink=280000 to281000,
2065+
fastLinkGz=60000 to61000,
20662066
fullLinkGz=43000 to44000,
20672067
))
20682068
}
20692069

20702070
case `default213Version`=>
20712071
if (!useMinifySizes) {
20722072
Some(ExpectedSizes(
2073-
fastLink=443000 to444000,
2073+
fastLink=440000 to441000,
20742074
fullLink=90000 to91000,
2075-
fastLinkGz=57000 to58000,
2075+
fastLinkGz=56000 to57000,
20762076
fullLinkGz=24000 to25000,
20772077
))
20782078
}else {
20792079
Some(ExpectedSizes(
2080-
fastLink=301000 to302000,
2081-
fullLink=259000 to260000,
2080+
fastLink=299000 to300000,
2081+
fullLink=256000 to257000,
20822082
fastLinkGz=47000 to48000,
20832083
fullLinkGz=42000 to43000,
20842084
))

0 commit comments

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