The Trunk: Collections-ul.341.mcz

Levente Uzonyi uploaded a new version of Collections to project The Trunk:
http://source.squeak.org/trunk/Collections-ul.341.mcz

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

Name: Collections-ul.341
Author: ul
Time: 19 March 2010, 2:24:31.907 pm
UUID: 9fbc9e35-4ba0-814c-8c2f-7d8923f4d20a
Ancestors: Collections-nice.340

- speed up identity-based hashed collections for heavy users by using different primes for capacity.

=============== Diff against Collections-nice.340 ===============

Item was added:
+ ----- Method: WeakIdentityKeyDictionary class>>goodPrimes (in category 'sizing') -----
+ goodPrimes
+
+ ^self goodPrimesForIdentityBasedHashedCollections!

Item was added:
+ ----- Method: IdentitySet class>>goodPrimes (in category 'sizing') -----
+ goodPrimes
+
+ ^self goodPrimesForIdentityBasedHashedCollections!

Item was added:
+ ----- Method: IdentityDictionary class>>goodPrimes (in category 'sizing') -----
+ goodPrimes
+
+ ^self goodPrimesForIdentityBasedHashedCollections!

Item was added:
+ ----- Method: KeyedIdentitySet class>>goodPrimes (in category 'sizing') -----
+ goodPrimes
+
+ ^self goodPrimesForIdentityBasedHashedCollections!

Item was added:
+ ----- Method: HashedCollection class>>goodPrimesForIdentityBasedHashedCollections (in category 'sizing') -----
+ goodPrimesForIdentityBasedHashedCollections
+ "These primes were chosen carefully so that the values produced by ((0 to: 4095) collect: [ :e | e << 18 \\ p ]) are distributed uniformly between 0 and p - 1, and so that gcd(p, (256^k) +/- a) = 1, for 0<a<=32 and 0<k<=8.  See Knuth's TAOCP for details."
+
+ ^#(5 11 17 23 31 41 59 79 107 149 197 263 353 467 631 839 1123 1511 2017
+ 2221 2411 2617 2789 2999 3163 3343 3527 3709 3907
+ 4391 4759 5087 5471 5791 6133 6547 6841 7151 7529 7927
+ 8807 9643 10211 10867 11677 12343 12919 13619 14347 14969 15733
+ 17827 19037 20483 21937 23297 24677 25939 27299 28753 29947 31489
+ 35311 38201 40771 43669 46187 49003 52051 54371 57301 60217 63331
+ 69859 76001 80347 85847 91199 95429 101051 105449 111187 115523 121229 126989
+ 139747 151967 161201 170557 181283 192323 201979 212029 221069 231877 241679 251443
+ 282089 303337 324427 342469 363037 381853 404009 424829 444113 464479 483317 505537
+ 563119 603623 645727 685427 723623 768191 808261 846721 883979 929399 964021 1016891
+ 1128371 1201469 1270319 1351711 1415647 1495097 1570193 1645927 1727941 1799381 1868231 1942141 2028401
+ 2251031 2399671 2560127 2703979 2846731 2999603 3146497 3281209 3450017 3582343 3744001 3902609 4037609
+ 4455361 4775681 5087581 5393053 5677013 6002951 6262499 6574507 6884641 7209841 7499519 7775039 8077189
+ 9031853 9532297 10226113 10750529 11414419 11939203 12623003 13230179 13749119 14337529 14945851 15561479 16201303
+ 17900063 19047559 20180161 21238843 22375079 23439089 24635519 25683829 26850101 27987329 29041303 30153919 31357063 32474083
+ 35800129 38020163 40234211 42477691 44750177 46935211 49175813 51405187 53700181 55960907 58210169 60365923 62667707 64872733
+ 71582779 76040311 80497843 84955361 89500331 93990023 98399369 102943471 107400401 111857071 116363579 120818933 125274367 129792889
+ 143165401 152156077 161068169 169980277 179000659 187911701 196822559 205832897 214748357 223662961 232625779 241638679 250549367 259459789
+ 285162679 301939921 318717121 335494331 352371517 369148753 385926017 402603193 419480419 436157621 453034849 469712051 486589307 503366497 520043707
+ 570475349 603929813 637584271 671138659 704693081 738247541 771701969 805356457 838910803 872365267 905919671 939574117 973128521 1006682977 1040237389 1073741833)!