[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 accessbuiltin/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