neoremind commented on issue #11608: URL: https://github.com/apache/lucene/issues/11608#issuecomment-5265355538
Happy to jump into this thread, I landed here while working on #16499 (a small BytesRefHash cleanup), and @dweiss points to #6916. I've spent some time on `BytesRefHash` performance during indexing as well, and I'd like to share my findings and 2 cents. ## Profiling Indexing 1KB wikipedia docs, `BytesRefHash` is indeed one of the hottest areas as you folks discussed here. First, from latest https://benchmarks.mikemccandless.com/2026.07.30.18.07.05.html ``` PERCENT CPU SAMPLES STACK 3.52% 121874 org.apache.lucene.util.BytesRefHash#findHash():376 [Inlined code] at org.apache.lucene.util.BytesRefHash#add():334 [JIT compiled code] at org.apache.lucene.index.TermsHashPerField#add():195 [JIT compiled code] at org.apache.lucene.index.IndexingChain$PerField#invertTokenStream():2010 [JIT compiled code] at org.apache.lucene.index.IndexingChain$PerField#invert():1898 [Inlined code] at org.apache.lucene.index.IndexingChain#invertAndStore():1418 [JIT compiled code] at org.apache.lucene.index.IndexingChain#processField():1392 [Inlined code] at org.apache.lucene.index.IndexingChain#processDocument():654 [JIT compiled code] 2.67% 92563 org.apache.lucene.util.BytesRefBlockPool#equals():160 [Inlined code] at org.apache.lucene.util.BytesRefHash#findHash():382 [Inlined code] at org.apache.lucene.util.BytesRefHash#add():334 [JIT compiled code] at org.apache.lucene.index.TermsHashPerField#add():195 [JIT compiled code] at org.apache.lucene.index.IndexingChain$PerField#invertTokenStream():2010 [JIT compiled code] at org.apache.lucene.index.IndexingChain$PerField#invert():1898 [Inlined code] at org.apache.lucene.index.IndexingChain#invertAndStore():1418 [JIT compiled code] at org.apache.lucene.index.IndexingChain#processField():1392 [Inlined code] ``` Second, the JFR CPU samples break-down from nightly: https://blunders.io/jfr-demo/indexing-1kb-2026.08.02.19.08.44/cpu-samples-drill-down <img width="1420" height="530" alt="Image" src="https://github.com/user-attachments/assets/a275cc0e-3033-4d99-82df-d6ac56b8ded7"; /> Third, I also ran on my local machine (Linux EC2 m5.4xlarge) and see the similar picture: <img width="1428" height="399" alt="Image" src="https://github.com/user-attachments/assets/a950fc27-6dd7-41d4-beac-ef12bfdf184c"; /> [my local flamegraph](https://neoremind.com/report/lucene/PR-16499/bench-index-bench_medium-wikimediumall.lucene.baseline.Lucene104.nd33.3326M-2026.05.23.10.48.33-baseline.html) and [detailed log](https://neoremind.com/report/lucene/PR-16499/bench_medium.wikimediumall.lucene.baseline.Lucene104.nd33.3326M.log) They all tell the same story: during inverted index building, we need to store terms plus their accumulated posting data (doc IDs, freq/prox) in memory before flushing. `BytesRefHash` is where we look up `hash(byteSequence) → termID`. As we can see, `doHash` takes some portion (worth looking at `murmurhash3_x86_32` performance separately), but the bigger portion is `findHash` itself, and the bytes comparison `BytesRefBlockPool#equals()` takes ~45% within the `findHash` time. ## Numbers deep dive Before sharing my analysis, I'd like to show some numbers. I instrumented `BytesRefHash` during indexing, check [this lucene branch](https://github.com/neoremind/lucene/commit/a79d207c7bc73a9b39e60a793bd50c7602008216#diff-6db24de5cbf0d5599b418aa78fa55defe081ac7a6f31c946277ef7bbc8e0cf68R120). Given the nightly setup, we use 2GB as max RAM buffer. **Per-segment stats:** - Each segment accumulates ~2M docs - ~5.6M unique terms but ~550M+ total `add()` calls per segment - The vast majority of `add()` calls are lookups of already-existing terms (>98%), proving the hash table is hit-heavy, not insertion-heavy. The percentage of seen terms climbs rapidly during indexing, the hash fills early, then new insertions become rare: <img width="2371" height="449" alt="Image" src="https://github.com/user-attachments/assets/d21c5a96-4631-490a-b85e-0e870e0308fc"; /> *- Note the the vertical light lines are segment flushes* <img width="2082" height="732" alt="Image" src="https://github.com/user-attachments/assets/6f655a03-8185-42af-b16f-9765d0cc565d"; /> *- See per-segment flush metrics [here](https://neoremind.com/report/lucene/PR-16499/bytesrefhash_metrics_segments.csv)* **Term length distribution:** Most add/seen terms are short. 3 - 6 bytes dominate lookups and comparisons. Average seen-term UTF-8 length is 6.7 bytes. Note that the diagram is log-based, otherwise I cannot fit them properly. <img width="2084" height="732" alt="Image" src="https://github.com/user-attachments/assets/4cad177c-2a6a-4a7c-9aa1-ecdcaf5716cc"; /> Some specifics: - 31.7% of all seen-term lookups are for terms ≤3 bytes - 46.1% are ≤4 bytes - 56.4% are ≤5 bytes Top terms at a glance: <img width="1483" height="1110" alt="Image" src="https://github.com/user-attachments/assets/5e89ec3b-1812-48d5-89eb-7c05f6f34460"; /> Top terms CSV: https://neoremind.com/report/lucene/PR-16499/bytesrefhash_metrics_top_terms.csv The above numbers align with @uschindler's hypothesis from earlier discussions. ## My thoughts I also put together a diagram of how `BytesRefHash` works internally. It's a hash table lookup of `hash(byteSequence) → termID` like @dweiss pointed out in https://github.com/apache/lucene/issues/6916. With an indirection through the `bytesStart[]` array that stores the location offset in the byte pool where the actual term UTF-8 bytes live. To locate those bytes, whether for `get()` by termID or checking existence during `add()`, we hop in different arrays to locate to the term bytes where the leading 1 or 2 bytes encode the len. <img width="890" height="722" alt="Image" src="https://github.com/user-attachments/assets/e27171ef-ff32-497c-9551-75d5231e4ccb"; /> ### 1. This is indeed memory-bound I agree with @jpountz , this is a memory-bound operation. We hop and jump randomly in memory for each term add operation, most of the time deep into the byte pool for seen terms for wikipedia scenario, sometimes may cut by `ids[]` if this is new term. Zoom in the hot path, looking up an already-existing seen term, which happens >98% of the time, we need to jump through 4 indirections: `ids[]` -> `bytesStart[]` -> small `buffers[]` -> `ByteBlockPool` -> actual bytes in the pool. After several rounds of rehash and expansion, `ids[]` can grow to tens of MB (~5.6M unique terms per 2G RAM buffer x 4 byte = 22MB), exceeding L2 cache. In multi-threaded indexing, it can thrash L3 or even to main memory. Hot terms inserted early get spread across the entire `ids[]`, losing cache locality and increasing TLB misses. The `bytesStart[]` and byte pool might be slightly better as I think most frequently-seen terms sit toward the front as indexing them early like `the`, `a`, `and`. Here's the wikipedia 1K docs indexing JFR breakdown backing this: | JFR Line | Source | Samples | %CPU | Notes | |----------|--------|---------|------|------| | 376 | `int e = ids[hashPos];` | 18,753 | 4.6% | cache miss and memory stall | | 381 | `while (e != -1` | 9,479 | 2.3% | | | 375 | `int hashPos = code & hashMask;` | 421 | 0.1% | | | 382 | `&& ((e & highMask) != highBits \|\| pool.equals(...))` | 339 | 0.08% | While condition on highBits filter | | 385 | `e = ids[hashPos];` (inside loop) | 87 | 0.02% | Probe loop to the next slot, since this is in the same cache line, almost free) | | 384 | `hashPos = code & hashMask;` | 85 | 0.02% | | | 377 | `final int highBits = hashcode & highMask;` | 24 | 0.006% | | | 383 | `code++;` | 15 | 0.004% | | <details> <summary> Command used to generate this</summary> ``` jfr print --events jdk.CPUTimeSample --stack-depth 1 \ "baseline/bench-index-bench_medium-wikimediumall.lucene.baseline.Lucene104.nd33.3326M.jfr" \ | awk '/stackTrace = \[/{getline; gsub(/^ +/,""); c[$0]++} END{for(f in c) print c[f], f}' \ | grep "findHash" \ | sort -rn ``` </details> ### 2. Murmurhash and collisions are fine Instrument the add operation, see below results, I think hash algorithm it's fine. ``` === BytesRefHash Test Results === Running time: 21367ms Documents processed: 1000000 Total tokens: 143762851 Unique terms: 3468696 Duplicate tokens: 140294155 Duplicate ratio: 97.59% RAM used (hash including pool): 85.07 MB RAM used (pool): 39.78 MB === MyBytesRefHash Metrics === FIND_TOTAL : 143762851 FIND_NEW : 3468696 (2.41%) FIND_SEEN : 140294155 (97.59%) FIND_COLLIDED : 4397357 (3.06%) PROBE_LOOP_ITERATIONS : 14667441 avg probes/collided : 3.336 ``` <details> <summary>Code used</summary> ``` private int findHash(BytesRef bytes, int hashcode) { //assert bytesStart != null : "bytesStart is null - not initialized"; //assert hashcode == doHash(bytes.bytes, bytes.offset, bytes.length); int code = hashcode; // final position int hashPos = code & hashMask; int e = ids[hashPos]; final int highBits = hashcode & highMask; // Conflict; use linear probe to find an open slot // (see LUCENE-5604): boolean collided = false; while (e != -1 && ((e & highMask) != highBits || pool.equals(bytesStart[e & hashMask], bytes) == false)) { if (!collided) { collided = true; FIND_COLLIDED.increment(); } PROBE_LOOP_ITERATIONS.increment(); code++; hashPos = code & hashMask; e = ids[hashPos]; } FIND_TOTAL.increment(); if (e == -1) { FIND_NEW.increment(); } else { FIND_SEEN.increment(); } return hashPos; } ``` </details> Only 3.06% of lookups experience a collision. Most hit target on the first probe, either new term or a match (existing term with matching high bits and equals to the bytes in pool). If collision happens, average probes is 3.3, might not be bad (maybe swisstable worth trying), that means the hash function and load factor of no more than 50% taken up looks good. The highBits check (`(e & highMask) != highBits`) from #14720 short-circuits before calling `pool.equals()`, it's a cheap filter that does help. But I think the benchmark for #14720 was biased toward totally random new terms, so the benefit diminishes on wikipedia body indexing where collisions are rare. ### 3. The inline length encoding looks good Since this is already memory-bound, always using 2 bytes would increase memory footprint, not worth it. I think @jpountz mentioned that splitting into two pools (one for terms <128 or 256 bytes using 1-byte, one for longer terms) could be one potential option. But the byte pool is shared and leaked outside of `BytesRefHash`, so routing to the right pool would need careful holistic design. ### 4. Resizing is almost invisible The growth/rehash cost barely show in profilers. There's no need for a more aggressive growth strategy. ## More on the future To be honest, I've spent hard time working on some more improvements, but it turns out not a low-hanging fruit. **Inlining 3 bytes into `bytesStart`**: storing the first 3 bytes of the term inline to avoid the pool indirection for short terms. In theory this saves a memory hop for the majority case. In practice, it doesn't improve much as I did the wikipedia 1k bench, it didn't offset the dominant `ids[]` cache miss, and I guess the CPU can pipeline the `bytesStart` load in parallel thanks to instruction-level parallelism. Plus it introduces complexity around where to store bytes for `get()` without creating many short-lived transient allocations. **Increasing load factor to 0.75**: I can show it improves multi-threaded Wikipedia indexing by ~4% overall (I see as big improvement), but it's a tie for single-threaded, and on a micro-benchmark with monotonically-incremental-ID-ish workloads, the condensed `ids[]` increases probe chain length to degrade performance. I'm not yet confident to ship this... Some thoughts, 1) splitting into two pools for short and long terms, 2) separating the posting chain from the terms bytes pool, these looks promising. -- 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]
