| Message ID | cc5ff0d5988691043206f9e912f5ffa1bcfee94e.1712578376.git.ps@pks.im (mailing list archive) |
|---|---|
| State | Accepted |
| Commit | 9da5c992dd8856035003cb06ff9c996a23956951 |
| Headers | show |
| Series | reftable: optimize table and block iterators | expand |
On 24/04/08 02:17PM, Patrick Steinhardt wrote: > When seeking a reftable record in a block we need to position the > iterator _before_ the sought-after record so that the next call to > `block_iter_next()` would yield that record. To achieve this, the loop > that performs the linear needs to restore the previous position once it Did we mean to say "linear seek" here? Otherwise this looks good to me. -Justin > has found the record. > > This is done by advancing two `block_iter`s: one to check whether the > next record is our sought-after record, and one that we update after > every iteration. This of course involves quite a lot of copying and also > leads to needless memory allocations. > > Refactor the code to get rid of the `next` iterator and the copying this > involves. Instead, we can restore the previous offset such that the call > to `next` will return the correct record. > > Next to being simpler conceptually this also leads to a nice speedup. > The following benchmark parser 10k refs out of 100k existing refs via > `git-rev-list --no-walk`: > > Benchmark 1: rev-list: print many refs (HEAD~) > Time (mean ± σ): 170.2 ms ± 1.7 ms [User: 86.1 ms, System: 83.6 ms] > Range (min … max): 166.4 ms … 180.3 ms 500 runs > > Benchmark 2: rev-list: print many refs (HEAD~) > Time (mean ± σ): 161.6 ms ± 1.6 ms [User: 78.1 ms, System: 83.0 ms] > Range (min … max): 158.4 ms … 172.3 ms 500 runs > > Summary > rev-list: print many refs (HEAD) ran > 1.05 ± 0.01 times faster than rev-list: print many refs (HEAD~) > > Signed-off-by: Patrick Steinhardt <ps@pks.im> ...
On Mon, Apr 08, 2024 at 08:29:14PM -0500, Justin Tobler wrote: > On 24/04/08 02:17PM, Patrick Steinhardt wrote: > > When seeking a reftable record in a block we need to position the > > iterator _before_ the sought-after record so that the next call to > > `block_iter_next()` would yield that record. To achieve this, the loop > > that performs the linear needs to restore the previous position once it > > Did we mean to say "linear seek" here? Otherwise this looks good to me. > > -Justin Oh, yes, of course. Thanks for reading this carefully! Patrick > > has found the record. > > > > This is done by advancing two `block_iter`s: one to check whether the > > next record is our sought-after record, and one that we update after > > every iteration. This of course involves quite a lot of copying and also > > leads to needless memory allocations. > > > > Refactor the code to get rid of the `next` iterator and the copying this > > involves. Instead, we can restore the previous offset such that the call > > to `next` will return the correct record. > > > > Next to being simpler conceptually this also leads to a nice speedup. > > The following benchmark parser 10k refs out of 100k existing refs via > > `git-rev-list --no-walk`: > > > > Benchmark 1: rev-list: print many refs (HEAD~) > > Time (mean ± σ): 170.2 ms ± 1.7 ms [User: 86.1 ms, System: 83.6 ms] > > Range (min … max): 166.4 ms … 180.3 ms 500 runs > > > > Benchmark 2: rev-list: print many refs (HEAD~) > > Time (mean ± σ): 161.6 ms ± 1.6 ms [User: 78.1 ms, System: 83.0 ms] > > Range (min … max): 158.4 ms … 172.3 ms 500 runs > > > > Summary > > rev-list: print many refs (HEAD) ran > > 1.05 ± 0.01 times faster than rev-list: print many refs (HEAD~) > > > > Signed-off-by: Patrick Steinhardt <ps@pks.im> > ...
diff --git a/reftable/block.c b/reftable/block.c index c6c4a68ea1..3e87460cba 100644 --- a/reftable/block.c +++ b/reftable/block.c @@ -365,16 +365,6 @@ 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, const struct block_iter *src) -{ - dest->block = src->block; - dest->block_len = src->block_len; - dest->hash_size = src->hash_size; - dest->next_off = src->next_off; - strbuf_reset(&dest->last_key); - strbuf_addbuf(&dest->last_key, &src->last_key); -} - int block_iter_next(struct block_iter *it, struct reftable_record *rec) { struct string_view in = { @@ -427,7 +417,6 @@ int block_iter_seek_key(struct block_iter *it, const struct block_reader *br, .needle = *want, .reader = br, }; - struct block_iter next = BLOCK_ITER_INIT; struct reftable_record rec; int err = 0; size_t i; @@ -486,11 +475,13 @@ int block_iter_seek_key(struct block_iter *it, const struct block_reader *br, * far and then back up. */ while (1) { - block_iter_copy_from(&next, it); - err = block_iter_next(&next, &rec); + size_t prev_off = it->next_off; + + err = block_iter_next(it, &rec); if (err < 0) goto done; if (err > 0) { + it->next_off = prev_off; err = 0; goto done; } @@ -501,18 +492,23 @@ int block_iter_seek_key(struct block_iter *it, const struct block_reader *br, * record does not exist in the block and can thus abort early. * In case it is equal to the sought-after key we have found * the desired record. + * + * Note that we store the next record's key record directly in + * `last_key` without restoring the key of the preceding record + * in case we need to go one record back. This is safe to do as + * `block_iter_next()` would return the ref whose key is equal + * to `last_key` now, and naturally all keys share a prefix + * with themselves. */ reftable_record_key(&rec, &it->last_key); - if (strbuf_cmp(&it->last_key, want) >= 0) + if (strbuf_cmp(&it->last_key, want) >= 0) { + it->next_off = prev_off; goto done; - - block_iter_copy_from(it, &next); + } } done: - block_iter_close(&next); reftable_record_release(&rec); - return err; } diff --git a/reftable/block.h b/reftable/block.h index c1bd1892cb..ea4384a7e2 100644 --- a/reftable/block.h +++ b/reftable/block.h @@ -121,8 +121,6 @@ void block_iter_seek_start(struct block_iter *it, const struct block_reader *br) int block_iter_seek_key(struct block_iter *it, const struct block_reader *br, struct strbuf *want); -void block_iter_copy_from(struct block_iter *dest, const struct block_iter *src); - /* return < 0 for error, 0 for OK, > 0 for EOF. */ int block_iter_next(struct block_iter *it, struct reftable_record *rec);
When seeking a reftable record in a block we need to position the iterator _before_ the sought-after record so that the next call to `block_iter_next()` would yield that record. To achieve this, the loop that performs the linear needs to restore the previous position once it has found the record. This is done by advancing two `block_iter`s: one to check whether the next record is our sought-after record, and one that we update after every iteration. This of course involves quite a lot of copying and also leads to needless memory allocations. Refactor the code to get rid of the `next` iterator and the copying this involves. Instead, we can restore the previous offset such that the call to `next` will return the correct record. Next to being simpler conceptually this also leads to a nice speedup. The following benchmark parser 10k refs out of 100k existing refs via `git-rev-list --no-walk`: Benchmark 1: rev-list: print many refs (HEAD~) Time (mean ± σ): 170.2 ms ± 1.7 ms [User: 86.1 ms, System: 83.6 ms] Range (min … max): 166.4 ms … 180.3 ms 500 runs Benchmark 2: rev-list: print many refs (HEAD~) Time (mean ± σ): 161.6 ms ± 1.6 ms [User: 78.1 ms, System: 83.0 ms] Range (min … max): 158.4 ms … 172.3 ms 500 runs Summary rev-list: print many refs (HEAD) ran 1.05 ± 0.01 times faster than rev-list: print many refs (HEAD~) Signed-off-by: Patrick Steinhardt <ps@pks.im> --- reftable/block.c | 32 ++++++++++++++------------------ reftable/block.h | 2 -- 2 files changed, 14 insertions(+), 20 deletions(-)