digitalmars.D.learn - Size threshold replace complex probing with linear search for small
=?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
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.
Feb 19 2018
Nathan S. <no.public.email example.com> writes:
On Monday, 19 February 2018 at 10:22:12 UTC, Nordlöw wrote:I'm currently developing a combined HashMap and HashSet with open addressingYou might want to consider using Robin Hood hashing to reduce the worst-case length of collision chains, regardless of what kind of probing scheme you use.
Feb 19 2018