[prev in list] [next in list] [prev in thread] [next in thread]
List: perl6-internals
Subject: Re: parrot-dev Digest, Vol 24, Issue 12
From: "Paul C. Anagnostopoulos" <paul () windfall ! com>
Date: 2010-08-11 13:21:56
Message-ID: 201008111324.o7BDONLf021245 () mail175c2 ! megamailservers ! com
[Download RAW message or body]
[Attachment #2 (multipart/alternative)]
At 8/11/2010 08:00 AM, parrot-dev-request@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
[Attachment #5 (text/html)]
<html>
<body>
<font size=3>At 8/11/2010 08:00 AM, parrot-dev-request@lists.parrot.org
wrote:<br><br>
<blockquote type=cite class=cite cite="">> It helps with hash
expansion because when you double the size of bucket <br>
> store you have to move arround only a half of the keys, and their
new <br>
> locations is guarantted to be free<br><br>
I'm not sure I believe that's the case with our implementation.
Besides that, <br>
I was under the impression (see The Practice of Programming) that picking
a <br>
prime number for the array size produces a better distribution of keys in
<br>
buckets. The argument is that the lack of a common factor between
the array <br>
size, the hash seed, and likely hash values produces a better
distribution.<br><br>
Maybe we need some sort of intrusive benchmark with likely hash values
that <br>
shows the statistical goodness or badness of our implementation.<br>
</blockquote><br>
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.<br><br>
There are so many design variants with hash tables. We certainly do need
a benchmark against which to evaluate design decisions.<br><br>
~~ Paul<br>
</font></body>
<br>
<body>
<font size=3><br>
----------------------------------------------------------------<br>
<b><i>Windfall
</i></b>
Paul C. Anagnostopoulos <br>
----------------------------------------------------------<br>
<b><i>Software</i></b>
978 371-2316 <br>
&n \
bsp; <a \
href="http://www.windfall.com/" eudora="autourl">www.windfall.com<br> \
</a>----------------------------------------------------------------<br> Metaphorical \
invocations ... often suffer from the<br> weakness of giving such satisfaction to the \
human<br> mind that they tend to be mistaken for incisive and<br>
illuminating observations. ---Torkel Franzen</font></body>
</html>
_______________________________________________
http://lists.parrot.org/mailman/listinfo/parrot-dev
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic