Separate term bytes pool from postings pool in TermsHash

[neoremind]

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, the termBytePool has been pointed to the same object as bytePool:

// 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) 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. 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 #11608 (comment). 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.

Luceneutil indexing configuration details

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,
  )

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

• Candidate

Baseline | Candidate

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

• Candidate

Baseline | Candidate

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

• Candidate

Baseline | Candidate

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%)

Commands used for the above analysis

jfr print --events jdk.CPUTimeSample --json "/Users/xuzh/Documents/lucene-log/separate-two-bytes-ref-pool/thread1/no-facet
/bench-index-baseline_vs_patch-wikimediumall.fork_lucene.candidate.Lucene104.nd33.3326M.jfr" > temp_fork.json

python3 << 'EOF'
import json
d=json.load(open('temp_fork.json'))
events=d['recording']['events']
count=0
for e in events:
    for f in e['values']['stackTrace']['frames']:
        if 'findHash' in f['method']['name'] and 'BytesRefHash' in f['method']['type']['name']:
            count+=1
            break
print(f"findHash inclusive: {count}/{len(events)} = {100*count/len(events):.2f}%")
EOF


python3 << 'EOF'
import json
d=json.load(open('temp_fork.json'))
events=d['recording']['events']
count=0
for e in events:
    for f in e['values']['stackTrace']['frames']:
        if 'positionStreamSlice' in f['method']['name'] and 'TermsHashPerField' in f['method']['type']['name']:
            count+=1
            break
print(f"TermsHashPerField.positionStreamSlice inclusive: {count}/{len(events)} = {100*count/len(events):.2f}%")
EOF


python3 << 'EOF'
import json
d=json.load(open('temp_fork.json'))
events=d['recording']['events']
count=0
for e in events:
    for f in e['values']['stackTrace']['frames']:
        if 'buildHistogram' in f['method']['name']:
            count+=1
            break
print(f"buildHistogram inclusive: {count}/{len(events)} = {100*count/len(events):.2f}%")
EOF

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 #16371 (comment) 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.

[rmuir]

The change where I said that was based upon past experiences particular to that change.

I agree the indexer (in real benchmark), is probably sensitive here. Maybe the indexing can be run with perf stat -ddd? You can then look at cache misses and so on. I think by default they are samples, but it's easier than measuring wall and more specific to what you're after

[neoremind]

Hi Robert, thank you for taking a look, just wanted to borrow the spirit from you :) I planed to do perf stat -e xx to check the L1, L3 and TLB cache miss to double confirm, but it turned out perf is not working for non-metal EC2 instances due to Nitro, so I skipped this, I don't have a metal on hand now, but I will attempt to give it a try to vet.

[mikemccand]

I like this idea! The expected and actual (in full enwiki luceneutil benchmarks) gains are due to locality of terms-heavy work (finding or adding a term during inversion, sorting for flush)? The byte[] block allocator is still shared between the two, right? It's just that in each block we would write only terms' UTF-8 bytes, or only postings, never mixing.

Thank you for the deep analysis / benchmarking / flame charts dev eye candy!

You might see even more gains if you turn on term vectors (<-- very confusingly named (long ago) Lucene feature!), which is a baby inverted index per document that is also looking up terms and assigning ordinals via document-private-and-reused TermsHash I think.

[neoremind]

Sorry for the late response, I ran benchmarks extensively, share the results.

First, to @mikemccand 's question

The expected and actual (in full enwiki luceneutil benchmarks) gains are due to locality of terms-heavy work (finding or adding a term during inversion, sorting for flush)? The byte[] block allocator is still shared between the two, right? It's just that in each block we would write only terms' UTF-8 bytes, or only postings, never mixing.

Exactly, the two pools share the same ByteBlockPool.Allocator. I ran wikipedia 5M docs with -tvs (term vectors + pos + offsets upon body field), it is 5,621.8 docs/s (baseline) vs. 5,725.0 docs/s (candidate), +1.8%, no regression with term vectors enabled but the gain is not that big, TermVectorsConsumerPerField.finishDocument takes ~11% of CPU in the flamegraph, the tv sort is only ~4%, and CPU is still dominated by inverting the body field.

1. End-to-end Wikipedia indexing with perf

Since EC2 non-metal doesn't support perf, I ran on Alibaba Cloud ecs.c9i.4xlarge (16 vCPU, 32G RAM, Intel Xeon 6982P-C, note it has 384K L1d and a larger 16MB L2 / 504MB L3 compared with EC2 c5.4xlarge).

