Re: [PATCH] revision: use priority queue in limit_list()
- From
Junio C Hamano <gitster@pobox.com>
- Date
- May 14, 2026, 19:40 UTC
- Message-ID
- <xmqq5x4pg4q1.fsf@gitster.g>
- In-Reply-To
- <pull.2114.git.1778777491939.gitgitgadget@gmail.com>
"Kristofer Karlsson via GitGitGadget" <gitgitgadget@gmail.com> writes:
Show 15 quoted lines
> Benchmark: git rev-list --left-right --count HEAD~N...HEAD > Repository: 2.3M commits, merge-heavy DAG (monorepo) > Best of 5 runs, times in seconds: > > commits in > symmetric diff baseline patched speedup > -------------- -------- ------- ------- > 10 0.01 0.01 1.0x > 50 0.01 0.01 1.0x > 3751 21.23 8.49 2.5x > 4524 21.70 8.29 2.6x > 10130 20.10 6.65 3.0x > > No change for small traversals; 2.5-3.0x faster when the queue grows > to thousands of commits.
Impressive.
Show 9 quoted lines
> Signed-off-by: Kristofer Karlsson <krka@spotify.com> > --- > revision: use priority queue in limit_list() > ... > This affects any command that triggers limit_list() — i.e., when > revs->limited is set — including --left-right, --cherry-mark, > --cherry-pick, --ancestry-path, bisect, and rebase's fork-point > computation. The practical trigger is git status --ahead-behind on a > branch that has diverged from upstream in a merge-heavy repository.
I found this description a bit curious. Notably missing from the above list of revs->limited users is a bog standard A..B and it is unclear the omission is because that case is not improved and if so why.
I think a major reason of the omission of A..B from the above is, despite my recollection that such a range (i.e., any presense of UNINTERESTING commit) computation _always_ worked on a limited list, these days we conditionally do not when we have commit graph and we are showing in --topo-order (which is implicitly enabled when many options other than --topo-order is in effect) since 1b4d8827 (revision: use generation for A..B --topo-order queries, 2019-05-21).
It might be interesting to extend your benchmark over the same history with the same command line, perhaps with and without an explicit "--topo-order" added, in a repository _without_ commit-graph enabled.
Thanks.