<div dir="ltr">Hi Max,<div><br></div><div>Theoretically, for a small number of elements, usually somewhere between 3 and 30 depending on implementations, a linear search is faster than a hash search, especially in the Pharo dictionary hash search implementation.</div><div><br></div><div>Efficient dictionary implementations are usually bucket-based. The dictionary holds a certain number of buckets, and based on the key hash, the bucket where the key value is present is determined. Small buckets are linear (arrays or linked list). Large buckets are typically balanced binary trees (red-black trees typically). Under a certain number of elements there is a single bucket, which means a linear search is performed, as for the SmallDictionary. When it grows the dictionary search becomes a combination between a hash search and a linear or tree search.</div><div><br></div><div>Pharo dictionary search is first hash-based, then all the buckets are represented next to each other in the same arrays and a linear search is performed there, leading to many collisions and slower search time (especially when the element is not found), sometimes the code searches over multiple buckets because the dictionary is too full or there are too many near-collisions. The memory consumption is competitive with the advanced implementations though (precise measurements would need to be made).</div><div><br></div><div>Method dictionaries are represented differently to optimize the look-up logic.</div><div><br></div><div>If you want to improve things and have one dictionary implementation instead of two, implement or look for a bucket based dictionary and put it in the base image instead of Dictionary. This is quite some work since there are many APIs to port. You can look at the Pinnochio implementation, it's quite good but they've not implemented large buckets.</div><div><br></div><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Jun 8, 2018 at 8:46 AM, Max Leske <span dir="ltr"><<a href="mailto:maxleske@gmail.com" target="_blank">maxleske@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi,<br>
<br>
I was messing around with SmallDictionary when I suddenly realised that I can't find a single reason to use it over a normal Dictionary. While its name and class comment imply that it is somehow an optimised Dictionary, I don't see any measurement where that actually holds up. The following was run in a Pharo 7 image on a recent VM (see below):<br>
<br>
| d |<br>
d := SmallDictionary new.<br>
d sizeInMemory. "24"<br>
[100000 timesRepeat: [<br>
        1 to: 100 do: [ :i | d at:i put: i] ] ] timeToRun. "0:00:00:05.226"<br>
<br>
[100000 timesRepeat: [<br>
        d at: 48 ifAbsent: [] ] ] timeToRun. "0:00:00:00.041"<br>
<br>
<br>
<br>
| d |<br>
d := Dictionary new.<br>
d sizeInMemory. "16"<br>
[100000 timesRepeat: [<br>
        1 to: 100 do: [ :i | d at:i put: i] ] ] timeToRun. "0:00:00:00.385"<br>
[100000 timesRepeat: [<br>
        d at: 48 ifAbsent: [] ] ] timeToRun.  "0:00:00:00.006"<br>
<br>
<br>
As you can see, SmallDictionary is 8 bytes larger per instance and significantly faster while reading and writing (I know that this isn't a good benchmark but it suffices to make my point).<br>
<br>
<br>
Is anyone aware of a reason for hanging on to SmallDictionary? I'm also curious to know how SmallDictionary came to be. There must have been some advantage over Dictionary at some point in the past.<br>
<br>
<br>
Cheers,<br>
Max<br>
<br>
<br>
<br>
<br>
<br>
Image version: Pharo 7.0<br>
Build information: Pharo-7.0+alpha.build.961.sha.<wbr>a69e72a97136bc3f93831584b6efa2<wbr>b1703deb84 (32 Bit)<br>
<br>
VM version: CoInterpreter VMMaker.oscog- nice.2281 uuid: 4beeaee7-567e-1a4b-b0fb-bd95ce<wbr>302516 Nov 27 2017<br>
StackToRegisterMappingCogit VMMaker.oscog-nice.2283 uuid: 2d20324d-a2ab-48d6-b0f6-9fc3d6<wbr>6899da Nov 27 2017<br>
VM: 201711262336 <a href="https://github.com/OpenSmalltalk/opensmalltalk-vm.git" rel="noreferrer" target="_blank">https://github.com/OpenSmallta<wbr>lk/opensmalltalk-vm.git</a> $ Date: Mon Nov 27 00:36:29 2017 +0100 $ Plugins: 201711262336 <a href="https://github.com/OpenSmalltalk/opensmalltalk-vm.git" rel="noreferrer" target="_blank">https://github.com/OpenSmallta<wbr>lk/opensmalltalk-vm.git</a> $<br>
<br>
OS: macOS 10.13.5<br>
Machine: MacBook Pro (13-inch, 2016, Four Thunderbolt 3 Ports)<br>
<br>
</blockquote></div><br><br clear="all"><div><br></div>-- <br><div class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div dir="ltr"><span style="font-size:12.8px">Clément Béra<br></span><span style="color:rgb(0,0,238)"><a href="https://clementbera.github.io/" target="_blank">https://clementbera.github.io/</a></span><div style="font-size:12.8px"><a href="https://clementbera.wordpress.com/" target="_blank">https://clementbera.wordpress.com/</a></div></div></div></div></div></div>
</div>