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@xxxxxx> > ...
Attachment:
signature.asc
Description: PGP signature
