GHashTable: Robin Hood hashing
Submitted by Hans Petter Jansson @hansp
Link to original bug (#770616)
Description
Created attachment 334488 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.
Patch 334488, "0001-GHashTable-Change-from-quadratic-probing-to-Robin-Ho.patch":
0001-GHashTable-Change-from-quadratic-probing-to-Robin-Ho.patch
Version: 2.49.x