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

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

From
Kristofer Karlsson via GitGitGadget <gitgitgadget@gmail.com>
Date
Jun 6, 2026, 19:01 UTC
Message-ID
<pull.2140.v2.git.1780772477.gitgitgadget@gmail.com>
In-Reply-To
<pull.2140.git.1780757885582.gitgitgadget@gmail.com>

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
-- 
gitgitgadget
Previous: Junio C HamanoNext: Kristofer Karlsson via GitGitGadget
Message 5 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.