Lwan ハッシュテーブルを刷新

A new hash table for Lwan2026-05-06For a long time, Lwan used to use a heavily modified version of the hash table from the kmod project. I was lightly involved with that project during its inception, so this seemed like a natural choice. Over the years, that hash table proved inneficient for the use cases in Lwan, so I began patching it to try and improve its performance; I succeeded in some cases, but the added complexity and years of technical debt eventually caught up with me, so things started failing.I've wanted to try a different way of implementing a hash table, possibly using some kind of linear probing method, for a good while, so that's what I did.InspirationI've been inspired by Rust's hashbrown, which has been the default hash table in its standard library for a good while. That hash table, in turn, was inspired by Abseil's SwissTable. Even the Go programming language began using a variation of this hash table since 2025.I wanted to make Lwan's new hash table as portable as possible; however, Swiss Tables require the use of SIMD instructions to perform acceptably. As you can see in the following diagram, a swiss table is laid out like so:It can have multiple groups, chained together;Each group contains a Control Word and the slots containing the actual items;The nth byte in the Control Word represents a Control Byte for the nth slot.The result of the hash function is split in two: H1, which chooses the first group where an item – either empty, unused, or deleted; and H2, which is stored in the Control Word. SIMD is used to determine which slots in a group matches the required H2 (or an empty or a deleted slot), in parallel, with minimal instructions. Even though it performs a linear probe, it does so in a very efficient manner that's not only cache efficient, it's also using hardware capabilities that are rarely exploited in data structures.NoteThe H2 hash has only 7 bits, with one bit left to signal if an item is empty, in use, or deleted. The distinction between deleted and empty is used for a few different things, including reducing fragmentation (or requiring constant rehashes), or straying too far from the original H1 % number_of_groups-th group.The hash table in LwanUsing SIMD directly was ruled out due to it not being portable enough; even though SWAR could be used where SIMD was not available (or in architectures I wasn't familiar with or had the hardware to test the implementation). In its place, the standard C function memchr() was used instead. This function is usually implemented using SIMD instructions anyway (although with higher fixed costs that wouldn't be an issue if SIMD was used directly, as it'll become clear with code snippets down below).As a result, instead of having multiple groups like Swiss Tables, the table in Lwan has only one group:With this structure, the hash H is split into two:uint8_t tophash = no_tombstone(H & 0xff), with no_tombstone() returning a value that's not used for a tombstone (\0);uint32_t startpos = (H >> 8) & (capacity - 1), with capacity being always a power of two.With both tophash and startpos in hand, the table is effectively split in two:Making it possible to define the internal hash table probing functions like this:static bool hash_probe_half(const struct hash *ht,

const void *key,

uint32_t *out_slot,

※ 著作権に配慮し、引用は冒頭3段落までです。続きは元記事をご覧ください。