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

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@pks.im>
     
 -:  ---------- > 13:  627bd1f5f7 refs/reftable: precompute prefix length