commit-reach: replace queue_has_nonstale with a counter

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           1796ms

Large 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           1999ms

Linear 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