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

[Patrick Steinhardt <ps@pks.im>]

[-- Attachment #1: Type: text/plain, Size: 6372 bytes --]

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
-- 
2.44.0


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]