The Trunk: Kernel-nice.306.mcz

Nicolas Cellier uploaded a new version of Kernel to project The Trunk:
http://source.squeak.org/trunk/Kernel-nice.306.mcz

==================== Summary ====================

Name: Kernel-nice.306
Author: nice
Time: 27 November 2009, 8:23:42 am
UUID: a1d781cc-fce8-6d4d-b7a5-149285a38851
Ancestors: Kernel-ul.305

Speed up highBit and lowBit according to http://bugs.squeak.org/view.php?id=7113
This is usefull for algorithms like DSA.
This version has a cache of known result for bytes.
Prerequisite: ByteArray literals #[]

{
[100000 timesRepeat: [123456798 highBit]] timeToRun.
[100000 timesRepeat: [122 highBit]] timeToRun.
[100000 timesRepeat: [12 highBit]] timeToRun.
[100000 timesRepeat: [3950591 lowBit]] timeToRun.
[100000 timesRepeat: [3950592 lowBit]] timeToRun.
[100000 timesRepeat: [8 lowBit]] timeToRun.
[100000 timesRepeat: [(-1073741824) lowBit]] timeToRun.
}
"OLD" #(186 139 138 92 165 134 1965) /
"NEW" #(115 96 96 83 97 79 743)
"SPEED UP FACTOR" collect: [:e | e roundTo: 0.1]
-> #(1.6 1.4 1.4 1.1 1.7 1.7 2.6)

=============== Diff against Kernel-ul.305 ===============

Item was changed:
  ----- Method: SmallInteger>>highBitOfPositiveReceiver (in category 'private') -----
  highBitOfPositiveReceiver
  | shifted bitNo |
  "Answer the index of the high order bit of the receiver, or zero if the
  receiver is zero. Receiver has to be positive!!"
  shifted := self.
  bitNo := 0.
+ [shifted < 65536]
- [shifted < 16]
- whileFalse:
- [shifted := shifted bitShift: -4.
- bitNo := bitNo + 4].
- [shifted = 0]
  whileFalse:
+ [shifted := shifted bitShift: -16.
+ bitNo := bitNo + 16].
+ shifted < 256
+ ifFalse:
+ [shifted := shifted bitShift: -8.
+ bitNo := bitNo + 8].
+
+ "The high bits table can be obtained with:
+ (1 to: 8) inject: #[0] into: [:highBits :rank | highBits , (highBits collect: [:e | rank])]."
+ ^bitNo + ( #[0 1 2 2 3 3 3 3 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8] at: shifted + 1)!
- [shifted := shifted bitShift: -1.
- bitNo := bitNo + 1].
- ^ bitNo!

Item was changed:
  ----- Method: SmallInteger>>lowBit (in category 'bit manipulation') -----
  lowBit
  " Answer the index of the low order one bit.
  2r00101000 lowBit       (Answers: 4)
  2r-00101000 lowBit      (Answers: 4)
+  First we skip bits in groups of 8, then do a lookup in a table.
-  First we skip bits in groups of 4, then single bits.
   While not optimal, this is a good tradeoff; long
   integer #lowBit always invokes us with bytes."
+ | n result lastByte |
- | n result |
  n := self.
  n = 0 ifTrue: [ ^ 0 ].
+ result := 0.
+ [(lastByte := n bitAnd: 16rFF) = 0]
- result := 1.
- [ (n bitAnd: 16rF) = 0 ]
- whileTrue: [
- result := result + 4.
- n := n bitShift: -4 ].
- [ (n bitAnd: 1) = 0 ]
  whileTrue: [
+ result := result + 8.
+ n := n bitShift: -8 ].
+
+ "The low bits table can be obtained with:
+ ((1 to: 8) inject: #[1] into: [:lowBits :rank | (lowBits copy at: 1 put: lowBits first + 1; yourself) , lowBits]) allButFirst."
+ ^result + ( #[1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 7 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 8 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 7 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1] at: lastByte)!
- result := result + 1.
- n := n bitShift: -1 ].
- ^ result!