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

[Derrick Stolee <stolee@gmail.com>]

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