On Fri, 26 Mar 2010, Igor Stasenko wrote:
On 25 March 2010 10:27, Levente Uzonyi leves@elte.hu wrote:
On Thu, 25 Mar 2010, Igor Stasenko wrote:
i think that #pointsTo: is a cheat :), which you can use in Sets but not dictionaries, because it contains associations. Also, it works only for identity-based collections.
Dictionaries don't have to use associations (for example MethodDictionary doesn't use them), that's why #pointsTo: works (MethodDictionary also uses it).
But that means a linear scan of the whole collection, even if done primitively, this is not scalable.
If you mean that MethodDictionaries implementation of #includesKey: doesn't scale, then you're right. But it doesn't have to scale at all. The average size of the MethodDictionaries in my image is ~11.1, the average capacity is ~17.2. For these dictionaries #includesKey: is >3x faster than the following (which is 30% faster than Dictionary >> #includesKey:):
^aSymbol ifNil: [ false ] ifNotNil: [ (array at: (self scanFor: aSymbol)) ~~ nil ]
The largest MethodDictionary contains 1176 keys in my image and the primitive is only 20% slower for that than the non-primitive method. The second largest has 610 entries and the primitive method is still 37% faster for that than the non-primitive version.
In LargeIdentityDictionary/LargeIdentitySet #pointsTo: does the same job as the list scanning loop in MaIdentityDictionary/MaIdentitySet, and #pointsTo: is faster than that.
Levente
I wonder how LargeIdentityDictionary compares to your dictionaries'.
me too.
If you give me a pointer to the source code, I can run the benchmarks.
Levente
-- Best regards, Igor Stasenko AKA sig.