GNOME Bugzilla – Bug 770616
GHashTable: Robin Hood hashing
Last modified: 2018-05-24 19:04:29 UTC
Created attachment 334488 [details] [review] 0001-GHashTable-Change-from-quadratic-probing-to-Robin-Ho.patch Alex' prodding in bug 526456 motivated me to patch GHashTable to use Robin Hood hashing. The patch passes the tests and works when linked with Evolution, but I'm still skeptical of its performance benefits. One nice thing about it is that I was able to eliminate the use of tombstones entirely. It still needs proper benchmarking of insertions, removals and lookups in an appropriate mix alongside the current implementation. There may also be some microoptimization/cleanup left to do.
Just leaving this here so I don't forget; Python hash tables save memory by adding one level of indirection: https://mail.python.org/pipermail/python-dev/2012-December/123028.html That's another optimization we could try.
Good article on the potential accidental quadratic behaviour of Robin Hood hashing as discovered by the Rust community: http://accidentallyquadratic.tumblr.com/post/153545455987/rust-hash-iteration-reinsertion
Here are some additional tricks you can do for robin hood hashes: https://probablydance.com/2017/02/26/i-wrote-the-fastest-hashtable/
-- GitLab Migration Automatic Message -- This bug has been migrated to GNOME's GitLab instance and has been closed from further activity. You can subscribe and participate further through the new bug through this link to our GitLab instance: https://gitlab.gnome.org/GNOME/glib/issues/1198.