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

2.44.GIT