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

Igor Stasenko siguctua at gmail.com
Wed Mar 24 19:36:10 UTC 2010


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.

-- 
Best regards,
Igor Stasenko AKA sig.



More information about the Squeak-dev mailing list