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@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.