[ENH] LargeInteger hash ([et] been working great for months for me)
afunkyobject at yahoo.com
Tue May 13 04:34:36 UTC 2003
Last year, we discovered a performance bug in Squeak related to poor
LargeInteger hashing. The following demonstrates the issue:
s _ Set new.
n _ 3298534883328. "any big number"
s addAll: (n to: n + 750).
[ s removeAll: s copy ] timeToRun
This code takes less than one second to run with the fix, as it should, but is
very slow on a standard 3.6 image.
Andres Valloud and Stephan Rudlof graciously donated a set of four change sets
that causes Squeak to utilize an *existing primitive* to get a LargeInteger
hash based on, apparently, an expert hashing function (see [ENH] LargeInteger
hash (24 November 2002) in the Squeak fixes archive) but it has apparently not
made it to the standard image yet.
I have been using this non-stop for months as I have developed Magma. When I
was using removeKey:, Magma was virtually unusable without this fix. Since
then, I have hacked Magma a little so as to avoid removeKey almost completely,
since it has performance issues besides the poor hash dispersion.
Nevertheless, removeKey is not the problem, it's just a great demonstration of
it. The problem was poor LargeInteger hash dispersion, which caused lots of
collisions, making deletes (removeKey), adds (at:put:) and reads (at:) all
suffer. Magma or any program which reasonably needs to put LargeIntegers into
a Set or Dictionary is going to suffer without this fix.
There has been a lot of discussions about the Guides roles lately, but I am
still not sure the what appropriate action I can take to lobby that this fix
become part of the standard image. I would really like to get this
incorporated so I can get it out of Magma's package.
Guides, I would appreciate any guidance on the next step toward this goal.
Do you Yahoo!?
The New Yahoo! Search - Faster. Easier. Bingo.
More information about the Squeak-dev