[squeak-dev] The Trunk: Kernel-tfel.1046.mcz
commits at source.squeak.org
commits at source.squeak.org
Wed Oct 19 15:35:07 UTC 2016
Tim Felgentreff uploaded a new version of Kernel to project The Trunk:
http://source.squeak.org/trunk/Kernel-tfel.1046.mcz
==================== Summary ====================
Name: Kernel-tfel.1046
Author: tfel
Time: 19 October 2016, 5:34:18.991659 pm
UUID: 12ebf345-b919-2845-8147-56a8b2f4cae4
Ancestors: Kernel-eem.1045
Improve performance of large integer fallback code for multiplication and division with small integers, by avoiding recalculating SmallInteger>>digitLength a lot of times. (This yields a 3x speedup in some integer heavy shootout benchmarks like pidigits for RSqueak, where we don't have a LargeIntegers plugin)
=============== Diff against Kernel-eem.1045 ===============
Item was changed:
----- Method: Integer>>digitDiv:neg: (in category 'private') -----
digitDiv: arg neg: ng
"Answer with an array of (quotient, remainder)."
+ | quo rem ql d div dh dnh dl qhi qlo j l hi lo r3 a t divDigitLength remDigitLength |
- | quo rem ql d div dh dnh dl qhi qlo j l hi lo r3 a t |
<primitive: 'primDigitDivNegative' module:'LargeIntegers'>
arg = 0 ifTrue: [^ (ZeroDivide dividend: self) signal].
"TFEI added this line"
l := self digitLength - arg digitLength + 1.
l <= 0 ifTrue: [^ Array with: 0 with: self].
"shortcut against #highBit"
d := 8 - arg lastDigit highBitOfByte.
div := arg digitLshift: d.
+ divDigitLength := div digitLength + 1.
+ div := div growto: divDigitLength.
- div := div growto: div digitLength + 1.
"shifts so high order word is >=128"
rem := self digitLshift: d.
rem digitLength = self digitLength ifTrue: [rem := rem growto: self digitLength + 1].
+ remDigitLength := rem digitLength.
"makes a copy and shifts"
quo := Integer new: l neg: ng.
+ dl := divDigitLength - 1.
- dl := div digitLength - 1.
"Last actual byte of data"
ql := l.
dh := div digitAt: dl.
dnh := dl = 1
ifTrue: [0]
ifFalse: [div digitAt: dl - 1].
1 to: ql do:
[:k |
"maintain quo*arg+rem=self"
"Estimate rem/div by dividing the leading to bytes of rem by dh."
"The estimate is q = qhi*16+qlo, where qhi and qlo are nibbles."
+ j := remDigitLength + 1 - k.
- j := rem digitLength + 1 - k.
"r1 := rem digitAt: j."
(rem digitAt: j)
= dh
ifTrue: [qhi := qlo := 15
"i.e. q=255"]
ifFalse:
["Compute q = (r1,r2)//dh, t = (r1,r2)\\dh.
Note that r1,r2 are bytes, not nibbles.
Be careful not to generate intermediate results exceeding 13
bits."
"r2 := (rem digitAt: j - 1)."
t := ((rem digitAt: j)
bitShift: 4)
+ ((rem digitAt: j - 1)
bitShift: -4).
qhi := t // dh.
t := (t \\ dh bitShift: 4)
+ ((rem digitAt: j - 1)
bitAnd: 15).
qlo := t // dh.
t := t \\ dh.
"Next compute (hi,lo) := q*dnh"
hi := qhi * dnh.
lo := qlo * dnh + ((hi bitAnd: 15)
bitShift: 4).
hi := (hi bitShift: -4)
+ (lo bitShift: -8).
lo := lo bitAnd: 255.
"Correct overestimate of q.
Max of 2 iterations through loop -- see Knuth vol. 2"
r3 := j < 3
ifTrue: [0]
ifFalse: [rem digitAt: j - 2].
[(t < hi
or: [t = hi and: [r3 < lo]])
and:
["i.e. (t,r3) < (hi,lo)"
qlo := qlo - 1.
lo := lo - dnh.
lo < 0
ifTrue:
[hi := hi - 1.
lo := lo + 256].
hi >= dh]]
whileTrue: [hi := hi - dh].
qlo < 0
ifTrue:
[qhi := qhi - 1.
qlo := qlo + 16]].
"Subtract q*div from rem"
l := j - dl.
a := 0.
+ 1 to: divDigitLength do:
- 1 to: div digitLength do:
[:i |
hi := (div digitAt: i)
* qhi.
lo := a + (rem digitAt: l) - ((hi bitAnd: 15)
bitShift: 4) - ((div digitAt: i)
* qlo).
rem digitAt: l put: lo - (lo // 256 * 256).
"sign-tolerant form of (lo bitAnd: 255)"
a := lo // 256 - (hi bitShift: -4).
l := l + 1].
a < 0
ifTrue:
["Add div back into rem, decrease q by 1"
qlo := qlo - 1.
l := j - dl.
a := 0.
+ 1 to: divDigitLength do:
- 1 to: div digitLength do:
[:i |
a := (a bitShift: -8)
+ (rem digitAt: l) + (div digitAt: i).
rem digitAt: l put: (a bitAnd: 255).
l := l + 1]].
+ quo digitAt: ql + 1 - k put: (qhi bitShift: 4)
- quo digitAt: quo digitLength + 1 - k put: (qhi bitShift: 4)
+ qlo].
rem := rem
digitRshift: d
bytes: 0
lookfirst: dl.
^ Array with: quo with: rem!
Item was changed:
----- Method: Integer>>digitMultiply:neg: (in category 'private') -----
digitMultiply: arg neg: ng
+ | selfLen argLen prod prodLen carry digit k ab |
- | prod prodLen carry digit k ab |
<primitive: 'primDigitMultiplyNegative' module:'LargeIntegers'>
+ argLen := arg digitLength.
+ (argLen = 1 and: [(arg digitAt: 1)
- (arg digitLength = 1 and: [(arg digitAt: 1)
= 0])
ifTrue: [^ 0].
+ selfLen := self digitLength.
+ (selfLen = 1 and: [(self digitAt: 1)
- (self digitLength = 1 and: [(self digitAt: 1)
= 0])
ifTrue: [^ 0].
+ prodLen := selfLen + argLen.
- prodLen := self digitLength + arg digitLength.
prod := Integer new: prodLen neg: ng.
"prod starts out all zero"
+ 1 to: selfLen do: [:i | (digit := self digitAt: i) ~= 0
- 1 to: self digitLength do: [:i | (digit := self digitAt: i) ~= 0
ifTrue:
[k := i.
carry := 0.
"Loop invariant: 0<=carry<=0377, k=i+j-1"
+ 1 to: argLen do:
- 1 to: arg digitLength do:
[:j |
ab := (arg digitAt: j)
* digit + carry + (prod digitAt: k).
carry := ab bitShift: -8.
prod digitAt: k put: (ab bitAnd: 255).
k := k + 1].
prod digitAt: k put: carry]].
^ prod normalize!
More information about the Squeak-dev
mailing list
|