The Inbox: Collections-ul.867.mcz

Levente Uzonyi uploaded a new version of Collections to project The Inbox:
http://source.squeak.org/inbox/Collections-ul.867.mcz

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

Name: Collections-ul.867
Author: ul
Time: 18 December 2019, 2:16:21.631833 am
UUID: febcf591-b053-4c58-9d3b-a29b0634ff84
Ancestors: Collections-mt.866

HashedCollection changes:
- speed up #goodPrimeAtLeast: when its argument is small
- let #sizeFor: return the smallest possible capacity (3)
- use #sizeFor: instead of #goodPrimeAtLeast: in #compact. This fixes the case when a 4 element dictionary is compacted to 80% capacity (array size = 5), which is higher than the advertised maximum: 75%.

=============== Diff against Collections-mt.866 ===============

Item was changed:
  ----- Method: HashedCollection class>>goodPrimeAtLeast: (in category 'sizing') -----
  goodPrimeAtLeast: lowerLimit
+ "Answer the smallest good prime >= lowerlimit.
+ If lowerLimit is larger than the largest known good prime, just make it odd.
+ Use linear search, and exponential search to speed up cases when lowerLimit is small (<2500 and <100000, respectively)."
- "Answer the next good prime >= lowerlimit.
- If lowerLimit is larger than the largest known good prime,
- just make it odd."
 
+ | high mid low prime primes |
- | low mid high prime primes |
  primes := self goodPrimes.
+ (primes at: primes size) < lowerLimit ifTrue: [
- high := primes size.
- lowerLimit > (primes at: high) ifTrue: [
  ^lowerLimit bitOr: 1 ].
+ lowerLimit < 2500 ifTrue: [
+ "Use linear search when the limit is small. The boundary is based on measurements."
+ high := 1.
+ [
+ (prime := primes at: high) >= lowerLimit ifTrue: [ ^prime ].
+ high := high + 1 ] repeat ].
+ lowerLimit < 100000
+ ifTrue: [
+ "Use exponential search when the limit is not too large. The boundary is based on measurements."
+ high := 1.
+ [ (primes at: high) < lowerLimit ] whileTrue: [
+ high := high * 2 ].
+ low := high // 2 + 1. "high // 2 was smaller than lowerLimit" ]
+ ifFalse: [
+ "Regular binary search."
+ low := 1.
+ high := primes size ].
- low := 1.
  [ high - low <= 1 ] whileFalse: [
  mid := high + low // 2.
  prime := primes at: mid.
  lowerLimit < prime
  ifTrue: [ high := mid ]
  ifFalse: [
  lowerLimit > prime
  ifTrue: [ low := mid ]
  ifFalse: [ ^prime ] ] ].
  (primes at: low) >= lowerLimit ifTrue: [ ^primes at: low ].
  ^primes at: high!

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

Item was changed:
  ----- Method: HashedCollection>>compact (in category 'private') -----
  compact
  "Reduce the size of array so that the load factor will be ~75%."
 
  | newCapacity |
+ newCapacity := self class sizeFor: tally.
- newCapacity := self class goodPrimeAtLeast: tally * 4 // 3.
  self growTo: newCapacity!