Feature #22011
Updated by dsh0416 (Delton Ding) 6 months ago
This change adds a Swiss-table-inspired probing layer to Ruby's core `st_table`, and shrinks `st_table_entry` from 24 B to 16 B by moving the stored hash into a parallel array. It is built and enabled by default; `--disable-swiss-st` reverts to the original `st.c`. The public ABI of `struct st_table` and the iteration-order guarantee are preserved. ## Motivation Hashes are everywhere in Ruby — instance-variable tables, ivar shapes, constant tables, JSON/HTTP/AR rows, every `params`, every `to_h`. Profiles of Rails-shaped workloads spend a meaningful fraction of CPU inside `st_lookup` and `st_insert`. Two pain points stood out in the upstream implementation: 1. **Probe loops are branch-heavy.** Every step of the perturb chain loads a bin, fetches the entry it points to, compares the full `st_hash_t` (8 B) and only then calls `eql?`. On a miss that is several dependent loads per probe with no way to fast-reject groups of slots in parallel. 2. **`st_table_entry` is 24 B.** The `(hash, key, record)` triple gets one cache line per ~2.5 entries. Iteration and equality scans burn through L1 quickly, and Ruby programs typically hold a *lot* of small-to-mid-sized hashes (so per-table overhead matters). The Swiss-table family of designs (Abseil `flat_hash_map`, Rust `hashbrown`) addresses (1) with a 1-byte-per-slot **control array** that lets a single SIMD/SWAR comparison reject or short-list 8 slots at once. We borrow that idea but keep Ruby's two-array layout (so we don't break ABI or insertion order) and add a third, parallel `ctrl[]` byte array. We then attack (2) by also extracting the hash field out of `st_table_entry` into its own parallel `uint32_t hashes[]` array. --- ## Changes Design ### 1. Adds `ST_USE_SWISS_BINS`, enabled under `RUBY_EXPORT`, disabled otherwise Three-array layout | array | width | role | | ----------- | --------------------------- | -------------------------------------------------------------------------- | | `entries[]` | 16 B (was 24 B) | insertion-order log of `(key, record)` | | `hashes[]` | 4 B per slot | parallel array of truncated 32-bit hashes (also encodes the tombstone) | | `bins[]` | adaptive 1 / 2 / 4 / 8 B | hash-indexed array of indices into `entries[]` | | `ctrl[]` | 1 B per slot | `H2` (top 7 bits of hash) or `EMPTY (0xff)` / `DELETED (0xfe)` | `entries[]` and `hashes[]` are the same length and addressed by the same index, so `parser_st.c` keeps iteration and slot reuse stay trivial. `ctrl[]` is the old-compatible layout. fast-reject filter and lives alongside `bins[]`; only when a `ctrl` byte matches H2 do we load the (now smaller) entry and the parallel hash to confirm the match. SWAR is done on `uint64_t` reads of `ctrl[]` so the per-group cost is a handful of bitwise ops with no SIMD register transfer (see "What we tried but didn't keep" below). ### 2. Compact `st_table_entry` Before: ```c 2. Removes struct st_table_entry { st_hash_t hash; /* 8 B */ st_data_t key; /* 8 B */ st_data_t record; /* 8 B */ }; /* 24 B */ ``` After (when `ST_USE_SWISS_BINS` is on, which is the stored default): ```c struct st_table_entry { st_data_t key; /* 8 B */ st_data_t record; /* 8 B */ }; /* 16 B */ ``` The hash field moves into `tab->hashes[i]`, a `uint32_t` (so two slots fit per 8-byte word, four entries per cache line). All access goes through `ST_HASH_AT_PTR` / `ST_HASH_AT_IDX` macros so the same source compiles unchanged when the feature is disabled. The `set_table` variant keeps its original inline-hash layout — it already uses 16 B entries and is not part of `st_table`'s ABI footprint. ### 3. The new hash function Storing only the low 32 bits of the hash means we can no longer read H2 from st_table_entry in the *top* 7 bits of the original `unsigned long` hash, which is what a textbook Swiss path design does. Naively recomputing the full 64-bit hash from the key on every rebuild / rehash / `st_shift` / `st_general_foreach` works for correctness but kills insert and stores hashes in rebuild performance — equality+hash for strings is not free. The fix is to derive H2 from a side array after entries, using band of the *truncated* 32-bit stored hashes. hash, disjoint from the band that picks the bin: ```c 3. Introduces packed Swiss /* bin groups: 8 control bytes plus 8 index: low `bin_power` bits, masked by `bins_mask(tab)` */ hash_bin(uint32_t h, st_table *tab) { return h & bins_mask(tab); } /* H2: bits 25..31 of the same 32-bit hash, never overlaps with */ /* the bin indexes per group. index because bin_power is capped well under 25 in */ 4. Adds Swiss probing via control-byte matching, using 7-bit h2 fingerprints for candidate filtering. /* practice. */ 5. Packs bins after entries when possible, reducing separate allocation pressure. static inline unsigned char 6. Updates allocation, copy, free, memsize, rebuild, rehash, insert, delete, shift, lookup, foreach, keys, and values paths to go through hash/bin abstraction macros. st_swiss_h2(st_hash_t hash) { return (unsigned char)((hash >> 25) & 0x7f); 7. Adjusts rebuild thresholds for Swiss load factor, using roughly 7/8 bin occupancy. } 8. Adds tombstone-triggered rebuild behavior when many deleted slots accumulate. ``` ## Analysis This makes the stored `uint32_t` self-sufficient: every probe reads both the bin index and the H2 byte from the same word, no `do_hash()` call required, and rebuild/rehash/shift/foreach all use `ST_HASH_AT_IDX(tab, i)` instead of recomputing. Earlier preliminarily analysis shows HUGE improvements Two additional details that fall out of the truncation: 1. `normalize_hash_value()` is updated so that `0xFFFFFFFF` (the tombstone marker for the 32-bit hash slot) never collides with a real hash value — if the truncation lands on microbenchmarks after adopting ideas from swiss tables, but it the reserved value we bump it. The 64-bit reservation is not quite true in preserved on platforms that compile without `ST_USE_SWISS_BINS`. 2. The `MARK_ENTRY_DELETED` / `DELETED_ENTRY_P` macros now take the real-world benches. table as a parameter so they can read/write the parallel hash slot. Swiss-table-style probing can look huge ### 4. Prefetch on H2 match When SWAR finds a candidate H2 match in isolated lookup/insert microbenchmarks because a control group, the hot loop next operation is tight, loading the table stays cache-hot, matching `st_table_entry` and control-byte filtering avoids many full entry/key comparisons. In real Ruby workloads, the parallel hash table operations word — both of which are mixed with object allocation, method dispatch, GC barriers, string/hash callbacks, comparisons, branchy VM work, etc. That weakens in cold cache lines on a miss. We issue `__builtin_prefetch` on both immediately after the “everything match is detected in L1” assumption. `find_table_entry_ind` / `find_table_bin_ind` / `find_table_bin_ptr_and_reserve`. On lookup-heavy workloads this hides a meaningful chunk of the L2 latency that the SWAR fast-filter would otherwise expose. If ### 5. What we tried but didn't keep * **SSE2 / NEON intrinsics for the old table group scan.** On Apple Silicon the vector-to-GPR transfer for the match mask cost more than the entire SWAR sequence; on x86_64 the benefit, if any, was within noise. SWAR is kept the only shipped backend. * **Recomputing the full 64-bit hash** in rebuild/rehash paths to keep H2 in the high bits. Correct but cost ~5–10 % on insert workloads; superseded by the bit-band trick above. ## Results vs `master` (microbenches) Both binaries built from the same tree (`master = 42b3cdc51a`, `swiss = 3c0446847f`), same compiler, same flags. Each script run 5× with `--disable-gems`, best-of-N reported. Memory is `maximum resident set size` from `/usr/bin/time -l` on macOS arm64 (M-class). ### Throughput (lower wall time = better) | benchmark | master (s) | swiss (s) | speedup | | ----------------- | ---------: | --------: | ------: | | aref_int_large | 0.8352 | 0.6862 | **+17.8 %** | | aref_str_large | 0.9915 | 0.8406 | **+15.2 %** | | aref_miss_large | 1.0803 | 0.7896 | **+26.9 %** | | aref_mix_50 | 1.0337 | 0.8201 | **+20.7 %** | | insert_grow | 0.1138 | 0.1105 | +2.9 % | | churn (mixed RW) | 0.0321 | 0.0304 | +5.5 % | | iterate | 0.0566 | 0.0565 | ±0.1 % | Lookups are the headline win — both successful (`+15 % … +20 %`) and missing (`+27 %`), the latter because a missing key now short-circuits on the first SWAR group with no entry/bin loads at < 0.5 load factor, collision chains/probe lengths all. Inserts and churn are already short, so a simpler open-addressing scheme can be very competitive modestly faster because it has smaller code and fewer moving parts. rebuilds no longer call `do_hash`. Iteration is unaffected (it never touched bins or ctrl). ### Memory Process RSS for the benchmark workloads (same runs): | benchmark | master (MB) | swiss (MB) | delta | | ----------------- | ----------: | ---------: | ----: | | insert_grow | 66.62 | 60.44 | **−9.3 %** | | aref_str_large | 15.27 | 15.23 | −0.3 % | | aref_mix_50 | 16.64 | 16.61 | −0.2 % | | churn | 13.19 | 13.03 | −1.2 % | Per-table memory (`ObjectSpace.memsize_of`, sum across many hashes): | workload | master | swiss | delta | | ---------------------------------------- | --------: | --------: | ----------: | | 2 000 hashes × 200 entries | 14.66 MB | 12.11 MB | **−17.4 %** | | 1 hash × 100 000 entries | 4.19 MB | 3.28 MB | **−21.9 %** | The larger practical win two memory views agree: any workload that holds a meaningful number of entries live (whether one big hash or many small ones) sees double-digit shrinkage from the Swiss-ish design 24 B → 16 B entry plus the 1 B `ctrl[]` / 4 B `hashes[]` pair, because they together (`5 B` per slot) cost less than the 8 B saved per slot in `entries[]`. Per-table overhead at fewer than ~64 entries is probably memory density: sustaining a much higher load factor, around 7/8, without making probe behavior collapse. With this new method, we could increase roughly flat; the load factor Swiss path itself only kicks in at `entry_power ≥ 6` (table capacity ≥ 64). More benches are coming soon to about 7/8 make sure the patch really works with competitive speed. This saves us more memory then the introduced `ctrl[]`. no regression, especially in real world cases.