parrot-dev Digest, Vol 24, Issue 12
Paul C. Anagnostopoulos
paul at windfall.com
Wed Aug 11 13:21:56 UTC 2010
At 8/11/2010 08:00 AM, parrot-dev-request at lists.parrot.org wrote:
>> It helps with hash expansion because when you double the size of bucket
>> store you have to move arround only a half of the keys, and their new
>> locations is guarantted to be free
>
>I'm not sure I believe that's the case with our implementation. Besides that,
>I was under the impression (see The Practice of Programming) that picking a
>prime number for the array size produces a better distribution of keys in
>buckets. The argument is that the lack of a common factor between the array
>size, the hash seed, and likely hash values produces a better distribution.
>
>Maybe we need some sort of intrusive benchmark with likely hash values that
>shows the statistical goodness or badness of our implementation.
I believe the current implementation, when enlarging a hash table, does make use of the fact that the table sizes are powers of 2 and that the new table is double in size. That does make for faster resizing. If we go to a scheme using a hash table size vector, we could detect the cases where we are doubling a power-of-2-sized table and use the faster algorithm.
There are so many design variants with hash tables. We certainly do need a benchmark against which to evaluate design decisions.
~~ Paul
----------------------------------------------------------------
Windfall Paul C. Anagnostopoulos
----------------------------------------------------------
Software 978 371-2316
www.windfall.com
----------------------------------------------------------------
Metaphorical invocations ... often suffer from the
weakness of giving such satisfaction to the human
mind that they tend to be mistaken for incisive and
illuminating observations. ---Torkel Franzen
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.parrot.org/pipermail/parrot-dev/attachments/20100811/456a9e73/attachment.html>
More information about the parrot-dev
mailing list