git/list[1] front-page[2] threads[3] people[4] search[5] about
 

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

From
René Scharfe <l.s.r@web.de>
Date
Jun 7, 2026, 07:30 UTC
Message-ID
<fe20bde6-9e86-4162-9bbd-af4d058e499e@web.de>
In-Reply-To
<pull.2140.v2.git.1780772477.gitgitgadget@gmail.com>
On 6/6/26 9:01 PM, Kristofer Karlsson via GitGitGadget wrote:
Show 71 quoted lines
> 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;
 }
Previous: Kristofer Karlsson via GitGitGadgetNext: Kristofer Karlsson
Message 8 of 18 in “prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion”
  1. prio-queue: fold lazy_queue into prio_queue for automatic get+put fusionKristofer Karlsson via GitGitGadget, Jun 6, 2026
  2. Junio C HamanoJun 6, 2026
  3. Kristofer KarlssonJun 6, 2026
  4. Junio C HamanoJun 8, 2026
  5. 0/2 prio-queue: fold lazy_queue into prio_queue for automatic get+put fusionKristofer Karlsson via GitGitGadget, Jun 6, 2026
  6. 1/2 prio-queue: fold lazy_queue into prio_queue for automatic get+put fusionKristofer Karlsson via GitGitGadget, Jun 6, 2026
  7. 2/2 prio-queue: rename .nr to .nr_internal to prevent direct accessKristofer Karlsson via GitGitGadget, Jun 6, 2026
  8. René ScharfeJun 7, 2026
  9. Kristofer KarlssonJun 7, 2026
  10. 0/2 prio-queue: fold lazy_queue into prio_queue for automatic get+put fusionKristofer Karlsson via GitGitGadget, Jun 7, 2026
  11. 1/2 prio-queue: fold lazy_queue into prio_queue for automatic get+put fusionKristofer Karlsson via GitGitGadget, Jun 7, 2026
  12. 2/2 prio-queue: rename .nr to .nr_internal to prevent direct accessKristofer Karlsson via GitGitGadget, Jun 7, 2026
  13. Junio C HamanoJun 8, 2026
  14. 0/2 prio-queue: fold lazy_queue into prio_queue for automatic get+put fusionKristofer Karlsson via GitGitGadget, Jun 8, 2026
  15. 1/2 prio-queue: rename .nr to .nr_ and add accessor helpersKristofer Karlsson via GitGitGadget, Jun 8, 2026
  16. 2/2 prio-queue: fold lazy_queue into prio_queue for automatic get+put fusionKristofer Karlsson via GitGitGadget, Jun 8, 2026
  17. Junio C HamanoJun 30, 2026
  18. Kristofer KarlssonJun 30, 2026

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.