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