[v2,0/9] reftable: code style improvements

Message

Patrick Steinhardt Feb. 1, 2024, 7:32 a.m. UTC

Hi,

this is the second version of my patch series that aims to improve the
code style of the reftable library.

The only changes compared to v1 are improvements for the commit
messages. The edit for commit 1 should hopefully make it a much more
compelling argument why we don't want to use the default growth factor
used by our own `ALLOC_GROW()` macro.

Thanks!

Patrick

Patrick Steinhardt (9):
  reftable: introduce macros to grow arrays
  reftable: introduce macros to allocate arrays
  reftable/stack: fix parameter validation when compacting range
  reftable/stack: index segments with `size_t`
  reftable/stack: use `size_t` to track stack slices during compaction
  reftable/stack: use `size_t` to track stack length
  reftable/merged: refactor seeking of records
  reftable/merged: refactor initialization of iterators
  reftable/record: improve semantics when initializing records

 reftable/basics.c          |  15 ++--
 reftable/basics.h          |  17 ++++-
 reftable/block.c           |  25 +++---
 reftable/block_test.c      |   2 +-
 reftable/blocksource.c     |   4 +-
 reftable/iter.c            |   3 +-
 reftable/merged.c          | 100 +++++++++++-------------
 reftable/merged_test.c     |  52 ++++++-------
 reftable/pq.c              |   8 +-
 reftable/publicbasics.c    |   3 +-
 reftable/reader.c          |  12 ++-
 reftable/readwrite_test.c  |   8 +-
 reftable/record.c          |  43 +++--------
 reftable/record.h          |  10 +--
 reftable/record_test.c     |   8 +-
 reftable/refname.c         |   4 +-
 reftable/reftable-merged.h |   2 +-
 reftable/stack.c           | 151 +++++++++++++++++--------------------
 reftable/stack.h           |   6 +-
 reftable/stack_test.c      |   7 +-
 reftable/tree.c            |   4 +-
 reftable/writer.c          |  21 ++----
 22 files changed, 221 insertions(+), 284 deletions(-)

Range-diff against v1:
 1:  0597e6944a !  1:  12bd721ddf reftable: introduce macros to grow arrays
    @@ Commit message
         Throughout the reftable library we have many cases where we need to grow
         arrays. In order to avoid too many reallocations, we roughly double the
         capacity of the array on each iteration. The resulting code pattern is
    -    thus duplicated across many sites.
    +    duplicated across many sites.
     
         We have similar patterns in our main codebase, which is why we have
         eventually introduced an `ALLOC_GROW()` macro to abstract it away and
    @@ Commit message
             + 16) * 3 / 2`.
     
         The second change is because we know a bit more about the allocation
    -    patterns in the reftable library. For In most cases, we end up only having a
    -    single item in the array, so the initial capacity that our global growth
    -    factor uses (which is 24), significantly overallocates in a lot of code
    -    paths. This effect is indeed measurable:
    +    patterns in the reftable library. In most cases, we end up only having a
    +    handful of items in the array and don't end up growing them. The initial
    +    capacity that our normal growth factor uses (which is 24) would thus end
    +    up over-allocating in a lot of code paths. This effect is measurable:
     
    -      Benchmark 1: update-ref: create many refs (growth factor = 2 * cap + 1)
    -        Time (mean ± σ):      4.834 s ±  0.020 s    [User: 2.219 s, System: 2.614 s]
    -        Range (min … max):    4.793 s …  4.871 s    20 runs
    +      - Before change:
     
    -      Benchmark 2: update-ref: create many refs (growth factor = (cap + 16) * 3 + 2)
    -        Time (mean ± σ):      4.933 s ±  0.021 s    [User: 2.325 s, System: 2.607 s]
    -        Range (min … max):    4.889 s …  4.962 s    20 runs
    +          HEAP SUMMARY:
    +              in use at exit: 671,983 bytes in 152 blocks
    +            total heap usage: 3,843,446 allocs, 3,843,294 frees, 223,761,402 bytes allocated
     
    -      Summary
    -        update-ref: create many refs (growth factor = 2 * cap + 1) ran
    -          1.02 ± 0.01 times faster than update-ref: create many refs (growth factor = (cap + 16) * 3 + 2)
    +      - After change with a growth factor of `(2 * alloc + 1)`:
    +
    +          HEAP SUMMARY:
    +              in use at exit: 671,983 bytes in 152 blocks
    +            total heap usage: 3,843,446 allocs, 3,843,294 frees, 223,761,410 bytes allocated
    +
    +      - After change with a growth factor of `(alloc + 16)* 2 / 3`:
    +
    +          HEAP SUMMARY:
    +              in use at exit: 671,983 bytes in 152 blocks
    +            total heap usage: 3,833,673 allocs, 3,833,521 frees, 4,728,251,742 bytes allocated
    +
    +    While the total heap usage is roughly the same, we do end up allocating
    +    significantly more bytes with our usual growth factor (in fact, roughly
    +    21 times as many).
     
         Convert the reftable library to use these new macros.
     
 2:  eee6580c84 =  2:  2dde581a02 reftable: introduce macros to allocate arrays
 3:  e2d05f7c38 =  3:  f134702dc5 reftable/stack: fix parameter validation when compacting range
 4:  b8b2cce742 =  4:  50dac904e8 reftable/stack: index segments with `size_t`
 5:  2f6a69aa14 =  5:  a5ffbf09dd reftable/stack: use `size_t` to track stack slices during compaction
 6:  1ee9a4477f =  6:  55605fb53b reftable/stack: use `size_t` to track stack length
 7:  00aeaeee63 !  7:  80cf2fd272 reftable/merged: refactor seeking of records
    @@ Commit message
         to read and does not conform to our coding style in multiple ways:
     
           - We have multiple exit paths where we release resources even though
    -        that is not really necessary
    +        that is not really necessary.
     
           - We use a scoped error variable `e` which is hard to reason about.
             This variable is not required at all.
 8:  31864740e9 =  8:  8c1be2b159 reftable/merged: refactor initialization of iterators
 9:  fd8a1ce99d =  9:  c39d7e30e7 reftable/record: improve semantics when initializing records

base-commit: bc7ee2e5e16f0d1e710ef8fab3db59ab11f2bbe7