| From: | Aviral Asthana <aviral(dot)asthana0704(at)gmail(dot)com> |
|---|---|
| To: | pgsql-hackers(at)postgresql(dot)org |
| Subject: | [PATCH] Implement Robin Hood distance-based early termination in simplehash |
| Date: | 2026-09-09 09:53:29 |
| Message-ID: | CAA7-H4u9-Sk5TqA5a2sR2Jaw+d5yGRJWN54Oxcz9+mOLxCfKgw@mail.gmail.com |
| Views: | Whole Thread | Raw Message | Download mbox | Resend email |
| Thread: | |
| Lists: | pgsql-hackers |
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(dot)asthana0704(at)gmail(dot)com
| Attachment | Content-Type | Size |
|---|---|---|
| robin-hood-optimization-v1-TESTED.patch | text/plain | 4.3 KB |
| From | Date | Subject | |
|---|---|---|---|
| Next Message | Nazir Bilal Yavuz | 2026-09-09 10:00:46 | Re: Speed up COPY FROM text/CSV parsing using SIMD |
| Previous Message | wenhui qiu | 2026-09-09 09:49:51 | Do we reduce autovacuum_naptime max values |