perfloop-agent opened a new pull request, #4919:
URL: https://github.com/apache/cassandra/pull/4919
Optimize RangeTombstoneList copying with copy-on-write array sharing
(CASSANDRA-21492)
### Description
Each memtable write carrying a range tombstone runs
`BTreePartitionUpdater.merge` -> existing `DeletionInfo.mutableCopy()` ->
`RangeTombstoneList.copy`, which unconditionally copies all four parallel
arrays (starts, ends, markedAts, and delTimesUnsignedIntegers) of the existing
list regardless of insert position.
Here, the variable `N` represents the number of range tombstones in the
`RangeTombstoneList`. Under modeled production workloads, `N` typically ranges
from small lists of size `N ~ 10` (for small partitions with light deletion
traffic) to large lists of size `N >= 1000` (under heavy range-delete or
partition-level tombstone-heavy workloads). Successive range-tombstone merges
into one unflushed partition pay O(N^2) parallel array copying work on the
mutation write path because unmutated lists are repeatedly re-copied.
Duplicating these parallel arrays is highly expensive at scale due to array
allocation and element-by-element copy overheads.
This optimization implements copy-on-write array sharing (starts, ends,
markedAts, and delTimesUnsignedIntegers backing arrays) between copies,
reducing unmutated copying to an O(1) pointer-sharing operation. This
optimization introduces no behavior changes and preserves full copy
independence under all mutating operations.
**Limits of the Mechanism**:
Because this is a copy-on-write mechanism, any subsequent mutation on a
shared list forces an O(N) isolation copy (via `isolate()`) before the write
occurs. This means that if mutations are performed immediately after copying,
the parallel array copying cost is deferred rather than eliminated. However, in
workloads where RangeTombstoneLists are copied but not subsequently mutated,
the copying cost is entirely eliminated.
### Headline Win (benchCopyOnly)
- **Primary Win**: `RangeTombstoneListBench.benchCopyOnly` drops from
`3362.5156478614854` ns/op to `9.018492886907715` ns/op (a **99.7318%**
reduction in copying latency, n=10, p=1.08251e-05).
### Guardrails (Categorized as Held)
- `RangeTombstoneListBench.benchCopyAndAdd` (size N=1000):
`8842.89307604306` ns/op -> `5485.592293470344` ns/op (**Held**, a **37.9661%**
reduction, n=10, p=1.08251e-05)
- `RangeTombstoneListSize10Bench.benchCopyOnly` (size N=10):
`56.7137252431266` ns/op -> `9.083180562797722` ns/op (**Held**, an
**83.9842%** reduction, n=10, p=1.08251e-05)
- `RangeTombstoneListSize10Bench.benchCopyAndAdd` (size N=10):
`186.2202636628365` ns/op -> `122.92588844176737` ns/op (**Held**, a
**33.989%** reduction, n=10, p=1.08251e-05)
### Co-measured Ground-Truth Comparison
Measurements are co-measured. The baseline was measured at baseline commit
tree with the benchmarks compiled in.
- **Baseline Commit**: `061749b0ae48d5b3be1f78754f177bdd745c7a1e`
- **Candidate Commit**: `ca5e7e41597ff05a09028d2e0f382df62db4620d` (shipped
commit `ca5e7e41`)
- **Benchmark Provenance**: Microbenchmarks authored by the agent.
| Benchmark Selector | Metric | Baseline (Median) | Shipped Commit
`ca5e7e41` (Median) | Delta (Median) | Outcome |
| :--- | :--- | :--- | :--- | :--- | :--- |
| `RangeTombstoneListBench.benchCopyOnly` | ns/op | 3362.5156478614854 |
9.018492886907715 | -99.7318% | Won |
| `RangeTombstoneListBench.benchCopyAndAdd` | ns/op | 8842.89307604306 |
5485.592293470344 | -37.9661% | Held |
| `RangeTombstoneListSize10Bench.benchCopyOnly` | ns/op | 56.7137252431266 |
9.083180562797722 | -83.9842% | Held |
| `RangeTombstoneListSize10Bench.benchCopyAndAdd` | ns/op |
186.2202636628365 | 122.92588844176737 | -33.989% | Held |
### Correctness Verification
The following correctness checks and suites passed completely:
- `pairing`, `environment_consistent`, `baseline_valid`, `benchmark_passed`,
`RangeTombstoneListTest` (verifies full copy independence under mutations),
`StyleCheck`, `measurements_sane`, `metric_present`, `sample_sufficiency`,
`sample_independence`.
### Reproduction
- **Environment**: linux/amd64/openjdk-21.0.11
- **Baseline Commit**: `061749b0ae48d5b3be1f78754f177bdd745c7a1e`
- **Candidate Commit**: `ca5e7e41597ff05a09028d2e0f382df62db4620d` (shipped
commit `ca5e7e41`)
- **Compilation Command**:
```bash
ant -lib
/workspace/deps/m2/org/apache/ant/ant-junit/1.10.12/ant-junit-1.10.12.jar
-Dno-build-accord=true -Dmaven.repo.local=/workspace/deps/m2
-Dlocal.repository=/workspace/deps/m2 build-test
```
- **Run Command**:
```bash
java -Dcassandra.config=file://$(pwd)/test/conf/cassandra.yaml -cp
"build/classes/main:build/test/classes:build/lib/jars/*:build/test/lib/jars/*:lib/*"
org.openjdk.jmh.Main -f 1 -wi 3 -w 1s -i 1 -r 1s -bm avgt -tu ns -foe true -rf
json -rff jmh.json -p size=1000
"^org\.apache\.cassandra\.test\.microbench\.RangeTombstoneListBench\.benchCopyOnly$"
```
### Full Proof
- **Case Page Link**: https://app.perfloop.ai/t/oss/case_w33wfzba46
---
This is an automated, human-reviewed Perfloop contribution opened by
perfloop-agent. The body links to reproducible proof for the change. The change
was benchmarked on perfloop/cassandra, an automation fork of apache/cassandra;
the commit on this PR's head branch carries the proof.
Assisted-by: PerfloopAgent:gemini-3.5-flash
--
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]
