<div dir="ltr">Thanks again Levente, once again, I somehow got my brain stuck :) and thought "Dictionary new" was the same as "Dictionary new: 7", but, in fact, it's the same as "Dictionary new: 3". Again, I conflated the desired size with the internal array's size needing extra space, sigh... It was this finally cleared it up for me:<div><div><br></div><div> (1 to: 10) collect: [ : n | Dictionary sizeFor: n ]. " #(5 5 5 7 11 11 11 13 13 17)"</div><div><br></div><div>So, back to my "problem", it looks like I'm safe to write:</div><div><br></div><div> Dictionary new: runtimeVar</div><div><br></div><div>and, no matter what size, there will never be a performance hit over Dictionary new. Whew!</div></div><div><br></div><div>Thanks,</div><div> Chris</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Fri, Jan 3, 2020 at 9:25 PM Levente Uzonyi <<a href="mailto:leves@caesar.elte.hu">leves@caesar.elte.hu</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">Hi Chris,<br>
<br>
The problem with that change is that #sizeFor: returns incorrect values <br>
when its argument is 4 or 5. The change breaks #compact, and the contract <br>
of #new: and #sizeFor:, because when you want to store 4 or 5 elements, <br>
you'll get a HashedCollection which can only store 3 elements, so there'll <br>
either be an extra grow involved or the collection will be overfilled.<br>
<br>
Here's an example where the change makes #compact break the contract of <br>
HashedCollecions:<br>
<br>
(1 to: 5) asSet compact; includes: 6 "#includes: will raise an error"<br>
<br>
The default HashedCollection instances created with #new can hold 3 <br>
elements without growing.<br>
If you need a fast way to create a Dictionary that can hold 5 elements <br>
without growing, then you can add a new method and use that in your code:<br>
<br>
HashedCollection class >> #newFor5<br>
<br>
^self basicNew initialize: 7<br>
<br>
This way the method guarantees the capacity is a good prime just like <br>
#new does. And it won't affect anything else.<br>
<br>
Or we could change #new: to create a larger array by default, but then we <br>
would use more memory. In my image 68.7% of all the HashedCollections have <br>
the default capacity: 5. And 69% of all HashedCollections have fewer than <br>
3 elements, so those could all be shrunk down to capacity 3, saving 232kB <br>
memory (64-bit image).<br>
If we changed the default capacity to 7, the size of the image would grow <br>
by 231kB, which is not much nowadays, but still something.<br>
<br>
Perhaps we could create a class variable to hold the default capacity:<br>
<br>
HashedCollection class >> #new<br>
<br>
^self basicNew initialize: DefaultCapacity<br>
<br>
And then you could change it to 7 or 11 in your images.<br>
<br>
<br>
Levente<br>
<br>
On Fri, 3 Jan 2020, Chris Muller wrote:<br>
<br>
> Hi Levente,<br>
> Due to ancestry, the diff of this over Collections-ul.867 is only this:<br>
> <br>
> + nElements < 6 ifTrue: [ ^5 ].<br>
> <br>
> The issue I'm facing is, I don't know the size of the Dictionary at compile time, but I do at runtime.<br>
> <br>
> Dictionary new: runtimeVar<br>
> <br>
> 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<br>
> or the other at compile time, but I can't. As developer, I'm "torn" whether to write:<br>
> <br>
> Dictionary new<br>
> Dictionary new: runtimeVar (44% speed of Dictionary new when runtimeVar < 6)<br>
> or (runtimeVar < 6) ifTrue: [ Dictionary new ] ifFalse: [ Dictionary new: runtimeVar ]<br>
> <br>
> That conflict is what this last tweak tries to solve. It improves the second case, above, to 89% of "Dictionary new".<br>
> <br>
> Everything about this looks good and would like to include it in 5.3.<br>
> <br>
> - Chris<br>
> <br>
> 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>
> 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>
> <br>
></blockquote></div>