Hi,
this is the second version of my patch series that improves raw ref
iteration performance with the reftable backend.
Changes compared to v1 are sparse:
- Adapted an include because we don't need "pq.h" anymore.
- Some commit message improvements.
- I re-did the performance benchmarks in patch 12 as I noticed they
were stale.
- I also included one more patch to avoid re-computing the prefix
length on every iteration.
This patch series is now based on "master" directly at a2082dbdd3 (Start
the 2.45 cycle, 2024-02-26).
Thanks!
Patrick
Patrick Steinhardt (13):
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
refs/reftable: precompute prefix length
refs/reftable-backend.c | 6 +-
reftable/block.c | 25 +++----
reftable/block.h | 2 -
reftable/iter.c | 5 --
reftable/iter.h | 4 --
reftable/merged.c | 139 +++++++++++++++++++------------------
reftable/merged.h | 11 +--
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 +
14 files changed, 175 insertions(+), 181 deletions(-)
Range-diff against v1:
1: eeaaac9e07 = 1: 292e5f8888 reftable/pq: use `size_t` to track iterator index
2: be807e7650 ! 2: 95e1ccafc4 reftable/merged: make `merged_iter` structure private
@@ reftable/merged.c: license that can be found in the LICENSE file or at
for (size_t i = 0; i < mi->stack_len; i++) {
## reftable/merged.h ##
+@@ reftable/merged.h: license that can be found in the LICENSE file or at
+ #ifndef MERGED_H
+ #define MERGED_H
+
+-#include "pq.h"
++#include "system.h"
+
+ struct reftable_merged_table {
+ struct reftable_table *stack;
@@ reftable/merged.h: struct reftable_merged_table {
uint64_t max;
};
3: 38d4599566 ! 3: 0e327e5fe3 reftable/merged: advance subiter on subsequent iteration
@@ Metadata
## Commit message ##
reftable/merged: advance subiter on subsequent iteration
- When advancing the merged iterator, we pop the top-most entry from its
+ When advancing the merged iterator, we pop the topmost entry from its
priority queue and then advance the sub-iterator that the entry belongs
to, adding the result as a new entry. This is quite sensible in the case
- where the merged iterator is used to actual iterate through records. But
- the merged iterator is also used when we look up a single record, only,
- so advancing the sub-iterator is wasted effort because we would never
- even look at the result.
+ where the merged iterator is used to actually iterate through records.
+ But the merged iterator is also used when we look up a single record,
+ only, so advancing the sub-iterator is wasted effort because we would
+ never even look at the result.
Instead of immediately advancing the sub-iterator, we can also defer
this to the next iteration of the merged iterator by storing the
4: 2c51c60d16 = 4: 494d74deff reftable/merged: make subiters own their records
5: f1156dbf51 = 5: 0adf34d08b reftable/merged: remove unnecessary null check for subiters
6: 4e50ac6550 = 6: 01152ce130 reftable/merged: handle subiter cleanup on close only
7: cd65d849a4 = 7: 370b6cfc6c reftable/merged: circumvent pqueue with single subiter
8: 68bd687113 = 8: 1e279f21e6 reftable/merged: avoid duplicate pqueue emptiness check
9: 3ba697036c = 9: 15a8cbf678 reftable/record: reuse refname when decoding
10: d7311598c0 = 10: 35b1af2f06 reftable/record: reuse refname when copying
11: f0663c1d62 = 11: d7151ef361 reftable/record: decode keys in place
12: 56ec654932 ! 12: 99b238a40d reftable: allow inlining of a few functions
@@ Commit message
can be inlined. This results in a performance improvement when iterating
over 1 million refs:
- Benchmark 1: show-ref: single matching ref (revision = HEAD~)
- Time (mean ± σ): 102.4 ms ± 3.7 ms [User: 99.6 ms, System: 2.7 ms]
- Range (min … max): 99.1 ms … 129.1 ms 1000 runs
+ Benchmark 1: show-ref: single matching ref (revision = HEAD~)
+ Time (mean ± σ): 105.9 ms ± 3.6 ms [User: 103.0 ms, System: 2.8 ms]
+ Range (min … max): 103.1 ms … 133.4 ms 1000 runs
- Benchmark 2: show-ref: single matching ref (revision = HEAD)
- Time (mean ± σ): 98.3 ms ± 3.7 ms [User: 95.4 ms, System: 2.7 ms]
- Range (min … max): 94.9 ms … 126.2 ms 1000 runs
+ Benchmark 2: show-ref: single matching ref (revision = HEAD)
+ Time (mean ± σ): 100.7 ms ± 3.4 ms [User: 97.8 ms, System: 2.8 ms]
+ Range (min … max): 97.8 ms … 124.0 ms 1000 runs
- Summary
- show-ref: single matching ref (revision = HEAD) ran
- 1.04 ± 0.05 times faster than show-ref: single matching ref (revision = HEAD~)
+ Summary
+ show-ref: single matching ref (revision = HEAD) ran
+ 1.05 ± 0.05 times faster than show-ref: single matching ref (revision = HEAD~)
Signed-off-by: Patrick Steinhardt <ps@xxxxxx>
-: ---------- > 13: 627bd1f5f7 refs/reftable: precompute prefix length
--
2.44.0
Attachment:
signature.asc
Description: PGP signature
