[PATCH v2 00/10] reftable: optimize table and block iterators

Hi,

this is the second version of my patch series that aims to optimize the reftable table and block iterators.

Changes compared to v1:

    - The series now deepends on ps/reftable-binsearch-update at
      d51d8cc368 (reftable/block: avoid decoding keys when searching
      restart points, 2024-04-03). This is to resolve a merge conflict
      with that other series which has landed in "next" already.

    - Rewrote a comment to be single-line to fit into the style of other
      comments better.

    - A new patch on top that avoids copying block iterators altogether
      for another speedup.

Thanks!

Patrick

Patrick Steinhardt (10):
  reftable/block: rename `block_reader_start()`
  reftable/block: merge `block_iter_seek()` and `block_reader_seek()`
  reftable/block: better grouping of functions
  reftable/block: introduce `block_reader_release()`
  reftable/block: move ownership of block reader into `struct
    table_iter`
  reftable/reader: iterate to next block in place
  reftable/block: reuse uncompressed blocks
  reftable/block: open-code call to `uncompress2()`
  reftable/block: reuse `zstream` state on inflation
  reftable/block: avoid copying block iterators on seek

 reftable/block.c      | 176 +++++++++++++++++++++++++-----------------
 reftable/block.h      |  47 ++++++-----
 reftable/block_test.c |   6 +-
 reftable/iter.c       |   2 +-
 reftable/reader.c     | 176 ++++++++++++++++++++++--------------------
 5 files changed, 229 insertions(+), 178 deletions(-)

Range-diff against v1:
 1:  24b0dda29e =  1:  eb487557a8 reftable/block: rename `block_reader_start()`
 2:  a2b7f0f559 !  2:  d0b318b8ee reftable/block: merge `block_iter_seek()` and `block_reader_seek()`
    @@ reftable/block.c: int block_reader_first_key(struct block_reader *br, struct str
     +int block_iter_seek_key(struct block_iter *it, struct block_reader *br,
     +			struct strbuf *want)
      {
    - 	struct restart_find_args args = {
    - 		.key = *want,
    + 	struct restart_needle_less_args args = {
    + 		.needle = *want,
     
      ## reftable/block.h ##
     @@ reftable/block.h: int block_reader_init(struct block_reader *br, struct reftable_block *bl,
 3:  88a705b3e2 =  3:  c3f928d1e9 reftable/block: better grouping of functions
 4:  9a1253649a =  4:  35f1bf5072 reftable/block: introduce `block_reader_release()`
 5:  f10882a084 !  5:  e8e8bbae62 reftable/block: move ownership of block reader into `struct table_iter`
    @@ reftable/block.c: int block_reader_first_key(struct block_reader *br, struct str
      	it->next_off = br->header_off + 4;
      }
     @@ reftable/block.c: void block_iter_seek_start(struct block_iter *it, struct block_reader *br)
    - struct restart_find_args {
    + struct restart_needle_less_args {
      	int error;
    - 	struct strbuf key;
    --	struct block_reader *r;
    -+	const struct block_reader *r;
    + 	struct strbuf needle;
    +-	struct block_reader *reader;
    ++	const struct block_reader *reader;
      };
      
    - static int restart_key_less(size_t idx, void *args)
    -@@ reftable/block.c: static int restart_key_less(size_t idx, void *args)
    - 	return result < 0;
    + static int restart_needle_less(size_t idx, void *_args)
    +@@ reftable/block.c: static int restart_needle_less(size_t idx, void *_args)
    + 	return args->needle.len < suffix_len;
      }
      
     -void block_iter_copy_from(struct block_iter *dest, struct block_iter *src)
    @@ reftable/block.c: int block_iter_next(struct block_iter *it, struct reftable_rec
     +int block_iter_seek_key(struct block_iter *it, const struct block_reader *br,
      			struct strbuf *want)
      {
    - 	struct restart_find_args args = {
    + 	struct restart_needle_less_args args = {
     @@ reftable/block.c: int block_iter_seek_key(struct block_iter *it, struct block_reader *br,
      		it->next_off = block_reader_restart_offset(br, i - 1);
      	else
    @@ reftable/block.h: struct block_iter {
      /* return < 0 for error, 0 for OK, > 0 for EOF. */
      int block_iter_next(struct block_iter *it, struct reftable_record *rec);
      
    -+/*
    -+ * Reset the block iterator to pristine state without releasing its memory.
    -+ */
    ++/* Reset the block iterator to pristine state without releasing its memory. */
     +void block_iter_reset(struct block_iter *it);
     +
      /* deallocate memory for `it`. The block reader and its block is left intact. */
 6:  ae359cb714 =  6:  685f0a40bc reftable/reader: iterate to next block in place
 7:  1e4eba7e9b =  7:  a7906a3383 reftable/block: reuse uncompressed blocks
 8:  bf4c1ab797 =  8:  6635c7b986 reftable/block: open-code call to `uncompress2()`
 9:  43e6538968 =  9:  587b5601c0 reftable/block: reuse `zstream` state on inflation
 -:  ---------- > 10:  cc5ff0d598 reftable/block: avoid copying block iterators on seek