Description Reimplement Scheme_hash_table using linear probing.
Add a unit-test and micro-benchmark, called from
input/regression/scheme-unit-test.ly
The GUILE hash table implementation uses conflict resolution by
chaining. This means that hash lookups involve walking linked lists,
which is both relatively slow on access, and on GC tracing (the CPU
cannot prefetch the next list item).
The micro-benchmark for lookup shows a 1.5x - 2x speedup compared to
GUILE's hashtables.
The resizing strategy is to double the size if the load factor reaches
50%, making for average load of around 1/3. Hence, compared to
chaining, we have 50% more memory overhead, measured in number of
bytes.
This is not implemented using STL hash_map, as that is specified by
the standard to use chaining for conflict resolution. (
https://stackoverflow.com/questions/21518704/how-does-c-stl-unordered-map-resolve-collisions)
This could be contributed to GUILE, but is kept here for simplicity of
deployment (improvements would likely go into GUILE 3.2 rather than
GUILE 1.8).
Patch Set 1 #
Total comments: 20
Patch Set 2 : dak comments #Patch Set 3 : fixes #
MessagesTotal messages: 11
|