On Friday, 3 April 2015 at 20:35:40 UTC, Martin Nowak wrote:
On 04/03/2015 06:11 PM, w0rp wrote:
Now, I am not the most fantastic Computer Science guy in the
world, and
I probably got a few things wrong. If anyone would like to
look at my
code and point out mistakes, please do. I will add any
improvements
suggested.
You should use triangular numbers and power of 2 bucket sizes
instead of
quadratic numbers and prime sized buckets, because that
guarantees full
utilisation of the buckets and a minimal period of the numbers.
The necessary loop is really trivial.
https://github.com/D-Programming-Language/dmd/blob/f234c39a0e633fc9a0b5474fe2def76be9a373ef/src/root/stringtable.c#L162
If you replace
i = (i + j) & (tabledim - 1);
with this
i = (i + 1) & (tabledim - 1);
you get linear probing btw.
I have pushed again, and now the hashmap uses powers of two and
triangular numbers, per your suggestion. I noticed a small
improvement in speed, probably coming from the & for modulo
trick. If you would like to test the maps with the benchmark
program you can run the following:
dub run -q --build=release --config=benchmark_hashmap
You can use the --compiler switch for dub to try different
compilers.
