[PATCH 0/3] commit-reach: replace queue_has_nonstale with a counter
- From
Kristofer Karlsson via GitGitGadget <gitgitgadget@gmail.com>
- Date
- May 24, 2026, 17:42 UTC
- Message-ID
- <pull.2124.git.1779644541.gitgitgadget@gmail.com>
paint_down_to_common() and ahead_behind() terminate when every commit in their priority queue is STALE. The current check, queue_has_nonstale(), does an O(n) linear scan of the queue on every iteration, costing O(n*m) total where n is the queue size and m is the number of commits processed. This series replaces that scan with an O(1) counter.
Performance measurements with git merge-base --all and git for-each-ref --format='%(ahead-behind:...)':
git.git (merge-base)
Baseline Dedup Dedup+Ctr
seen..next, 33 merge bases: 157ms 165ms 143ms
seen..master, 1 base: 47ms 40ms 44ms
master..next, 1 base: 62ms 60ms 63ms(seen=fe056fe1, next=c82f1880, master=6a4418c3)
Large monorepo, 2.4M commits (merge-base)
Baseline Dedup+Ctr
component import, wide frontier (1): 8083ms 3778ms
component import, wide frontier (2): 5664ms 4207ms
component import, wide frontier (3): 4558ms 1796msLarge monorepo, 2.4M commits (ahead-behind)
Baseline Dedup+Ctr
component import, wide frontier (1): 8216ms 4145ms
component import, wide frontier (2): 6107ms 4528ms
component import, wide frontier (3): 4725ms 1999msLinear history (merge-base), no regression: master vs HEAD~10000: 4410ms 4180ms master vs HEAD~50000: 4412ms 4494ms
The improvement depends on how wide the frontier gets during the walk. Component imports in the monorepo create wide frontiers where the queue grows large, making the O(n) scan expensive -- up to 2.5x speedup for merge-base and 2.4x for ahead-behind. Linear history and simple merges show no regression.
With a very narrow frontier the counter approach adds a small constant overhead per iteration (maintaining the counter and the ENQUEUED flag) compared to the old scan which would return almost immediately. Both are O(1) and cheap in that scenario, so it should not matter in practice -- the benchmark numbers above confirm this.
Kristofer Karlsson (3): commit-reach: deduplicate queue entries in paint_down_to_common commit-reach: optimize queue scan in paint_down_to_common commit-reach: optimize queue scan in ahead_behind
commit-reach.c | 58 ++++++++++++++++++++++++++++++++++++-------------- object.h | 2 +- 2 files changed, 43 insertions(+), 17 deletions(-)
base-commit: 6a4418c36d6bad69a599044b3cf49dcbd049cb45 Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2124%2Fspkrka%2Fqueue-has-nonstale-v3-v1 Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2124/spkrka/queue-has-nonstale-v3-v1 Pull-Request: https://github.com/gitgitgadget/git/pull/2124
-- gitgitgadget