From: Kristofer Karlsson Date: Sun, 17 May 2026 15:26:06 GMT Subject: Re: [PATCH] revision: use priority queue in limit_list() Message-ID: In-Reply-To: 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 wrote: > > 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 > >