jayzhan211 commented on PR #25247: URL: https://github.com/apache/datafusion/pull/25247#issuecomment-5650105447
**Per probe (every input row).** Both layouts hash the input key once (`key.hash(state)`) to find the bucket. The old layout then compares `hash == h` (free, it is in the bucket) *and* loads `values[group_index]`, a dependent random read that misses cache at high cardinality. The new layout compares `key.is_eq(stored_key)` against the entry it has already loaded. So on the probe path the new layout does strictly less work: the same single hash, minus one cache miss. Nothing is recomputed here. **Per resize (rare).** `hashbrown` rehashes every entry when the table doubles. Old: the hasher closure returns the stored `h`, free. New: `stored_key.hash(state)` per entry, an in-register ahash of a `u64`, roughly 1–2 ns. Summed over all doublings that is ~2n hashes, so at 10M groups on the order of 20M × 1.5 ns ≈ 30 ms across the whole build (estimate). It is also hidden: a rehash *moves* each entry to a random slot of the new table, which is a cache miss per entry (10–20 ns), and the hash arithmetic overlaps with that. On the probe side the same query does 40M rows, each saving a dependent miss: measured 16.2 → 11.5 ns/row, about 190 ms. **Storing the hash as well is measurably worse.** Standalone probe benchmark, random `i64` keys, 10M groups, ns/row including the table build: | entry | size | ns/row | |---|---|---| | `(group_index, hash)` + `values[group_index]` compare (before) | 16 B | 16.2 | | `(group_index, hash, key)` — key in entry *and* stored hash | 24 B | 12.8 | | `(group_index, key)` — hash recomputed on resize (this PR) | 16 B | **11.5** | The wider entry costs more in cache misses on every probe than the recomputation costs on every resize. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
