From: Junio C Hamano Date: Thu, 14 May 2026 19:40:06 GMT Subject: Re: [PATCH] revision: use priority queue in limit_list() Message-ID: In-Reply-To: "Kristofer Karlsson via GitGitGadget" writes: > 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. > Signed-off-by: Kristofer Karlsson > --- > 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.