git/list[1] front-page[2] threads[3] people[4] search[5] about
 

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.
Previous: Kristofer Karlsson via GitGitGadgetNext: Derrick Stolee
Message 2 of 12 in “revision: use priority queue in limit_list()”
  1. revision: use priority queue in limit_list()Kristofer Karlsson via GitGitGadget, May 14, 2026
  2. Junio C HamanoMay 14, 2026
  3. Derrick StoleeMay 14, 2026
  4. René ScharfeMay 17, 2026
  5. Jeff KingMay 15, 2026
  6. Kristofer KarlssonMay 15, 2026
  7. Derrick StoleeMay 15, 2026
  8. Kristofer KarlssonMay 17, 2026
  9. Junio C HamanoMay 17, 2026
  10. Jeff KingMay 19, 2026
  11. Kristofer KarlssonMay 19, 2026
  12. Jeff KingMay 19, 2026

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.