salvatorecampagna opened a new pull request, #16282: URL: https://github.com/apache/lucene/pull/16282
## TL;DR Make `FixedBitSet.copyOf()` 135x to 193x faster for `DenseLiveDocs` and 11x to 48x faster for `SparseLiveDocs`. ## Summary `FixedBitSet.copyOf(Bits)` has fast paths for `FixedBitSet` and `FixedBits` but not for `SparseLiveDocs` and `DenseLiveDocs`, the two `LiveDocs` types introduced in #15413. Both fall through to the generic O(maxDoc) per-bit loop. The hot caller is `PendingDeletes.getMutableBits()`, which invokes `FixedBitSet.copyOf(liveDocs)` on the first delete after a reader snapshot. Under write-heavy workloads this cost accumulates across open reader generations. Each type now exposes a package-private `toFixedBitSet()` method that `FixedBitSet.copyOf()` delegates to, keeping the copy logic next to the data it knows about. `DenseLiveDocs` stores live docs in a `FixedBitSet` with identical semantics, so `toFixedBitSet()` clones it at O(maxDoc/64). `SparseLiveDocs` stores deleted positions in a `SparseFixedBitSet`, so `toFixedBitSet()` allocates the backing `long[]` prefilled with `-1L` (all live), masks off the ghost bits in the last word to satisfy `FixedBitSet` invariants, then clears only the deleted positions via `nextSetBit` at O(maxDoc/64 + deletedDocs). ## Benchmarks `LiveDocsCopyOfBenchmark` — `FixedBitSet.copyOf()` average time (µs/op), `-wi 5 -i 7 -f 3`. Baseline = `main` HEAD; contender = this PR. ### DenseLiveDocs | maxDoc | del rate | baseline (µs) | err% | contender (µs) | err% | speedup | |-------:|:--------:|--------------:|-----:|---------------:|-----:|--------:| | 1M | 0.1% | 317.838 ± 5.686 | 1.8% | 2.362 ± 0.039 | 1.7% | **135x** | | 10M | 0.1% | 3166.801 ± 91.964 | 2.9% | 20.797 ± 1.160 | 5.6% | **152x** | | 100M | 0.1% | 31434.474 ± 234.936 | 0.7% | 198.186 ± 11.443 | 5.8% | **159x** | | 1M | 1% | 371.669 ± 6.345 | 1.7% | 2.302 ± 0.054 | 2.3% | **162x** | | 10M | 1% | 3766.590 ± 35.200 | 0.9% | 19.476 ± 0.684 | 3.5% | **193x** | | 100M | 1% | 37788.094 ± 191.936 | 0.5% | 203.131 ± 10.855 | 5.3% | **186x** | ### SparseLiveDocs | maxDoc | del rate | baseline (µs) | err% | contender (µs) | err% | speedup | |-------:|:--------:|--------------:|-----:|---------------:|-----:|--------:| | 1M | 0.1% | 518.084 ± 6.739 | 1.3% | 10.900 ± 0.096 | 0.9% | **48x** | | 10M | 0.1% | 4976.429 ± 55.761 | 1.1% | 111.454 ± 1.495 | 1.3% | **45x** | | 100M | 0.1% | 49412.733 ± 424.527 | 0.9% | 1152.935 ± 12.952 | 1.1% | **43x** | | 1M | 1% | 1201.822 ± 43.661 | 3.6% | 97.187 ± 1.349 | 1.4% | **12x** | | 10M | 1% | 12062.162 ± 146.840 | 1.2% | 986.402 ± 14.975 | 1.5% | **12x** | | 100M | 1% | 119511.553 ± 688.099 | 0.6% | 10884.173 ± 159.084 | 1.5% | **11x** | The `SparseLiveDocs` speedup shrinks as the deletion rate grows: the contender always pays O(maxDoc/64) to fill the backing array, and on top of that clears one position per deleted document. At low deletion rates the fill dominates and the gap with the O(maxDoc) baseline is large; at higher rates the clearing loop contributes more and the advantage narrows. -- 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]
