[PATCH 0/3] commit-reach: replace queue_has_nonstale with a counter

["Kristofer Karlsson via GitGitGadget" <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           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