Size threshold replace complex probing with linear search for small hash tables
Nordlöw
per.nordlow at gmail.com
Mon Feb 19 10:22:12 UTC 2018
I'm currently developing a combined HashMap and HashSet with open
addressing at
https://github.com/nordlow/phobos-next/blob/master/src/open_hashmap_or_hashset.d
with probing using steps of triangular numbers when length is a
power of two at
https://github.com/nordlow/phobos-next/blob/master/src/probing.d
I've read that for small tables (where the size of the entire
array Element[] is smaller than a certain threshold) a linear
search is usually faster. Is this threshold somehow related to
the sizes of cache-line?
Suggestions for compile-time or run-time logic that decides when
to use linear search are very welcome!
My current proposal is to use linear search when
ElementType.sizeof*length <= byte-size of a cache-line.
More information about the Digitalmars-d-learn
mailing list