From: Kristofer Karlsson via GitGitGadget Date: Sat, 06 Jun 2026 19:01:14 GMT Subject: [PATCH v2 0/2] prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion Message-ID: In-Reply-To: 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