Re: [PATCH v2 0/2] prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion

["René Scharfe" <l.s.r@web.de>]

On 6/6/26 9:01 PM, Kristofer Karlsson via GitGitGadget wrote:
> Rene's lazy_queue wrapper in describe.c was a clever optimization -- by
> deferring the get, a following put becomes a simple replace, avoiding a full
> remove-rebalance-insert cycle.
> 
> It turns out this pattern is so common in git's traversal code that it makes
> sense to fold it into prio_queue itself. Gets and puts are interleaved in
> virtually every commit walk, so the fusion is essentially always a win.
> 
> This is mostly a code simplification -- three callers had independently
> reimplemented the same optimization, and they all collapse to plain get+put
> now. The 3-6% speedup on traversal-heavy workloads is a nice bonus.
> 
> More details and benchmark numbers in the commit message. Benchmarks were
> run on next which includes kk/commit-reach-optim -- those results represent
> the more realistic end state.
> 
> Related to but independent of the cascade sift-down work in
> kk/prio-queue-cascade-sift -- the two can land in either order.
> 
> Changes since v1:
> 
>  * Added a second commit that renames .nr to .nr_internal so that direct
>    access from outside prio-queue.c is a compile error. Verified that after
>    the rename, only prio-queue.c references nr_internal.
> 
>  * Added prio_queue_for_each() macro for callers that need to walk all
>    elements (describe.c, show-branch.c, commit-reach.c, revision.c,
>    negotiator/skipping.c).
> 
>  * Converted remaining .nr loop conditions to use
>    prio_queue_get()/prio_queue_peek() as the loop condition, or
>    prio_queue_size() where get/peek isn't suitable.
> 
>  * Fixed several callers missed in v1 (object-name.c, fetch-pack.c,
>    path-walk.c, pack-bitmap-write.c, negotiator/default.c,
>    negotiator/skipping.c, revision.c, builtin/last-modified.c).
> 
> Kristofer Karlsson (2):
>   prio-queue: fold lazy_queue into prio_queue for automatic get+put
>     fusion
>   prio-queue: rename .nr to .nr_internal to prevent direct access
> 
>  builtin/describe.c          | 70 ++++++++-------------------------
>  builtin/last-modified.c     |  7 ++--
>  builtin/show-branch.c       | 24 +++++-------
>  commit-reach.c              | 24 ++++++------
>  commit.c                    | 11 +-----
>  fetch-pack.c                |  4 +-
>  negotiator/default.c        |  4 +-
>  negotiator/skipping.c       | 12 +++---
>  object-name.c               |  2 +-
>  pack-bitmap-write.c         | 10 ++---
>  path-walk.c                 |  8 ++--
>  prio-queue.c                | 77 ++++++++++++++++++++-----------------
>  prio-queue.h                | 19 +++++----
>  revision.c                  | 16 ++++----
>  t/unit-tests/u-prio-queue.c |  6 +--
>  walker.c                    |  4 +-
>  16 files changed, 129 insertions(+), 169 deletions(-)
> 
> 
> base-commit: 9ac3f193c05c2237e2b14ebaa1149e9fc8a1abe0
> Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2140%2Fspkrka%2Flazy-prio-queue-pr-v2
> Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2140/spkrka/lazy-prio-queue-pr-v2
> Pull-Request: https://github.com/gitgitgadget/git/pull/2140
> 
> Range-diff vs v1:
> 
>  1:  29af24445e = 1:  29af24445e prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion
>  -:  ---------- > 2:  bb8b0f78f1 prio-queue: rename .nr to .nr_internal to prevent direct access
> 

My earlier attempt in <90270818-c52b-4611-8da2-6cee20628fc2@web.de>
copied the last item to the root and decreased .nr, to allow callers to
scan items and get their count directly.

Checking emptiness by doing the existing calls of prio_queue_peek() and
prio_queue_get() a bit earlier and scanning using a foreach macro are
fine as well and arguably cleaner, at the low cost of having to change
all the callers.

The result is faster than my attempt, but still slower than the current
code in the describe benchmark from 30598ccc4d (describe: use oidset in
finish_depth_computation(), 2025-09-02):

Benchmark 1: ./git_main describe $(git rev-list v2.41.0..v2.47.0)
  Time (mean ± σ):     601.7 ms ±   1.9 ms    [User: 538.6 ms, System: 47.3 ms]
  Range (min … max):   599.3 ms … 606.5 ms    10 runs

Benchmark 2: ./git_auto_replace describe $(git rev-list v2.41.0..v2.47.0)
  Time (mean ± σ):     618.0 ms ±   1.1 ms    [User: 554.5 ms, System: 47.6 ms]
  Range (min … max):   616.7 ms … 620.2 ms    10 runs

Benchmark 3: ./git_fold describe $(git rev-list v2.41.0..v2.47.0)
  Time (mean ± σ):     609.9 ms ±   0.8 ms    [User: 546.7 ms, System: 47.4 ms]
  Range (min … max):   608.8 ms … 611.2 ms    10 runs

Benchmark 4: ./git describe $(git rev-list v2.41.0..v2.47.0)
  Time (mean ± σ):     606.1 ms ±   1.2 ms    [User: 543.7 ms, System: 46.7 ms]
  Range (min … max):   604.7 ms … 609.1 ms    10 runs

Summary
  ./git_main describe $(git rev-list v2.41.0..v2.47.0) ran
    1.01 ± 0.00 times faster than ./git describe $(git rev-list v2.41.0..v2.47.0)
    1.01 ± 0.00 times faster than ./git_fold describe $(git rev-list v2.41.0..v2.47.0)
    1.03 ± 0.00 times faster than ./git_auto_replace describe $(git rev-list v2.41.0..v2.47.0)

git_auto_replace: <90270818-c52b-4611-8da2-6cee20628fc2@web.de> and
  revert of 08bb69d70f (describe: use prio_queue_replace(), 2025-08-03)
git_fold: this series
git: this series and the patch below

My attempt leaves performance on the table by using a bool.  Using
an unsigned for the flag is measurably faster -- but still slower
than your series here.

Calling flush_get() later, when we know that we have items and a
compare function, is cleaner, as we never need it in LIFO mode, and
is also slightly faster (patch below).

Still there's this 1% performance gap to the current code that I
don't understand.  Do you see it as well?

René

---
 prio-queue.c | 7 +++----
 1 file changed, 3 insertions(+), 4 deletions(-)

diff --git a/prio-queue.c b/prio-queue.c
index d11ca6ac36..45709187d3 100644
--- a/prio-queue.c
+++ b/prio-queue.c
@@ -100,24 +100,23 @@ static void sift_down_root(struct prio_queue *queue)
 
 void *prio_queue_get(struct prio_queue *queue)
 {
-	flush_get(queue);
-
 	if (!queue->nr_internal)
 		return NULL;
 	if (!queue->compare)
 		return queue->array[--queue->nr_internal].data; /* LIFO */
 
+	flush_get(queue);
 	queue->get_pending = 1;
 	return queue->array[0].data;
 }
 
 void *prio_queue_peek(struct prio_queue *queue)
 {
-	flush_get(queue);
-
 	if (!queue->nr_internal)
 		return NULL;
 	if (!queue->compare)
 		return queue->array[queue->nr_internal - 1].data;
+
+	flush_get(queue);
 	return queue->array[0].data;
 }