The Trunk: Collections-ar.212.mcz

Andreas Raab uploaded a new version of Collections to project The Trunk:
http://source.squeak.org/trunk/Collections-ar.212.mcz

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

Name: Collections-ar.212
Author: ar
Time: 24 November 2009, 9:48:13 am
UUID: fdceaa93-63c2-fe47-bf3e-0c2ba9e1a0f8
Ancestors: Collections-ul.209, Collections-ul.211

Merging Collections-ul.210, Collections-ul.211:

- HashedCollections have prime capacity (if they are not oversized)
- HashedCollections' growth rate is not 2, but 1.5 (2 for small sizes which decreases to 1.5 as the size increases)

(based on Andrés Valloud's changes made for pharo)
Load Kernel-ul.305 before this.

- replaced 32359813 with 32435981 in HashedCollection >> #goodPrimes.

=============== Diff against Collections-ul.209 ===============

Item was changed:
  ----- Method: HashedCollection>>growSize (in category 'private') -----
  growSize
+ "Answer what my next higher table size should be"
+
+ ^self class goodPrimeAtLeast: array size * 3 // 2 + 2!
- ^ array size max: 2!

Item was changed:
+ ----- Method: HashedCollection class>>sizeFor: (in category 'sizing') -----
- ----- Method: HashedCollection class>>sizeFor: (in category 'instance creation') -----
  sizeFor: nElements
+ "Large enough prime (or odd if too large) size to hold nElements with some slop (see fullCheck)"
+
+ nElements < 4 ifTrue: [ ^5 ].
+ ^self goodPrimeAtLeast: nElements + 1 * 4 // 3!
- "Large enough size to hold nElements with some slop (see fullCheck)"
- nElements <= 0 ifTrue: [^ 1].
- ^ nElements+1*4//3!

Item was added:
+ ----- Method: HashedCollection class>>goodPrimes (in category 'sizing') -----
+ goodPrimes
+ "Answer a sorted array of prime numbers less than one billion that make good
+ hash table sizes. Should be expanded as needed.  See comments below code"
+
+ ^#(5 11 17 23 31 43 59 79 107 149 199 269 359 479 641 857 1151 1549 2069
+ 2237 2423 2617 2797 2999 3167 3359 3539 3727 3911
+ 4441 4787 5119 5471 5801 6143 6521 6827 7177 7517 7853
+ 8887 9587 10243 10937 11617 12289 12967 13649 14341 15013 15727
+ 17749 19121 20479 21859 23209 24593 25939 27329 28669 30047 31469
+ 35507 38231 40961 43711 46439 49157 51893 54617 57347 60077 62801
+ 70583 75619 80669 85703 90749 95783 100823 105871 110909 115963 120997 126031
+ 141157 151237 161323 171401 181499 191579 201653 211741 221813 231893 241979 252079
+ 282311 302483 322649 342803 362969 383143 403301 423457 443629 463787 483953 504121
+ 564617 604949 645313 685609 725939 766273 806609 846931 887261 927587 967919 1008239
+ 1123477 1198397 1273289 1348177 1423067 1497983 1572869 1647761 1722667 1797581 1872461 1947359 2022253
+ 2246953 2396759 2546543 2696363 2846161 2995973 3145739 3295541 3445357 3595117 3744941 3894707 4044503
+ 4493921 4793501 5093089 5392679 5692279 5991883 6291469 6591059 6890641 7190243 7489829 7789447 8089033
+ 8987807 9586981 10186177 10785371 11384539 11983729 12582917 13182109 13781291 14380469 14979667 15578861 16178053
+ 17895707 19014187 20132683 21251141 22369661 23488103 24606583 25725083 26843549 27962027 29080529 30198989 31317469 32435981
+ 35791397 38028379 40265327 42502283 44739259 46976221 49213237 51450131 53687099 55924061 58161041 60397993 62634959 64871921
+ 71582857 76056727 80530643 85004567 89478503 93952427 98426347 102900263 107374217 111848111 116322053 120795971 125269877 129743807
+ 143165587 152113427 161061283 170009141 178956983 187904819 196852693 205800547 214748383 223696237 232644089 241591943 250539763 259487603
+ 285212677 301989917 318767107 335544323 352321547 369098771 385876021 402653189 419430419 436207619 452984849 469762049 486539323 503316511 520093703
+ 570425377 603979799 637534277 671088667 704643083 738197549 771751961 805306457 838860817 872415239 905969671 939524129 973078537 1006632983 1040187403
+ 1073741789)
+
+ "The above primes past 2069 were chosen carefully so that they do not interact badly with 1664525 (used by hashMultiply), and so that gcd(p, (256^k) +/- a) = 1, for 0<a<=32 and 0<k<=8.  See Knuth's TAOCP for details."!

Item was changed:
  ----- Method: HashedCollection>>grow (in category 'private') -----
  grow
  "Grow the elements array and reinsert the old elements"
 
+ self growTo: self growSize!
- self growTo: array size + self growSize!

Item was added:
+ ----- Method: HashedCollection class>>goodPrimeAtLeast: (in category 'sizing') -----
+ goodPrimeAtLeast: lowerLimit
+ "Answer the next good prime >= lowerlimit.
+ If lowerLimit is larger than the largest known good prime,
+ just make it odd."
+
+ | primes low mid high prime |
+ primes := self goodPrimes.
+ low := 1.
+ high := primes size.
+ lowerLimit > (primes at: high) ifTrue: [
+ ^lowerLimit even
+ ifTrue: [ lowerLimit + 1 ]
+ ifFalse: [ lowerLimit ] ].
+ [ high - low <= 1 ] whileFalse: [
+ mid := high + low // 2.
+ prime := primes at: mid.
+ prime = lowerLimit ifTrue: [ ^prime ].
+ prime < lowerLimit
+ ifTrue: [ low := mid ]
+ ifFalse: [ high := mid ] ].
+ (primes at: low) >= lowerLimit ifTrue: [ ^primes at: low ].
+ ^primes at: high!