[squeak-dev] 4.1 - hashed collections still a problem
leves at elte.hu
Tue Mar 23 10:36:27 UTC 2010
On Mon, 22 Mar 2010, Chris Muller wrote:
> 4.1 hashed collections, across the board, small to large, are slower
> by a factor of 2?! I just don't think we can keep doing this; getting
> slower and slower and slower, like molasses.. I'm sorry, but I really
> care about this and I know you do too because speed was the whole
> premise of putting these changes in.
> What went wrong? More importantly, how can we fix this?
What went wrong?
I think nothing. :) IdentitySet and IdentityDictionary wasn't ment to
support really large collections. The main reason is that there are only
4096 different hash values. So practically these collections are growing
4096 lists in a single array. In 3.9 and 3.10 these collections used a
hash expansion technique which distributed the elements uniformly. This
was changed when we integrated Andrés' hash changes. As you noticed some
of the primes didn't work well with #scaledIdentityHash, it's far better
now, though there may be even better primes. Finding such primes is a
computationally intensive task and the current ones (up to 10000000) are
pretty close to optimal.
Other than that there are two things that cause slowdown:
+1 extra message send/scanning: #scaledIdentityHash (the new hash
expansion scheme, but we save one by not using #findElementOrNil:)
+k (worst case) extra message send/scanning: #enclosedSetElement (OO nil
support, this only applies for IdentitySet)
Where k is the length of the list. Since there are only 4096 different
identity hash values for n = 250000 k will be ~61 (if the identity hashes
have a uniform distribution). For n = 1000000 it will be ~244. Note that
your benchmark exploits the worst case.
The long lists are bad, because HashedCollection is optimized for O(1)
list length. In this case the length of the list is not O(1), but
O(n) (with a very small constant).
How can we fix this?
I see two possible solutions for the problem:
1) use #largeHash instead of #identityHash, which is the identity hash of
the object mixed with the identity hash of its class. This helps if there
are objects from different classes in the set, but it doesn't help with
your benchmark. SystemTracer uses this method.
2) use differently implemented collections which are optimized for your
use case. For example I wrote LargeIdentitySet which probably has the best
performance you can have: http://leves.web.elte.hu/squeak/LargeIdentitySet.st
(note that it's hardly tested, probably contains bugs)
More information about the Squeak-dev