[ENH] Ten Percent Faster Morphic! (with conversion)

Stephen Pair spair at acm.org
Tue Aug 6 14:54:57 UTC 2002


> -----Original Message-----
> From: squeak-dev-admin at lists.squeakfoundation.org 
> [mailto:squeak-dev-admin at lists.squeakfoundation.org] On 
> Behalf Of Henrik Gedenryd
> Sent: Tuesday, August 06, 2002 10:43 AM
> To: squeak-dev
> Subject: Re: [ENH] Ten Percent Faster Morphic! (with conversion)
> 
> 
> > Could we make all really small hashed structures do linear searches?
> > 
> > - Stephen
> 
> Can you elaborate on exactly what improvement you are thinking of?
> 
> The hash algorithm is already more or less linear, the hash 
> is used to get the first index to look at, and then the code 
> scans thru the remaining slots in consecutive order (index _ 
> index + 1) wrapping around as needed.
> 
> (This apparently inefficient scanning strategy is to make 
> scanning during message lookup cheap; more complex schemes 
> such as double hashing would require more complex operations 
> there. IIRC I measured that the gain from scanning fewer 
> slots would be relatively minor.)
> 
> The only difference that I see for small dictionaries is to 
> always start the scan at 1; this would merely save the 
> calculation of the hash value for the key, and I think the 
> gain is negligible.

Exactly...for small dicts you would skip the hash and always start the
scan at 1.  Of course, it all depends on the hash, and how frequently
the contents are accessed to determine just how much time is saved.  As
Ned discovered, in Morphic, the savings can be significant.  But, on the
other side, keeping things simple is sometimes worth sacrificing a
little performance.
 
> I could be wrong though, and this is why I ask the above question.
> 
> Henrik

- Stephen




More information about the Squeak-dev mailing list