10 runs each for baseline and candidate, average the numbers. The work is fixed 33.3M docs, so same amount of work, this is apples-to-apples comparison.

metric                                                         baseline             candidate     delta
docs/sec           (higher better)                               19,387                19,870    +2.49%
GB/hour            (higher better)                               61.522                63.054    +2.49%
indexing time (s)                                                 1,727                 1,685    -2.43%
cycles                                                6,765,903,927,133     6,620,475,201,879    -2.15%
instructions                                         18,591,609,777,819    18,554,900,017,263    -0.20%
L1-dcache-loads                                       5,510,389,329,948     5,475,077,968,974    -0.64%
L1-dcache-load-misses                                    83,655,672,024        81,184,905,840    -2.95%
cache-references                                         39,439,016,147        37,052,003,826    -6.05%
cache-misses                                             15,026,052,690        12,976,203,435   -13.64%
branch-misses                                            32,325,424,554        32,321,949,549    -0.01%
dTLB-load-misses                                            873,810,938           794,619,567    -9.06%
insn per cycle                                                    2.756                 2.811    +2.00%
L1-dcache-load-misses % of all L1-dcache accesses                 1.518                 1.483    -2.32%
cache-misses % of all cache refs                                 37.936                34.895    -8.02%

Find raw results here.

The instruction count is unchanged, −0.2% across 18.6 trillion instructions, the performance gain comes from less cycles, better cache locality, less memory stall and higher IPC, −2.15% cycles, +2% IPC, and notably −13.64% LLC misses and −9.06% dTLB-load-misses. With denser term bytes pool, fewer cache lines need to stay hot during lookups and the sort phase, this matches my original analysis.

2. Scaled-up micro JMH (new since last time)

Original JMH (aka light workload):

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%

Scaled up JMH (run time 5s -> 10s, vocab size 256k -> 2M, total num of tokens 2M -> 16M run on c5.4xlarge):

Benchmark	Skew	Baseline (ns/op)	Candidate (ns/op)	Delta
indexSegment	1.0	678.7	711.6	+4.8%
indexSegment	3.0	651.7	666.8	+2.3%
indexSegment	6.0	518.4	517.3	−0.2%
indexSegment	UUID	442.4	444.8	+0.5%
indexSegmentAndSort	1.0	717.6	750.7	+4.6%
indexSegmentAndSort	3.0	680.9	713.9	+4.8%
indexSegmentAndSort	6.0	557.2	555.2	−0.4%
indexSegmentAndSort	UUID	1016.3	940.7	−7.4%

Separation is bad for low-frequency terms (skew=1.0 ~= uniform, skew=3.0), and gets worse with scale. In the shared pool, adding a new term writes byte[pool index][bytes] at the pool frontier and then allocates the first 5-byte postings slice immediately after. So for a term's posting fits in the first slice (which is what happens for low-frequency terms, terms stay in the first slice, growing into chained slices slowly or never), one cache line serves both the terms comparison and the postings write, co-location is better. Plus there are also two write byte[pool index] to keep hot in CPU cache instead of just one, should be small impact.

The wikipedia-text-like frequent seen terms case (skew=6.0), regression is gone compared with light workload, my read is once lookups actually miss cache, the denser term-byte pool during two terms comparison compensates for the loss of co-location of terms and postings. And for frequent terms there was no co-location to lose as well because the postings should grow out of the first slice and reside elsewhere in the pool anyway.

UUID stays neutral for add-only, and add+sort wins more.

All use case benefit from denser terms during sort, this is for sure.

I re-ran light workload micro JMH with perf on on ecs.c9i.4xlarge again, the better cache locality, the better results, we can check the perf result below, the better result comes from higher IPC and less cache miss as well.

JMH benchmark perf of light workload

=== indexSegment skew=6.0   baseline n=10, candidate n=10 ===
metric                                                         baseline             candidate     delta
score (ns/op)                                                   103.142               104.111    +0.94%
cycles                                                  539,434,567,680       540,045,569,100    +0.11%
instructions                                            769,266,504,619       764,165,706,867    -0.66%
L1-dcache-loads                                         221,565,144,658       220,440,593,073    -0.51%
L1-dcache-load-misses                                    10,582,990,714        10,777,176,254    +1.83%
cache-references                                         11,169,562,769        11,353,917,436    +1.65%
cache-misses                                              1,186,079,489         1,158,510,297    -2.32%
branch-misses                                             3,569,840,826         3,531,362,193    -1.08%
dTLB-load-misses                                              7,542,230             7,386,600    -2.06%
insn per cycle                                                    1.426                 1.415    -0.77%
L1-dcache-load-misses % of all L1-dcache accesses                 0.048                 0.049    +2.34%
cache-misses % of all cache refs                                  0.106                 0.102    -3.88%

