Re: [PATCH v2 10/10] reftable/block: avoid copying block iterators on seek

[Patrick Steinhardt <ps@pks.im>]

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

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

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