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

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

From
Derrick Stolee <stolee@gmail.com>
Date
May 15, 2026, 13:10 UTC
Message-ID
<aad34ac2-4cd5-4c85-b8ff-14c0caaa1c7b@gmail.com>
In-Reply-To
<CAL71e4Mfq3SCO7vnTbFCxpzH9txWPTencV-vq-aQ=wJ7dPMV2g@mail.gmail.com>
On 5/15/2026 3:47 AM, Kristofer Karlsson wrote:
Show 12 quoted lines
> 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: Kristofer KarlssonNext: Kristofer Karlsson
Message 7 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.