The Trunk: Kernel-tfel.1046.mcz

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!