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

Re: [PATCH] revision: use priority queue in limit_list()

From
Kristofer Karlsson <krka@spotify.com>
Date
May 17, 2026, 15:26 UTC
Message-ID
<CAL71e4MxhcZqxPVEe38Shuqt7h5dxLDGi66hN2cFXnmg-POKWA@mail.gmail.com>
In-Reply-To
<aad34ac2-4cd5-4c85-b8ff-14c0caaa1c7b@gmail.com>

Another note - I think I managed to apply the same change to get_revision_1 too - speeding up a monorepo "git rev-list HEAD" by 3.3x so it seems like a reasonable thing to do. This simplifies process_parents and also makes commit_list_insert_by_date dead code.

The only caveat is that get_revision_1 starts to get messier and the rev_info struct needs both a prio_queue and a linked list of commits - and then flushing everything from the list into the prio_queue when executing get_revision_1.

I don't want to pollute this patch with that change - should I start a separate thread for it or just revisit this later? (Perhaps I have too many optimization patches in flux already)

- Kristofer
On Fri, 15 May 2026 at 15:10, Derrick Stolee <stolee@gmail.com> wrote:
Show 43 quoted lines
>
> On 5/15/2026 3:47 AM, Kristofer Karlsson wrote:
>
> > Unfortunately git.git's mostly-linear history doesn't
> > trigger the quadratic behavior (the queue stays narrow). Even with
> > 5,584 commits in the symmetric diff, `--left-right --count` finishes
> > in ~0.4s on git.git for both baseline and patched. A 50-pair
> > interleaved run shows no statistically significant difference:
> >
> >     git rev-list --left-right --count v2.47.1...v2.54.0 (git.git, 5,584 commits)
> >     50 interleaved paired runs:
> >
> >     baseline: mean 393ms, stdev 13ms, median 392ms
> >     patched:  mean 396ms, stdev 14ms, median 393ms
> >     paired t-test: +2.9ms, t=1.16, p>0.05 (not significant)
>
> Thanks for sharing these details! Consider my curiosity sated.
> > The existing t/perf tests don't cover this path. p0001 doesn't
> > use --left-right and p6010 is merge-base specific. I could add a
> > perf test, though it would need a merge-heavy test repo to show the
> > difference. Would a synthetic one (like p6010 does) be useful?
>
> I'm usually interested in encoding ways to repeatedly exercise
> these performance gains and preventing regression in the future.
> However, you've demonstrated that not all repositories have a
> data shape that reveals the performance problem.
>
> If you happen to find a publicly-available repository that shows
> this improvement, then documenting the performance benefits for
> that repo would be sufficient. I'm familiar with performance
> work that doesn't reveal its most important gains until working
> with private repositories at the proper scale, so don't sweat
> not having a public example.
>
> I don't think it's worth constructing a synthetic repo to
> demonstrate this issue. I was hoping that it would be low-
> hanging fruit to cover this in the perf test suite, but that
> does not seem to be the case.
>
> Thanks,
> -Stolee
>
>
Previous: Derrick StoleeNext: Junio C Hamano
Message 8 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.