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

Chris Muller asqueaker at gmail.com
Thu Mar 25 03:58:56 UTC 2010

I have not tested LargeIdentitySet.  Igor, I may have used the wrong
words, but I *meant* to say that your Dictionary and Sets are the
fastest I've tested and I'm testing switching my software to use them
everywhere, not just a few places in Magma.

I have not tested LargeIdentitySet because Levente said
LargeIdentitySet may have bugs and I like the family of collections
provided by your solution anyway, I need them.

 - Chris

On Wed, Mar 24, 2010 at 2:36 PM, Igor Stasenko <siguctua at gmail.com> 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.
> --
> Best regards,
> Igor Stasenko AKA sig.

More information about the Squeak-dev mailing list