[squeak-dev] 4.1 - hashed collections still a problem

Andres Valloud avalloud at smalltalk.comcastbiz.net
Fri Mar 26 05:51:10 UTC 2010


Typically, linked lists are better when the hash function is not of very 
high quality.  However, when the hash function is good, open addressing 
linear probing will beat everything else.

On 3/24/10 12:36 , Igor Stasenko wrote:
> On a board's meeting, Chris mentioned my implementation, and he says
> that it outperforms the LargeIdentitySet.
> I'm not sure how Chris compared it, because i implemented this scheme
> only for dictionaries , not sets.
>
> If you interested in details, you can check it in Magma.
> Brief description:
> i using a linked list for storing associations which keys having same hash value
> so, in addition to key/value pair there is next ivar.
> And dictionary's array entries look like this:
> ...
> ...
> ...
> e1 ->  e2 ->  e3
> ...
> ...
>
> where e1,e2,e3 is associations , which having same hash value, but
> different keys.
> So, when it doing lookup for a key, say e3, initially by doing hash
> lookup it finds e1, and then since #= for e1 answers false, it looks
> for the next linked association, until e3 is found.
>
> If i remember, the last time i benched this implementation, it almost
> same in speed as an original implementation for small sizes, and
> outperforms on a large sizes, especially, when you got more than 4096
> elements.
>
> So, Chris, can you give us details how you compared the speed between
> LargeIdentitySet and my dictionaries?
> I don't think its correct to compare them, because dictionaries need
> to handle more data than sets, and we should expect some slowdown
> because of it.
> But sure, you can imitate the Set behavior with dicts, by simply
> ignoring the value field of association (set it to nil), and use only
> keys, i.e.
> set add: object
> is like:
> dict at: object put: nil.
>
>    



More information about the Squeak-dev mailing list