[ENH] LargeInteger hash ([et][approved])
Doug Way
dway at riskmetrics.com
Tue May 27 23:02:54 UTC 2003
[approved]
Chris Muller wrote:
>
> Last year, we discovered a performance bug in Squeak related to poor
> LargeInteger hashing. The following demonstrates the issue:
>
> |s n|
> 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.
> Thank you!
>
> Regards,
> Chris
>
> __________________________________
> Do you Yahoo!?
> The New Yahoo! Search - Faster. Easier. Bingo.
> http://search.yahoo.com
More information about the Squeak-dev
mailing list
|