<div dir="ltr">Hi Levente,<div><br></div><div>Due to ancestry, the diff of this over Collections-ul.867 is only this:</div><div><br></div><div> + nElements < 6 ifTrue: [ ^5 ].<br><div><br></div><div>The issue I'm facing is, I don't know the size of the Dictionary at compile time, but I do at runtime.</div><div><br></div><div> Dictionary new: runtimeVar</div><div><br></div><div>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:</div><div><br></div><div> Dictionary new</div><div> Dictionary new: runtimeVar (44% speed of Dictionary new when runtimeVar < 6)</div><div>or (runtimeVar < 6) ifTrue: [ Dictionary new ] ifFalse: [ Dictionary new: runtimeVar ]</div><div><br></div><div>That conflict is what this last tweak tries to solve. It improves the second case, above, to 89% of "Dictionary new".</div><div><br></div><div>Everything about this looks good and would like to include it in 5.3.</div><div><br></div><div> - Chris</div></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Fri, Jan 3, 2020 at 7:59 PM <<a href="mailto:commits@source.squeak.org" target="_blank">commits@source.squeak.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Chris Muller uploaded a new version of Collections to project The Inbox:<br>
<a href="http://source.squeak.org/inbox/Collections-cmm.870.mcz" rel="noreferrer" target="_blank">http://source.squeak.org/inbox/Collections-cmm.870.mcz</a><br>
<br>
==================== Summary ====================<br>
<br>
Name: Collections-cmm.870<br>
Author: cmm<br>
Time: 3 January 2020, 7:59:19.257837 pm<br>
UUID: b3e2efab-cf35-426d-9910-adab44aa4ed4<br>
Ancestors: Collections-fn.869, Collections-ul.867<br>
<br>
Building on Collections-ul.867, let "Dictionary new: anySize" _never_ be significantly slower than "Dictionary new".<br>
<br>
=============== Diff against Collections-fn.869 ===============<br>
<br>
Item was changed:<br>
----- Method: HashedCollection class>>goodPrimeAtLeast: (in category 'sizing') -----<br>
goodPrimeAtLeast: lowerLimit<br>
+ "Answer the smallest good prime >= lowerlimit.<br>
+ If lowerLimit is larger than the largest known good prime, just make it odd.<br>
+ Use linear search, and exponential search to speed up cases when lowerLimit is small (<2500 and <100000, respectively)."<br>
- "Answer the next good prime >= lowerlimit.<br>
- If lowerLimit is larger than the largest known good prime,<br>
- just make it odd."<br>
<br>
+ | high mid low prime primes |<br>
- | low mid high prime primes |<br>
primes := self goodPrimes.<br>
+ (primes at: primes size) < lowerLimit ifTrue: [<br>
- high := primes size.<br>
- lowerLimit > (primes at: high) ifTrue: [<br>
^lowerLimit bitOr: 1 ].<br>
+ lowerLimit < 2500 ifTrue: [<br>
+ "Use linear search when the limit is small. The boundary is based on measurements."<br>
+ high := 1.<br>
+ [ <br>
+ (prime := primes at: high) >= lowerLimit ifTrue: [ ^prime ].<br>
+ high := high + 1 ] repeat ].<br>
+ lowerLimit < 100000 <br>
+ ifTrue: [<br>
+ "Use exponential search when the limit is not too large. The boundary is based on measurements."<br>
+ high := 1.<br>
+ [ (primes at: high) < lowerLimit ] whileTrue: [<br>
+ high := high * 2 ].<br>
+ low := high // 2 + 1. "high // 2 was smaller than lowerLimit" ]<br>
+ ifFalse: [<br>
+ "Regular binary search."<br>
+ low := 1.<br>
+ high := primes size ].<br>
- low := 1.<br>
[ high - low <= 1 ] whileFalse: [<br>
mid := high + low // 2.<br>
prime := primes at: mid.<br>
lowerLimit < prime<br>
ifTrue: [ high := mid ]<br>
ifFalse: [<br>
lowerLimit > prime<br>
ifTrue: [ low := mid ]<br>
ifFalse: [ ^prime ] ] ].<br>
(primes at: low) >= lowerLimit ifTrue: [ ^primes at: low ].<br>
^primes at: high!<br>
<br>
Item was changed:<br>
----- Method: HashedCollection class>>sizeFor: (in category 'sizing') -----<br>
sizeFor: nElements<br>
"Large enough prime (or odd if too large) size to hold nElements with some slop (see fullCheck)"<br>
<br>
+ nElements < 6 ifTrue: [ ^5 ].<br>
- nElements < 4 ifTrue: [ ^5 ].<br>
^self goodPrimeAtLeast: nElements + 1 * 4 // 3!<br>
<br>
Item was changed:<br>
----- Method: HashedCollection>>compact (in category 'private') -----<br>
compact<br>
"Reduce the size of array so that the load factor will be ~75%."<br>
<br>
| newCapacity |<br>
+ newCapacity := self class sizeFor: tally.<br>
- newCapacity := self class goodPrimeAtLeast: tally * 4 // 3.<br>
self growTo: newCapacity!<br>
<br>
<br>
</blockquote></div>