Hi,
this is the second part of my patch series that aim to improve raw ref
iteration performance with the reftable backend. The target of this
series was to get the reftable backend performant enough to match the
files backend. This was achieved via two angles:
- Refactorings of the merged iterators that allow us to skip copying
and allocating records from the sub-iterators to the caller. This is
implemented by the first 8 patches.
- Refactorings of how we decode reftable records so that we reuse
allocated memory. Like this the number of allocations don't scale
with the number of iterated records anymore, but instead with the
number of blocks which we're iterating over.
Combined, these refactorings lead to a sizeable speedup when iterating
over 1 million refs:
```
Benchmark 1: show-ref: single matching ref (revision = HEAD~)
Time (mean ± σ): 146.1 ms ± 4.2 ms [User: 143.2 ms, System: 2.8 ms]
Range (min … max): 140.7 ms … 180.2 ms 1000 runs
Benchmark 2: show-ref: single matching ref (revision = HEAD)
Time (mean ± σ): 97.6 ms ± 3.2 ms [User: 94.8 ms, System: 2.7 ms]
Range (min … max): 94.6 ms … 122.1 ms 1000 runs
Summary
show-ref: single matching ref (revision = HEAD) ran
1.50 ± 0.07 times faster than show-ref: single matching ref (revision = HEAD~)
```
With this, the reftable backend is now on par with the files backend:
```
Benchmark 1: show-ref: single matching ref (refformat = files)
Time (mean ± σ): 97.8 ms ± 3.4 ms [User: 87.6 ms, System: 10.0 ms]
Range (min … max): 95.0 ms … 121.3 ms 1000 runs
Benchmark 2: show-ref: single matching ref (refformat = reftable)
Time (mean ± σ): 97.4 ms ± 3.2 ms [User: 94.5 ms, System: 2.7 ms]
Range (min … max): 94.1 ms … 126.3 ms 1000 runs
Summary
show-ref: single matching ref (refformat = reftable) ran
1.00 ± 0.05 times faster than show-ref: single matching ref (refformat = files)
```
There are still optimization opportunities left, but given that the
original target has been fulfilled I decided to stop so that the patch
series remains somewhat reasonably sized.
The patch series is based on `master` at 2996f11c1d (Sync with 'maint',
2024-02-12) and depends on ps/reftable-iteration-perf at c68ca7abd3
(reftable/reader: add comments to `table_iter_next()`, 2024-02-12).
Patrick
Patrick Steinhardt (12):
reftable/pq: use `size_t` to track iterator index
reftable/merged: make `merged_iter` structure private
reftable/merged: advance subiter on subsequent iteration
reftable/merged: make subiters own their records
reftable/merged: remove unnecessary null check for subiters
reftable/merged: handle subiter cleanup on close only
reftable/merged: circumvent pqueue with single subiter
reftable/merged: avoid duplicate pqueue emptiness check
reftable/record: reuse refname when decoding
reftable/record: reuse refname when copying
reftable/record: decode keys in place
reftable: allow inlining of a few functions
reftable/block.c | 25 +++----
reftable/block.h | 2 -
reftable/iter.c | 5 --
reftable/iter.h | 4 --
reftable/merged.c | 139 +++++++++++++++++++------------------
reftable/merged.h | 9 ---
reftable/pq.c | 18 +----
reftable/pq.h | 16 +++--
reftable/pq_test.c | 41 +++++------
reftable/record.c | 64 +++++++++--------
reftable/record.h | 21 ++++--
reftable/record_test.c | 3 +-
reftable/reftable-record.h | 1 +
13 files changed, 170 insertions(+), 178 deletions(-)
base-commit: 2996f11c1d11ab68823f0939b6469dedc2b9ab90
--
2.43.GIT
Attachment:
signature.asc
Description: PGP signature
