But please take care that you are using tommy-hashdyn outside its scope.
tommy-hashdyn is an intrusive data structure, that requires to have its node embedded in the object that you store in the hashtable.
In your benchmark this doesn't happen, and you have an extra malloc() call for each value inserted, that obviously kills the performance.
So, for storing ints, tommy-hashdyn is just not a good match, as doesn't make sense to have a node bigger than the object itself. For strings, it could work, but only embedding the node inside the string.
Another aspect that you are not evaluating is that you are testing in the best condition for an open addressing hash table, with only insertions and no deletions.
This always results in a table without any "deleted" entry, that allows to search for elements always in the best condition.
Anyway, if you are interested, I've adapted the TommyDS benchmark for your libdynamic implementation, and you can find the resulting graphs at :
Note that likely you would like to adjust your implementation in reallocation as it seems to have a very slow worst case with some specific sizes just a little smaller than a power of 2.
The problem seems to be that if the table size is near at the realloc limit, a small sequence of inserts and deletes triggers a reallocation, but the new size chosen is the same as before, resulting in another reallocation in a short time.
Hi,
FYI, I've done a hash table lookup benchmark, where I just included tommy_hashdyn.
https://lonewolfer.wordpress.com/2015/02/07/benchmarking-string-hash-tables/
Kind regards,
Fredrik
Hi Fredrik,
Thanks for the benchmark!
But please take care that you are using tommy-hashdyn outside its scope.
tommy-hashdyn is an intrusive data structure, that requires to have its node embedded in the object that you store in the hashtable.
In your benchmark this doesn't happen, and you have an extra malloc() call for each value inserted, that obviously kills the performance.
So, for storing ints, tommy-hashdyn is just not a good match, as doesn't make sense to have a node bigger than the object itself. For strings, it could work, but only embedding the node inside the string.
Another aspect that you are not evaluating is that you are testing in the best condition for an open addressing hash table, with only insertions and no deletions.
This always results in a table without any "deleted" entry, that allows to search for elements always in the best condition.
Anyway, if you are interested, I've adapted the TommyDS benchmark for your libdynamic implementation, and you can find the resulting graphs at :
http://tommyds.sourceforge.net/beta/libdynamic/
Note that likely you would like to adjust your implementation in reallocation as it seems to have a very slow worst case with some specific sizes just a little smaller than a power of 2.
For example, see the random_change graph :
http://tommyds.sourceforge.net/beta/libdynamic/img_random_change.png
The problem seems to be that if the table size is near at the realloc limit, a small sequence of inserts and deletes triggers a reallocation, but the new size chosen is the same as before, resulting in another reallocation in a short time.
You can see the benchmark source at :
https://github.com/amadvance/tommyds/tree/libdynamic
Ciao,
Andrea
Last edit: Andrea Mazzoleni 2015-02-11