[PATCH 00/12] reftable: improve ref iteration performance (pt.2)

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