neoremind commented on issue #16574: URL: https://github.com/apache/lucene/issues/16574#issuecomment-5529170155
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](https://neoremind.com/report/lucene/I-16574/bench-index-baseline_vs_patch-wikimedium5m.fork_lucene.candidate.tv.Lucene104.nd5M.html), 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](https://neoremind.com/report/lucene/I-16574/perf-wikipedia-10runs.md). 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. <details> <summary>JMH benchmark perf of light workload</summary> ``` === 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% ``` </details> ### 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 https://github.com/apache/lucene/issues/11608#issuecomment-5267614934: improvements should better not come with problems with other configurations. Would like thoughts from folks on how to weigh the trade-off. -- 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]
