Hi Levente,
Due to ancestry, the diff of this over Collections-ul.867 is only this:
+ nElements < 6 ifTrue: [ ^5 ].
The issue I'm facing is, I don't know the size of the Dictionary at compile time, but I do at runtime.
Dictionary new: runtimeVar
However, I don't know what the runtimeVar values will be. It could be run millions of times with a value less than the default size given by "Dictionary new", or greater. The implementation is forcing me to optimize for one or the other at compile time, but I can't. As developer, I'm "torn" whether to write:
Dictionary new Dictionary new: runtimeVar (44% speed of Dictionary new when runtimeVar < 6) or (runtimeVar < 6) ifTrue: [ Dictionary new ] ifFalse: [ Dictionary new: runtimeVar ]
That conflict is what this last tweak tries to solve. It improves the second case, above, to 89% of "Dictionary new".
Everything about this looks good and would like to include it in 5.3.
- Chris
On Fri, Jan 3, 2020 at 7:59 PM commits@source.squeak.org wrote:
Chris Muller uploaded a new version of Collections to project The Inbox: http://source.squeak.org/inbox/Collections-cmm.870.mcz
==================== Summary ====================
Name: Collections-cmm.870 Author: cmm Time: 3 January 2020, 7:59:19.257837 pm UUID: b3e2efab-cf35-426d-9910-adab44aa4ed4 Ancestors: Collections-fn.869, Collections-ul.867
Building on Collections-ul.867, let "Dictionary new: anySize" _never_ be significantly slower than "Dictionary new".
=============== Diff against Collections-fn.869 ===============
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, justmake it odd.
Use linear search, and exponential search to speed up cases whenlowerLimit 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 boundaryis based on measurements."
high := 1.[(prime := primes at: high) >= lowerLimit ifTrue: [^prime ].
high := high + 1 ] repeat ].lowerLimit < 100000ifTrue: ["Use exponential search when the limit is not toolarge. The boundary is based on measurements."
high := 1.[ (primes at: high) < lowerLimit ] whileTrue: [high := high * 2 ].low := high // 2 + 1. "high // 2 was smaller thanlowerLimit" ]
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: nElements "Large enough prime (or odd if too large) size to hold nElements with some slop (see fullCheck)"
nElements < 6 ifTrue: [ ^5 ].
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!