=== indexSegment skew=UUID   baseline n=10, candidate n=10 ===
metric                                                         baseline             candidate     delta
score (ns/op)                                                   160.434               159.469    -0.60%
cycles                                                  560,302,054,118       563,971,547,157    +0.65%
instructions                                            793,348,202,847       807,634,079,963    +1.80%
L1-dcache-loads                                         178,825,446,700       183,525,758,314    +2.63%
L1-dcache-load-misses                                     3,754,396,240         3,824,056,264    +1.86%
cache-references                                         15,054,041,303        15,059,350,274    +0.04%
cache-misses                                              3,138,923,252         3,151,730,898    +0.41%
branch-misses                                             1,033,258,881         1,045,266,963    +1.16%
dTLB-load-misses                                              3,817,774             3,865,767    +1.26%
insn per cycle                                                    1.416                 1.432    +1.14%
L1-dcache-load-misses % of all L1-dcache accesses                 0.021                 0.021    -0.74%
cache-misses % of all cache refs                                  0.209                 0.209    +0.37%

=== indexSegmentAndSort skew=6.0   baseline n=10, candidate n=10 ===
metric                                                         baseline             candidate     delta
score (ns/op)                                                   108.662               110.263    +1.47%
cycles                                                  543,912,988,725       547,410,725,177    +0.64%
instructions                                            807,646,658,594       801,016,376,979    -0.82%
L1-dcache-loads                                         230,798,601,366       228,660,312,822    -0.93%
L1-dcache-load-misses                                    10,754,623,517        10,857,199,332    +0.95%
cache-references                                         11,084,030,962        11,086,027,209    +0.02%
cache-misses                                              1,151,450,478         1,150,687,133    -0.07%
branch-misses                                             3,573,909,434         3,543,303,910    -0.86%
dTLB-load-misses                                              8,037,174             8,196,482    +1.98%
insn per cycle                                                    1.485                 1.463    -1.46%
L1-dcache-load-misses % of all L1-dcache accesses                 0.047                 0.047    +1.93%
cache-misses % of all cache refs                                  0.104                 0.104    -0.09%

=== indexSegmentAndSort skew=UUID   baseline n=10, candidate n=10 ===
metric                                                         baseline             candidate     delta
score (ns/op)                                                   294.088               289.587    -1.53%
cycles                                                  552,365,367,573       554,017,542,436    +0.30%
instructions                                            992,518,226,109     1,011,384,883,214    +1.90%
L1-dcache-loads                                         263,743,347,493       268,976,052,733    +1.98%
L1-dcache-load-misses                                     5,161,702,956         5,070,236,433    -1.77%
cache-references                                         13,560,882,588        13,359,187,708    -1.49%
cache-misses                                              1,976,000,840         1,936,634,950    -1.99%
branch-misses                                             1,588,225,916         1,615,830,908    +1.74%
dTLB-load-misses                                              4,241,660             4,270,986    +0.69%
insn per cycle                                                    1.797                 1.825    +1.59%
L1-dcache-load-misses % of all L1-dcache accesses                 0.020                 0.019    -3.68%
cache-misses % of all cache refs                                  0.146                 0.145    -0.51%

3. My take

I think my above "Why end-to-end wins but the microbenchmark doesn't" analysis still stands.

But, I am a bit hesitant about making the separation, because it looks not a one-size-fits-all change. It helps when there's a large term-byte region that gets worked repeatedly like findHash lookups once the working set exceeds cache, and the radix sort before flush, this is typical wikipedia-like frequent-term text or UUID-heavy workloads (if we disable body in wikipedia benchmark, title, id, date are almost unique). But it does introduce a small cost for rare, low-frequency terms, where we lose the co-location of term bytes and the first postings slice. As I and @uschindler discussed in #11608 (comment): improvements should better not come with problems with other configurations. Would like thoughts from folks on how to weigh the trade-off.