Reserving/Preallocating associative array?

[Benjamin Thaut]

Am 27.12.2013 17:49, schrieb Gordon:
>
> Benjamin,
> Can you point me to your Hashmap implementation? I could perhaps use it
> to improve the timings even more.

https://github.com/Ingrater/druntime/blob/merge64/src/core/hashmap.d

This implementation depends on my own allocator design, but it should be 
possible to remove that dependeny quite easly by replacing all 
allocations / frees with malloc/free or GC.malloc / nothing. Just make 
sure that memory is not initialized beforehand (as new 
ubyte[sizeInBytes] would do) because that also has a considerable 
performance impact. Also when allocating with GC.malloc you should 
specify the GC.BlkAttr.NO_SCAN flag, because you know that your data 
does not contain any pointers. That way the GC will not scan that huge 
memory block and it should speed up collection a lot.

To improve the performance of the hashmap you can try:
- specifingy different hashing functions (via the hash policy). See 
https://github.com/Ingrater/thBase/blob/master/src/thBase/policies/hashing.d 
for more examples of hashing policies.
- Change the amount of always free entries in the hashmap (currently 
25%) for that change line 233, 207, 210 (not factored into a constant 
yet). Reducing the free entries might result in less cache misses, but 
more linear search, as this is a linear probing hashmap. Increasing the 
free entries might reduce the amount of linear search, but increase 
cache misses and increases memory usage.
- Compute a series of prime numbers, for which each prime number is at 
least twice as big as the previous one and use that as the possible 
sizes for the hashmap. Prime number sizes give better distribution of 
the items within the hashmap, therefor reduce the amount of linear 
searching neccessary and thus improve the hashmap performance.
- When searching for the next free spot in the hashmap, it currently 
just adds 1 to the previous index found (line 301). It is also possible 
to rehash the previous index (just put it into the hashing function 
again), which would give a new index that is more distant in the hashmap 
from the current one. This would again improve the distribution of the 
items in the hashmap, and thus reduce linear search time, but may 
increase the amount of cache-misses as it no longer does linear memory 
access.

In case you are interrested in my implementation of your problem see here:
http://dpaste.dzfl.pl/8d0d174e

You won't be able to compile the code unless you setup my custom D 
environment. Which I would not recommend unless you really hate the D 
garbage collector ;-)

Kind Regards
Benjamin Thaut