neoremind opened a new issue, #16574: URL: https://github.com/apache/lucene/issues/16574
### Description ## Background I am looking at the `ByteBlockPool` sharing design in `TermsHash` (related to #11608). Today, `TermsHash` uses a single shared `ByteBlockPool` to store both term bytes (used by `BytesRefHash`) and terms' postings data (doc ID deltas, freqs, pos, offsets, payloads). 16 years ago, in the initial [commit](https://github.com/apache/lucene/commit/42b9f0caa32ff71782a949264d033a346ede7b26#diff-22ab6c31dc6317827019d7c86faa08fc826efe921188da71743bc3b884d058ee), the `termBytePool` has been pointed to the same object as `bytePool`: ```java // In TermsHash constructor if (nextTermsHash != null) { termBytePool = bytePool; // reuse the same pool here nextTermsHash.termBytePool = bytePool; } ``` This means term bytes and their respective postings slices are interleaved in the same byte pool. I drew a diagram to illustrate:  ## The Change and Benchmark Separating the two pools is simple (see my [commit](https://github.com/apache/lucene/commit/8138180422371fe9f24b6171985de749aa4d2543)) with just a few lines of code. I ran both micro and end-to-end benchmarks to vet. All benchmarks run on EC2 c5.4xlarge (16 vCPU, 32G RAM), OpenJDK 25.0.2. ### JMH Microbenchmark I wrote a JMH benchmark that runs `TermsHashPerField.add()` in a tight loop for a single field, see the benchmark [here](https://github.com/apache/lucene/commit/58c86c4326d36482fc0fcc37a639b4ce6c0466fe). It uses 256k vocab size, 2M token stream with different Zipfian-ish skew configs, and a UUID unique workload, 1k tokens per doc. The Zipfian-ish skew way simulates the frequent seen terms in real workloads as I observed in https://github.com/apache/lucene/issues/11608#issuecomment-5265355538. Two microbenchmarks: `indexSegment` (add only) and `indexSegmentAndSort` (add + radix sort, mimic the in-memory accumulation phase before segment flush). To mitigate noise, I use below JMH config and run multiple times to average: ``` # Warmup: 3 iterations, 3 s each # Measurement: 5 iterations, 3 s each # Fork: 5 # JVM args: -Xmx12g -Xms12g -XX:+AlwaysPreTouch # Params: shortRatio=0.75, tokensPerDoc=1000 ``` - Thread 1 (10 runs averaged) | Benchmark | Skew | Baseline (ns/op) | Candidate (ns/op) | Delta | |---|---|---|---|---| | indexSegment | 1.0 | 259.5 | 265.3 | +2.2% | | indexSegment | 3.0 | 230.2 | 235.6 | +2.3% | | indexSegment | 6.0 | 193.8 | 199.2 | +2.8% | | indexSegment | UUID | 315.6 | 315.3 | −0.1% | | indexSegmentAndSort | 1.0 | 269.1 | 274.0 | +1.8% | | indexSegmentAndSort | 3.0 | 243.1 | 245.9 | +1.1% | | indexSegmentAndSort | 6.0 | 197.6 | 202.3 | +2.4% | | indexSegmentAndSort | UUID | 620.8 | 601.1 | **−3.2%** | - Thread 4 (5 runs averaged) | Benchmark | Skew | Baseline (ns/op) | Candidate (ns/op) | Delta | |---|---|---|---|---| | indexSegment | 1.0 | 430.2 | 452.6 | +5.2% | | indexSegment | 3.0 | 355.2 | 366.9 | +3.3% | | indexSegment | 6.0 | 249.5 | 258.2 | +3.5% | | indexSegment | UUID | 375.5 | 372.3 | −0.9% | | indexSegmentAndSort | 1.0 | 442.0 | 462.9 | +4.7% | | indexSegmentAndSort | 3.0 | 370.0 | 376.5 | +1.8% | | indexSegmentAndSort | 6.0 | 261.6 | 269.6 | +3.1% | | indexSegmentAndSort | UUID | 703.9 | 686.3 | **−2.5%** | The JMH shows **no improvement or even slight regression** for typical workloads. My read is that by separating pools, we introduce an extra indirection to locate posting slices in a different pool. The benchmark is genuinely **CPU-bound** in a tight single-field loop, the Zipfian-ish skew term-bytes total working set is ~8 MB fitting in L3 cache with no memory pressure or thrashing. For UUID (97 MB term bytes, exceeds L3), the sort phase benefits most because term bytes are densely packed without posting interleaving, better spatial locality for the radix sort. ### End-to-End luceneutil Wikipedia benchmark This is a totally different story. I ran full 33M Wikipedia documents, no in-flight merge, `ramBufferMB=2G` to allow purely flushing segments one by one, about ~5.6M unique terms per segment, ~550M+ total `add()` calls per segment. <details> <summary>Luceneutil indexing configuration details</summary> ```python index = comp.newIndex( args.baseline, sourceData, postingsFormat="Lucene104", idFieldPostingsFormat="Lucene104", directory="MMapDirectory", ramBufferMB=2048, waitForMerges=False, waitForCommit=False, grouping=False, verbose=False, mergePolicy="NoMergePolicy", useCMS=False, ) ``` </details> #### Thread 1 (10 runs) | Metric | Baseline | Candidate | Delta | |---|---|---|---| | docs/sec (mean) | 11,513.9 | 11,749.4 | **+2.05%** | | docs/sec (median) | 11,499.4 | 11,710.5 | +1.83% | | GB/hour (mean) | 36.539 | 37.286 | **+2.04%** | Due to Amdahl's law, the change only targets `sortTerms` in the flush phase and `findHash` which together consumes <20% of total CPU, so the absolute improvement is small. But it is consistent, the best baseline run (11,614 docs/sec) is still slower than the candidate's worst (11,672 docs/sec). Flamegraph: - Baseline <img width="1420" height="647" alt="Image" src="https://github.com/user-attachments/assets/92c7c2b7-a7d0-47b1-a1d5-128f1ea0a904"; /> - Candidate <img width="1419" height="633" alt="Image" src="https://github.com/user-attachments/assets/25062d69-8484-464d-beeb-b4b817e65754"; /> [Baseline](https://neoremind.com/report/log/lucene/TermHash/flamegraph/thread-1/bench-index-baseline_vs_patch-wikimediumall.lucene.Lucene104.nd33.3326M.html) | [Candidate](https://neoremind.com/report/log/lucene/TermHash/flamegraph/thread-1/bench-index-baseline_vs_patch-wikimediumall.fork_lucene.candidate.Lucene104.nd33.3326M.html) If zooming into the flamegraph, `sortTerms` and `findHash` shrinked in the candidate. #### Thread 8 (10 runs) | Metric | Baseline | Candidate | Delta | |---|---|---|------------| | docs/sec (mean) | 74,583.2 | 76,336.4 | **+2.35%** | | docs/sec (median) | 75,902.5 | 76,343.4 | +0.58% | | GB/hour (mean) | 234.061 | 239.710 | **+2.41%** | For multi-threaded cases, there are more variance here, throughput ranges overlap between runs, but the candidate's overall numbers still win. Flamegraph: - Baseline <img width="1419" height="630" alt="Image" src="https://github.com/user-attachments/assets/343c3bac-1b88-43e4-bf8d-00f6f1358921"; /> - Candidate <img width="1419" height="651" alt="Image" src="https://github.com/user-attachments/assets/89e4652a-4194-4f38-8ef2-f698f79d5f99"; /> [Baseline](https://neoremind.com/report/log/lucene/TermHash/flamegraph/thread-8/bench-index-baseline_vs_patch-wikimediumall.lucene.Lucene104.nd33.3326M.html) | [Candidate](https://neoremind.com/report/log/lucene/TermHash/flamegraph/thread-8/bench-index-baseline_vs_patch-wikimediumall.fork_lucene.candidate.Lucene104.nd33.3326M.html) #### Thread 1 w/ body field disabled (10 runs) To isolate the heavy full-text indexing, I disabled the body text field, use only mono-incremental IDs, title, date, and numeric fields. Without the heavy inverted-index workload, the result is neutral, no regression and slightly better: | Metric | Baseline | Candidate | Delta | |---|---|---|---| | docs/sec (mean) | 148,345.6 | 149,069.7 | +0.49% | | docs/sec (median) | 148,418.3 | 149,328.0 | +0.61% | | GB/hour (mean) | 470.566 | 472.911 | +0.50% | Flamegraph: - Baseline <img width="1422" height="596" alt="Image" src="https://github.com/user-attachments/assets/518adc97-6c4a-4356-a008-1e355ee77f60"; /> - Candidate <img width="1419" height="638" alt="Image" src="https://github.com/user-attachments/assets/b2e65757-f2a0-4e41-afb7-c4e27fa65b77"; /> [Baseline](https://neoremind.com/report/log/lucene/TermHash/flamegraph/thread-1-disable-body/bench-index-baseline_vs_patch-wikimediumall.lucene.Lucene104.nd33.3326M.html) | [Candidate](https://neoremind.com/report/log/lucene/TermHash/flamegraph/thread-1-disable-body/bench-index-baseline_vs_patch-wikimediumall.fork_lucene.candidate.Lucene104.nd33.3326M.html) #### JFR analysis Thread 1: total CPU samples 290,263 (baseline) -> 284,515 (candidate), −2.0%: | Method | Baseline | Candidate | Delta | |---|---|---|---| | `BytesRefHash.findHash` | 43844 / 290263 = 15.10% | 40217 / 284515 = 14.14% | -3627 | | `TermsHashPerField.positionStreamSlice` | 47500 / 290263 = 16.36% | 47771 / 284515 = 16.79% | +271 | | `BytesRefHash.buildHistogram` | 4603 / 290263 = 1.59% | 2504 / 284515 = 0.88% | -2099 (relatively -45.6%) | Thread 8: total CPU samples 346,346 (baseline) -> 330,370 (candidate), −4.6%: | Method | Baseline | Candidate | Delta | |---|---|---|---| | `BytesRefHash.findHash` | 45939 / 346346 = 13.26% | 43304 / 330370 = 13.11% | -2635 | | `TermsHashPerField.positionStreamSlice` | 63528 / 346346 = 18.34% | 64041 / 330370 = 19.38% | +513 | | `BytesRefHash.buildHistogram` | 5321 / 346346 = 1.54% | 3015 / 330370 = 0.91% | -2306 (relatively -43.3%) | The JFR confirms that the speedup comes from `findHash` and the sort phase where term bytes are now denser, while the expected overhead shows up a minor increase in `positionStreamSlice` because the postings write path now has an extra pool indirection. ## Why end-to-end wins but the microbenchmark doesn't My 2 cents: 1. **Inter-doc and intra-doc (inter-field) cache pollution.**: Though both benchmarks hit the same code path, the workload is different. In real indexing, `IndexingChain` processes each doc with multiple consumers including inverted index, stored fields, or dv, points/BKD, and between each doc there are pre/post-processing as well. Each phase touches different memory regions. By the time we finish doc N's stored fields or dv and come back to process doc N+1's text field, the CPU cache lines holding term bytes may have been evicted. Separating provides better spatial and temporal locality. 2. **Denser cache lines for frequent-term lookups.**: Luceneutil Wikipedia is biased towards frequently-seen terms, the vast majority of add() calls are lookups of already-existing terms (>98%), 56.4% of all seen-term lookups are <=5 bytes. With the shared pool, when `BytesRefHash.equals()` reloads a cache line to compare term bytes, that cache line also carries unnecessary interleaving postings, it is burden. With a separated pool, pure term bytes per cache line, increasing the chance of cache line reuse in L1–L3 across lookups. 3. **The sort phase is the most significant contributor**: −45% samples in `buildHistogram`. The radix sort walks term bytes multiple times. With a dense term-only pool, it is better. 4. The UUID microbenchmark case (all unique) is neutral, an disabling the body field in end-to-end is also neutral, so without heavy inverted-index work, there is not much term-hash cache pressure to optimize and UUID benefits most from denser terms sort. ## Asks and guidance required I remember @rmuir once expressed in https://github.com/apache/lucene/pull/16371#issuecomment-5053592144 that "It might look good in a microbenchmark but not in an overall indexer run.". My findings are the opposite, the microbenchmark shows no gain (or slight cost from the extra indirection), but the end-to-end indexer run shows a consistent improvement or no regression. So I'd like to seek guidance from experts and folks who are familiar with this area to help justify whether such separation is worth shipping. Happy to discuss. -- 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]
