A new hash table for Lwan

2 days ago

Lwan transitioned from a modified kmod hash table to a new design inspired by Rust's hashbrown and Abseil's SwissTable.
The new hash table uses a single group instead of multiple groups, splitting the hash into tophash and startpos to enable linear probing.
SIMD instructions are replaced with memchr() for portability, balancing performance and cross-architecture compatibility.
Key functions include hash_probe_half() and hash_probe_startpos() for lookups, with separate handling for insertion and deletion.
Deletion requires rehashing the entire table, and future improvements may focus on in-place or lazy rehashing to reduce latency.
The API includes HASH_FOREACH() for iteration and unit tests via SELF_TEST() to ensure reliability during development.
While performance gains are likely, the primary goal was simplification and maintainability over the previous complex implementation.
Future work may explore direct SIMD usage or improved rehashing techniques, with code available in the Lwan repository.

Hasty Briefsbeta