[PATCH] Implement Robin Hood distance-based early termination in simplehash
Hackorum builds and tests every patch posted to the lists, not only commitfest submissions. This is Hackorum's own CI rather than the PostgreSQL project's, and it is still under testing - please report anything that looks wrong.
You can run a PostgreSQL built from this patch straight from Docker, with no checkout and no build:
docker run --rm -p 5432:5432 ghcr.io/hackorum-dev/postgres-patch:t253752psql -h localhost -U postgresBuilt from patchset v1 (message #1), September 20, 2026 at 03:10 PM.
Every patchset is also pushed to a branch of our PostgreSQL fork, so you can check out the same tree CI built. Without a PostgreSQL checkout:
git clone --branch t253752_1 https://github.com/hackorum-dev/postgres.gitIn a checkout you already have, add the fork once:
git remote add hackorum https://github.com/hackorum-dev/postgres.gitthen, for this patchset and every later one:
git fetch hackorum t253752_1 && git checkout t253752_1Patchset v1 (message #1) is on t253752_1
Hi,
I noticed two TODO comments in simplehash.h (lines 825 and 923) asking
whether
we could stop hash table searches based on distance-from-optimal. Since
simplehash uses Robin Hood hashing, which keeps elements implicitly sorted
by
distance, this optimization is straightforward to implement.
This patch adds early termination to SH_LOOKUP_HASH_INTERNAL and SH_DELETE.
When searching at distance D, if we encounter an element with distance < D,
we can immediately return NULL/false because Robin Hood insertion would have
placed our target before this element if it existed.
The optimization is only enabled when SH_STORE_HASH is defined, to avoid
recomputing hashes during search (as suggested in the original TODO
comment).
Implementation details:
1. Added searchdist counter tracking probe distance from optimal bucket
2. At each probe, compare current element's distance vs. search distance
3. Early return when current distance < search distance
4. Increment searchdist after each probe
5. Conditional compilation via #ifdef SH_STORE_HASH
Benefits:
- Faster unsuccessful lookups (common in hash operations)
- Better average-case performance, especially at high load factors
- Zero memory overhead
- No performance cost when SH_STORE_HASH is undefined
- Preserves correctness
Testing:
- Build tested successfully with --enable-cassert --enable-debug
- All regression tests pass (make check)
- Edge cases verified: empty tables, single elements, wraparound, long
collision chains
The optimization has the biggest impact on unsuccessful lookups in hash
tables with many collisions, which is a common scenario in query processing.
Patch attached.
Aviral Asthana
aviral.asthana0704@gmail.com