On Thu, Feb 1, 2024 at 8:17 AM Patrick Steinhardt <ps@xxxxxx> wrote: > When retrieving the next entry of a merged iterator we need to drop all > records of other sub-iterators that would be shadowed by the record that > we are about to return. We do this by comparing record keys, dropping > all keys that are smaller or equal to the key of the record we are about > to return. > > There is an edge case here where we can skip that comparison: when the > record in the priority queue comes from the same subiterator than the s/than/as/ > record we are about to return then we know that its key must be larger > than the key of the record we are about to return. This property is > guaranteed by the sub-iterators, and if it didn't hold then the whole > merged iterator would return records in the wrong order, too. > > While this may seem like a very specific edge case it's in fact quite > likely to happen. For most repositories out there you can assume that we > will end up with one large table and several smaller ones on top of it. > Thus, it is very likely that the next entry will sort towards the top of > the priority queue. > > Special case this and break out of the loop in that case. The following > benchmark uses git-show-ref(1) to print a single ref matching a pattern > out of 1 million refs: > > Benchmark 1: show-ref: single matching ref (revision = HEAD~) > Time (mean ± σ): 162.6 ms ± 4.5 ms [User: 159.0 ms, System: 3.5 ms] > Range (min … max): 156.6 ms … 188.5 ms 1000 runs > > Benchmark 2: show-ref: single matching ref (revision = HEAD) > Time (mean ± σ): 156.8 ms ± 4.7 ms [User: 153.0 ms, System: 3.6 ms] > Range (min … max): 151.4 ms … 188.4 ms 1000 runs > > Summary > show-ref: single matching ref (revision = HEAD) ran > 1.04 ± 0.04 times faster than show-ref: single matching ref (revision = HEAD~) > > Signed-off-by: Patrick Steinhardt <ps@xxxxxx>
