Re: [PATCH v2 10/10] reftable/block: avoid copying block iterators on seek
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
Show 28 quoted lines
> 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>
Justin Tobler <jltobler@gmail.com>