{"thread":{"id":"65764","subject":"[PATCH] prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion","startedAt":"2026-06-06T14:58:08Z","lastAt":"2026-06-30T21:16:43Z","messageCount":18,"participants":["Kristofer Karlsson via GitGitGadget","Junio C Hamano","Kristofer Karlsson","René Scharfe"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"544832","messageId":"pull.2140.git.1780757885582.gitgitgadget@gmail.com","threadId":"65764","inReplyTo":null,"subject":"[PATCH] prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-06-06T14:58:04Z","receivedAt":"2026-06-06T14:58:08Z","isPatch":true,"body":"From: Kristofer Karlsson <krka@spotify.com>\n\nDefer the actual removal in prio_queue_get() until the next\noperation.  If that next operation is a prio_queue_put(), the\nremoval and insertion are fused into a single replace — writing\nthe new element at the root and sifting it down — which avoids\na full remove-rebalance-insert cycle.\n\nThis matches the dominant usage pattern in git's commit traversal:\nget a commit, then put its parents.  The first parent insertion\nafter each get is now a replace operation automatically.\n\nThis generalizes the lazy_queue pattern from builtin/describe.c\n(introduced in 08bb69d70f) into prio_queue itself.  Three callers\nindependently implemented the same get+put fusion:\n\n  - builtin/describe.c had a full lazy_queue wrapper\n  - commit.c:pop_most_recent_commit() reimplements the same\n    get_pending flag with peek+replace\n  - builtin/show-branch.c:join_revs() used the same peek+replace\n    pattern\n\nAll three now collapse to plain _get() and _put(),\nwith the data structure handling the fusion internally.\n\nRemove prio_queue_replace() since no external callers remain.\nAdd prio_queue_size() for callers that need the logical element\ncount, since the physical nr may temporarily include a\npending-removal element.\n\nBenchmarked on a large monorepo (10-15 interleaved runs, 1 warmup):\n\n  Command                       base    patched  speedup\n  merge-base --all A A~1000     3.88s   3.77s    1.03x\n  rev-list --count A~1000..A    3.57s   3.43s    1.04x\n  log --oneline A~1000..A       3.70s   3.49s    1.06x\n  rev-parse :/pattern           365ms   364ms    1.00x\n  describe HEAD (linux.git)     184ms   190ms    1.00x\n\nNo regressions in any scenario.\n\nSigned-off-by: Kristofer Karlsson <krka@spotify.com>\n---\n    prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion\n    \n    Rene's lazy_queue wrapper in describe.c was a clever optimization -- by\n    deferring the get, a following put becomes a simple replace, avoiding a\n    full remove-rebalance-insert cycle.\n    \n    It turns out this pattern is so common in git's traversal code that it\n    makes sense to fold it into prio_queue itself. Gets and puts are\n    interleaved in virtually every commit walk, so the fusion is essentially\n    always a win.\n    \n    This is mostly a code simplification -- three callers had independently\n    reimplemented the same optimization, and they all collapse to plain\n    get+put now. The 3-6% speedup on traversal-heavy workloads is a nice\n    bonus.\n    \n    More details and benchmark numbers in the commit message. Benchmarks\n    were run on next which includes kk/commit-reach-optim -- those results\n    represent the more realistic end state.\n    \n    Related to but independent of the cascade sift-down work in\n    kk/prio-queue-cascade-sift -- the two can land in either order.\n\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-2140%2Fspkrka%2Flazy-prio-queue-pr-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2140/spkrka/lazy-prio-queue-pr-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/2140\n\n builtin/describe.c          | 67 +++++++++----------------------------\n builtin/last-modified.c     |  4 +--\n builtin/show-branch.c       | 17 ++++------\n commit-reach.c              |  5 ++-\n commit.c                    | 11 ++----\n pack-bitmap-write.c         |  4 +--\n prio-queue.c                | 49 +++++++++++++++------------\n prio-queue.h                | 12 +++----\n revision.c                  |  5 ++-\n t/unit-tests/u-prio-queue.c |  6 ++--\n walker.c                    |  4 +--\n 11 files changed, 68 insertions(+), 116 deletions(-)\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 1c47d7c0b7..85564f3487 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -251,56 +251,20 @@ static int compare_pt(const void *a_, const void *b_)\n \treturn 0;\n }\n \n-struct lazy_queue {\n-\tstruct prio_queue queue;\n-\tbool get_pending;\n-};\n-\n-#define LAZY_QUEUE_INIT { { compare_commits_by_commit_date }, false }\n-\n-static void *lazy_queue_get(struct lazy_queue *queue)\n-{\n-\tif (queue->get_pending)\n-\t\tprio_queue_get(&queue->queue);\n-\telse\n-\t\tqueue->get_pending = true;\n-\treturn prio_queue_peek(&queue->queue);\n-}\n-\n-static void lazy_queue_put(struct lazy_queue *queue, void *thing)\n-{\n-\tif (queue->get_pending)\n-\t\tprio_queue_replace(&queue->queue, thing);\n-\telse\n-\t\tprio_queue_put(&queue->queue, thing);\n-\tqueue->get_pending = false;\n-}\n-\n-static bool lazy_queue_empty(const struct lazy_queue *queue)\n-{\n-\treturn queue->queue.nr == (queue->get_pending ? 1 : 0);\n-}\n-\n-static void lazy_queue_clear(struct lazy_queue *queue)\n-{\n-\tclear_prio_queue(&queue->queue);\n-\tqueue->get_pending = false;\n-}\n-\n-static unsigned long finish_depth_computation(struct lazy_queue *queue,\n+static unsigned long finish_depth_computation(struct prio_queue *queue,\n \t\t\t\t\t      struct possible_tag *best)\n {\n \tunsigned long seen_commits = 0;\n \tstruct oidset unflagged = OIDSET_INIT;\n+\tstruct commit *c;\n \n-\tfor (size_t i = queue->get_pending ? 1 : 0; i < queue->queue.nr; i++) {\n-\t\tstruct commit *commit = queue->queue.array[i].data;\n+\tfor (size_t i = queue->get_pending; i < queue->nr; i++) {\n+\t\tstruct commit *commit = queue->array[i].data;\n \t\tif (!(commit->object.flags & best->flag_within))\n \t\t\toidset_insert(&unflagged, &commit->object.oid);\n \t}\n \n-\twhile (!lazy_queue_empty(queue)) {\n-\t\tstruct commit *c = lazy_queue_get(queue);\n+\twhile ((c = prio_queue_get(queue))) {\n \t\tstruct commit_list *parents = c->parents;\n \t\tseen_commits++;\n \t\tif (c->object.flags & best->flag_within) {\n@@ -316,7 +280,7 @@ static unsigned long finish_depth_computation(struct lazy_queue *queue,\n \t\t\trepo_parse_commit(the_repository, p);\n \t\t\tseen = p->object.flags & SEEN;\n \t\t\tif (!seen)\n-\t\t\t\tlazy_queue_put(queue, p);\n+\t\t\t\tprio_queue_put(queue, p);\n \t\t\tflag_before = p->object.flags & best->flag_within;\n \t\t\tp->object.flags |= c->object.flags;\n \t\t\tflag_after = p->object.flags & best->flag_within;\n@@ -364,8 +328,8 @@ static void append_suffix(int depth, const struct object_id *oid, struct strbuf\n \n static void describe_commit(struct commit *cmit, struct strbuf *dst)\n {\n-\tstruct commit *gave_up_on = NULL;\n-\tstruct lazy_queue queue = LAZY_QUEUE_INIT;\n+\tstruct commit *c, *gave_up_on = NULL;\n+\tstruct prio_queue queue = { compare_commits_by_commit_date };\n \tstruct commit_name *n;\n \tstruct possible_tag all_matches[MAX_TAGS];\n \tunsigned int match_cnt = 0, annotated_cnt = 0, cur_match;\n@@ -407,9 +371,8 @@ static void describe_commit(struct commit *cmit, struct strbuf *dst)\n \t}\n \n \tcmit->object.flags = SEEN;\n-\tlazy_queue_put(&queue, cmit);\n-\twhile (!lazy_queue_empty(&queue)) {\n-\t\tstruct commit *c = lazy_queue_get(&queue);\n+\tprio_queue_put(&queue, cmit);\n+\twhile ((c = prio_queue_get(&queue))) {\n \t\tstruct commit_list *parents = c->parents;\n \t\tstruct commit_name **slot;\n \n@@ -443,7 +406,7 @@ static void describe_commit(struct commit *cmit, struct strbuf *dst)\n \t\t\t\tt->depth++;\n \t\t}\n \t\t/* Stop if last remaining path already covered by best candidate(s) */\n-\t\tif (annotated_cnt && lazy_queue_empty(&queue)) {\n+\t\tif (annotated_cnt && !prio_queue_size(&queue)) {\n \t\t\tint best_depth = INT_MAX;\n \t\t\tunsigned best_within = 0;\n \t\t\tfor (cur_match = 0; cur_match < match_cnt; cur_match++) {\n@@ -466,7 +429,7 @@ static void describe_commit(struct commit *cmit, struct strbuf *dst)\n \t\t\tstruct commit *p = parents->item;\n \t\t\trepo_parse_commit(the_repository, p);\n \t\t\tif (!(p->object.flags & SEEN))\n-\t\t\t\tlazy_queue_put(&queue, p);\n+\t\t\t\tprio_queue_put(&queue, p);\n \t\t\tp->object.flags |= c->object.flags;\n \t\t\tparents = parents->next;\n \n@@ -481,7 +444,7 @@ static void describe_commit(struct commit *cmit, struct strbuf *dst)\n \t\t\tstrbuf_add_unique_abbrev(dst, cmit_oid, abbrev);\n \t\t\tif (suffix)\n \t\t\t\tstrbuf_addstr(dst, suffix);\n-\t\t\tlazy_queue_clear(&queue);\n+\t\t\tclear_prio_queue(&queue);\n \t\t\treturn;\n \t\t}\n \t\tif (unannotated_cnt)\n@@ -497,11 +460,11 @@ static void describe_commit(struct commit *cmit, struct strbuf *dst)\n \tQSORT(all_matches, match_cnt, compare_pt);\n \n \tif (gave_up_on) {\n-\t\tlazy_queue_put(&queue, gave_up_on);\n+\t\tprio_queue_put(&queue, gave_up_on);\n \t\tseen_commits--;\n \t}\n \tseen_commits += finish_depth_computation(&queue, &all_matches[0]);\n-\tlazy_queue_clear(&queue);\n+\tclear_prio_queue(&queue);\n \n \tif (debug) {\n \t\tstatic int label_width = -1;\ndiff --git a/builtin/last-modified.c b/builtin/last-modified.c\nindex 8900ceece1..df2a508244 100644\n--- a/builtin/last-modified.c\n+++ b/builtin/last-modified.c\n@@ -344,6 +344,7 @@ static void process_parent(struct last_modified *lm,\n static int last_modified_run(struct last_modified *lm)\n {\n \tint max_count, queue_popped = 0;\n+\tstruct commit *c;\n \tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n \tstruct prio_queue not_queue = { compare_commits_by_gen_then_commit_date };\n \tstruct commit_list *list;\n@@ -389,10 +390,9 @@ static int last_modified_run(struct last_modified *lm)\n \t\t}\n \t}\n \n-\twhile (queue.nr) {\n+\twhile ((c = prio_queue_get(&queue))) {\n \t\tint parent_i;\n \t\tstruct commit_list *p;\n-\t\tstruct commit *c = prio_queue_get(&queue);\n \t\tstruct bitmap *active_c = active_paths_for(lm, c);\n \n \t\tif ((0 <= max_count && max_count < ++queue_popped) ||\ndiff --git a/builtin/show-branch.c b/builtin/show-branch.c\nindex f02831b085..9f7f28f339 100644\n--- a/builtin/show-branch.c\n+++ b/builtin/show-branch.c\n@@ -62,7 +62,7 @@ static const char *get_color_reset_code(void)\n \n static struct commit *interesting(struct prio_queue *queue)\n {\n-\tfor (size_t i = 0; i < queue->nr; i++) {\n+\tfor (size_t i = queue->get_pending; i < queue->nr; i++) {\n \t\tstruct commit *commit = queue->array[i].data;\n \t\tif (commit->object.flags & UNINTERESTING)\n \t\t\tcontinue;\n@@ -228,17 +228,18 @@ static void join_revs(struct prio_queue *queue,\n {\n \tint all_mask = ((1u << (REV_SHIFT + num_rev)) - 1);\n \tint all_revs = all_mask & ~((1u << REV_SHIFT) - 1);\n+\tstruct commit *commit;\n \n-\twhile (queue->nr) {\n+\twhile ((commit = prio_queue_peek(queue))) {\n \t\tstruct commit_list *parents;\n \t\tint still_interesting = !!interesting(queue);\n-\t\tstruct commit *commit = prio_queue_peek(queue);\n-\t\tbool get_pending = true;\n \t\tint flags = commit->object.flags & all_mask;\n \n \t\tif (!still_interesting && extra <= 0)\n \t\t\tbreak;\n \n+\t\tprio_queue_get(queue);\n+\n \t\tmark_seen(commit, seen_p);\n \t\tif ((flags & all_revs) == all_revs)\n \t\t\tflags |= UNINTERESTING;\n@@ -254,14 +255,8 @@ static void join_revs(struct prio_queue *queue,\n \t\t\tif (mark_seen(p, seen_p) && !still_interesting)\n \t\t\t\textra--;\n \t\t\tp->object.flags |= flags;\n-\t\t\tif (get_pending)\n-\t\t\t\tprio_queue_replace(queue, p);\n-\t\t\telse\n-\t\t\t\tprio_queue_put(queue, p);\n-\t\t\tget_pending = false;\n+\t\t\tprio_queue_put(queue, p);\n \t\t}\n-\t\tif (get_pending)\n-\t\t\tprio_queue_get(queue);\n \t}\n \n \t/*\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 9b3ea46d6f..0fec2f00be 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -1269,7 +1269,7 @@ int get_branch_base_for_tip(struct repository *r,\n \t\t\t    size_t bases_nr)\n {\n \tint best_index = -1;\n-\tstruct commit *branch_point = NULL;\n+\tstruct commit *c, *branch_point = NULL;\n \tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n \tint found_missing_gen = 0;\n \n@@ -1322,8 +1322,7 @@ int get_branch_base_for_tip(struct repository *r,\n \t\tprio_queue_put(&queue, c);\n \t}\n \n-\twhile (queue.nr) {\n-\t\tstruct commit *c = prio_queue_get(&queue);\n+\twhile ((c = prio_queue_get(&queue))) {\n \t\tint best_for_c = get_best(c);\n \t\tint best_for_p, positive;\n \t\tstruct commit *parent;\ndiff --git a/commit.c b/commit.c\nindex fd8723502e..976bfc4618 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -795,24 +795,17 @@ void commit_list_sort_by_date(struct commit_list **list)\n struct commit *pop_most_recent_commit(struct prio_queue *queue,\n \t\t\t\t      unsigned int mark)\n {\n-\tstruct commit *ret = prio_queue_peek(queue);\n-\tint get_pending = 1;\n+\tstruct commit *ret = prio_queue_get(queue);\n \tstruct commit_list *parents = ret->parents;\n \n \twhile (parents) {\n \t\tstruct commit *commit = parents->item;\n \t\tif (!repo_parse_commit(the_repository, commit) && !(commit->object.flags & mark)) {\n \t\t\tcommit->object.flags |= mark;\n-\t\t\tif (get_pending)\n-\t\t\t\tprio_queue_replace(queue, commit);\n-\t\t\telse\n-\t\t\t\tprio_queue_put(queue, commit);\n-\t\t\tget_pending = 0;\n+\t\t\tprio_queue_put(queue, commit);\n \t\t}\n \t\tparents = parents->next;\n \t}\n-\tif (get_pending)\n-\t\tprio_queue_get(queue);\n \treturn ret;\n }\n \ndiff --git a/pack-bitmap-write.c b/pack-bitmap-write.c\nindex 1c8070f99c..f7c63e3027 100644\n--- a/pack-bitmap-write.c\n+++ b/pack-bitmap-write.c\n@@ -513,6 +513,7 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,\n \t\t\t      struct bitmap_index *old_bitmap,\n \t\t\t      const uint32_t *mapping)\n {\n+\tstruct commit *c;\n \tint found;\n \tuint32_t pos;\n \tif (!ent->bitmap)\n@@ -520,9 +521,8 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,\n \n \tprio_queue_put(queue, commit);\n \n-\twhile (queue->nr) {\n+\twhile ((c = prio_queue_get(queue))) {\n \t\tstruct commit_list *p;\n-\t\tstruct commit *c = prio_queue_get(queue);\n \n \t\tif (old_bitmap && mapping) {\n \t\t\tstruct ewah_bitmap *old;\ndiff --git a/prio-queue.c b/prio-queue.c\nindex 9748528ce6..1407f2f801 100644\n--- a/prio-queue.c\n+++ b/prio-queue.c\n@@ -34,12 +34,34 @@ void clear_prio_queue(struct prio_queue *queue)\n \tqueue->nr = 0;\n \tqueue->alloc = 0;\n \tqueue->insertion_ctr = 0;\n+\tqueue->get_pending = 0;\n+}\n+\n+static void sift_down_root(struct prio_queue *queue);\n+\n+static inline void flush_get(struct prio_queue *queue)\n+{\n+\tif (!queue->get_pending)\n+\t\treturn;\n+\tqueue->get_pending = 0;\n+\tif (!--queue->nr)\n+\t\treturn;\n+\tqueue->array[0] = queue->array[queue->nr];\n+\tsift_down_root(queue);\n }\n \n void prio_queue_put(struct prio_queue *queue, void *thing)\n {\n \tsize_t ix, parent;\n \n+\tif (queue->get_pending) {\n+\t\tqueue->get_pending = 0;\n+\t\tqueue->array[0].ctr = queue->insertion_ctr++;\n+\t\tqueue->array[0].data = thing;\n+\t\tsift_down_root(queue);\n+\t\treturn;\n+\t}\n+\n \t/* Append at the end */\n \tALLOC_GROW(queue->array, queue->nr + 1, queue->alloc);\n \tqueue->array[queue->nr].ctr = queue->insertion_ctr++;\n@@ -78,41 +100,24 @@ static void sift_down_root(struct prio_queue *queue)\n \n void *prio_queue_get(struct prio_queue *queue)\n {\n-\tvoid *result;\n+\tflush_get(queue);\n \n \tif (!queue->nr)\n \t\treturn NULL;\n \tif (!queue->compare)\n \t\treturn queue->array[--queue->nr].data; /* LIFO */\n \n-\tresult = queue->array[0].data;\n-\tif (!--queue->nr)\n-\t\treturn result;\n-\n-\tqueue->array[0] = queue->array[queue->nr];\n-\tsift_down_root(queue);\n-\treturn result;\n+\tqueue->get_pending = 1;\n+\treturn queue->array[0].data;\n }\n \n void *prio_queue_peek(struct prio_queue *queue)\n {\n+\tflush_get(queue);\n+\n \tif (!queue->nr)\n \t\treturn NULL;\n \tif (!queue->compare)\n \t\treturn queue->array[queue->nr - 1].data;\n \treturn queue->array[0].data;\n }\n-\n-void prio_queue_replace(struct prio_queue *queue, void *thing)\n-{\n-\tif (!queue->nr) {\n-\t\tprio_queue_put(queue, thing);\n-\t} else if (!queue->compare) {\n-\t\tqueue->array[queue->nr - 1].ctr = queue->insertion_ctr++;\n-\t\tqueue->array[queue->nr - 1].data = thing;\n-\t} else {\n-\t\tqueue->array[0].ctr = queue->insertion_ctr++;\n-\t\tqueue->array[0].data = thing;\n-\t\tsift_down_root(queue);\n-\t}\n-}\ndiff --git a/prio-queue.h b/prio-queue.h\nindex da7fad2f1f..482ab5e71d 100644\n--- a/prio-queue.h\n+++ b/prio-queue.h\n@@ -32,6 +32,7 @@ struct prio_queue {\n \tvoid *cb_data;\n \tsize_t alloc, nr;\n \tstruct prio_queue_entry *array;\n+\tunsigned get_pending;\n };\n \n /*\n@@ -52,13 +53,10 @@ void *prio_queue_get(struct prio_queue *);\n  */\n void *prio_queue_peek(struct prio_queue *);\n \n-/*\n- * Replace the \"thing\" that compares the smallest with a new \"thing\",\n- * like prio_queue_get()+prio_queue_put() would do, but in a more\n- * efficient way.  Does the same as prio_queue_put() if the queue is\n- * empty.\n- */\n-void prio_queue_replace(struct prio_queue *queue, void *thing);\n+static inline size_t prio_queue_size(struct prio_queue *queue)\n+{\n+\treturn queue->nr - queue->get_pending;\n+}\n \n void clear_prio_queue(struct prio_queue *);\n \ndiff --git a/revision.c b/revision.c\nindex 5693618be4..8ce8ffa43d 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -1446,7 +1446,7 @@ static int limit_list(struct rev_info *revs)\n \tstruct commit_list *original_list = revs->commits;\n \tstruct commit_list *newlist = NULL;\n \tstruct commit_list **p = &newlist;\n-\tstruct commit *interesting_cache = NULL;\n+\tstruct commit *commit, *interesting_cache = NULL;\n \tstruct prio_queue queue = { .compare = compare_commits_by_commit_date };\n \n \tif (revs->ancestry_path_implicit_bottoms) {\n@@ -1461,8 +1461,7 @@ static int limit_list(struct rev_info *revs)\n \t\tprio_queue_put(&queue, commit);\n \t}\n \n-\twhile (queue.nr) {\n-\t\tstruct commit *commit = prio_queue_get(&queue);\n+\twhile ((commit = prio_queue_get(&queue))) {\n \t\tstruct object *obj = &commit->object;\n \n \t\tif (commit == interesting_cache)\ndiff --git a/t/unit-tests/u-prio-queue.c b/t/unit-tests/u-prio-queue.c\nindex 63e58114ae..af3e0b8598 100644\n--- a/t/unit-tests/u-prio-queue.c\n+++ b/t/unit-tests/u-prio-queue.c\n@@ -53,13 +53,13 @@ static void test_prio_queue(int *input, size_t input_size,\n \t\t\tprio_queue_reverse(&pq);\n \t\t\tbreak;\n \t\tcase REPLACE:\n-\t\t\tpeek = prio_queue_peek(&pq);\n+\t\t\tget = prio_queue_get(&pq);\n \t\t\tcl_assert(i + 1 < input_size);\n \t\t\tcl_assert(input[i + 1] >= 0);\n \t\t\tcl_assert(j < result_size);\n-\t\t\tcl_assert_equal_i(result[j], show(peek));\n+\t\t\tcl_assert_equal_i(result[j], show(get));\n \t\t\tj++;\n-\t\t\tprio_queue_replace(&pq, &input[++i]);\n+\t\t\tprio_queue_put(&pq, &input[++i]);\n \t\t\tbreak;\n \t\tdefault:\n \t\t\tprio_queue_put(&pq, &input[i]);\ndiff --git a/walker.c b/walker.c\nindex e98eb6da53..e3de77f092 100644\n--- a/walker.c\n+++ b/walker.c\n@@ -84,12 +84,12 @@ static struct prio_queue complete = { compare_commits_by_commit_date };\n static int process_commit(struct walker *walker, struct commit *commit)\n {\n \tstruct commit_list *parents;\n+\tstruct commit *item;\n \n \tif (repo_parse_commit(the_repository, commit))\n \t\treturn -1;\n \n-\twhile (complete.nr) {\n-\t\tstruct commit *item = prio_queue_peek(&complete);\n+\twhile ((item = prio_queue_peek(&complete))) {\n \t\tif (item->date < commit->date)\n \t\t\tbreak;\n \t\tpop_most_recent_commit(&complete, COMPLETE);\n\nbase-commit: 9ac3f193c05c2237e2b14ebaa1149e9fc8a1abe0\n-- \ngitgitgadget\n"},{"id":"544833","messageId":"xmqqqzmjbpfp.fsf@gitster.g","threadId":"65764","inReplyTo":"pull.2140.git.1780757885582.gitgitgadget@gmail.com","subject":"Re: [PATCH] prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-06-06T16:31:54Z","receivedAt":"2026-06-06T16:31:58Z","isPatch":true,"body":"\"Kristofer Karlsson via GitGitGadget\" <gitgitgadget@gmail.com>\nwrites:\n\n> Add prio_queue_size() for callers that need the logical element\n> count, since the physical nr may temporarily include a\n> pending-removal element.\n\nMany code paths used to learn how many elements it logically has by\ndirectly peeking into .nr member of the prio_queue struct.  Now they\nshould call this new helper function, and you converted some in this\npatch.\n\nHow can we be sure that all such users of prio_queue has been\nconverted?  Are direct references to .nr member, outside of the\nprio-queue.c implementation, all now suspect?\n\nFor example, object-name.c:get_oid_oneline() uses a prio-queue\n\"copy\", and loops \"while (copy.nr)\".  In the loop, it calls\npop_most_recent_commit(), which does a get followed by put of its\nparents.  If the get become hanging (e.g., root commit, causing no\n_put() performed in pop_most_recent_commit()), would copy.nr still\nremain 1 but logically no elements remain in the queue.\n\nThere seem to be other direct peeking of .nr member remaining in the\ncode.  Perhaps the member should be renamed to catch in-flight\ntopics that add more users of prio-queue that peek into the .nr\nmember, or something like that.\n"},{"id":"544834","messageId":"CAL71e4MbC+tdTuN6p1HiHtE1XYuS1gBM-KSejFZJ1wbftxNveg@mail.gmail.com","threadId":"65764","inReplyTo":"xmqqqzmjbpfp.fsf@gitster.g","subject":"Re: [PATCH] prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-06-06T17:24:07Z","receivedAt":"2026-06-06T17:24:19Z","isPatch":true,"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> How can we be sure that all such users of prio_queue has been\n> converted?  Are direct references to .nr member, outside of the\n> prio-queue.c implementation, all now suspect?\n\nYou're right, and the patch is thus broken in its current state.\n\nI did a rename of .nr to ._nr on the branch and rebuilt -- that\nimmediately found several callers I missed:\n\n - object-name.c: get_oid_oneline()\n   (like you also found)\n - fetch-pack.c: mark_recent_complete_commits()\n - builtin/last-modified.c: last_modified_run()\n - path-walk.c: walk_objects_by_path()\n - commit-reach.c: queue_has_nonstale()\n\nThe describe.c and show-branch.c callers already compensate for\nget_pending in their iteration bounds, but they still reach into\n.nr directly.\n\n> Perhaps the member should be renamed to catch in-flight topics\n> that add more users of prio-queue that peek into the .nr member,\n> or something like that.\n\nAgreed, that's the right fix. I looked for existing ways of marking\nfields as private, internal or hidden but the only thing I found was\nthe convention of using a code comment: /* for internal use only */\n\nI will apply a rename and submit a v2. Perhaps something like\nnr_internal to make it look less like a public API.\n"},{"id":"544835","messageId":"pull.2140.v2.git.1780772477.gitgitgadget@gmail.com","threadId":"65764","inReplyTo":"pull.2140.git.1780757885582.gitgitgadget@gmail.com","subject":"[PATCH v2 0/2] prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-06-06T19:01:14Z","receivedAt":"2026-06-06T19:01:19Z","isPatch":true,"body":"Rene's lazy_queue wrapper in describe.c was a clever optimization -- by\ndeferring the get, a following put becomes a simple replace, avoiding a full\nremove-rebalance-insert cycle.\n\nIt turns out this pattern is so common in git's traversal code that it makes\nsense to fold it into prio_queue itself. Gets and puts are interleaved in\nvirtually every commit walk, so the fusion is essentially always a win.\n\nThis is mostly a code simplification -- three callers had independently\nreimplemented the same optimization, and they all collapse to plain get+put\nnow. The 3-6% speedup on traversal-heavy workloads is a nice bonus.\n\nMore details and benchmark numbers in the commit message. Benchmarks were\nrun on next which includes kk/commit-reach-optim -- those results represent\nthe more realistic end state.\n\nRelated to but independent of the cascade sift-down work in\nkk/prio-queue-cascade-sift -- the two can land in either order.\n\nChanges since v1:\n\n * Added a second commit that renames .nr to .nr_internal so that direct\n   access from outside prio-queue.c is a compile error. Verified that after\n   the rename, only prio-queue.c references nr_internal.\n\n * Added prio_queue_for_each() macro for callers that need to walk all\n   elements (describe.c, show-branch.c, commit-reach.c, revision.c,\n   negotiator/skipping.c).\n\n * Converted remaining .nr loop conditions to use\n   prio_queue_get()/prio_queue_peek() as the loop condition, or\n   prio_queue_size() where get/peek isn't suitable.\n\n * Fixed several callers missed in v1 (object-name.c, fetch-pack.c,\n   path-walk.c, pack-bitmap-write.c, negotiator/default.c,\n   negotiator/skipping.c, revision.c, builtin/last-modified.c).\n\nKristofer Karlsson (2):\n  prio-queue: fold lazy_queue into prio_queue for automatic get+put\n    fusion\n  prio-queue: rename .nr to .nr_internal to prevent direct access\n\n builtin/describe.c          | 70 ++++++++-------------------------\n builtin/last-modified.c     |  7 ++--\n builtin/show-branch.c       | 24 +++++-------\n commit-reach.c              | 24 ++++++------\n commit.c                    | 11 +-----\n fetch-pack.c                |  4 +-\n negotiator/default.c        |  4 +-\n negotiator/skipping.c       | 12 +++---\n object-name.c               |  2 +-\n pack-bitmap-write.c         | 10 ++---\n path-walk.c                 |  8 ++--\n prio-queue.c                | 77 ++++++++++++++++++++-----------------\n prio-queue.h                | 19 +++++----\n revision.c                  | 16 ++++----\n t/unit-tests/u-prio-queue.c |  6 +--\n walker.c                    |  4 +-\n 16 files changed, 129 insertions(+), 169 deletions(-)\n\n\nbase-commit: 9ac3f193c05c2237e2b14ebaa1149e9fc8a1abe0\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-2140%2Fspkrka%2Flazy-prio-queue-pr-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2140/spkrka/lazy-prio-queue-pr-v2\nPull-Request: https://github.com/gitgitgadget/git/pull/2140\n\nRange-diff vs v1:\n\n 1:  29af24445e = 1:  29af24445e prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion\n -:  ---------- > 2:  bb8b0f78f1 prio-queue: rename .nr to .nr_internal to prevent direct access\n\n-- \ngitgitgadget\n"},{"id":"544836","messageId":"29af24445edac2a8149635505871abcf5b024cd8.1780772477.git.gitgitgadget@gmail.com","threadId":"65764","inReplyTo":"pull.2140.v2.git.1780772477.gitgitgadget@gmail.com","subject":"[PATCH v2 1/2] prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-06-06T19:01:15Z","receivedAt":"2026-06-06T19:01:21Z","isPatch":true,"body":"From: Kristofer Karlsson <krka@spotify.com>\n\nDefer the actual removal in prio_queue_get() until the next\noperation.  If that next operation is a prio_queue_put(), the\nremoval and insertion are fused into a single replace — writing\nthe new element at the root and sifting it down — which avoids\na full remove-rebalance-insert cycle.\n\nThis matches the dominant usage pattern in git's commit traversal:\nget a commit, then put its parents.  The first parent insertion\nafter each get is now a replace operation automatically.\n\nThis generalizes the lazy_queue pattern from builtin/describe.c\n(introduced in 08bb69d70f) into prio_queue itself.  Three callers\nindependently implemented the same get+put fusion:\n\n  - builtin/describe.c had a full lazy_queue wrapper\n  - commit.c:pop_most_recent_commit() reimplements the same\n    get_pending flag with peek+replace\n  - builtin/show-branch.c:join_revs() used the same peek+replace\n    pattern\n\nAll three now collapse to plain _get() and _put(),\nwith the data structure handling the fusion internally.\n\nRemove prio_queue_replace() since no external callers remain.\nAdd prio_queue_size() for callers that need the logical element\ncount, since the physical nr may temporarily include a\npending-removal element.\n\nBenchmarked on a large monorepo (10-15 interleaved runs, 1 warmup):\n\n  Command                       base    patched  speedup\n  merge-base --all A A~1000     3.88s   3.77s    1.03x\n  rev-list --count A~1000..A    3.57s   3.43s    1.04x\n  log --oneline A~1000..A       3.70s   3.49s    1.06x\n  rev-parse :/pattern           365ms   364ms    1.00x\n  describe HEAD (linux.git)     184ms   190ms    1.00x\n\nNo regressions in any scenario.\n\nSigned-off-by: Kristofer Karlsson <krka@spotify.com>\n---\n builtin/describe.c          | 67 +++++++++----------------------------\n builtin/last-modified.c     |  4 +--\n builtin/show-branch.c       | 17 ++++------\n commit-reach.c              |  5 ++-\n commit.c                    | 11 ++----\n pack-bitmap-write.c         |  4 +--\n prio-queue.c                | 49 +++++++++++++++------------\n prio-queue.h                | 12 +++----\n revision.c                  |  5 ++-\n t/unit-tests/u-prio-queue.c |  6 ++--\n walker.c                    |  4 +--\n 11 files changed, 68 insertions(+), 116 deletions(-)\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 1c47d7c0b7..85564f3487 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -251,56 +251,20 @@ static int compare_pt(const void *a_, const void *b_)\n \treturn 0;\n }\n \n-struct lazy_queue {\n-\tstruct prio_queue queue;\n-\tbool get_pending;\n-};\n-\n-#define LAZY_QUEUE_INIT { { compare_commits_by_commit_date }, false }\n-\n-static void *lazy_queue_get(struct lazy_queue *queue)\n-{\n-\tif (queue->get_pending)\n-\t\tprio_queue_get(&queue->queue);\n-\telse\n-\t\tqueue->get_pending = true;\n-\treturn prio_queue_peek(&queue->queue);\n-}\n-\n-static void lazy_queue_put(struct lazy_queue *queue, void *thing)\n-{\n-\tif (queue->get_pending)\n-\t\tprio_queue_replace(&queue->queue, thing);\n-\telse\n-\t\tprio_queue_put(&queue->queue, thing);\n-\tqueue->get_pending = false;\n-}\n-\n-static bool lazy_queue_empty(const struct lazy_queue *queue)\n-{\n-\treturn queue->queue.nr == (queue->get_pending ? 1 : 0);\n-}\n-\n-static void lazy_queue_clear(struct lazy_queue *queue)\n-{\n-\tclear_prio_queue(&queue->queue);\n-\tqueue->get_pending = false;\n-}\n-\n-static unsigned long finish_depth_computation(struct lazy_queue *queue,\n+static unsigned long finish_depth_computation(struct prio_queue *queue,\n \t\t\t\t\t      struct possible_tag *best)\n {\n \tunsigned long seen_commits = 0;\n \tstruct oidset unflagged = OIDSET_INIT;\n+\tstruct commit *c;\n \n-\tfor (size_t i = queue->get_pending ? 1 : 0; i < queue->queue.nr; i++) {\n-\t\tstruct commit *commit = queue->queue.array[i].data;\n+\tfor (size_t i = queue->get_pending; i < queue->nr; i++) {\n+\t\tstruct commit *commit = queue->array[i].data;\n \t\tif (!(commit->object.flags & best->flag_within))\n \t\t\toidset_insert(&unflagged, &commit->object.oid);\n \t}\n \n-\twhile (!lazy_queue_empty(queue)) {\n-\t\tstruct commit *c = lazy_queue_get(queue);\n+\twhile ((c = prio_queue_get(queue))) {\n \t\tstruct commit_list *parents = c->parents;\n \t\tseen_commits++;\n \t\tif (c->object.flags & best->flag_within) {\n@@ -316,7 +280,7 @@ static unsigned long finish_depth_computation(struct lazy_queue *queue,\n \t\t\trepo_parse_commit(the_repository, p);\n \t\t\tseen = p->object.flags & SEEN;\n \t\t\tif (!seen)\n-\t\t\t\tlazy_queue_put(queue, p);\n+\t\t\t\tprio_queue_put(queue, p);\n \t\t\tflag_before = p->object.flags & best->flag_within;\n \t\t\tp->object.flags |= c->object.flags;\n \t\t\tflag_after = p->object.flags & best->flag_within;\n@@ -364,8 +328,8 @@ static void append_suffix(int depth, const struct object_id *oid, struct strbuf\n \n static void describe_commit(struct commit *cmit, struct strbuf *dst)\n {\n-\tstruct commit *gave_up_on = NULL;\n-\tstruct lazy_queue queue = LAZY_QUEUE_INIT;\n+\tstruct commit *c, *gave_up_on = NULL;\n+\tstruct prio_queue queue = { compare_commits_by_commit_date };\n \tstruct commit_name *n;\n \tstruct possible_tag all_matches[MAX_TAGS];\n \tunsigned int match_cnt = 0, annotated_cnt = 0, cur_match;\n@@ -407,9 +371,8 @@ static void describe_commit(struct commit *cmit, struct strbuf *dst)\n \t}\n \n \tcmit->object.flags = SEEN;\n-\tlazy_queue_put(&queue, cmit);\n-\twhile (!lazy_queue_empty(&queue)) {\n-\t\tstruct commit *c = lazy_queue_get(&queue);\n+\tprio_queue_put(&queue, cmit);\n+\twhile ((c = prio_queue_get(&queue))) {\n \t\tstruct commit_list *parents = c->parents;\n \t\tstruct commit_name **slot;\n \n@@ -443,7 +406,7 @@ static void describe_commit(struct commit *cmit, struct strbuf *dst)\n \t\t\t\tt->depth++;\n \t\t}\n \t\t/* Stop if last remaining path already covered by best candidate(s) */\n-\t\tif (annotated_cnt && lazy_queue_empty(&queue)) {\n+\t\tif (annotated_cnt && !prio_queue_size(&queue)) {\n \t\t\tint best_depth = INT_MAX;\n \t\t\tunsigned best_within = 0;\n \t\t\tfor (cur_match = 0; cur_match < match_cnt; cur_match++) {\n@@ -466,7 +429,7 @@ static void describe_commit(struct commit *cmit, struct strbuf *dst)\n \t\t\tstruct commit *p = parents->item;\n \t\t\trepo_parse_commit(the_repository, p);\n \t\t\tif (!(p->object.flags & SEEN))\n-\t\t\t\tlazy_queue_put(&queue, p);\n+\t\t\t\tprio_queue_put(&queue, p);\n \t\t\tp->object.flags |= c->object.flags;\n \t\t\tparents = parents->next;\n \n@@ -481,7 +444,7 @@ static void describe_commit(struct commit *cmit, struct strbuf *dst)\n \t\t\tstrbuf_add_unique_abbrev(dst, cmit_oid, abbrev);\n \t\t\tif (suffix)\n \t\t\t\tstrbuf_addstr(dst, suffix);\n-\t\t\tlazy_queue_clear(&queue);\n+\t\t\tclear_prio_queue(&queue);\n \t\t\treturn;\n \t\t}\n \t\tif (unannotated_cnt)\n@@ -497,11 +460,11 @@ static void describe_commit(struct commit *cmit, struct strbuf *dst)\n \tQSORT(all_matches, match_cnt, compare_pt);\n \n \tif (gave_up_on) {\n-\t\tlazy_queue_put(&queue, gave_up_on);\n+\t\tprio_queue_put(&queue, gave_up_on);\n \t\tseen_commits--;\n \t}\n \tseen_commits += finish_depth_computation(&queue, &all_matches[0]);\n-\tlazy_queue_clear(&queue);\n+\tclear_prio_queue(&queue);\n \n \tif (debug) {\n \t\tstatic int label_width = -1;\ndiff --git a/builtin/last-modified.c b/builtin/last-modified.c\nindex 8900ceece1..df2a508244 100644\n--- a/builtin/last-modified.c\n+++ b/builtin/last-modified.c\n@@ -344,6 +344,7 @@ static void process_parent(struct last_modified *lm,\n static int last_modified_run(struct last_modified *lm)\n {\n \tint max_count, queue_popped = 0;\n+\tstruct commit *c;\n \tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n \tstruct prio_queue not_queue = { compare_commits_by_gen_then_commit_date };\n \tstruct commit_list *list;\n@@ -389,10 +390,9 @@ static int last_modified_run(struct last_modified *lm)\n \t\t}\n \t}\n \n-\twhile (queue.nr) {\n+\twhile ((c = prio_queue_get(&queue))) {\n \t\tint parent_i;\n \t\tstruct commit_list *p;\n-\t\tstruct commit *c = prio_queue_get(&queue);\n \t\tstruct bitmap *active_c = active_paths_for(lm, c);\n \n \t\tif ((0 <= max_count && max_count < ++queue_popped) ||\ndiff --git a/builtin/show-branch.c b/builtin/show-branch.c\nindex f02831b085..9f7f28f339 100644\n--- a/builtin/show-branch.c\n+++ b/builtin/show-branch.c\n@@ -62,7 +62,7 @@ static const char *get_color_reset_code(void)\n \n static struct commit *interesting(struct prio_queue *queue)\n {\n-\tfor (size_t i = 0; i < queue->nr; i++) {\n+\tfor (size_t i = queue->get_pending; i < queue->nr; i++) {\n \t\tstruct commit *commit = queue->array[i].data;\n \t\tif (commit->object.flags & UNINTERESTING)\n \t\t\tcontinue;\n@@ -228,17 +228,18 @@ static void join_revs(struct prio_queue *queue,\n {\n \tint all_mask = ((1u << (REV_SHIFT + num_rev)) - 1);\n \tint all_revs = all_mask & ~((1u << REV_SHIFT) - 1);\n+\tstruct commit *commit;\n \n-\twhile (queue->nr) {\n+\twhile ((commit = prio_queue_peek(queue))) {\n \t\tstruct commit_list *parents;\n \t\tint still_interesting = !!interesting(queue);\n-\t\tstruct commit *commit = prio_queue_peek(queue);\n-\t\tbool get_pending = true;\n \t\tint flags = commit->object.flags & all_mask;\n \n \t\tif (!still_interesting && extra <= 0)\n \t\t\tbreak;\n \n+\t\tprio_queue_get(queue);\n+\n \t\tmark_seen(commit, seen_p);\n \t\tif ((flags & all_revs) == all_revs)\n \t\t\tflags |= UNINTERESTING;\n@@ -254,14 +255,8 @@ static void join_revs(struct prio_queue *queue,\n \t\t\tif (mark_seen(p, seen_p) && !still_interesting)\n \t\t\t\textra--;\n \t\t\tp->object.flags |= flags;\n-\t\t\tif (get_pending)\n-\t\t\t\tprio_queue_replace(queue, p);\n-\t\t\telse\n-\t\t\t\tprio_queue_put(queue, p);\n-\t\t\tget_pending = false;\n+\t\t\tprio_queue_put(queue, p);\n \t\t}\n-\t\tif (get_pending)\n-\t\t\tprio_queue_get(queue);\n \t}\n \n \t/*\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 9b3ea46d6f..0fec2f00be 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -1269,7 +1269,7 @@ int get_branch_base_for_tip(struct repository *r,\n \t\t\t    size_t bases_nr)\n {\n \tint best_index = -1;\n-\tstruct commit *branch_point = NULL;\n+\tstruct commit *c, *branch_point = NULL;\n \tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n \tint found_missing_gen = 0;\n \n@@ -1322,8 +1322,7 @@ int get_branch_base_for_tip(struct repository *r,\n \t\tprio_queue_put(&queue, c);\n \t}\n \n-\twhile (queue.nr) {\n-\t\tstruct commit *c = prio_queue_get(&queue);\n+\twhile ((c = prio_queue_get(&queue))) {\n \t\tint best_for_c = get_best(c);\n \t\tint best_for_p, positive;\n \t\tstruct commit *parent;\ndiff --git a/commit.c b/commit.c\nindex fd8723502e..976bfc4618 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -795,24 +795,17 @@ void commit_list_sort_by_date(struct commit_list **list)\n struct commit *pop_most_recent_commit(struct prio_queue *queue,\n \t\t\t\t      unsigned int mark)\n {\n-\tstruct commit *ret = prio_queue_peek(queue);\n-\tint get_pending = 1;\n+\tstruct commit *ret = prio_queue_get(queue);\n \tstruct commit_list *parents = ret->parents;\n \n \twhile (parents) {\n \t\tstruct commit *commit = parents->item;\n \t\tif (!repo_parse_commit(the_repository, commit) && !(commit->object.flags & mark)) {\n \t\t\tcommit->object.flags |= mark;\n-\t\t\tif (get_pending)\n-\t\t\t\tprio_queue_replace(queue, commit);\n-\t\t\telse\n-\t\t\t\tprio_queue_put(queue, commit);\n-\t\t\tget_pending = 0;\n+\t\t\tprio_queue_put(queue, commit);\n \t\t}\n \t\tparents = parents->next;\n \t}\n-\tif (get_pending)\n-\t\tprio_queue_get(queue);\n \treturn ret;\n }\n \ndiff --git a/pack-bitmap-write.c b/pack-bitmap-write.c\nindex 1c8070f99c..f7c63e3027 100644\n--- a/pack-bitmap-write.c\n+++ b/pack-bitmap-write.c\n@@ -513,6 +513,7 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,\n \t\t\t      struct bitmap_index *old_bitmap,\n \t\t\t      const uint32_t *mapping)\n {\n+\tstruct commit *c;\n \tint found;\n \tuint32_t pos;\n \tif (!ent->bitmap)\n@@ -520,9 +521,8 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,\n \n \tprio_queue_put(queue, commit);\n \n-\twhile (queue->nr) {\n+\twhile ((c = prio_queue_get(queue))) {\n \t\tstruct commit_list *p;\n-\t\tstruct commit *c = prio_queue_get(queue);\n \n \t\tif (old_bitmap && mapping) {\n \t\t\tstruct ewah_bitmap *old;\ndiff --git a/prio-queue.c b/prio-queue.c\nindex 9748528ce6..1407f2f801 100644\n--- a/prio-queue.c\n+++ b/prio-queue.c\n@@ -34,12 +34,34 @@ void clear_prio_queue(struct prio_queue *queue)\n \tqueue->nr = 0;\n \tqueue->alloc = 0;\n \tqueue->insertion_ctr = 0;\n+\tqueue->get_pending = 0;\n+}\n+\n+static void sift_down_root(struct prio_queue *queue);\n+\n+static inline void flush_get(struct prio_queue *queue)\n+{\n+\tif (!queue->get_pending)\n+\t\treturn;\n+\tqueue->get_pending = 0;\n+\tif (!--queue->nr)\n+\t\treturn;\n+\tqueue->array[0] = queue->array[queue->nr];\n+\tsift_down_root(queue);\n }\n \n void prio_queue_put(struct prio_queue *queue, void *thing)\n {\n \tsize_t ix, parent;\n \n+\tif (queue->get_pending) {\n+\t\tqueue->get_pending = 0;\n+\t\tqueue->array[0].ctr = queue->insertion_ctr++;\n+\t\tqueue->array[0].data = thing;\n+\t\tsift_down_root(queue);\n+\t\treturn;\n+\t}\n+\n \t/* Append at the end */\n \tALLOC_GROW(queue->array, queue->nr + 1, queue->alloc);\n \tqueue->array[queue->nr].ctr = queue->insertion_ctr++;\n@@ -78,41 +100,24 @@ static void sift_down_root(struct prio_queue *queue)\n \n void *prio_queue_get(struct prio_queue *queue)\n {\n-\tvoid *result;\n+\tflush_get(queue);\n \n \tif (!queue->nr)\n \t\treturn NULL;\n \tif (!queue->compare)\n \t\treturn queue->array[--queue->nr].data; /* LIFO */\n \n-\tresult = queue->array[0].data;\n-\tif (!--queue->nr)\n-\t\treturn result;\n-\n-\tqueue->array[0] = queue->array[queue->nr];\n-\tsift_down_root(queue);\n-\treturn result;\n+\tqueue->get_pending = 1;\n+\treturn queue->array[0].data;\n }\n \n void *prio_queue_peek(struct prio_queue *queue)\n {\n+\tflush_get(queue);\n+\n \tif (!queue->nr)\n \t\treturn NULL;\n \tif (!queue->compare)\n \t\treturn queue->array[queue->nr - 1].data;\n \treturn queue->array[0].data;\n }\n-\n-void prio_queue_replace(struct prio_queue *queue, void *thing)\n-{\n-\tif (!queue->nr) {\n-\t\tprio_queue_put(queue, thing);\n-\t} else if (!queue->compare) {\n-\t\tqueue->array[queue->nr - 1].ctr = queue->insertion_ctr++;\n-\t\tqueue->array[queue->nr - 1].data = thing;\n-\t} else {\n-\t\tqueue->array[0].ctr = queue->insertion_ctr++;\n-\t\tqueue->array[0].data = thing;\n-\t\tsift_down_root(queue);\n-\t}\n-}\ndiff --git a/prio-queue.h b/prio-queue.h\nindex da7fad2f1f..482ab5e71d 100644\n--- a/prio-queue.h\n+++ b/prio-queue.h\n@@ -32,6 +32,7 @@ struct prio_queue {\n \tvoid *cb_data;\n \tsize_t alloc, nr;\n \tstruct prio_queue_entry *array;\n+\tunsigned get_pending;\n };\n \n /*\n@@ -52,13 +53,10 @@ void *prio_queue_get(struct prio_queue *);\n  */\n void *prio_queue_peek(struct prio_queue *);\n \n-/*\n- * Replace the \"thing\" that compares the smallest with a new \"thing\",\n- * like prio_queue_get()+prio_queue_put() would do, but in a more\n- * efficient way.  Does the same as prio_queue_put() if the queue is\n- * empty.\n- */\n-void prio_queue_replace(struct prio_queue *queue, void *thing);\n+static inline size_t prio_queue_size(struct prio_queue *queue)\n+{\n+\treturn queue->nr - queue->get_pending;\n+}\n \n void clear_prio_queue(struct prio_queue *);\n \ndiff --git a/revision.c b/revision.c\nindex 5693618be4..8ce8ffa43d 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -1446,7 +1446,7 @@ static int limit_list(struct rev_info *revs)\n \tstruct commit_list *original_list = revs->commits;\n \tstruct commit_list *newlist = NULL;\n \tstruct commit_list **p = &newlist;\n-\tstruct commit *interesting_cache = NULL;\n+\tstruct commit *commit, *interesting_cache = NULL;\n \tstruct prio_queue queue = { .compare = compare_commits_by_commit_date };\n \n \tif (revs->ancestry_path_implicit_bottoms) {\n@@ -1461,8 +1461,7 @@ static int limit_list(struct rev_info *revs)\n \t\tprio_queue_put(&queue, commit);\n \t}\n \n-\twhile (queue.nr) {\n-\t\tstruct commit *commit = prio_queue_get(&queue);\n+\twhile ((commit = prio_queue_get(&queue))) {\n \t\tstruct object *obj = &commit->object;\n \n \t\tif (commit == interesting_cache)\ndiff --git a/t/unit-tests/u-prio-queue.c b/t/unit-tests/u-prio-queue.c\nindex 63e58114ae..af3e0b8598 100644\n--- a/t/unit-tests/u-prio-queue.c\n+++ b/t/unit-tests/u-prio-queue.c\n@@ -53,13 +53,13 @@ static void test_prio_queue(int *input, size_t input_size,\n \t\t\tprio_queue_reverse(&pq);\n \t\t\tbreak;\n \t\tcase REPLACE:\n-\t\t\tpeek = prio_queue_peek(&pq);\n+\t\t\tget = prio_queue_get(&pq);\n \t\t\tcl_assert(i + 1 < input_size);\n \t\t\tcl_assert(input[i + 1] >= 0);\n \t\t\tcl_assert(j < result_size);\n-\t\t\tcl_assert_equal_i(result[j], show(peek));\n+\t\t\tcl_assert_equal_i(result[j], show(get));\n \t\t\tj++;\n-\t\t\tprio_queue_replace(&pq, &input[++i]);\n+\t\t\tprio_queue_put(&pq, &input[++i]);\n \t\t\tbreak;\n \t\tdefault:\n \t\t\tprio_queue_put(&pq, &input[i]);\ndiff --git a/walker.c b/walker.c\nindex e98eb6da53..e3de77f092 100644\n--- a/walker.c\n+++ b/walker.c\n@@ -84,12 +84,12 @@ static struct prio_queue complete = { compare_commits_by_commit_date };\n static int process_commit(struct walker *walker, struct commit *commit)\n {\n \tstruct commit_list *parents;\n+\tstruct commit *item;\n \n \tif (repo_parse_commit(the_repository, commit))\n \t\treturn -1;\n \n-\twhile (complete.nr) {\n-\t\tstruct commit *item = prio_queue_peek(&complete);\n+\twhile ((item = prio_queue_peek(&complete))) {\n \t\tif (item->date < commit->date)\n \t\t\tbreak;\n \t\tpop_most_recent_commit(&complete, COMPLETE);\n-- \ngitgitgadget\n\n"},{"id":"544837","messageId":"bb8b0f78f192398a3233df104849880e4058d53b.1780772477.git.gitgitgadget@gmail.com","threadId":"65764","inReplyTo":"pull.2140.v2.git.1780772477.gitgitgadget@gmail.com","subject":"[PATCH v2 2/2] prio-queue: rename .nr to .nr_internal to prevent direct access","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-06-06T19:01:16Z","receivedAt":"2026-06-06T19:01:22Z","isPatch":true,"body":"From: Kristofer Karlsson <krka@spotify.com>\n\nRename the .nr member to .nr_internal so that callers outside\nprio-queue.c that directly reference .nr get a compilation error.\nThis catches both existing misuse and future in-flight topics.\n\nAdd prio_queue_for_each() macro for callers that need to walk all\nelements in the queue, accounting for the get_pending offset.\n\nConvert all external .nr users:\n - Loop conditions: use prio_queue_size(), prio_queue_get(), or\n   prio_queue_peek() as the loop condition\n - Array iterations: use prio_queue_for_each()\n\nSigned-off-by: Kristofer Karlsson <krka@spotify.com>\n---\n builtin/describe.c      |  7 +++----\n builtin/last-modified.c |  5 ++---\n builtin/show-branch.c   |  9 ++++-----\n commit-reach.c          | 19 +++++++++++--------\n fetch-pack.c            |  4 ++--\n negotiator/default.c    |  4 +++-\n negotiator/skipping.c   | 12 +++++++-----\n object-name.c           |  2 +-\n pack-bitmap-write.c     |  6 +++---\n path-walk.c             |  8 ++++----\n prio-queue.c            | 32 ++++++++++++++++----------------\n prio-queue.h            |  9 +++++++--\n revision.c              | 11 +++++------\n 13 files changed, 68 insertions(+), 60 deletions(-)\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 85564f3487..64424543ef 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -258,10 +258,9 @@ static unsigned long finish_depth_computation(struct prio_queue *queue,\n \tstruct oidset unflagged = OIDSET_INIT;\n \tstruct commit *c;\n \n-\tfor (size_t i = queue->get_pending; i < queue->nr; i++) {\n-\t\tstruct commit *commit = queue->array[i].data;\n-\t\tif (!(commit->object.flags & best->flag_within))\n-\t\t\toidset_insert(&unflagged, &commit->object.oid);\n+\tprio_queue_for_each(queue, c) {\n+\t\tif (!(c->object.flags & best->flag_within))\n+\t\t\toidset_insert(&unflagged, &c->object.oid);\n \t}\n \n \twhile ((c = prio_queue_get(queue))) {\ndiff --git a/builtin/last-modified.c b/builtin/last-modified.c\nindex df2a508244..5478182f2e 100644\n--- a/builtin/last-modified.c\n+++ b/builtin/last-modified.c\n@@ -344,7 +344,7 @@ static void process_parent(struct last_modified *lm,\n static int last_modified_run(struct last_modified *lm)\n {\n \tint max_count, queue_popped = 0;\n-\tstruct commit *c;\n+\tstruct commit *c, *n;\n \tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n \tstruct prio_queue not_queue = { compare_commits_by_gen_then_commit_date };\n \tstruct commit_list *list;\n@@ -416,9 +416,8 @@ static int last_modified_run(struct last_modified *lm)\n \t\t */\n \t\trepo_parse_commit(lm->rev.repo, c);\n \n-\t\twhile (not_queue.nr) {\n+\t\twhile ((n = prio_queue_get(&not_queue))) {\n \t\t\tstruct commit_list *np;\n-\t\t\tstruct commit *n = prio_queue_get(&not_queue);\n \n \t\t\trepo_parse_commit(lm->rev.repo, n);\n \ndiff --git a/builtin/show-branch.c b/builtin/show-branch.c\nindex 9f7f28f339..2435e8aeda 100644\n--- a/builtin/show-branch.c\n+++ b/builtin/show-branch.c\n@@ -62,11 +62,10 @@ static const char *get_color_reset_code(void)\n \n static struct commit *interesting(struct prio_queue *queue)\n {\n-\tfor (size_t i = queue->get_pending; i < queue->nr; i++) {\n-\t\tstruct commit *commit = queue->array[i].data;\n-\t\tif (commit->object.flags & UNINTERESTING)\n-\t\t\tcontinue;\n-\t\treturn commit;\n+\tstruct commit *commit;\n+\tprio_queue_for_each(queue, commit) {\n+\t\tif (!(commit->object.flags & UNINTERESTING))\n+\t\t\treturn commit;\n \t}\n \treturn NULL;\n }\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 0fec2f00be..dfe6016cb2 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -41,8 +41,8 @@ static int compare_commits_by_gen(const void *_a, const void *_b)\n \n static int queue_has_nonstale(struct prio_queue *queue)\n {\n-\tfor (size_t i = 0; i < queue->nr; i++) {\n-\t\tstruct commit *commit = queue->array[i].data;\n+\tstruct commit *commit;\n+\tprio_queue_for_each(queue, commit) {\n \t\tif (!(commit->object.flags & STALE))\n \t\t\treturn 1;\n \t}\n@@ -1069,6 +1069,7 @@ void ahead_behind(struct repository *r,\n \t\t  struct commit **commits, size_t commits_nr,\n \t\t  struct ahead_behind_count *counts, size_t counts_nr)\n {\n+\tstruct commit *c;\n \tstruct prio_queue queue = { .compare = compare_commits_by_gen_then_commit_date };\n \tsize_t width = DIV_ROUND_UP(commits_nr, BITS_IN_EWORD);\n \n@@ -1085,17 +1086,19 @@ void ahead_behind(struct repository *r,\n \tinit_bit_arrays(&bit_arrays);\n \n \tfor (size_t i = 0; i < commits_nr; i++) {\n-\t\tstruct commit *c = commits[i];\n-\t\tstruct bitmap *bitmap = get_bit_array(c, width);\n+\t\tstruct bitmap *bitmap;\n+\t\tc = commits[i];\n+\t\tbitmap = get_bit_array(c, width);\n \n \t\tbitmap_set(bitmap, i);\n \t\tinsert_no_dup(&queue, c);\n \t}\n \n \twhile (queue_has_nonstale(&queue)) {\n-\t\tstruct commit *c = prio_queue_get(&queue);\n \t\tstruct commit_list *p;\n-\t\tstruct bitmap *bitmap_c = get_bit_array(c, width);\n+\t\tstruct bitmap *bitmap_c;\n+\t\tc = prio_queue_get(&queue);\n+\t\tbitmap_c = get_bit_array(c, width);\n \n \t\tfor (size_t i = 0; i < counts_nr; i++) {\n \t\t\tint reach_from_tip = !!bitmap_get(bitmap_c, counts[i].tip_index);\n@@ -1135,8 +1138,8 @@ void ahead_behind(struct repository *r,\n \n \t/* STALE is used here, PARENT2 is used by insert_no_dup(). */\n \trepo_clear_commit_marks(r, PARENT2 | STALE);\n-\tfor (size_t i = 0; i < queue.nr; i++)\n-\t\tfree_bit_array(queue.array[i].data);\n+\tprio_queue_for_each(&queue, c)\n+\t\tfree_bit_array(c);\n \tclear_bit_arrays(&bit_arrays);\n \tclear_prio_queue(&queue);\n }\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex 120e01f3cf..29c41132ee 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -662,8 +662,8 @@ static int mark_complete_oid(const struct reference *ref, void *cb_data UNUSED)\n static void mark_recent_complete_commits(struct fetch_pack_args *args,\n \t\t\t\t\t timestamp_t cutoff)\n {\n-\twhile (complete.nr) {\n-\t\tstruct commit *item = prio_queue_peek(&complete);\n+\tstruct commit *item;\n+\twhile ((item = prio_queue_peek(&complete))) {\n \t\tif (item->date < cutoff)\n \t\t\tbreak;\n \t\tprint_verbose(args, _(\"Marking %s as complete\"),\ndiff --git a/negotiator/default.c b/negotiator/default.c\nindex 78d58d57ce..19cdf3808c 100644\n--- a/negotiator/default.c\n+++ b/negotiator/default.c\n@@ -113,10 +113,12 @@ static const struct object_id *get_rev(struct negotiation_state *ns)\n \t\tunsigned int mark;\n \t\tstruct commit_list *parents;\n \n-\t\tif (ns->rev_list.nr == 0 || ns->non_common_revs == 0)\n+\t\tif (ns->non_common_revs == 0)\n \t\t\treturn NULL;\n \n \t\tcommit = prio_queue_get(&ns->rev_list);\n+\t\tif (!commit)\n+\t\t\treturn NULL;\n \t\trepo_parse_commit(the_repository, commit);\n \t\tparents = commit->parents;\n \ndiff --git a/negotiator/skipping.c b/negotiator/skipping.c\nindex 68c9b3b997..db90fa77b5 100644\n--- a/negotiator/skipping.c\n+++ b/negotiator/skipping.c\n@@ -143,8 +143,7 @@ static int push_parent(struct data *data, struct entry *entry,\n \t\t/*\n \t\t * Find the existing entry and use it.\n \t\t */\n-\t\tfor (size_t i = 0; i < data->rev_list.nr; i++) {\n-\t\t\tparent_entry = data->rev_list.array[i].data;\n+\t\tprio_queue_for_each(&data->rev_list, parent_entry) {\n \t\t\tif (parent_entry->commit == to_push)\n \t\t\t\tgoto parent_found;\n \t\t}\n@@ -181,10 +180,12 @@ static const struct object_id *get_rev(struct data *data)\n \t\tstruct commit_list *p;\n \t\tint parent_pushed = 0;\n \n-\t\tif (data->rev_list.nr == 0 || data->non_common_revs == 0)\n+\t\tif (data->non_common_revs == 0)\n \t\t\treturn NULL;\n \n \t\tentry = prio_queue_get(&data->rev_list);\n+\t\tif (!entry)\n+\t\t\treturn NULL;\n \t\tcommit = entry->commit;\n \t\tcommit->object.flags |= POPPED;\n \t\tif (!(commit->object.flags & COMMON))\n@@ -253,8 +254,9 @@ static void have_sent(struct fetch_negotiator *n, struct commit *c)\n static void release(struct fetch_negotiator *n)\n {\n \tstruct data *data = n->data;\n-\tfor (size_t i = 0; i < data->rev_list.nr; i++)\n-\t\tfree(data->rev_list.array[i].data);\n+\tvoid *entry;\n+\tprio_queue_for_each(&data->rev_list, entry)\n+\t\tfree(entry);\n \tclear_prio_queue(&data->rev_list);\n \tFREE_AND_NULL(data);\n }\ndiff --git a/object-name.c b/object-name.c\nindex 9ac86f19c7..2fedfe1761 100644\n--- a/object-name.c\n+++ b/object-name.c\n@@ -1208,7 +1208,7 @@ static int get_oid_oneline(struct repository *r,\n \t\tl->item->object.flags |= ONELINE_SEEN;\n \t\tprio_queue_put(&copy, l->item);\n \t}\n-\twhile (copy.nr) {\n+\twhile (prio_queue_size(&copy)) {\n \t\tconst char *p, *buf;\n \t\tstruct commit *commit;\n \t\tint matches;\ndiff --git a/pack-bitmap-write.c b/pack-bitmap-write.c\nindex f7c63e3027..ed9714b135 100644\n--- a/pack-bitmap-write.c\n+++ b/pack-bitmap-write.c\n@@ -514,6 +514,7 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,\n \t\t\t      const uint32_t *mapping)\n {\n \tstruct commit *c;\n+\tstruct tree *tree;\n \tint found;\n \tuint32_t pos;\n \tif (!ent->bitmap)\n@@ -574,9 +575,8 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,\n \t\t}\n \t}\n \n-\twhile (tree_queue->nr) {\n-\t\tif (fill_bitmap_tree(writer, ent->bitmap,\n-\t\t\t\t     prio_queue_get(tree_queue)) < 0)\n+\twhile ((tree = prio_queue_get(tree_queue))) {\n+\t\tif (fill_bitmap_tree(writer, ent->bitmap, tree) < 0)\n \t\t\treturn -1;\n \t}\n \treturn 0;\ndiff --git a/path-walk.c b/path-walk.c\nindex 94ff90bd15..cf3b2d0765 100644\n--- a/path-walk.c\n+++ b/path-walk.c\n@@ -699,6 +699,7 @@ int walk_objects_by_path(struct path_walk_info *info)\n \tint ret;\n \tsize_t commits_nr = 0, paths_nr = 0;\n \tstruct commit *c;\n+\tchar *path;\n \tstruct type_and_oid_list *root_tree_list;\n \tstruct type_and_oid_list *commit_list;\n \tstruct path_walk_context ctx = {\n@@ -808,8 +809,7 @@ int walk_objects_by_path(struct path_walk_info *info)\n \tfree(commit_list);\n \n \ttrace2_region_enter(\"path-walk\", \"path-walk\", info->revs->repo);\n-\twhile (!ret && ctx.path_stack.nr) {\n-\t\tchar *path = prio_queue_get(&ctx.path_stack);\n+\twhile (!ret && (path = prio_queue_get(&ctx.path_stack))) {\n \t\tpaths_nr++;\n \n \t\tret = walk_path(&ctx, path);\n@@ -821,12 +821,12 @@ int walk_objects_by_path(struct path_walk_info *info)\n \tif (!strmap_empty(&ctx.paths_to_lists)) {\n \t\tstruct hashmap_iter iter;\n \t\tstruct strmap_entry *entry;\n+\t\tchar *path;\n \n \t\tstrmap_for_each_entry(&ctx.paths_to_lists, &iter, entry)\n \t\t\tpush_to_stack(&ctx, entry->key);\n \n-\t\twhile (!ret && ctx.path_stack.nr) {\n-\t\t\tchar *path = prio_queue_get(&ctx.path_stack);\n+\t\twhile (!ret && (path = prio_queue_get(&ctx.path_stack))) {\n \t\t\tpaths_nr++;\n \n \t\t\tret = walk_path(&ctx, path);\ndiff --git a/prio-queue.c b/prio-queue.c\nindex 1407f2f801..d11ca6ac36 100644\n--- a/prio-queue.c\n+++ b/prio-queue.c\n@@ -22,16 +22,16 @@ void prio_queue_reverse(struct prio_queue *queue)\n \n \tif (queue->compare)\n \t\tBUG(\"prio_queue_reverse() on non-LIFO queue\");\n-\tif (!queue->nr)\n+\tif (!queue->nr_internal)\n \t\treturn;\n-\tfor (i = 0; i < (j = (queue->nr - 1) - i); i++)\n+\tfor (i = 0; i < (j = (queue->nr_internal - 1) - i); i++)\n \t\tswap(queue, i, j);\n }\n \n void clear_prio_queue(struct prio_queue *queue)\n {\n \tFREE_AND_NULL(queue->array);\n-\tqueue->nr = 0;\n+\tqueue->nr_internal = 0;\n \tqueue->alloc = 0;\n \tqueue->insertion_ctr = 0;\n \tqueue->get_pending = 0;\n@@ -44,9 +44,9 @@ static inline void flush_get(struct prio_queue *queue)\n \tif (!queue->get_pending)\n \t\treturn;\n \tqueue->get_pending = 0;\n-\tif (!--queue->nr)\n+\tif (!--queue->nr_internal)\n \t\treturn;\n-\tqueue->array[0] = queue->array[queue->nr];\n+\tqueue->array[0] = queue->array[queue->nr_internal];\n \tsift_down_root(queue);\n }\n \n@@ -63,15 +63,15 @@ void prio_queue_put(struct prio_queue *queue, void *thing)\n \t}\n \n \t/* Append at the end */\n-\tALLOC_GROW(queue->array, queue->nr + 1, queue->alloc);\n-\tqueue->array[queue->nr].ctr = queue->insertion_ctr++;\n-\tqueue->array[queue->nr].data = thing;\n-\tqueue->nr++;\n+\tALLOC_GROW(queue->array, queue->nr_internal + 1, queue->alloc);\n+\tqueue->array[queue->nr_internal].ctr = queue->insertion_ctr++;\n+\tqueue->array[queue->nr_internal].data = thing;\n+\tqueue->nr_internal++;\n \tif (!queue->compare)\n \t\treturn; /* LIFO */\n \n \t/* Bubble up the new one */\n-\tfor (ix = queue->nr - 1; ix; ix = parent) {\n+\tfor (ix = queue->nr_internal - 1; ix; ix = parent) {\n \t\tparent = (ix - 1) / 2;\n \t\tif (compare(queue, parent, ix) <= 0)\n \t\t\tbreak;\n@@ -85,9 +85,9 @@ static void sift_down_root(struct prio_queue *queue)\n \tsize_t ix, child;\n \n \t/* Push down the one at the root */\n-\tfor (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {\n+\tfor (ix = 0; ix * 2 + 1 < queue->nr_internal; ix = child) {\n \t\tchild = ix * 2 + 1; /* left */\n-\t\tif (child + 1 < queue->nr &&\n+\t\tif (child + 1 < queue->nr_internal &&\n \t\t    compare(queue, child, child + 1) >= 0)\n \t\t\tchild++; /* use right child */\n \n@@ -102,10 +102,10 @@ void *prio_queue_get(struct prio_queue *queue)\n {\n \tflush_get(queue);\n \n-\tif (!queue->nr)\n+\tif (!queue->nr_internal)\n \t\treturn NULL;\n \tif (!queue->compare)\n-\t\treturn queue->array[--queue->nr].data; /* LIFO */\n+\t\treturn queue->array[--queue->nr_internal].data; /* LIFO */\n \n \tqueue->get_pending = 1;\n \treturn queue->array[0].data;\n@@ -115,9 +115,9 @@ void *prio_queue_peek(struct prio_queue *queue)\n {\n \tflush_get(queue);\n \n-\tif (!queue->nr)\n+\tif (!queue->nr_internal)\n \t\treturn NULL;\n \tif (!queue->compare)\n-\t\treturn queue->array[queue->nr - 1].data;\n+\t\treturn queue->array[queue->nr_internal - 1].data;\n \treturn queue->array[0].data;\n }\ndiff --git a/prio-queue.h b/prio-queue.h\nindex 482ab5e71d..f08ab87691 100644\n--- a/prio-queue.h\n+++ b/prio-queue.h\n@@ -30,7 +30,7 @@ struct prio_queue {\n \tprio_queue_compare_fn compare;\n \tsize_t insertion_ctr;\n \tvoid *cb_data;\n-\tsize_t alloc, nr;\n+\tsize_t alloc, nr_internal; /* use prio_queue_size() for logical count */\n \tstruct prio_queue_entry *array;\n \tunsigned get_pending;\n };\n@@ -55,9 +55,14 @@ void *prio_queue_peek(struct prio_queue *);\n \n static inline size_t prio_queue_size(struct prio_queue *queue)\n {\n-\treturn queue->nr - queue->get_pending;\n+\treturn queue->nr_internal - queue->get_pending;\n }\n \n+#define prio_queue_for_each(queue, it) \\\n+\tfor (size_t pq_ix_ = (queue)->get_pending; \\\n+\t     pq_ix_ < (queue)->nr_internal && ((it) = (queue)->array[pq_ix_].data, 1); \\\n+\t     pq_ix_++)\n+\n void clear_prio_queue(struct prio_queue *);\n \n /* Reverse the LIFO elements */\ndiff --git a/revision.c b/revision.c\nindex 8ce8ffa43d..34e2d146f4 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -476,16 +476,15 @@ static struct commit *handle_commit(struct rev_info *revs,\n static int everybody_uninteresting(struct prio_queue *orig,\n \t\t\t\t   struct commit **interesting_cache)\n {\n-\tsize_t i;\n+\tstruct commit *commit;\n \n \tif (*interesting_cache) {\n-\t\tstruct commit *commit = *interesting_cache;\n+\t\tcommit = *interesting_cache;\n \t\tif (!(commit->object.flags & UNINTERESTING))\n \t\t\treturn 0;\n \t}\n \n-\tfor (i = 0; i < orig->nr; i++) {\n-\t\tstruct commit *commit = orig->array[i].data;\n+\tprio_queue_for_each(orig, commit) {\n \t\tif (commit->object.flags & UNINTERESTING)\n \t\t\tcontinue;\n \n@@ -4027,8 +4026,8 @@ static enum rewrite_result rewrite_one_1(struct rev_info *revs,\n \n static void merge_queue_into_list(struct prio_queue *q, struct commit_list **list)\n {\n-\twhile (q->nr) {\n-\t\tstruct commit *item = prio_queue_peek(q);\n+\tstruct commit *item;\n+\twhile ((item = prio_queue_peek(q))) {\n \t\tstruct commit_list *p = *list;\n \n \t\tif (p && p->item->date >= item->date)\n-- \ngitgitgadget\n"},{"id":"544840","messageId":"fe20bde6-9e86-4162-9bbd-af4d058e499e@web.de","threadId":"65764","inReplyTo":"pull.2140.v2.git.1780772477.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 0/2] prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2026-06-07T07:30:41Z","receivedAt":"2026-06-07T07:30:49Z","isPatch":true,"body":"On 6/6/26 9:01 PM, Kristofer Karlsson via GitGitGadget wrote:\n> Rene's lazy_queue wrapper in describe.c was a clever optimization -- by\n> deferring the get, a following put becomes a simple replace, avoiding a full\n> remove-rebalance-insert cycle.\n> \n> It turns out this pattern is so common in git's traversal code that it makes\n> sense to fold it into prio_queue itself. Gets and puts are interleaved in\n> virtually every commit walk, so the fusion is essentially always a win.\n> \n> This is mostly a code simplification -- three callers had independently\n> reimplemented the same optimization, and they all collapse to plain get+put\n> now. The 3-6% speedup on traversal-heavy workloads is a nice bonus.\n> \n> More details and benchmark numbers in the commit message. Benchmarks were\n> run on next which includes kk/commit-reach-optim -- those results represent\n> the more realistic end state.\n> \n> Related to but independent of the cascade sift-down work in\n> kk/prio-queue-cascade-sift -- the two can land in either order.\n> \n> Changes since v1:\n> \n>  * Added a second commit that renames .nr to .nr_internal so that direct\n>    access from outside prio-queue.c is a compile error. Verified that after\n>    the rename, only prio-queue.c references nr_internal.\n> \n>  * Added prio_queue_for_each() macro for callers that need to walk all\n>    elements (describe.c, show-branch.c, commit-reach.c, revision.c,\n>    negotiator/skipping.c).\n> \n>  * Converted remaining .nr loop conditions to use\n>    prio_queue_get()/prio_queue_peek() as the loop condition, or\n>    prio_queue_size() where get/peek isn't suitable.\n> \n>  * Fixed several callers missed in v1 (object-name.c, fetch-pack.c,\n>    path-walk.c, pack-bitmap-write.c, negotiator/default.c,\n>    negotiator/skipping.c, revision.c, builtin/last-modified.c).\n> \n> Kristofer Karlsson (2):\n>   prio-queue: fold lazy_queue into prio_queue for automatic get+put\n>     fusion\n>   prio-queue: rename .nr to .nr_internal to prevent direct access\n> \n>  builtin/describe.c          | 70 ++++++++-------------------------\n>  builtin/last-modified.c     |  7 ++--\n>  builtin/show-branch.c       | 24 +++++-------\n>  commit-reach.c              | 24 ++++++------\n>  commit.c                    | 11 +-----\n>  fetch-pack.c                |  4 +-\n>  negotiator/default.c        |  4 +-\n>  negotiator/skipping.c       | 12 +++---\n>  object-name.c               |  2 +-\n>  pack-bitmap-write.c         | 10 ++---\n>  path-walk.c                 |  8 ++--\n>  prio-queue.c                | 77 ++++++++++++++++++++-----------------\n>  prio-queue.h                | 19 +++++----\n>  revision.c                  | 16 ++++----\n>  t/unit-tests/u-prio-queue.c |  6 +--\n>  walker.c                    |  4 +-\n>  16 files changed, 129 insertions(+), 169 deletions(-)\n> \n> \n> base-commit: 9ac3f193c05c2237e2b14ebaa1149e9fc8a1abe0\n> Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2140%2Fspkrka%2Flazy-prio-queue-pr-v2\n> Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2140/spkrka/lazy-prio-queue-pr-v2\n> Pull-Request: https://github.com/gitgitgadget/git/pull/2140\n> \n> Range-diff vs v1:\n> \n>  1:  29af24445e = 1:  29af24445e prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion\n>  -:  ---------- > 2:  bb8b0f78f1 prio-queue: rename .nr to .nr_internal to prevent direct access\n> \n\nMy earlier attempt in <90270818-c52b-4611-8da2-6cee20628fc2@web.de>\ncopied the last item to the root and decreased .nr, to allow callers to\nscan items and get their count directly.\n\nChecking emptiness by doing the existing calls of prio_queue_peek() and\nprio_queue_get() a bit earlier and scanning using a foreach macro are\nfine as well and arguably cleaner, at the low cost of having to change\nall the callers.\n\nThe result is faster than my attempt, but still slower than the current\ncode in the describe benchmark from 30598ccc4d (describe: use oidset in\nfinish_depth_computation(), 2025-09-02):\n\nBenchmark 1: ./git_main describe $(git rev-list v2.41.0..v2.47.0)\n  Time (mean ± σ):     601.7 ms ±   1.9 ms    [User: 538.6 ms, System: 47.3 ms]\n  Range (min … max):   599.3 ms … 606.5 ms    10 runs\n\nBenchmark 2: ./git_auto_replace describe $(git rev-list v2.41.0..v2.47.0)\n  Time (mean ± σ):     618.0 ms ±   1.1 ms    [User: 554.5 ms, System: 47.6 ms]\n  Range (min … max):   616.7 ms … 620.2 ms    10 runs\n\nBenchmark 3: ./git_fold describe $(git rev-list v2.41.0..v2.47.0)\n  Time (mean ± σ):     609.9 ms ±   0.8 ms    [User: 546.7 ms, System: 47.4 ms]\n  Range (min … max):   608.8 ms … 611.2 ms    10 runs\n\nBenchmark 4: ./git describe $(git rev-list v2.41.0..v2.47.0)\n  Time (mean ± σ):     606.1 ms ±   1.2 ms    [User: 543.7 ms, System: 46.7 ms]\n  Range (min … max):   604.7 ms … 609.1 ms    10 runs\n\nSummary\n  ./git_main describe $(git rev-list v2.41.0..v2.47.0) ran\n    1.01 ± 0.00 times faster than ./git describe $(git rev-list v2.41.0..v2.47.0)\n    1.01 ± 0.00 times faster than ./git_fold describe $(git rev-list v2.41.0..v2.47.0)\n    1.03 ± 0.00 times faster than ./git_auto_replace describe $(git rev-list v2.41.0..v2.47.0)\n\ngit_auto_replace: <90270818-c52b-4611-8da2-6cee20628fc2@web.de> and\n  revert of 08bb69d70f (describe: use prio_queue_replace(), 2025-08-03)\ngit_fold: this series\ngit: this series and the patch below\n\nMy attempt leaves performance on the table by using a bool.  Using\nan unsigned for the flag is measurably faster -- but still slower\nthan your series here.\n\nCalling flush_get() later, when we know that we have items and a\ncompare function, is cleaner, as we never need it in LIFO mode, and\nis also slightly faster (patch below).\n\nStill there's this 1% performance gap to the current code that I\ndon't understand.  Do you see it as well?\n\nRené\n\n---\n prio-queue.c | 7 +++----\n 1 file changed, 3 insertions(+), 4 deletions(-)\n\ndiff --git a/prio-queue.c b/prio-queue.c\nindex d11ca6ac36..45709187d3 100644\n--- a/prio-queue.c\n+++ b/prio-queue.c\n@@ -100,24 +100,23 @@ static void sift_down_root(struct prio_queue *queue)\n \n void *prio_queue_get(struct prio_queue *queue)\n {\n-\tflush_get(queue);\n-\n \tif (!queue->nr_internal)\n \t\treturn NULL;\n \tif (!queue->compare)\n \t\treturn queue->array[--queue->nr_internal].data; /* LIFO */\n \n+\tflush_get(queue);\n \tqueue->get_pending = 1;\n \treturn queue->array[0].data;\n }\n \n void *prio_queue_peek(struct prio_queue *queue)\n {\n-\tflush_get(queue);\n-\n \tif (!queue->nr_internal)\n \t\treturn NULL;\n \tif (!queue->compare)\n \t\treturn queue->array[queue->nr_internal - 1].data;\n+\n+\tflush_get(queue);\n \treturn queue->array[0].data;\n }\n\n"},{"id":"544841","messageId":"CAL71e4NDJtMN+i6E+BwQ=rvM4o8gwuDRUAn5fuQhYnQH_CzCxA@mail.gmail.com","threadId":"65764","inReplyTo":"fe20bde6-9e86-4162-9bbd-af4d058e499e@web.de","subject":"Re: [PATCH v2 0/2] prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-06-07T09:30:13Z","receivedAt":"2026-06-07T09:30:25Z","isPatch":true,"body":"On Sun, 7 Jun 2026 at 09:30, René Scharfe <l.s.r@web.de> wrote:\n>\n> Calling flush_get() later, when we know that we have items and a\n> compare function, is cleaner, as we never need it in LIFO mode, and\n> is also slightly faster (patch below).\n\nThanks for the benchmark and the suggestion to move flush_get()\nbelow the LIFO check - that's cleaner since LIFO never sets\nget_pending.\n\nOne edge case to note: without a second !nr_internal check after\nflush_get(), two consecutive get() calls on a single-element queue\nwill return stale data instead of NULL. I went a step further and\ninlined the flush logic directly into get()/peek(), which also\nremoves the forward declaration.\n\n> Still there's this 1% performance gap to the current code that I\n> don't understand.  Do you see it as well?\n\nYes, I saw a similar trend on my laptop (Core Ultra 7 155U),\nbut with very high variance - the results were too noisy to be\nconclusive even with 20+ runs.\nOn an idle server (Xeon @ 2.20GHz) with much lower variance, all\nthree variants (v2 as posted, your patch, and the inlined version)\ncame out ~1.3% faster than the baseline across 30 interleaved\nruns (p < 0.01). So it seems CPU-dependent - possibly branch\nprediction or code alignment differences between microarchitectures.\n\nResults from the idle server (30 interleaved runs, paired t-test):\n\n  Variant               Avg       SE  vs baseline           95% CI          p\n  -------------- ---------- -------- ------------ ---------------- ----------\n  baseline          2002.5ms     9.2ms   (baseline)\n  v2-posted         1976.6ms     3.2ms      -1.29%    -41 to -11ms     0.0019\n  v2-rene           1977.7ms     3.1ms      -1.24%    -42 to  -8ms     0.0071\n  v2-latest         1975.3ms     1.8ms      -1.36%    -46 to  -9ms     0.0069\n\n  baseline:  9ac3f193c0 (The 11th batch)\n  v2-posted: v2 as sent to the list\n  v2-rene:   v2 + your flush_get patch\n  v2-latest: v2 + inlined flush (for v3)\n\nWill send a v3 with the inlined flush shortly.\n\n- Kristofer\n"},{"id":"544842","messageId":"pull.2140.v3.git.1780832592.gitgitgadget@gmail.com","threadId":"65764","inReplyTo":"pull.2140.v2.git.1780772477.gitgitgadget@gmail.com","subject":"[PATCH v3 0/2] prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-06-07T11:43:09Z","receivedAt":"2026-06-07T11:43:16Z","isPatch":true,"body":"Rene's lazy_queue wrapper in describe.c was a clever optimization -- by\ndeferring the get, a following put becomes a simple replace, avoiding a full\nremove-rebalance-insert cycle.\n\nIt turns out this pattern is so common in git's traversal code that it makes\nsense to fold it into prio_queue itself. Gets and puts are interleaved in\nvirtually every commit walk, so the fusion is essentially always a win.\n\nThis is mostly a code simplification -- three callers had independently\nreimplemented the same optimization, and they all collapse to plain get+put\nnow. The 1.7-2.7% speedup on traversal-heavy workloads is a nice bonus.\n\nMore details and benchmark numbers in the commit message.\n\nRelated to but independent of the cascade sift-down work in\nkk/prio-queue-cascade-sift -- the two can land in either order.\n\nChanges in v3:\n\n * Adopted Rene's suggestion to move the flush logic below the LIFO\n   early-return (LIFO mode never sets get_pending, so flushing there is a\n   no-op).\n\n * Went a step further and inlined the flush logic directly into get() and\n   peek(), eliminating the flush_get() helper and its forward declaration of\n   sift_down_root().\n\n * Updated benchmark numbers with more rigorous methodology: 30 interleaved\n   runs with paired t-test on an idle server. Split results into code paths\n   that already had manual fusion (neutral) vs code paths that benefit from\n   the new automatic fusion (1.7-2.7% improvement).\n\nChanges in v2:\n\n * Added a second commit that renames .nr to .nr_internal so that direct\n   access from outside prio-queue.c is a compile error. Verified that after\n   the rename, only prio-queue.c references nr_internal.\n\n * Added prio_queue_for_each() macro for callers that need to walk all\n   elements (describe.c, show-branch.c, commit-reach.c, revision.c,\n   negotiator/skipping.c).\n\n * Converted remaining .nr loop conditions to use\n   prio_queue_get()/prio_queue_peek() as the loop condition, or\n   prio_queue_size() where get/peek isn't suitable.\n\n * Fixed several callers missed in v1 (object-name.c, fetch-pack.c,\n   path-walk.c, pack-bitmap-write.c, negotiator/default.c,\n   negotiator/skipping.c, revision.c, builtin/last-modified.c).\n\nKristofer Karlsson (2):\n  prio-queue: fold lazy_queue into prio_queue for automatic get+put\n    fusion\n  prio-queue: rename .nr to .nr_internal to prevent direct access\n\n builtin/describe.c          |  70 ++++++------------------\n builtin/last-modified.c     |   7 +--\n builtin/show-branch.c       |  24 +++-----\n commit-reach.c              |  24 ++++----\n commit.c                    |  11 +---\n fetch-pack.c                |   4 +-\n negotiator/default.c        |   4 +-\n negotiator/skipping.c       |  12 ++--\n object-name.c               |   2 +-\n pack-bitmap-write.c         |  10 ++--\n path-walk.c                 |   8 +--\n prio-queue.c                | 106 +++++++++++++++++++-----------------\n prio-queue.h                |  19 ++++---\n revision.c                  |  16 +++---\n t/unit-tests/u-prio-queue.c |   6 +-\n walker.c                    |   4 +-\n 16 files changed, 144 insertions(+), 183 deletions(-)\n\n\nbase-commit: 9ac3f193c05c2237e2b14ebaa1149e9fc8a1abe0\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-2140%2Fspkrka%2Flazy-prio-queue-pr-v3\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2140/spkrka/lazy-prio-queue-pr-v3\nPull-Request: https://github.com/gitgitgadget/git/pull/2140\n\nRange-diff vs v2:\n\n 1:  29af24445e ! 1:  e882206d29 prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion\n     @@ Commit message\n      \n          Defer the actual removal in prio_queue_get() until the next\n          operation.  If that next operation is a prio_queue_put(), the\n     -    removal and insertion are fused into a single replace — writing\n     -    the new element at the root and sifting it down — which avoids\n     +    removal and insertion are fused into a single replace, writing\n     +    the new element at the root and sifting it down which avoids\n          a full remove-rebalance-insert cycle.\n      \n          This matches the dominant usage pattern in git's commit traversal:\n     -    get a commit, then put its parents.  The first parent insertion\n     +    get a commit, then put its parents. The first parent insertion\n          after each get is now a replace operation automatically.\n      \n          This generalizes the lazy_queue pattern from builtin/describe.c\n     -    (introduced in 08bb69d70f) into prio_queue itself.  Three callers\n     +    (introduced in 08bb69d70f) into prio_queue itself. Three callers\n          independently implemented the same get+put fusion:\n      \n            - builtin/describe.c had a full lazy_queue wrapper\n     -      - commit.c:pop_most_recent_commit() reimplements the same\n     -        get_pending flag with peek+replace\n     -      - builtin/show-branch.c:join_revs() used the same peek+replace\n     -        pattern\n     +      - commit.c:pop_most_recent_commit() used peek+replace\n     +      - builtin/show-branch.c:join_revs() used peek+replace\n      \n     -    All three now collapse to plain _get() and _put(),\n     -    with the data structure handling the fusion internally.\n     +    All three now collapse to plain _get() and _put(), with the data\n     +    structure handling the fusion internally. This simplifies callers\n     +    and means every prio_queue user gets the optimization for free\n     +    without needing to implement it manually.\n      \n          Remove prio_queue_replace() since no external callers remain.\n          Add prio_queue_size() for callers that need the logical element\n          count, since the physical nr may temporarily include a\n          pending-removal element.\n      \n     -    Benchmarked on a large monorepo (10-15 interleaved runs, 1 warmup):\n     +    Benchmarked on a large monorepo (30 interleaved runs,\n     +    paired t-test, Xeon @ 2.20GHz):\n      \n     -      Command                       base    patched  speedup\n     -      merge-base --all A A~1000     3.88s   3.77s    1.03x\n     -      rev-list --count A~1000..A    3.57s   3.43s    1.04x\n     -      log --oneline A~1000..A       3.70s   3.49s    1.06x\n     -      rev-parse :/pattern           365ms   364ms    1.00x\n     -      describe HEAD (linux.git)     184ms   190ms    1.00x\n     +    Code paths that previously did eager get+put (new optimization):\n     +\n     +      Command                       base    patched  change  p\n     +      merge-base --all A A~1000     3828ms  3725ms   -2.69%  0.0001\n     +      rev-list --count A~1000..A    3055ms  2986ms   -2.27%  0.0601\n     +      log --oneline A~1000..A       3408ms  3350ms   -1.71%  0.0482\n     +\n     +    Code paths that already had manual get+put fusion (expect\n     +    neutral - the optimization moves into prio_queue but the number\n     +    of heap operations stays the same):\n     +\n     +      Command                base   patched  change  p\n     +      show-branch A A~1000   9156ms  9127ms  -0.32%  0.3470\n     +      describe (git.git)     1983ms  1963ms  -1.02%  <0.001\n      \n          No regressions in any scenario.\n      \n     +    Suggested-by: René Scharfe <l.s.r@web.de>\n          Signed-off-by: Kristofer Karlsson <krka@spotify.com>\n      \n       ## builtin/describe.c ##\n     @@ prio-queue.c: void clear_prio_queue(struct prio_queue *queue)\n      +\tqueue->get_pending = 0;\n      +}\n      +\n     -+static void sift_down_root(struct prio_queue *queue);\n     -+\n     -+static inline void flush_get(struct prio_queue *queue)\n     ++static void sift_down_root(struct prio_queue *queue)\n      +{\n     -+\tif (!queue->get_pending)\n     -+\t\treturn;\n     -+\tqueue->get_pending = 0;\n     -+\tif (!--queue->nr)\n     -+\t\treturn;\n     -+\tqueue->array[0] = queue->array[queue->nr];\n     -+\tsift_down_root(queue);\n     ++\tsize_t ix, child;\n     ++\n     ++\tfor (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {\n     ++\t\tchild = ix * 2 + 1;\n     ++\t\tif (child + 1 < queue->nr &&\n     ++\t\t    compare(queue, child, child + 1) >= 0)\n     ++\t\t\tchild++;\n     ++\t\tif (compare(queue, ix, child) <= 0)\n     ++\t\t\tbreak;\n     ++\t\tswap(queue, child, ix);\n     ++\t}\n       }\n       \n       void prio_queue_put(struct prio_queue *queue, void *thing)\n       {\n       \tsize_t ix, parent;\n       \n     +-\t/* Append at the end */\n      +\tif (queue->get_pending) {\n      +\t\tqueue->get_pending = 0;\n      +\t\tqueue->array[0].ctr = queue->insertion_ctr++;\n     @@ prio-queue.c: void clear_prio_queue(struct prio_queue *queue)\n      +\t\treturn;\n      +\t}\n      +\n     - \t/* Append at the end */\n       \tALLOC_GROW(queue->array, queue->nr + 1, queue->alloc);\n       \tqueue->array[queue->nr].ctr = queue->insertion_ctr++;\n     -@@ prio-queue.c: static void sift_down_root(struct prio_queue *queue)\n     + \tqueue->array[queue->nr].data = thing;\n     + \tqueue->nr++;\n     + \tif (!queue->compare)\n     +-\t\treturn; /* LIFO */\n     ++\t\treturn;\n     + \n     +-\t/* Bubble up the new one */\n     + \tfor (ix = queue->nr - 1; ix; ix = parent) {\n     + \t\tparent = (ix - 1) / 2;\n     + \t\tif (compare(queue, parent, ix) <= 0)\n     + \t\t\tbreak;\n     +-\n     + \t\tswap(queue, parent, ix);\n     + \t}\n     + }\n       \n     +-static void sift_down_root(struct prio_queue *queue)\n     +-{\n     +-\tsize_t ix, child;\n     +-\n     +-\t/* Push down the one at the root */\n     +-\tfor (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {\n     +-\t\tchild = ix * 2 + 1; /* left */\n     +-\t\tif (child + 1 < queue->nr &&\n     +-\t\t    compare(queue, child, child + 1) >= 0)\n     +-\t\t\tchild++; /* use right child */\n     +-\n     +-\t\tif (compare(queue, ix, child) <= 0)\n     +-\t\t\tbreak;\n     +-\n     +-\t\tswap(queue, child, ix);\n     +-\t}\n     +-}\n     +-\n       void *prio_queue_get(struct prio_queue *queue)\n       {\n      -\tvoid *result;\n     -+\tflush_get(queue);\n     - \n     +-\n       \tif (!queue->nr)\n       \t\treturn NULL;\n       \tif (!queue->compare)\n     - \t\treturn queue->array[--queue->nr].data; /* LIFO */\n     - \n     +-\t\treturn queue->array[--queue->nr].data; /* LIFO */\n     +-\n      -\tresult = queue->array[0].data;\n      -\tif (!--queue->nr)\n      -\t\treturn result;\n     --\n     ++\t\treturn queue->array[--queue->nr].data;\n     ++\n     ++\tif (queue->get_pending) {\n     ++\t\tif (!--queue->nr) {\n     ++\t\t\tqueue->get_pending = 0;\n     ++\t\t\treturn NULL;\n     ++\t\t}\n     ++\t\tqueue->array[0] = queue->array[queue->nr];\n     ++\t\tsift_down_root(queue);\n     ++\t}\n     + \n      -\tqueue->array[0] = queue->array[queue->nr];\n      -\tsift_down_root(queue);\n      -\treturn result;\n     @@ prio-queue.c: static void sift_down_root(struct prio_queue *queue)\n       }\n       \n       void *prio_queue_peek(struct prio_queue *queue)\n     - {\n     -+\tflush_get(queue);\n     -+\n     - \tif (!queue->nr)\n     +@@ prio-queue.c: void *prio_queue_peek(struct prio_queue *queue)\n       \t\treturn NULL;\n       \tif (!queue->compare)\n       \t\treturn queue->array[queue->nr - 1].data;\n     - \treturn queue->array[0].data;\n     - }\n     --\n     +-\treturn queue->array[0].data;\n     +-}\n     + \n      -void prio_queue_replace(struct prio_queue *queue, void *thing)\n      -{\n      -\tif (!queue->nr) {\n     @@ prio-queue.c: static void sift_down_root(struct prio_queue *queue)\n      -\t} else {\n      -\t\tqueue->array[0].ctr = queue->insertion_ctr++;\n      -\t\tqueue->array[0].data = thing;\n     --\t\tsift_down_root(queue);\n     --\t}\n     --}\n     ++\tif (queue->get_pending) {\n     ++\t\tqueue->get_pending = 0;\n     ++\t\tif (!--queue->nr)\n     ++\t\t\treturn NULL;\n     ++\t\tqueue->array[0] = queue->array[queue->nr];\n     + \t\tsift_down_root(queue);\n     + \t}\n     ++\n     ++\treturn queue->array[0].data;\n     + }\n      \n       ## prio-queue.h ##\n      @@ prio-queue.h: struct prio_queue {\n 2:  bb8b0f78f1 ! 2:  033215e304 prio-queue: rename .nr to .nr_internal to prevent direct access\n     @@ prio-queue.c: void prio_queue_reverse(struct prio_queue *queue)\n       \tqueue->alloc = 0;\n       \tqueue->insertion_ctr = 0;\n       \tqueue->get_pending = 0;\n     -@@ prio-queue.c: static inline void flush_get(struct prio_queue *queue)\n     - \tif (!queue->get_pending)\n     - \t\treturn;\n     - \tqueue->get_pending = 0;\n     --\tif (!--queue->nr)\n     -+\tif (!--queue->nr_internal)\n     - \t\treturn;\n     --\tqueue->array[0] = queue->array[queue->nr];\n     -+\tqueue->array[0] = queue->array[queue->nr_internal];\n     - \tsift_down_root(queue);\n     - }\n     +@@ prio-queue.c: static void sift_down_root(struct prio_queue *queue)\n     + {\n     + \tsize_t ix, child;\n       \n     +-\tfor (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {\n     +-\t\tchild = ix * 2 + 1;\n     +-\t\tif (child + 1 < queue->nr &&\n     ++\t/* Push down the one at the root */\n     ++\tfor (ix = 0; ix * 2 + 1 < queue->nr_internal; ix = child) {\n     ++\t\tchild = ix * 2 + 1; /* left */\n     ++\t\tif (child + 1 < queue->nr_internal &&\n     + \t\t    compare(queue, child, child + 1) >= 0)\n     +-\t\t\tchild++;\n     ++\t\t\tchild++; /* use right child */\n     ++\n     + \t\tif (compare(queue, ix, child) <= 0)\n     + \t\t\tbreak;\n     ++\n     + \t\tswap(queue, child, ix);\n     + \t}\n     + }\n      @@ prio-queue.c: void prio_queue_put(struct prio_queue *queue, void *thing)\n     + \t\treturn;\n       \t}\n       \n     - \t/* Append at the end */\n      -\tALLOC_GROW(queue->array, queue->nr + 1, queue->alloc);\n      -\tqueue->array[queue->nr].ctr = queue->insertion_ctr++;\n      -\tqueue->array[queue->nr].data = thing;\n      -\tqueue->nr++;\n     ++\t/* Append at the end */\n      +\tALLOC_GROW(queue->array, queue->nr_internal + 1, queue->alloc);\n      +\tqueue->array[queue->nr_internal].ctr = queue->insertion_ctr++;\n      +\tqueue->array[queue->nr_internal].data = thing;\n      +\tqueue->nr_internal++;\n       \tif (!queue->compare)\n     - \t\treturn; /* LIFO */\n     +-\t\treturn;\n     ++\t\treturn; /* LIFO */\n       \n     - \t/* Bubble up the new one */\n      -\tfor (ix = queue->nr - 1; ix; ix = parent) {\n     ++\t/* Bubble up the new one */\n      +\tfor (ix = queue->nr_internal - 1; ix; ix = parent) {\n       \t\tparent = (ix - 1) / 2;\n       \t\tif (compare(queue, parent, ix) <= 0)\n       \t\t\tbreak;\n     -@@ prio-queue.c: static void sift_down_root(struct prio_queue *queue)\n     - \tsize_t ix, child;\n     - \n     - \t/* Push down the one at the root */\n     --\tfor (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {\n     -+\tfor (ix = 0; ix * 2 + 1 < queue->nr_internal; ix = child) {\n     - \t\tchild = ix * 2 + 1; /* left */\n     --\t\tif (child + 1 < queue->nr &&\n     -+\t\tif (child + 1 < queue->nr_internal &&\n     - \t\t    compare(queue, child, child + 1) >= 0)\n     - \t\t\tchild++; /* use right child */\n     ++\n     + \t\tswap(queue, parent, ix);\n     + \t}\n     + }\n       \n     -@@ prio-queue.c: void *prio_queue_get(struct prio_queue *queue)\n     + void *prio_queue_get(struct prio_queue *queue)\n       {\n     - \tflush_get(queue);\n     - \n      -\tif (!queue->nr)\n      +\tif (!queue->nr_internal)\n       \t\treturn NULL;\n       \tif (!queue->compare)\n     --\t\treturn queue->array[--queue->nr].data; /* LIFO */\n     +-\t\treturn queue->array[--queue->nr].data;\n      +\t\treturn queue->array[--queue->nr_internal].data; /* LIFO */\n       \n     - \tqueue->get_pending = 1;\n     - \treturn queue->array[0].data;\n     -@@ prio-queue.c: void *prio_queue_peek(struct prio_queue *queue)\n     - {\n     - \tflush_get(queue);\n     + \tif (queue->get_pending) {\n     +-\t\tif (!--queue->nr) {\n     ++\t\tif (!--queue->nr_internal) {\n     + \t\t\tqueue->get_pending = 0;\n     + \t\t\treturn NULL;\n     + \t\t}\n     +-\t\tqueue->array[0] = queue->array[queue->nr];\n     ++\t\tqueue->array[0] = queue->array[queue->nr_internal];\n     + \t\tsift_down_root(queue);\n     + \t}\n       \n     +@@ prio-queue.c: void *prio_queue_get(struct prio_queue *queue)\n     + \n     + void *prio_queue_peek(struct prio_queue *queue)\n     + {\n      -\tif (!queue->nr)\n      +\tif (!queue->nr_internal)\n       \t\treturn NULL;\n       \tif (!queue->compare)\n      -\t\treturn queue->array[queue->nr - 1].data;\n      +\t\treturn queue->array[queue->nr_internal - 1].data;\n     - \treturn queue->array[0].data;\n     - }\n     + \n     + \tif (queue->get_pending) {\n     + \t\tqueue->get_pending = 0;\n     +-\t\tif (!--queue->nr)\n     ++\t\tif (!--queue->nr_internal)\n     + \t\t\treturn NULL;\n     +-\t\tqueue->array[0] = queue->array[queue->nr];\n     ++\t\tqueue->array[0] = queue->array[queue->nr_internal];\n     + \t\tsift_down_root(queue);\n     + \t}\n     + \n      \n       ## prio-queue.h ##\n      @@ prio-queue.h: struct prio_queue {\n\n-- \ngitgitgadget\n"},{"id":"544843","messageId":"e882206d29406604b1ea135b0bc00df85b097f45.1780832592.git.gitgitgadget@gmail.com","threadId":"65764","inReplyTo":"pull.2140.v3.git.1780832592.gitgitgadget@gmail.com","subject":"[PATCH v3 1/2] prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-06-07T11:43:10Z","receivedAt":"2026-06-07T11:43:17Z","isPatch":true,"body":"From: Kristofer Karlsson <krka@spotify.com>\n\nDefer the actual removal in prio_queue_get() until the next\noperation.  If that next operation is a prio_queue_put(), the\nremoval and insertion are fused into a single replace, writing\nthe new element at the root and sifting it down which avoids\na full remove-rebalance-insert cycle.\n\nThis matches the dominant usage pattern in git's commit traversal:\nget a commit, then put its parents. The first parent insertion\nafter each get is now a replace operation automatically.\n\nThis generalizes the lazy_queue pattern from builtin/describe.c\n(introduced in 08bb69d70f) into prio_queue itself. Three callers\nindependently implemented the same get+put fusion:\n\n  - builtin/describe.c had a full lazy_queue wrapper\n  - commit.c:pop_most_recent_commit() used peek+replace\n  - builtin/show-branch.c:join_revs() used peek+replace\n\nAll three now collapse to plain _get() and _put(), with the data\nstructure handling the fusion internally. This simplifies callers\nand means every prio_queue user gets the optimization for free\nwithout needing to implement it manually.\n\nRemove prio_queue_replace() since no external callers remain.\nAdd prio_queue_size() for callers that need the logical element\ncount, since the physical nr may temporarily include a\npending-removal element.\n\nBenchmarked on a large monorepo (30 interleaved runs,\npaired t-test, Xeon @ 2.20GHz):\n\nCode paths that previously did eager get+put (new optimization):\n\n  Command                       base    patched  change  p\n  merge-base --all A A~1000     3828ms  3725ms   -2.69%  0.0001\n  rev-list --count A~1000..A    3055ms  2986ms   -2.27%  0.0601\n  log --oneline A~1000..A       3408ms  3350ms   -1.71%  0.0482\n\nCode paths that already had manual get+put fusion (expect\nneutral - the optimization moves into prio_queue but the number\nof heap operations stays the same):\n\n  Command                base   patched  change  p\n  show-branch A A~1000   9156ms  9127ms  -0.32%  0.3470\n  describe (git.git)     1983ms  1963ms  -1.02%  <0.001\n\nNo regressions in any scenario.\n\nSuggested-by: René Scharfe <l.s.r@web.de>\nSigned-off-by: Kristofer Karlsson <krka@spotify.com>\n---\n builtin/describe.c          | 67 +++++++---------------------\n builtin/last-modified.c     |  4 +-\n builtin/show-branch.c       | 17 +++----\n commit-reach.c              |  5 +--\n commit.c                    | 11 +----\n pack-bitmap-write.c         |  4 +-\n prio-queue.c                | 88 ++++++++++++++++++-------------------\n prio-queue.h                | 12 +++--\n revision.c                  |  5 +--\n t/unit-tests/u-prio-queue.c |  6 +--\n walker.c                    |  4 +-\n 11 files changed, 85 insertions(+), 138 deletions(-)\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 1c47d7c0b7..85564f3487 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -251,56 +251,20 @@ static int compare_pt(const void *a_, const void *b_)\n \treturn 0;\n }\n \n-struct lazy_queue {\n-\tstruct prio_queue queue;\n-\tbool get_pending;\n-};\n-\n-#define LAZY_QUEUE_INIT { { compare_commits_by_commit_date }, false }\n-\n-static void *lazy_queue_get(struct lazy_queue *queue)\n-{\n-\tif (queue->get_pending)\n-\t\tprio_queue_get(&queue->queue);\n-\telse\n-\t\tqueue->get_pending = true;\n-\treturn prio_queue_peek(&queue->queue);\n-}\n-\n-static void lazy_queue_put(struct lazy_queue *queue, void *thing)\n-{\n-\tif (queue->get_pending)\n-\t\tprio_queue_replace(&queue->queue, thing);\n-\telse\n-\t\tprio_queue_put(&queue->queue, thing);\n-\tqueue->get_pending = false;\n-}\n-\n-static bool lazy_queue_empty(const struct lazy_queue *queue)\n-{\n-\treturn queue->queue.nr == (queue->get_pending ? 1 : 0);\n-}\n-\n-static void lazy_queue_clear(struct lazy_queue *queue)\n-{\n-\tclear_prio_queue(&queue->queue);\n-\tqueue->get_pending = false;\n-}\n-\n-static unsigned long finish_depth_computation(struct lazy_queue *queue,\n+static unsigned long finish_depth_computation(struct prio_queue *queue,\n \t\t\t\t\t      struct possible_tag *best)\n {\n \tunsigned long seen_commits = 0;\n \tstruct oidset unflagged = OIDSET_INIT;\n+\tstruct commit *c;\n \n-\tfor (size_t i = queue->get_pending ? 1 : 0; i < queue->queue.nr; i++) {\n-\t\tstruct commit *commit = queue->queue.array[i].data;\n+\tfor (size_t i = queue->get_pending; i < queue->nr; i++) {\n+\t\tstruct commit *commit = queue->array[i].data;\n \t\tif (!(commit->object.flags & best->flag_within))\n \t\t\toidset_insert(&unflagged, &commit->object.oid);\n \t}\n \n-\twhile (!lazy_queue_empty(queue)) {\n-\t\tstruct commit *c = lazy_queue_get(queue);\n+\twhile ((c = prio_queue_get(queue))) {\n \t\tstruct commit_list *parents = c->parents;\n \t\tseen_commits++;\n \t\tif (c->object.flags & best->flag_within) {\n@@ -316,7 +280,7 @@ static unsigned long finish_depth_computation(struct lazy_queue *queue,\n \t\t\trepo_parse_commit(the_repository, p);\n \t\t\tseen = p->object.flags & SEEN;\n \t\t\tif (!seen)\n-\t\t\t\tlazy_queue_put(queue, p);\n+\t\t\t\tprio_queue_put(queue, p);\n \t\t\tflag_before = p->object.flags & best->flag_within;\n \t\t\tp->object.flags |= c->object.flags;\n \t\t\tflag_after = p->object.flags & best->flag_within;\n@@ -364,8 +328,8 @@ static void append_suffix(int depth, const struct object_id *oid, struct strbuf\n \n static void describe_commit(struct commit *cmit, struct strbuf *dst)\n {\n-\tstruct commit *gave_up_on = NULL;\n-\tstruct lazy_queue queue = LAZY_QUEUE_INIT;\n+\tstruct commit *c, *gave_up_on = NULL;\n+\tstruct prio_queue queue = { compare_commits_by_commit_date };\n \tstruct commit_name *n;\n \tstruct possible_tag all_matches[MAX_TAGS];\n \tunsigned int match_cnt = 0, annotated_cnt = 0, cur_match;\n@@ -407,9 +371,8 @@ static void describe_commit(struct commit *cmit, struct strbuf *dst)\n \t}\n \n \tcmit->object.flags = SEEN;\n-\tlazy_queue_put(&queue, cmit);\n-\twhile (!lazy_queue_empty(&queue)) {\n-\t\tstruct commit *c = lazy_queue_get(&queue);\n+\tprio_queue_put(&queue, cmit);\n+\twhile ((c = prio_queue_get(&queue))) {\n \t\tstruct commit_list *parents = c->parents;\n \t\tstruct commit_name **slot;\n \n@@ -443,7 +406,7 @@ static void describe_commit(struct commit *cmit, struct strbuf *dst)\n \t\t\t\tt->depth++;\n \t\t}\n \t\t/* Stop if last remaining path already covered by best candidate(s) */\n-\t\tif (annotated_cnt && lazy_queue_empty(&queue)) {\n+\t\tif (annotated_cnt && !prio_queue_size(&queue)) {\n \t\t\tint best_depth = INT_MAX;\n \t\t\tunsigned best_within = 0;\n \t\t\tfor (cur_match = 0; cur_match < match_cnt; cur_match++) {\n@@ -466,7 +429,7 @@ static void describe_commit(struct commit *cmit, struct strbuf *dst)\n \t\t\tstruct commit *p = parents->item;\n \t\t\trepo_parse_commit(the_repository, p);\n \t\t\tif (!(p->object.flags & SEEN))\n-\t\t\t\tlazy_queue_put(&queue, p);\n+\t\t\t\tprio_queue_put(&queue, p);\n \t\t\tp->object.flags |= c->object.flags;\n \t\t\tparents = parents->next;\n \n@@ -481,7 +444,7 @@ static void describe_commit(struct commit *cmit, struct strbuf *dst)\n \t\t\tstrbuf_add_unique_abbrev(dst, cmit_oid, abbrev);\n \t\t\tif (suffix)\n \t\t\t\tstrbuf_addstr(dst, suffix);\n-\t\t\tlazy_queue_clear(&queue);\n+\t\t\tclear_prio_queue(&queue);\n \t\t\treturn;\n \t\t}\n \t\tif (unannotated_cnt)\n@@ -497,11 +460,11 @@ static void describe_commit(struct commit *cmit, struct strbuf *dst)\n \tQSORT(all_matches, match_cnt, compare_pt);\n \n \tif (gave_up_on) {\n-\t\tlazy_queue_put(&queue, gave_up_on);\n+\t\tprio_queue_put(&queue, gave_up_on);\n \t\tseen_commits--;\n \t}\n \tseen_commits += finish_depth_computation(&queue, &all_matches[0]);\n-\tlazy_queue_clear(&queue);\n+\tclear_prio_queue(&queue);\n \n \tif (debug) {\n \t\tstatic int label_width = -1;\ndiff --git a/builtin/last-modified.c b/builtin/last-modified.c\nindex 8900ceece1..df2a508244 100644\n--- a/builtin/last-modified.c\n+++ b/builtin/last-modified.c\n@@ -344,6 +344,7 @@ static void process_parent(struct last_modified *lm,\n static int last_modified_run(struct last_modified *lm)\n {\n \tint max_count, queue_popped = 0;\n+\tstruct commit *c;\n \tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n \tstruct prio_queue not_queue = { compare_commits_by_gen_then_commit_date };\n \tstruct commit_list *list;\n@@ -389,10 +390,9 @@ static int last_modified_run(struct last_modified *lm)\n \t\t}\n \t}\n \n-\twhile (queue.nr) {\n+\twhile ((c = prio_queue_get(&queue))) {\n \t\tint parent_i;\n \t\tstruct commit_list *p;\n-\t\tstruct commit *c = prio_queue_get(&queue);\n \t\tstruct bitmap *active_c = active_paths_for(lm, c);\n \n \t\tif ((0 <= max_count && max_count < ++queue_popped) ||\ndiff --git a/builtin/show-branch.c b/builtin/show-branch.c\nindex f02831b085..9f7f28f339 100644\n--- a/builtin/show-branch.c\n+++ b/builtin/show-branch.c\n@@ -62,7 +62,7 @@ static const char *get_color_reset_code(void)\n \n static struct commit *interesting(struct prio_queue *queue)\n {\n-\tfor (size_t i = 0; i < queue->nr; i++) {\n+\tfor (size_t i = queue->get_pending; i < queue->nr; i++) {\n \t\tstruct commit *commit = queue->array[i].data;\n \t\tif (commit->object.flags & UNINTERESTING)\n \t\t\tcontinue;\n@@ -228,17 +228,18 @@ static void join_revs(struct prio_queue *queue,\n {\n \tint all_mask = ((1u << (REV_SHIFT + num_rev)) - 1);\n \tint all_revs = all_mask & ~((1u << REV_SHIFT) - 1);\n+\tstruct commit *commit;\n \n-\twhile (queue->nr) {\n+\twhile ((commit = prio_queue_peek(queue))) {\n \t\tstruct commit_list *parents;\n \t\tint still_interesting = !!interesting(queue);\n-\t\tstruct commit *commit = prio_queue_peek(queue);\n-\t\tbool get_pending = true;\n \t\tint flags = commit->object.flags & all_mask;\n \n \t\tif (!still_interesting && extra <= 0)\n \t\t\tbreak;\n \n+\t\tprio_queue_get(queue);\n+\n \t\tmark_seen(commit, seen_p);\n \t\tif ((flags & all_revs) == all_revs)\n \t\t\tflags |= UNINTERESTING;\n@@ -254,14 +255,8 @@ static void join_revs(struct prio_queue *queue,\n \t\t\tif (mark_seen(p, seen_p) && !still_interesting)\n \t\t\t\textra--;\n \t\t\tp->object.flags |= flags;\n-\t\t\tif (get_pending)\n-\t\t\t\tprio_queue_replace(queue, p);\n-\t\t\telse\n-\t\t\t\tprio_queue_put(queue, p);\n-\t\t\tget_pending = false;\n+\t\t\tprio_queue_put(queue, p);\n \t\t}\n-\t\tif (get_pending)\n-\t\t\tprio_queue_get(queue);\n \t}\n \n \t/*\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 9b3ea46d6f..0fec2f00be 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -1269,7 +1269,7 @@ int get_branch_base_for_tip(struct repository *r,\n \t\t\t    size_t bases_nr)\n {\n \tint best_index = -1;\n-\tstruct commit *branch_point = NULL;\n+\tstruct commit *c, *branch_point = NULL;\n \tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n \tint found_missing_gen = 0;\n \n@@ -1322,8 +1322,7 @@ int get_branch_base_for_tip(struct repository *r,\n \t\tprio_queue_put(&queue, c);\n \t}\n \n-\twhile (queue.nr) {\n-\t\tstruct commit *c = prio_queue_get(&queue);\n+\twhile ((c = prio_queue_get(&queue))) {\n \t\tint best_for_c = get_best(c);\n \t\tint best_for_p, positive;\n \t\tstruct commit *parent;\ndiff --git a/commit.c b/commit.c\nindex fd8723502e..976bfc4618 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -795,24 +795,17 @@ void commit_list_sort_by_date(struct commit_list **list)\n struct commit *pop_most_recent_commit(struct prio_queue *queue,\n \t\t\t\t      unsigned int mark)\n {\n-\tstruct commit *ret = prio_queue_peek(queue);\n-\tint get_pending = 1;\n+\tstruct commit *ret = prio_queue_get(queue);\n \tstruct commit_list *parents = ret->parents;\n \n \twhile (parents) {\n \t\tstruct commit *commit = parents->item;\n \t\tif (!repo_parse_commit(the_repository, commit) && !(commit->object.flags & mark)) {\n \t\t\tcommit->object.flags |= mark;\n-\t\t\tif (get_pending)\n-\t\t\t\tprio_queue_replace(queue, commit);\n-\t\t\telse\n-\t\t\t\tprio_queue_put(queue, commit);\n-\t\t\tget_pending = 0;\n+\t\t\tprio_queue_put(queue, commit);\n \t\t}\n \t\tparents = parents->next;\n \t}\n-\tif (get_pending)\n-\t\tprio_queue_get(queue);\n \treturn ret;\n }\n \ndiff --git a/pack-bitmap-write.c b/pack-bitmap-write.c\nindex 1c8070f99c..f7c63e3027 100644\n--- a/pack-bitmap-write.c\n+++ b/pack-bitmap-write.c\n@@ -513,6 +513,7 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,\n \t\t\t      struct bitmap_index *old_bitmap,\n \t\t\t      const uint32_t *mapping)\n {\n+\tstruct commit *c;\n \tint found;\n \tuint32_t pos;\n \tif (!ent->bitmap)\n@@ -520,9 +521,8 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,\n \n \tprio_queue_put(queue, commit);\n \n-\twhile (queue->nr) {\n+\twhile ((c = prio_queue_get(queue))) {\n \t\tstruct commit_list *p;\n-\t\tstruct commit *c = prio_queue_get(queue);\n \n \t\tif (old_bitmap && mapping) {\n \t\t\tstruct ewah_bitmap *old;\ndiff --git a/prio-queue.c b/prio-queue.c\nindex 9748528ce6..a03c617470 100644\n--- a/prio-queue.c\n+++ b/prio-queue.c\n@@ -34,64 +34,69 @@ void clear_prio_queue(struct prio_queue *queue)\n \tqueue->nr = 0;\n \tqueue->alloc = 0;\n \tqueue->insertion_ctr = 0;\n+\tqueue->get_pending = 0;\n+}\n+\n+static void sift_down_root(struct prio_queue *queue)\n+{\n+\tsize_t ix, child;\n+\n+\tfor (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {\n+\t\tchild = ix * 2 + 1;\n+\t\tif (child + 1 < queue->nr &&\n+\t\t    compare(queue, child, child + 1) >= 0)\n+\t\t\tchild++;\n+\t\tif (compare(queue, ix, child) <= 0)\n+\t\t\tbreak;\n+\t\tswap(queue, child, ix);\n+\t}\n }\n \n void prio_queue_put(struct prio_queue *queue, void *thing)\n {\n \tsize_t ix, parent;\n \n-\t/* Append at the end */\n+\tif (queue->get_pending) {\n+\t\tqueue->get_pending = 0;\n+\t\tqueue->array[0].ctr = queue->insertion_ctr++;\n+\t\tqueue->array[0].data = thing;\n+\t\tsift_down_root(queue);\n+\t\treturn;\n+\t}\n+\n \tALLOC_GROW(queue->array, queue->nr + 1, queue->alloc);\n \tqueue->array[queue->nr].ctr = queue->insertion_ctr++;\n \tqueue->array[queue->nr].data = thing;\n \tqueue->nr++;\n \tif (!queue->compare)\n-\t\treturn; /* LIFO */\n+\t\treturn;\n \n-\t/* Bubble up the new one */\n \tfor (ix = queue->nr - 1; ix; ix = parent) {\n \t\tparent = (ix - 1) / 2;\n \t\tif (compare(queue, parent, ix) <= 0)\n \t\t\tbreak;\n-\n \t\tswap(queue, parent, ix);\n \t}\n }\n \n-static void sift_down_root(struct prio_queue *queue)\n-{\n-\tsize_t ix, child;\n-\n-\t/* Push down the one at the root */\n-\tfor (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {\n-\t\tchild = ix * 2 + 1; /* left */\n-\t\tif (child + 1 < queue->nr &&\n-\t\t    compare(queue, child, child + 1) >= 0)\n-\t\t\tchild++; /* use right child */\n-\n-\t\tif (compare(queue, ix, child) <= 0)\n-\t\t\tbreak;\n-\n-\t\tswap(queue, child, ix);\n-\t}\n-}\n-\n void *prio_queue_get(struct prio_queue *queue)\n {\n-\tvoid *result;\n-\n \tif (!queue->nr)\n \t\treturn NULL;\n \tif (!queue->compare)\n-\t\treturn queue->array[--queue->nr].data; /* LIFO */\n-\n-\tresult = queue->array[0].data;\n-\tif (!--queue->nr)\n-\t\treturn result;\n+\t\treturn queue->array[--queue->nr].data;\n+\n+\tif (queue->get_pending) {\n+\t\tif (!--queue->nr) {\n+\t\t\tqueue->get_pending = 0;\n+\t\t\treturn NULL;\n+\t\t}\n+\t\tqueue->array[0] = queue->array[queue->nr];\n+\t\tsift_down_root(queue);\n+\t}\n \n-\tqueue->array[0] = queue->array[queue->nr];\n-\tsift_down_root(queue);\n-\treturn result;\n+\tqueue->get_pending = 1;\n+\treturn queue->array[0].data;\n }\n \n void *prio_queue_peek(struct prio_queue *queue)\n@@ -100,19 +105,14 @@ void *prio_queue_peek(struct prio_queue *queue)\n \t\treturn NULL;\n \tif (!queue->compare)\n \t\treturn queue->array[queue->nr - 1].data;\n-\treturn queue->array[0].data;\n-}\n \n-void prio_queue_replace(struct prio_queue *queue, void *thing)\n-{\n-\tif (!queue->nr) {\n-\t\tprio_queue_put(queue, thing);\n-\t} else if (!queue->compare) {\n-\t\tqueue->array[queue->nr - 1].ctr = queue->insertion_ctr++;\n-\t\tqueue->array[queue->nr - 1].data = thing;\n-\t} else {\n-\t\tqueue->array[0].ctr = queue->insertion_ctr++;\n-\t\tqueue->array[0].data = thing;\n+\tif (queue->get_pending) {\n+\t\tqueue->get_pending = 0;\n+\t\tif (!--queue->nr)\n+\t\t\treturn NULL;\n+\t\tqueue->array[0] = queue->array[queue->nr];\n \t\tsift_down_root(queue);\n \t}\n+\n+\treturn queue->array[0].data;\n }\ndiff --git a/prio-queue.h b/prio-queue.h\nindex da7fad2f1f..482ab5e71d 100644\n--- a/prio-queue.h\n+++ b/prio-queue.h\n@@ -32,6 +32,7 @@ struct prio_queue {\n \tvoid *cb_data;\n \tsize_t alloc, nr;\n \tstruct prio_queue_entry *array;\n+\tunsigned get_pending;\n };\n \n /*\n@@ -52,13 +53,10 @@ void *prio_queue_get(struct prio_queue *);\n  */\n void *prio_queue_peek(struct prio_queue *);\n \n-/*\n- * Replace the \"thing\" that compares the smallest with a new \"thing\",\n- * like prio_queue_get()+prio_queue_put() would do, but in a more\n- * efficient way.  Does the same as prio_queue_put() if the queue is\n- * empty.\n- */\n-void prio_queue_replace(struct prio_queue *queue, void *thing);\n+static inline size_t prio_queue_size(struct prio_queue *queue)\n+{\n+\treturn queue->nr - queue->get_pending;\n+}\n \n void clear_prio_queue(struct prio_queue *);\n \ndiff --git a/revision.c b/revision.c\nindex 5693618be4..8ce8ffa43d 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -1446,7 +1446,7 @@ static int limit_list(struct rev_info *revs)\n \tstruct commit_list *original_list = revs->commits;\n \tstruct commit_list *newlist = NULL;\n \tstruct commit_list **p = &newlist;\n-\tstruct commit *interesting_cache = NULL;\n+\tstruct commit *commit, *interesting_cache = NULL;\n \tstruct prio_queue queue = { .compare = compare_commits_by_commit_date };\n \n \tif (revs->ancestry_path_implicit_bottoms) {\n@@ -1461,8 +1461,7 @@ static int limit_list(struct rev_info *revs)\n \t\tprio_queue_put(&queue, commit);\n \t}\n \n-\twhile (queue.nr) {\n-\t\tstruct commit *commit = prio_queue_get(&queue);\n+\twhile ((commit = prio_queue_get(&queue))) {\n \t\tstruct object *obj = &commit->object;\n \n \t\tif (commit == interesting_cache)\ndiff --git a/t/unit-tests/u-prio-queue.c b/t/unit-tests/u-prio-queue.c\nindex 63e58114ae..af3e0b8598 100644\n--- a/t/unit-tests/u-prio-queue.c\n+++ b/t/unit-tests/u-prio-queue.c\n@@ -53,13 +53,13 @@ static void test_prio_queue(int *input, size_t input_size,\n \t\t\tprio_queue_reverse(&pq);\n \t\t\tbreak;\n \t\tcase REPLACE:\n-\t\t\tpeek = prio_queue_peek(&pq);\n+\t\t\tget = prio_queue_get(&pq);\n \t\t\tcl_assert(i + 1 < input_size);\n \t\t\tcl_assert(input[i + 1] >= 0);\n \t\t\tcl_assert(j < result_size);\n-\t\t\tcl_assert_equal_i(result[j], show(peek));\n+\t\t\tcl_assert_equal_i(result[j], show(get));\n \t\t\tj++;\n-\t\t\tprio_queue_replace(&pq, &input[++i]);\n+\t\t\tprio_queue_put(&pq, &input[++i]);\n \t\t\tbreak;\n \t\tdefault:\n \t\t\tprio_queue_put(&pq, &input[i]);\ndiff --git a/walker.c b/walker.c\nindex e98eb6da53..e3de77f092 100644\n--- a/walker.c\n+++ b/walker.c\n@@ -84,12 +84,12 @@ static struct prio_queue complete = { compare_commits_by_commit_date };\n static int process_commit(struct walker *walker, struct commit *commit)\n {\n \tstruct commit_list *parents;\n+\tstruct commit *item;\n \n \tif (repo_parse_commit(the_repository, commit))\n \t\treturn -1;\n \n-\twhile (complete.nr) {\n-\t\tstruct commit *item = prio_queue_peek(&complete);\n+\twhile ((item = prio_queue_peek(&complete))) {\n \t\tif (item->date < commit->date)\n \t\t\tbreak;\n \t\tpop_most_recent_commit(&complete, COMPLETE);\n-- \ngitgitgadget\n\n"},{"id":"544844","messageId":"033215e3042ece9e1bfae3579f844dd8950d1323.1780832592.git.gitgitgadget@gmail.com","threadId":"65764","inReplyTo":"pull.2140.v3.git.1780832592.gitgitgadget@gmail.com","subject":"[PATCH v3 2/2] prio-queue: rename .nr to .nr_internal to prevent direct access","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-06-07T11:43:11Z","receivedAt":"2026-06-07T11:43:20Z","isPatch":true,"body":"From: Kristofer Karlsson <krka@spotify.com>\n\nRename the .nr member to .nr_internal so that callers outside\nprio-queue.c that directly reference .nr get a compilation error.\nThis catches both existing misuse and future in-flight topics.\n\nAdd prio_queue_for_each() macro for callers that need to walk all\nelements in the queue, accounting for the get_pending offset.\n\nConvert all external .nr users:\n - Loop conditions: use prio_queue_size(), prio_queue_get(), or\n   prio_queue_peek() as the loop condition\n - Array iterations: use prio_queue_for_each()\n\nSigned-off-by: Kristofer Karlsson <krka@spotify.com>\n---\n builtin/describe.c      |  7 +++---\n builtin/last-modified.c |  5 ++---\n builtin/show-branch.c   |  9 ++++----\n commit-reach.c          | 19 +++++++++-------\n fetch-pack.c            |  4 ++--\n negotiator/default.c    |  4 +++-\n negotiator/skipping.c   | 12 ++++++-----\n object-name.c           |  2 +-\n pack-bitmap-write.c     |  6 +++---\n path-walk.c             |  8 +++----\n prio-queue.c            | 48 +++++++++++++++++++++++------------------\n prio-queue.h            |  9 ++++++--\n revision.c              | 11 +++++-----\n 13 files changed, 79 insertions(+), 65 deletions(-)\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 85564f3487..64424543ef 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -258,10 +258,9 @@ static unsigned long finish_depth_computation(struct prio_queue *queue,\n \tstruct oidset unflagged = OIDSET_INIT;\n \tstruct commit *c;\n \n-\tfor (size_t i = queue->get_pending; i < queue->nr; i++) {\n-\t\tstruct commit *commit = queue->array[i].data;\n-\t\tif (!(commit->object.flags & best->flag_within))\n-\t\t\toidset_insert(&unflagged, &commit->object.oid);\n+\tprio_queue_for_each(queue, c) {\n+\t\tif (!(c->object.flags & best->flag_within))\n+\t\t\toidset_insert(&unflagged, &c->object.oid);\n \t}\n \n \twhile ((c = prio_queue_get(queue))) {\ndiff --git a/builtin/last-modified.c b/builtin/last-modified.c\nindex df2a508244..5478182f2e 100644\n--- a/builtin/last-modified.c\n+++ b/builtin/last-modified.c\n@@ -344,7 +344,7 @@ static void process_parent(struct last_modified *lm,\n static int last_modified_run(struct last_modified *lm)\n {\n \tint max_count, queue_popped = 0;\n-\tstruct commit *c;\n+\tstruct commit *c, *n;\n \tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n \tstruct prio_queue not_queue = { compare_commits_by_gen_then_commit_date };\n \tstruct commit_list *list;\n@@ -416,9 +416,8 @@ static int last_modified_run(struct last_modified *lm)\n \t\t */\n \t\trepo_parse_commit(lm->rev.repo, c);\n \n-\t\twhile (not_queue.nr) {\n+\t\twhile ((n = prio_queue_get(&not_queue))) {\n \t\t\tstruct commit_list *np;\n-\t\t\tstruct commit *n = prio_queue_get(&not_queue);\n \n \t\t\trepo_parse_commit(lm->rev.repo, n);\n \ndiff --git a/builtin/show-branch.c b/builtin/show-branch.c\nindex 9f7f28f339..2435e8aeda 100644\n--- a/builtin/show-branch.c\n+++ b/builtin/show-branch.c\n@@ -62,11 +62,10 @@ static const char *get_color_reset_code(void)\n \n static struct commit *interesting(struct prio_queue *queue)\n {\n-\tfor (size_t i = queue->get_pending; i < queue->nr; i++) {\n-\t\tstruct commit *commit = queue->array[i].data;\n-\t\tif (commit->object.flags & UNINTERESTING)\n-\t\t\tcontinue;\n-\t\treturn commit;\n+\tstruct commit *commit;\n+\tprio_queue_for_each(queue, commit) {\n+\t\tif (!(commit->object.flags & UNINTERESTING))\n+\t\t\treturn commit;\n \t}\n \treturn NULL;\n }\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 0fec2f00be..dfe6016cb2 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -41,8 +41,8 @@ static int compare_commits_by_gen(const void *_a, const void *_b)\n \n static int queue_has_nonstale(struct prio_queue *queue)\n {\n-\tfor (size_t i = 0; i < queue->nr; i++) {\n-\t\tstruct commit *commit = queue->array[i].data;\n+\tstruct commit *commit;\n+\tprio_queue_for_each(queue, commit) {\n \t\tif (!(commit->object.flags & STALE))\n \t\t\treturn 1;\n \t}\n@@ -1069,6 +1069,7 @@ void ahead_behind(struct repository *r,\n \t\t  struct commit **commits, size_t commits_nr,\n \t\t  struct ahead_behind_count *counts, size_t counts_nr)\n {\n+\tstruct commit *c;\n \tstruct prio_queue queue = { .compare = compare_commits_by_gen_then_commit_date };\n \tsize_t width = DIV_ROUND_UP(commits_nr, BITS_IN_EWORD);\n \n@@ -1085,17 +1086,19 @@ void ahead_behind(struct repository *r,\n \tinit_bit_arrays(&bit_arrays);\n \n \tfor (size_t i = 0; i < commits_nr; i++) {\n-\t\tstruct commit *c = commits[i];\n-\t\tstruct bitmap *bitmap = get_bit_array(c, width);\n+\t\tstruct bitmap *bitmap;\n+\t\tc = commits[i];\n+\t\tbitmap = get_bit_array(c, width);\n \n \t\tbitmap_set(bitmap, i);\n \t\tinsert_no_dup(&queue, c);\n \t}\n \n \twhile (queue_has_nonstale(&queue)) {\n-\t\tstruct commit *c = prio_queue_get(&queue);\n \t\tstruct commit_list *p;\n-\t\tstruct bitmap *bitmap_c = get_bit_array(c, width);\n+\t\tstruct bitmap *bitmap_c;\n+\t\tc = prio_queue_get(&queue);\n+\t\tbitmap_c = get_bit_array(c, width);\n \n \t\tfor (size_t i = 0; i < counts_nr; i++) {\n \t\t\tint reach_from_tip = !!bitmap_get(bitmap_c, counts[i].tip_index);\n@@ -1135,8 +1138,8 @@ void ahead_behind(struct repository *r,\n \n \t/* STALE is used here, PARENT2 is used by insert_no_dup(). */\n \trepo_clear_commit_marks(r, PARENT2 | STALE);\n-\tfor (size_t i = 0; i < queue.nr; i++)\n-\t\tfree_bit_array(queue.array[i].data);\n+\tprio_queue_for_each(&queue, c)\n+\t\tfree_bit_array(c);\n \tclear_bit_arrays(&bit_arrays);\n \tclear_prio_queue(&queue);\n }\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex 120e01f3cf..29c41132ee 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -662,8 +662,8 @@ static int mark_complete_oid(const struct reference *ref, void *cb_data UNUSED)\n static void mark_recent_complete_commits(struct fetch_pack_args *args,\n \t\t\t\t\t timestamp_t cutoff)\n {\n-\twhile (complete.nr) {\n-\t\tstruct commit *item = prio_queue_peek(&complete);\n+\tstruct commit *item;\n+\twhile ((item = prio_queue_peek(&complete))) {\n \t\tif (item->date < cutoff)\n \t\t\tbreak;\n \t\tprint_verbose(args, _(\"Marking %s as complete\"),\ndiff --git a/negotiator/default.c b/negotiator/default.c\nindex 78d58d57ce..19cdf3808c 100644\n--- a/negotiator/default.c\n+++ b/negotiator/default.c\n@@ -113,10 +113,12 @@ static const struct object_id *get_rev(struct negotiation_state *ns)\n \t\tunsigned int mark;\n \t\tstruct commit_list *parents;\n \n-\t\tif (ns->rev_list.nr == 0 || ns->non_common_revs == 0)\n+\t\tif (ns->non_common_revs == 0)\n \t\t\treturn NULL;\n \n \t\tcommit = prio_queue_get(&ns->rev_list);\n+\t\tif (!commit)\n+\t\t\treturn NULL;\n \t\trepo_parse_commit(the_repository, commit);\n \t\tparents = commit->parents;\n \ndiff --git a/negotiator/skipping.c b/negotiator/skipping.c\nindex 68c9b3b997..db90fa77b5 100644\n--- a/negotiator/skipping.c\n+++ b/negotiator/skipping.c\n@@ -143,8 +143,7 @@ static int push_parent(struct data *data, struct entry *entry,\n \t\t/*\n \t\t * Find the existing entry and use it.\n \t\t */\n-\t\tfor (size_t i = 0; i < data->rev_list.nr; i++) {\n-\t\t\tparent_entry = data->rev_list.array[i].data;\n+\t\tprio_queue_for_each(&data->rev_list, parent_entry) {\n \t\t\tif (parent_entry->commit == to_push)\n \t\t\t\tgoto parent_found;\n \t\t}\n@@ -181,10 +180,12 @@ static const struct object_id *get_rev(struct data *data)\n \t\tstruct commit_list *p;\n \t\tint parent_pushed = 0;\n \n-\t\tif (data->rev_list.nr == 0 || data->non_common_revs == 0)\n+\t\tif (data->non_common_revs == 0)\n \t\t\treturn NULL;\n \n \t\tentry = prio_queue_get(&data->rev_list);\n+\t\tif (!entry)\n+\t\t\treturn NULL;\n \t\tcommit = entry->commit;\n \t\tcommit->object.flags |= POPPED;\n \t\tif (!(commit->object.flags & COMMON))\n@@ -253,8 +254,9 @@ static void have_sent(struct fetch_negotiator *n, struct commit *c)\n static void release(struct fetch_negotiator *n)\n {\n \tstruct data *data = n->data;\n-\tfor (size_t i = 0; i < data->rev_list.nr; i++)\n-\t\tfree(data->rev_list.array[i].data);\n+\tvoid *entry;\n+\tprio_queue_for_each(&data->rev_list, entry)\n+\t\tfree(entry);\n \tclear_prio_queue(&data->rev_list);\n \tFREE_AND_NULL(data);\n }\ndiff --git a/object-name.c b/object-name.c\nindex 9ac86f19c7..2fedfe1761 100644\n--- a/object-name.c\n+++ b/object-name.c\n@@ -1208,7 +1208,7 @@ static int get_oid_oneline(struct repository *r,\n \t\tl->item->object.flags |= ONELINE_SEEN;\n \t\tprio_queue_put(&copy, l->item);\n \t}\n-\twhile (copy.nr) {\n+\twhile (prio_queue_size(&copy)) {\n \t\tconst char *p, *buf;\n \t\tstruct commit *commit;\n \t\tint matches;\ndiff --git a/pack-bitmap-write.c b/pack-bitmap-write.c\nindex f7c63e3027..ed9714b135 100644\n--- a/pack-bitmap-write.c\n+++ b/pack-bitmap-write.c\n@@ -514,6 +514,7 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,\n \t\t\t      const uint32_t *mapping)\n {\n \tstruct commit *c;\n+\tstruct tree *tree;\n \tint found;\n \tuint32_t pos;\n \tif (!ent->bitmap)\n@@ -574,9 +575,8 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,\n \t\t}\n \t}\n \n-\twhile (tree_queue->nr) {\n-\t\tif (fill_bitmap_tree(writer, ent->bitmap,\n-\t\t\t\t     prio_queue_get(tree_queue)) < 0)\n+\twhile ((tree = prio_queue_get(tree_queue))) {\n+\t\tif (fill_bitmap_tree(writer, ent->bitmap, tree) < 0)\n \t\t\treturn -1;\n \t}\n \treturn 0;\ndiff --git a/path-walk.c b/path-walk.c\nindex 94ff90bd15..cf3b2d0765 100644\n--- a/path-walk.c\n+++ b/path-walk.c\n@@ -699,6 +699,7 @@ int walk_objects_by_path(struct path_walk_info *info)\n \tint ret;\n \tsize_t commits_nr = 0, paths_nr = 0;\n \tstruct commit *c;\n+\tchar *path;\n \tstruct type_and_oid_list *root_tree_list;\n \tstruct type_and_oid_list *commit_list;\n \tstruct path_walk_context ctx = {\n@@ -808,8 +809,7 @@ int walk_objects_by_path(struct path_walk_info *info)\n \tfree(commit_list);\n \n \ttrace2_region_enter(\"path-walk\", \"path-walk\", info->revs->repo);\n-\twhile (!ret && ctx.path_stack.nr) {\n-\t\tchar *path = prio_queue_get(&ctx.path_stack);\n+\twhile (!ret && (path = prio_queue_get(&ctx.path_stack))) {\n \t\tpaths_nr++;\n \n \t\tret = walk_path(&ctx, path);\n@@ -821,12 +821,12 @@ int walk_objects_by_path(struct path_walk_info *info)\n \tif (!strmap_empty(&ctx.paths_to_lists)) {\n \t\tstruct hashmap_iter iter;\n \t\tstruct strmap_entry *entry;\n+\t\tchar *path;\n \n \t\tstrmap_for_each_entry(&ctx.paths_to_lists, &iter, entry)\n \t\t\tpush_to_stack(&ctx, entry->key);\n \n-\t\twhile (!ret && ctx.path_stack.nr) {\n-\t\t\tchar *path = prio_queue_get(&ctx.path_stack);\n+\t\twhile (!ret && (path = prio_queue_get(&ctx.path_stack))) {\n \t\t\tpaths_nr++;\n \n \t\t\tret = walk_path(&ctx, path);\ndiff --git a/prio-queue.c b/prio-queue.c\nindex a03c617470..f96b810c15 100644\n--- a/prio-queue.c\n+++ b/prio-queue.c\n@@ -22,16 +22,16 @@ void prio_queue_reverse(struct prio_queue *queue)\n \n \tif (queue->compare)\n \t\tBUG(\"prio_queue_reverse() on non-LIFO queue\");\n-\tif (!queue->nr)\n+\tif (!queue->nr_internal)\n \t\treturn;\n-\tfor (i = 0; i < (j = (queue->nr - 1) - i); i++)\n+\tfor (i = 0; i < (j = (queue->nr_internal - 1) - i); i++)\n \t\tswap(queue, i, j);\n }\n \n void clear_prio_queue(struct prio_queue *queue)\n {\n \tFREE_AND_NULL(queue->array);\n-\tqueue->nr = 0;\n+\tqueue->nr_internal = 0;\n \tqueue->alloc = 0;\n \tqueue->insertion_ctr = 0;\n \tqueue->get_pending = 0;\n@@ -41,13 +41,16 @@ static void sift_down_root(struct prio_queue *queue)\n {\n \tsize_t ix, child;\n \n-\tfor (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {\n-\t\tchild = ix * 2 + 1;\n-\t\tif (child + 1 < queue->nr &&\n+\t/* Push down the one at the root */\n+\tfor (ix = 0; ix * 2 + 1 < queue->nr_internal; ix = child) {\n+\t\tchild = ix * 2 + 1; /* left */\n+\t\tif (child + 1 < queue->nr_internal &&\n \t\t    compare(queue, child, child + 1) >= 0)\n-\t\t\tchild++;\n+\t\t\tchild++; /* use right child */\n+\n \t\tif (compare(queue, ix, child) <= 0)\n \t\t\tbreak;\n+\n \t\tswap(queue, child, ix);\n \t}\n }\n@@ -64,34 +67,37 @@ void prio_queue_put(struct prio_queue *queue, void *thing)\n \t\treturn;\n \t}\n \n-\tALLOC_GROW(queue->array, queue->nr + 1, queue->alloc);\n-\tqueue->array[queue->nr].ctr = queue->insertion_ctr++;\n-\tqueue->array[queue->nr].data = thing;\n-\tqueue->nr++;\n+\t/* Append at the end */\n+\tALLOC_GROW(queue->array, queue->nr_internal + 1, queue->alloc);\n+\tqueue->array[queue->nr_internal].ctr = queue->insertion_ctr++;\n+\tqueue->array[queue->nr_internal].data = thing;\n+\tqueue->nr_internal++;\n \tif (!queue->compare)\n-\t\treturn;\n+\t\treturn; /* LIFO */\n \n-\tfor (ix = queue->nr - 1; ix; ix = parent) {\n+\t/* Bubble up the new one */\n+\tfor (ix = queue->nr_internal - 1; ix; ix = parent) {\n \t\tparent = (ix - 1) / 2;\n \t\tif (compare(queue, parent, ix) <= 0)\n \t\t\tbreak;\n+\n \t\tswap(queue, parent, ix);\n \t}\n }\n \n void *prio_queue_get(struct prio_queue *queue)\n {\n-\tif (!queue->nr)\n+\tif (!queue->nr_internal)\n \t\treturn NULL;\n \tif (!queue->compare)\n-\t\treturn queue->array[--queue->nr].data;\n+\t\treturn queue->array[--queue->nr_internal].data; /* LIFO */\n \n \tif (queue->get_pending) {\n-\t\tif (!--queue->nr) {\n+\t\tif (!--queue->nr_internal) {\n \t\t\tqueue->get_pending = 0;\n \t\t\treturn NULL;\n \t\t}\n-\t\tqueue->array[0] = queue->array[queue->nr];\n+\t\tqueue->array[0] = queue->array[queue->nr_internal];\n \t\tsift_down_root(queue);\n \t}\n \n@@ -101,16 +107,16 @@ void *prio_queue_get(struct prio_queue *queue)\n \n void *prio_queue_peek(struct prio_queue *queue)\n {\n-\tif (!queue->nr)\n+\tif (!queue->nr_internal)\n \t\treturn NULL;\n \tif (!queue->compare)\n-\t\treturn queue->array[queue->nr - 1].data;\n+\t\treturn queue->array[queue->nr_internal - 1].data;\n \n \tif (queue->get_pending) {\n \t\tqueue->get_pending = 0;\n-\t\tif (!--queue->nr)\n+\t\tif (!--queue->nr_internal)\n \t\t\treturn NULL;\n-\t\tqueue->array[0] = queue->array[queue->nr];\n+\t\tqueue->array[0] = queue->array[queue->nr_internal];\n \t\tsift_down_root(queue);\n \t}\n \ndiff --git a/prio-queue.h b/prio-queue.h\nindex 482ab5e71d..f08ab87691 100644\n--- a/prio-queue.h\n+++ b/prio-queue.h\n@@ -30,7 +30,7 @@ struct prio_queue {\n \tprio_queue_compare_fn compare;\n \tsize_t insertion_ctr;\n \tvoid *cb_data;\n-\tsize_t alloc, nr;\n+\tsize_t alloc, nr_internal; /* use prio_queue_size() for logical count */\n \tstruct prio_queue_entry *array;\n \tunsigned get_pending;\n };\n@@ -55,9 +55,14 @@ void *prio_queue_peek(struct prio_queue *);\n \n static inline size_t prio_queue_size(struct prio_queue *queue)\n {\n-\treturn queue->nr - queue->get_pending;\n+\treturn queue->nr_internal - queue->get_pending;\n }\n \n+#define prio_queue_for_each(queue, it) \\\n+\tfor (size_t pq_ix_ = (queue)->get_pending; \\\n+\t     pq_ix_ < (queue)->nr_internal && ((it) = (queue)->array[pq_ix_].data, 1); \\\n+\t     pq_ix_++)\n+\n void clear_prio_queue(struct prio_queue *);\n \n /* Reverse the LIFO elements */\ndiff --git a/revision.c b/revision.c\nindex 8ce8ffa43d..34e2d146f4 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -476,16 +476,15 @@ static struct commit *handle_commit(struct rev_info *revs,\n static int everybody_uninteresting(struct prio_queue *orig,\n \t\t\t\t   struct commit **interesting_cache)\n {\n-\tsize_t i;\n+\tstruct commit *commit;\n \n \tif (*interesting_cache) {\n-\t\tstruct commit *commit = *interesting_cache;\n+\t\tcommit = *interesting_cache;\n \t\tif (!(commit->object.flags & UNINTERESTING))\n \t\t\treturn 0;\n \t}\n \n-\tfor (i = 0; i < orig->nr; i++) {\n-\t\tstruct commit *commit = orig->array[i].data;\n+\tprio_queue_for_each(orig, commit) {\n \t\tif (commit->object.flags & UNINTERESTING)\n \t\t\tcontinue;\n \n@@ -4027,8 +4026,8 @@ static enum rewrite_result rewrite_one_1(struct rev_info *revs,\n \n static void merge_queue_into_list(struct prio_queue *q, struct commit_list **list)\n {\n-\twhile (q->nr) {\n-\t\tstruct commit *item = prio_queue_peek(q);\n+\tstruct commit *item;\n+\twhile ((item = prio_queue_peek(q))) {\n \t\tstruct commit_list *p = *list;\n \n \t\tif (p && p->item->date >= item->date)\n-- \ngitgitgadget\n"},{"id":"544921","messageId":"xmqq5x3tyx0e.fsf@gitster.g","threadId":"65764","inReplyTo":"pull.2140.v3.git.1780832592.gitgitgadget@gmail.com","subject":"Re: [PATCH v3 0/2] prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-06-08T13:36:33Z","receivedAt":"2026-06-08T13:36:35Z","isPatch":true,"body":"\"Kristofer Karlsson via GitGitGadget\" <gitgitgadget@gmail.com>\nwrites:\n\n> Changes in v3:\n>\n>  * Adopted Rene's suggestion to move the flush logic below the LIFO\n>    early-return (LIFO mode never sets get_pending, so flushing there is a\n>    no-op).\n\nSensible.\n\n\n>  * Went a step further and inlined the flush logic directly into get() and\n>    peek(), eliminating the flush_get() helper and its forward declaration of\n>    sift_down_root().\n\nHmph, unless there is a reason to allow the copies in get() and\npeek() to deviate from each other, e.g., what flush_get() had to do\ninside get() and peek() were slightly different, I am not sure if\nthis is a good move.  I do not know if the slight difference of the\n\"inlined\" logic we have in the patch between the one in get() and\nthe other one in peek() has merit, either.  It certainly lets you\navoid an unnecessary clearing of the get_pending bit (when a get was\npending but the queue has more items to yield) immediately followed\nby turning it back on again (which happens always unless the\nfunction makes an early return for an empty queue) in get(), which\nwill never happen in flush() that will always clear the bit before\nit returns, but is such an avoidance of an assignment really worth\nit?  I suspect that with the static inline version of flush_get(),\ncompilers are smart enough to optimize it away, but I dunno.\n\n>        void *prio_queue_get(struct prio_queue *queue)\n>        {\n>        \tif (!queue->nr)\n>        \t\treturn NULL;\n>        \tif (!queue->compare)\n>      ++\t\treturn queue->array[--queue->nr].data;\n>      ++\n>      ++\tif (queue->get_pending) {\n>      ++\t\tif (!--queue->nr) {\n>      ++\t\t\tqueue->get_pending = 0;\n>      ++\t\t\treturn NULL;\n>      ++\t\t}\n>      ++\t\tqueue->array[0] = queue->array[queue->nr];\n>      ++\t\tsift_down_root(queue);\n>      ++\t}\n>      + \n\nThe above is from [1/2] (this is a minor point, but flipping the\norder of two patches to make the \"nr_internal clean-up\" as a\npreliminary step might have made commenting on this part easier to\nread).  I wondered if it is easier to understand if the first early\nreturn is guarded by a conditional that takes get_pending into\naccount.\n\n\tif (queue->nr_internal <= queue->get_pending)\n\t\treturn NULL;\n\nAs I said, since the above hunk is immediately followed by an\nunconditional assignment of \"queue->get_pending = 1\", clearing\nget_pending = 0 only when we leave inside the if() block works as an\noptimization that is not available on the peek() side.  But with the\n\"ah the queue is empty already, the queue->ne == 1 is due to the\nlazy get that did not rebalance\" tweak, it would become unneeded, I\nthink.\n\n>      + void *prio_queue_peek(struct prio_queue *queue)\n>      + {\n>       +\tif (!queue->nr_internal)\n>        \t\treturn NULL;\n>        \tif (!queue->compare)\n>       +\t\treturn queue->array[queue->nr_internal - 1].data;\n>      + \n>      + \tif (queue->get_pending) {\n>      + \t\tqueue->get_pending = 0;\n>      +-\t\tif (!--queue->nr)\n>      ++\t\tif (!--queue->nr_internal)\n>      + \t\t\treturn NULL;\n>      +-\t\tqueue->array[0] = queue->array[queue->nr];\n>      ++\t\tqueue->array[0] = queue->array[queue->nr_internal];\n>      + \t\tsift_down_root(queue);\n>      + \t}\n\nThis is from [2/2]; the same \n\n\tif (queue->nr_internal <= queue->get_pending)\n\t\treturn NULL;\n\napplies here, I think.\n"},{"id":"544931","messageId":"xmqqldcpxh0n.fsf@gitster.g","threadId":"65764","inReplyTo":"CAL71e4MbC+tdTuN6p1HiHtE1XYuS1gBM-KSejFZJ1wbftxNveg@mail.gmail.com","subject":"Re: [PATCH] prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-06-08T14:07:20Z","receivedAt":"2026-06-08T14:07:22Z","isPatch":true,"body":"Kristofer Karlsson <krka@spotify.com> writes:\n\n> Agreed, that's the right fix. I looked for existing ways of marking\n> fields as private, internal or hidden but the only thing I found was\n> the convention of using a code comment: /* for internal use only */\n>\n> I will apply a rename and submit a v2. Perhaps something like\n> nr_internal to make it look less like a public API.\n\n\nI think we often use trailing underscore (e.g., \"n_\") to mark\nvariables for \"not to be used casually, there are better ways to\naccess this information\", which pre-ANSI C people probably used\nleading underscore (e.g. \"_n\") for.\n\nThis is often used in callback functions where the types of their\nformal parameters are specified by the API and use of them with\ncasting at every use site is awkward.  For example, qsort() and\nfriends often take a pointer to the location that stores the value\nto be compared, but it is awkward, so we do cast just once upfront\nlike so:\n\nstatic int compare_callback(const void *a_, const void *b_)\n{\n\tconst a_type a = *((const a_type *)a_);\n\tconst a_type b = *((const a_type *)b_);\n\n        ... use values 'a' and 'b', without having to cast a_ or b_ ...\n\n\treturn a - b;\n}\n\nI think the technique/convention can be used in a similar way for\n\"this is hidden and unless you can tell if you should be using it\ndirectly, you probably shouldn't\" kind of structure members.\n\nSo, nr_internal is perfectly fine, but if you find it too long, nr_\nis probably just as good.\n"},{"id":"544960","messageId":"pull.2140.v4.git.1780945851.gitgitgadget@gmail.com","threadId":"65764","inReplyTo":"pull.2140.v3.git.1780832592.gitgitgadget@gmail.com","subject":"[PATCH v4 0/2] prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-06-08T19:10:49Z","receivedAt":"2026-06-08T19:10:55Z","isPatch":true,"body":"Rene's lazy_queue wrapper in describe.c was a clever optimization -- by\ndeferring the get, a following put becomes a simple replace, avoiding a full\nremove-rebalance-insert cycle.\n\nIt turns out this pattern is so common in git's traversal code that it makes\nsense to fold it into prio_queue itself. Gets and puts are interleaved in\nvirtually every commit walk, so the fusion is essentially always a win.\n\nThis is mostly a code simplification -- three callers had independently\nreimplemented the same optimization, and they all collapse to plain get+put\nnow. The 1.7-2.7% speedup on traversal-heavy workloads is a nice bonus.\n\nMore details and benchmark numbers in the commit message.\n\nRelated to but independent of the cascade sift-down work in\nkk/prio-queue-cascade-sift -- the two can land in either order.\n\nChanges in v4:\n\n * Thanks Junio for review, applied all suggestions.\n\n * Renamed .nr_internal to .nr_\n\n * Restored flush_get() as a static inline helper instead of inlining the\n   flush logic into get() and peek().\n\n * Guard empty-queue check with nr_ <= get_pending.\n\n * Flipped commit order: the rename/accessor commit is now first, and the\n   behavioral fusion change is second. This was partly messy -- the first\n   rename commit introduces some ugly intermediate code (e.g. describe.c's\n   prio_queue_for_each with a skip variable) that gets cleaned up in commit\n   2 when the lazy get makes it unnecessary.\n\nChanges in v3:\n\n * Adopted Rene's suggestion to move the flush logic below the LIFO\n   early-return (LIFO mode never sets get_pending, so flushing there is a\n   no-op).\n\n * Went a step further and inlined the flush logic directly into get() and\n   peek(), eliminating the flush_get() helper and its forward declaration of\n   sift_down_root().\n\n * Updated benchmark numbers with more rigorous methodology: 30 interleaved\n   runs with paired t-test on an idle server. Split results into code paths\n   that already had manual fusion (neutral) vs code paths that benefit from\n   the new automatic fusion (1.7-2.7% improvement).\n\nChanges in v2:\n\n * Added a second commit that renames .nr to .nr_internal so that direct\n   access from outside prio-queue.c is a compile error. Verified that after\n   the rename, only prio-queue.c references nr_internal.\n\n * Added prio_queue_for_each() macro for callers that need to walk all\n   elements (describe.c, show-branch.c, commit-reach.c, revision.c,\n   negotiator/skipping.c).\n\n * Converted remaining .nr loop conditions to use\n   prio_queue_get()/prio_queue_peek() as the loop condition, or\n   prio_queue_size() where get/peek isn't suitable.\n\n * Fixed several callers missed in v1 (object-name.c, fetch-pack.c,\n   path-walk.c, pack-bitmap-write.c, negotiator/default.c,\n   negotiator/skipping.c, revision.c, builtin/last-modified.c).\n\nKristofer Karlsson (2):\n  prio-queue: rename .nr to .nr_ and add accessor helpers\n  prio-queue: fold lazy_queue into prio_queue for automatic get+put\n    fusion\n\n builtin/describe.c          |  70 ++++++-----------------\n builtin/last-modified.c     |   7 +--\n builtin/show-branch.c       |  24 +++-----\n commit-reach.c              |  14 ++---\n commit.c                    |  11 +---\n fetch-pack.c                |   4 +-\n negotiator/default.c        |   4 +-\n negotiator/skipping.c       |  12 ++--\n object-name.c               |   2 +-\n pack-bitmap-write.c         |  10 ++--\n path-walk.c                 |   8 +--\n prio-queue.c                | 110 +++++++++++++++++++-----------------\n prio-queue.h                |  19 ++++---\n revision.c                  |  16 +++---\n t/unit-tests/u-prio-queue.c |   6 +-\n walker.c                    |   4 +-\n 16 files changed, 141 insertions(+), 180 deletions(-)\n\n\nbase-commit: 9ac3f193c05c2237e2b14ebaa1149e9fc8a1abe0\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-2140%2Fspkrka%2Flazy-prio-queue-pr-v4\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2140/spkrka/lazy-prio-queue-pr-v4\nPull-Request: https://github.com/gitgitgadget/git/pull/2140\n\nRange-diff vs v3:\n\n 2:  033215e304 ! 1:  d0f2294661 prio-queue: rename .nr to .nr_internal to prevent direct access\n     @@ Metadata\n      Author: Kristofer Karlsson <krka@spotify.com>\n      \n       ## Commit message ##\n     -    prio-queue: rename .nr to .nr_internal to prevent direct access\n     +    prio-queue: rename .nr to .nr_ and add accessor helpers\n      \n     -    Rename the .nr member to .nr_internal so that callers outside\n     -    prio-queue.c that directly reference .nr get a compilation error.\n     -    This catches both existing misuse and future in-flight topics.\n     +    Rename the .nr member to .nr_ so that callers outside prio-queue.c\n     +    that directly reference .nr get a compilation error.  This catches\n     +    both existing misuse and future in-flight topics.\n      \n     -    Add prio_queue_for_each() macro for callers that need to walk all\n     -    elements in the queue, accounting for the get_pending offset.\n     +    Add prio_queue_size() for callers that need to know the element count\n     +    and prio_queue_for_each() for callers that need to walk all elements.\n      \n          Convert all external .nr users:\n           - Loop conditions: use prio_queue_size(), prio_queue_get(), or\n     @@ Commit message\n          Signed-off-by: Kristofer Karlsson <krka@spotify.com>\n      \n       ## builtin/describe.c ##\n     -@@ builtin/describe.c: static unsigned long finish_depth_computation(struct prio_queue *queue,\n     - \tstruct oidset unflagged = OIDSET_INIT;\n     - \tstruct commit *c;\n     +@@ builtin/describe.c: static void lazy_queue_put(struct lazy_queue *queue, void *thing)\n       \n     --\tfor (size_t i = queue->get_pending; i < queue->nr; i++) {\n     --\t\tstruct commit *commit = queue->array[i].data;\n     --\t\tif (!(commit->object.flags & best->flag_within))\n     --\t\t\toidset_insert(&unflagged, &commit->object.oid);\n     -+\tprio_queue_for_each(queue, c) {\n     -+\t\tif (!(c->object.flags & best->flag_within))\n     -+\t\t\toidset_insert(&unflagged, &c->object.oid);\n     - \t}\n     + static bool lazy_queue_empty(const struct lazy_queue *queue)\n     + {\n     +-\treturn queue->queue.nr == (queue->get_pending ? 1 : 0);\n     ++\treturn prio_queue_size(&queue->queue) == (queue->get_pending ? 1 : 0);\n     + }\n       \n     - \twhile ((c = prio_queue_get(queue))) {\n     + static void lazy_queue_clear(struct lazy_queue *queue)\n     +@@ builtin/describe.c: static unsigned long finish_depth_computation(struct lazy_queue *queue,\n     + {\n     + \tunsigned long seen_commits = 0;\n     + \tstruct oidset unflagged = OIDSET_INIT;\n     ++\tstruct commit *commit;\n     ++\tint skip = queue->get_pending ? 1 : 0;\n     + \n     +-\tfor (size_t i = queue->get_pending ? 1 : 0; i < queue->queue.nr; i++) {\n     +-\t\tstruct commit *commit = queue->queue.array[i].data;\n     ++\tprio_queue_for_each(&queue->queue, commit) {\n     ++\t\tif (skip) {\n     ++\t\t\tskip = 0;\n     ++\t\t\tcontinue;\n     ++\t\t}\n     + \t\tif (!(commit->object.flags & best->flag_within))\n     + \t\t\toidset_insert(&unflagged, &commit->object.oid);\n     + \t}\n      \n       ## builtin/last-modified.c ##\n      @@ builtin/last-modified.c: static void process_parent(struct last_modified *lm,\n       static int last_modified_run(struct last_modified *lm)\n       {\n       \tint max_count, queue_popped = 0;\n     --\tstruct commit *c;\n      +\tstruct commit *c, *n;\n       \tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n       \tstruct prio_queue not_queue = { compare_commits_by_gen_then_commit_date };\n       \tstruct commit_list *list;\n     +@@ builtin/last-modified.c: static int last_modified_run(struct last_modified *lm)\n     + \t\t}\n     + \t}\n     + \n     +-\twhile (queue.nr) {\n     ++\twhile ((c = prio_queue_get(&queue))) {\n     + \t\tint parent_i;\n     + \t\tstruct commit_list *p;\n     +-\t\tstruct commit *c = prio_queue_get(&queue);\n     + \t\tstruct bitmap *active_c = active_paths_for(lm, c);\n     + \n     + \t\tif ((0 <= max_count && max_count < ++queue_popped) ||\n      @@ builtin/last-modified.c: static int last_modified_run(struct last_modified *lm)\n       \t\t */\n       \t\trepo_parse_commit(lm->rev.repo, c);\n     @@ builtin/show-branch.c: static const char *get_color_reset_code(void)\n       \n       static struct commit *interesting(struct prio_queue *queue)\n       {\n     --\tfor (size_t i = queue->get_pending; i < queue->nr; i++) {\n     +-\tfor (size_t i = 0; i < queue->nr; i++) {\n      -\t\tstruct commit *commit = queue->array[i].data;\n      -\t\tif (commit->object.flags & UNINTERESTING)\n      -\t\t\tcontinue;\n     @@ builtin/show-branch.c: static const char *get_color_reset_code(void)\n       \t}\n       \treturn NULL;\n       }\n     +@@ builtin/show-branch.c: static void join_revs(struct prio_queue *queue,\n     + {\n     + \tint all_mask = ((1u << (REV_SHIFT + num_rev)) - 1);\n     + \tint all_revs = all_mask & ~((1u << REV_SHIFT) - 1);\n     ++\tstruct commit *commit;\n     + \n     +-\twhile (queue->nr) {\n     ++\twhile ((commit = prio_queue_peek(queue))) {\n     + \t\tstruct commit_list *parents;\n     + \t\tint still_interesting = !!interesting(queue);\n     +-\t\tstruct commit *commit = prio_queue_peek(queue);\n     + \t\tbool get_pending = true;\n     + \t\tint flags = commit->object.flags & all_mask;\n     + \n      \n       ## commit-reach.c ##\n      @@ commit-reach.c: static int compare_commits_by_gen(const void *_a, const void *_b)\n     @@ commit-reach.c: static int compare_commits_by_gen(const void *_a, const void *_b\n       \t\t\treturn 1;\n       \t}\n      @@ commit-reach.c: void ahead_behind(struct repository *r,\n     - \t\t  struct commit **commits, size_t commits_nr,\n       \t\t  struct ahead_behind_count *counts, size_t counts_nr)\n       {\n     -+\tstruct commit *c;\n       \tstruct prio_queue queue = { .compare = compare_commits_by_gen_then_commit_date };\n     ++\tvoid *entry;\n       \tsize_t width = DIV_ROUND_UP(commits_nr, BITS_IN_EWORD);\n       \n     -@@ commit-reach.c: void ahead_behind(struct repository *r,\n     - \tinit_bit_arrays(&bit_arrays);\n     - \n     - \tfor (size_t i = 0; i < commits_nr; i++) {\n     --\t\tstruct commit *c = commits[i];\n     --\t\tstruct bitmap *bitmap = get_bit_array(c, width);\n     -+\t\tstruct bitmap *bitmap;\n     -+\t\tc = commits[i];\n     -+\t\tbitmap = get_bit_array(c, width);\n     - \n     - \t\tbitmap_set(bitmap, i);\n     - \t\tinsert_no_dup(&queue, c);\n     - \t}\n     - \n     - \twhile (queue_has_nonstale(&queue)) {\n     --\t\tstruct commit *c = prio_queue_get(&queue);\n     - \t\tstruct commit_list *p;\n     --\t\tstruct bitmap *bitmap_c = get_bit_array(c, width);\n     -+\t\tstruct bitmap *bitmap_c;\n     -+\t\tc = prio_queue_get(&queue);\n     -+\t\tbitmap_c = get_bit_array(c, width);\n     - \n     - \t\tfor (size_t i = 0; i < counts_nr; i++) {\n     - \t\t\tint reach_from_tip = !!bitmap_get(bitmap_c, counts[i].tip_index);\n     + \tif (!commits_nr || !counts_nr)\n      @@ commit-reach.c: void ahead_behind(struct repository *r,\n       \n       \t/* STALE is used here, PARENT2 is used by insert_no_dup(). */\n       \trepo_clear_commit_marks(r, PARENT2 | STALE);\n      -\tfor (size_t i = 0; i < queue.nr; i++)\n      -\t\tfree_bit_array(queue.array[i].data);\n     -+\tprio_queue_for_each(&queue, c)\n     -+\t\tfree_bit_array(c);\n     ++\tprio_queue_for_each(&queue, entry)\n     ++\t\tfree_bit_array(entry);\n       \tclear_bit_arrays(&bit_arrays);\n       \tclear_prio_queue(&queue);\n       }\n     +@@ commit-reach.c: int get_branch_base_for_tip(struct repository *r,\n     + \t\t\t    size_t bases_nr)\n     + {\n     + \tint best_index = -1;\n     +-\tstruct commit *branch_point = NULL;\n     ++\tstruct commit *c, *branch_point = NULL;\n     + \tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n     + \tint found_missing_gen = 0;\n     + \n     +@@ commit-reach.c: int get_branch_base_for_tip(struct repository *r,\n     + \t\tprio_queue_put(&queue, c);\n     + \t}\n     + \n     +-\twhile (queue.nr) {\n     +-\t\tstruct commit *c = prio_queue_get(&queue);\n     ++\twhile ((c = prio_queue_get(&queue))) {\n     + \t\tint best_for_c = get_best(c);\n     + \t\tint best_for_p, positive;\n     + \t\tstruct commit *parent;\n      \n       ## fetch-pack.c ##\n      @@ fetch-pack.c: static int mark_complete_oid(const struct reference *ref, void *cb_data UNUSED)\n     @@ object-name.c: static int get_oid_oneline(struct repository *r,\n      \n       ## pack-bitmap-write.c ##\n      @@ pack-bitmap-write.c: static int fill_bitmap_commit(struct bitmap_writer *writer,\n     + \t\t\t      struct bitmap_index *old_bitmap,\n       \t\t\t      const uint32_t *mapping)\n       {\n     - \tstruct commit *c;\n     ++\tstruct commit *c;\n      +\tstruct tree *tree;\n       \tint found;\n       \tuint32_t pos;\n       \tif (!ent->bitmap)\n      @@ pack-bitmap-write.c: static int fill_bitmap_commit(struct bitmap_writer *writer,\n     + \n     + \tprio_queue_put(queue, commit);\n     + \n     +-\twhile (queue->nr) {\n     ++\twhile ((c = prio_queue_get(queue))) {\n     + \t\tstruct commit_list *p;\n     +-\t\tstruct commit *c = prio_queue_get(queue);\n     + \n     + \t\tif (old_bitmap && mapping) {\n     + \t\t\tstruct ewah_bitmap *old;\n     +@@ pack-bitmap-write.c: static int fill_bitmap_commit(struct bitmap_writer *writer,\n       \t\t}\n       \t}\n       \n     @@ prio-queue.c: void prio_queue_reverse(struct prio_queue *queue)\n       \tif (queue->compare)\n       \t\tBUG(\"prio_queue_reverse() on non-LIFO queue\");\n      -\tif (!queue->nr)\n     -+\tif (!queue->nr_internal)\n     ++\tif (!queue->nr_)\n       \t\treturn;\n      -\tfor (i = 0; i < (j = (queue->nr - 1) - i); i++)\n     -+\tfor (i = 0; i < (j = (queue->nr_internal - 1) - i); i++)\n     ++\tfor (i = 0; i < (j = (queue->nr_ - 1) - i); i++)\n       \t\tswap(queue, i, j);\n       }\n       \n     @@ prio-queue.c: void prio_queue_reverse(struct prio_queue *queue)\n       {\n       \tFREE_AND_NULL(queue->array);\n      -\tqueue->nr = 0;\n     -+\tqueue->nr_internal = 0;\n     ++\tqueue->nr_ = 0;\n       \tqueue->alloc = 0;\n       \tqueue->insertion_ctr = 0;\n     - \tqueue->get_pending = 0;\n     -@@ prio-queue.c: static void sift_down_root(struct prio_queue *queue)\n     - {\n     - \tsize_t ix, child;\n     - \n     --\tfor (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {\n     --\t\tchild = ix * 2 + 1;\n     --\t\tif (child + 1 < queue->nr &&\n     -+\t/* Push down the one at the root */\n     -+\tfor (ix = 0; ix * 2 + 1 < queue->nr_internal; ix = child) {\n     -+\t\tchild = ix * 2 + 1; /* left */\n     -+\t\tif (child + 1 < queue->nr_internal &&\n     - \t\t    compare(queue, child, child + 1) >= 0)\n     --\t\t\tchild++;\n     -+\t\t\tchild++; /* use right child */\n     -+\n     - \t\tif (compare(queue, ix, child) <= 0)\n     - \t\t\tbreak;\n     -+\n     - \t\tswap(queue, child, ix);\n     - \t}\n       }\n      @@ prio-queue.c: void prio_queue_put(struct prio_queue *queue, void *thing)\n     - \t\treturn;\n     - \t}\n     + \tsize_t ix, parent;\n       \n     + \t/* Append at the end */\n      -\tALLOC_GROW(queue->array, queue->nr + 1, queue->alloc);\n      -\tqueue->array[queue->nr].ctr = queue->insertion_ctr++;\n      -\tqueue->array[queue->nr].data = thing;\n      -\tqueue->nr++;\n     -+\t/* Append at the end */\n     -+\tALLOC_GROW(queue->array, queue->nr_internal + 1, queue->alloc);\n     -+\tqueue->array[queue->nr_internal].ctr = queue->insertion_ctr++;\n     -+\tqueue->array[queue->nr_internal].data = thing;\n     -+\tqueue->nr_internal++;\n     ++\tALLOC_GROW(queue->array, queue->nr_ + 1, queue->alloc);\n     ++\tqueue->array[queue->nr_].ctr = queue->insertion_ctr++;\n     ++\tqueue->array[queue->nr_].data = thing;\n     ++\tqueue->nr_++;\n       \tif (!queue->compare)\n     --\t\treturn;\n     -+\t\treturn; /* LIFO */\n     + \t\treturn; /* LIFO */\n       \n     + \t/* Bubble up the new one */\n      -\tfor (ix = queue->nr - 1; ix; ix = parent) {\n     -+\t/* Bubble up the new one */\n     -+\tfor (ix = queue->nr_internal - 1; ix; ix = parent) {\n     ++\tfor (ix = queue->nr_ - 1; ix; ix = parent) {\n       \t\tparent = (ix - 1) / 2;\n       \t\tif (compare(queue, parent, ix) <= 0)\n       \t\t\tbreak;\n     -+\n     - \t\tswap(queue, parent, ix);\n     - \t}\n     - }\n     +@@ prio-queue.c: static void sift_down_root(struct prio_queue *queue)\n     + \tsize_t ix, child;\n     + \n     + \t/* Push down the one at the root */\n     +-\tfor (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {\n     ++\tfor (ix = 0; ix * 2 + 1 < queue->nr_; ix = child) {\n     + \t\tchild = ix * 2 + 1; /* left */\n     +-\t\tif (child + 1 < queue->nr &&\n     ++\t\tif (child + 1 < queue->nr_ &&\n     + \t\t    compare(queue, child, child + 1) >= 0)\n     + \t\t\tchild++; /* use right child */\n       \n     - void *prio_queue_get(struct prio_queue *queue)\n     +@@ prio-queue.c: void *prio_queue_get(struct prio_queue *queue)\n       {\n     + \tvoid *result;\n     + \n      -\tif (!queue->nr)\n     -+\tif (!queue->nr_internal)\n     ++\tif (!queue->nr_)\n       \t\treturn NULL;\n       \tif (!queue->compare)\n     --\t\treturn queue->array[--queue->nr].data;\n     -+\t\treturn queue->array[--queue->nr_internal].data; /* LIFO */\n     - \n     - \tif (queue->get_pending) {\n     --\t\tif (!--queue->nr) {\n     -+\t\tif (!--queue->nr_internal) {\n     - \t\t\tqueue->get_pending = 0;\n     - \t\t\treturn NULL;\n     - \t\t}\n     --\t\tqueue->array[0] = queue->array[queue->nr];\n     -+\t\tqueue->array[0] = queue->array[queue->nr_internal];\n     - \t\tsift_down_root(queue);\n     - \t}\n     - \n     -@@ prio-queue.c: void *prio_queue_get(struct prio_queue *queue)\n     +-\t\treturn queue->array[--queue->nr].data; /* LIFO */\n     ++\t\treturn queue->array[--queue->nr_].data; /* LIFO */\n     + \n     + \tresult = queue->array[0].data;\n     +-\tif (!--queue->nr)\n     ++\tif (!--queue->nr_)\n     + \t\treturn result;\n     + \n     +-\tqueue->array[0] = queue->array[queue->nr];\n     ++\tqueue->array[0] = queue->array[queue->nr_];\n     + \tsift_down_root(queue);\n     + \treturn result;\n     + }\n       \n       void *prio_queue_peek(struct prio_queue *queue)\n       {\n      -\tif (!queue->nr)\n     -+\tif (!queue->nr_internal)\n     ++\tif (!queue->nr_)\n       \t\treturn NULL;\n       \tif (!queue->compare)\n      -\t\treturn queue->array[queue->nr - 1].data;\n     -+\t\treturn queue->array[queue->nr_internal - 1].data;\n     - \n     - \tif (queue->get_pending) {\n     - \t\tqueue->get_pending = 0;\n     --\t\tif (!--queue->nr)\n     -+\t\tif (!--queue->nr_internal)\n     - \t\t\treturn NULL;\n     --\t\tqueue->array[0] = queue->array[queue->nr];\n     -+\t\tqueue->array[0] = queue->array[queue->nr_internal];\n     - \t\tsift_down_root(queue);\n     - \t}\n     ++\t\treturn queue->array[queue->nr_ - 1].data;\n     + \treturn queue->array[0].data;\n     + }\n       \n     + void prio_queue_replace(struct prio_queue *queue, void *thing)\n     + {\n     +-\tif (!queue->nr) {\n     ++\tif (!queue->nr_) {\n     + \t\tprio_queue_put(queue, thing);\n     + \t} else if (!queue->compare) {\n     +-\t\tqueue->array[queue->nr - 1].ctr = queue->insertion_ctr++;\n     +-\t\tqueue->array[queue->nr - 1].data = thing;\n     ++\t\tqueue->array[queue->nr_ - 1].ctr = queue->insertion_ctr++;\n     ++\t\tqueue->array[queue->nr_ - 1].data = thing;\n     + \t} else {\n     + \t\tqueue->array[0].ctr = queue->insertion_ctr++;\n     + \t\tqueue->array[0].data = thing;\n      \n       ## prio-queue.h ##\n      @@ prio-queue.h: struct prio_queue {\n     @@ prio-queue.h: struct prio_queue {\n       \tsize_t insertion_ctr;\n       \tvoid *cb_data;\n      -\tsize_t alloc, nr;\n     -+\tsize_t alloc, nr_internal; /* use prio_queue_size() for logical count */\n     ++\tsize_t alloc, nr_;\n       \tstruct prio_queue_entry *array;\n     - \tunsigned get_pending;\n       };\n     -@@ prio-queue.h: void *prio_queue_peek(struct prio_queue *);\n       \n     - static inline size_t prio_queue_size(struct prio_queue *queue)\n     - {\n     --\treturn queue->nr - queue->get_pending;\n     -+\treturn queue->nr_internal - queue->get_pending;\n     - }\n     +@@ prio-queue.h: void *prio_queue_get(struct prio_queue *);\n     +  */\n     + void *prio_queue_peek(struct prio_queue *);\n       \n     ++static inline size_t prio_queue_size(const struct prio_queue *queue)\n     ++{\n     ++\treturn queue->nr_;\n     ++}\n     ++\n      +#define prio_queue_for_each(queue, it) \\\n     -+\tfor (size_t pq_ix_ = (queue)->get_pending; \\\n     -+\t     pq_ix_ < (queue)->nr_internal && ((it) = (queue)->array[pq_ix_].data, 1); \\\n     ++\tfor (size_t pq_ix_ = 0; \\\n     ++\t     pq_ix_ < (queue)->nr_ && ((it) = (queue)->array[pq_ix_].data, 1); \\\n      +\t     pq_ix_++)\n      +\n     - void clear_prio_queue(struct prio_queue *);\n     - \n     - /* Reverse the LIFO elements */\n     + /*\n     +  * Replace the \"thing\" that compares the smallest with a new \"thing\",\n     +  * like prio_queue_get()+prio_queue_put() would do, but in a more\n      \n       ## revision.c ##\n      @@ revision.c: static struct commit *handle_commit(struct rev_info *revs,\n     @@ revision.c: static struct commit *handle_commit(struct rev_info *revs,\n       \t\tif (commit->object.flags & UNINTERESTING)\n       \t\t\tcontinue;\n       \n     +@@ revision.c: static int limit_list(struct rev_info *revs)\n     + \tstruct commit_list *original_list = revs->commits;\n     + \tstruct commit_list *newlist = NULL;\n     + \tstruct commit_list **p = &newlist;\n     +-\tstruct commit *interesting_cache = NULL;\n     ++\tstruct commit *commit, *interesting_cache = NULL;\n     + \tstruct prio_queue queue = { .compare = compare_commits_by_commit_date };\n     + \n     + \tif (revs->ancestry_path_implicit_bottoms) {\n     +@@ revision.c: static int limit_list(struct rev_info *revs)\n     + \t\tprio_queue_put(&queue, commit);\n     + \t}\n     + \n     +-\twhile (queue.nr) {\n     +-\t\tstruct commit *commit = prio_queue_get(&queue);\n     ++\twhile ((commit = prio_queue_get(&queue))) {\n     + \t\tstruct object *obj = &commit->object;\n     + \n     + \t\tif (commit == interesting_cache)\n      @@ revision.c: static enum rewrite_result rewrite_one_1(struct rev_info *revs,\n       \n       static void merge_queue_into_list(struct prio_queue *q, struct commit_list **list)\n     @@ revision.c: static enum rewrite_result rewrite_one_1(struct rev_info *revs,\n       \t\tstruct commit_list *p = *list;\n       \n       \t\tif (p && p->item->date >= item->date)\n     +\n     + ## walker.c ##\n     +@@ walker.c: static struct prio_queue complete = { compare_commits_by_commit_date };\n     + static int process_commit(struct walker *walker, struct commit *commit)\n     + {\n     + \tstruct commit_list *parents;\n     ++\tstruct commit *item;\n     + \n     + \tif (repo_parse_commit(the_repository, commit))\n     + \t\treturn -1;\n     + \n     +-\twhile (complete.nr) {\n     +-\t\tstruct commit *item = prio_queue_peek(&complete);\n     ++\twhile ((item = prio_queue_peek(&complete))) {\n     + \t\tif (item->date < commit->date)\n     + \t\t\tbreak;\n     + \t\tpop_most_recent_commit(&complete, COMPLETE);\n 1:  e882206d29 ! 2:  a3f4cb57f2 prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion\n     @@ Commit message\n      \n          Defer the actual removal in prio_queue_get() until the next\n          operation.  If that next operation is a prio_queue_put(), the\n     -    removal and insertion are fused into a single replace, writing\n     -    the new element at the root and sifting it down which avoids\n     +    removal and insertion are fused into a single replace — writing\n     +    the new element at the root and sifting it down — which avoids\n          a full remove-rebalance-insert cycle.\n      \n          This matches the dominant usage pattern in git's commit traversal:\n     -    get a commit, then put its parents. The first parent insertion\n     +    get a commit, then put its parents.  The first parent insertion\n          after each get is now a replace operation automatically.\n      \n          This generalizes the lazy_queue pattern from builtin/describe.c\n     -    (introduced in 08bb69d70f) into prio_queue itself. Three callers\n     +    (introduced in 08bb69d70f) into prio_queue itself.  Three callers\n          independently implemented the same get+put fusion:\n      \n            - builtin/describe.c had a full lazy_queue wrapper\n     @@ Commit message\n            - builtin/show-branch.c:join_revs() used peek+replace\n      \n          All three now collapse to plain _get() and _put(), with the data\n     -    structure handling the fusion internally. This simplifies callers\n     +    structure handling the fusion internally.  This simplifies callers\n          and means every prio_queue user gets the optimization for free\n          without needing to implement it manually.\n      \n          Remove prio_queue_replace() since no external callers remain.\n     -    Add prio_queue_size() for callers that need the logical element\n     -    count, since the physical nr may temporarily include a\n     -    pending-removal element.\n      \n     -    Benchmarked on a large monorepo (30 interleaved runs,\n     +    Benchmarked on a 1.8M-commit monorepo (30 interleaved runs,\n          paired t-test, Xeon @ 2.20GHz):\n      \n          Code paths that previously did eager get+put (new optimization):\n      \n     -      Command                       base    patched  change  p\n     +      Command                       base    patched  change      p\n            merge-base --all A A~1000     3828ms  3725ms   -2.69%  0.0001\n            rev-list --count A~1000..A    3055ms  2986ms   -2.27%  0.0601\n            log --oneline A~1000..A       3408ms  3350ms   -1.71%  0.0482\n      \n          Code paths that already had manual get+put fusion (expect\n     -    neutral - the optimization moves into prio_queue but the number\n     +    neutral — the optimization moves into prio_queue but the number\n          of heap operations stays the same):\n      \n     -      Command                base   patched  change  p\n     -      show-branch A A~1000   9156ms  9127ms  -0.32%  0.3470\n     -      describe (git.git)     1983ms  1963ms  -1.02%  <0.001\n     +      Command                       base    patched  change      p\n     +      show-branch A A~1000          9156ms  9127ms   -0.32%  0.3470\n     +      describe (4751 revs, 81K repo) 1983ms 1963ms  -1.02%  <0.001\n      \n          No regressions in any scenario.\n      \n     @@ builtin/describe.c: static int compare_pt(const void *a_, const void *b_)\n      -\n      -static bool lazy_queue_empty(const struct lazy_queue *queue)\n      -{\n     --\treturn queue->queue.nr == (queue->get_pending ? 1 : 0);\n     +-\treturn prio_queue_size(&queue->queue) == (queue->get_pending ? 1 : 0);\n      -}\n      -\n      -static void lazy_queue_clear(struct lazy_queue *queue)\n     @@ builtin/describe.c: static int compare_pt(const void *a_, const void *b_)\n       {\n       \tunsigned long seen_commits = 0;\n       \tstruct oidset unflagged = OIDSET_INIT;\n     +-\tstruct commit *commit;\n     +-\tint skip = queue->get_pending ? 1 : 0;\n      +\tstruct commit *c;\n       \n     --\tfor (size_t i = queue->get_pending ? 1 : 0; i < queue->queue.nr; i++) {\n     --\t\tstruct commit *commit = queue->queue.array[i].data;\n     -+\tfor (size_t i = queue->get_pending; i < queue->nr; i++) {\n     -+\t\tstruct commit *commit = queue->array[i].data;\n     - \t\tif (!(commit->object.flags & best->flag_within))\n     - \t\t\toidset_insert(&unflagged, &commit->object.oid);\n     +-\tprio_queue_for_each(&queue->queue, commit) {\n     +-\t\tif (skip) {\n     +-\t\t\tskip = 0;\n     +-\t\t\tcontinue;\n     +-\t\t}\n     +-\t\tif (!(commit->object.flags & best->flag_within))\n     +-\t\t\toidset_insert(&unflagged, &commit->object.oid);\n     ++\tprio_queue_for_each(queue, c) {\n     ++\t\tif (!(c->object.flags & best->flag_within))\n     ++\t\t\toidset_insert(&unflagged, &c->object.oid);\n       \t}\n       \n      -\twhile (!lazy_queue_empty(queue)) {\n     @@ builtin/describe.c: static void describe_commit(struct commit *cmit, struct strb\n       \tif (debug) {\n       \t\tstatic int label_width = -1;\n      \n     - ## builtin/last-modified.c ##\n     -@@ builtin/last-modified.c: static void process_parent(struct last_modified *lm,\n     - static int last_modified_run(struct last_modified *lm)\n     - {\n     - \tint max_count, queue_popped = 0;\n     -+\tstruct commit *c;\n     - \tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n     - \tstruct prio_queue not_queue = { compare_commits_by_gen_then_commit_date };\n     - \tstruct commit_list *list;\n     -@@ builtin/last-modified.c: static int last_modified_run(struct last_modified *lm)\n     - \t\t}\n     - \t}\n     - \n     --\twhile (queue.nr) {\n     -+\twhile ((c = prio_queue_get(&queue))) {\n     - \t\tint parent_i;\n     - \t\tstruct commit_list *p;\n     --\t\tstruct commit *c = prio_queue_get(&queue);\n     - \t\tstruct bitmap *active_c = active_paths_for(lm, c);\n     - \n     - \t\tif ((0 <= max_count && max_count < ++queue_popped) ||\n     -\n       ## builtin/show-branch.c ##\n     -@@ builtin/show-branch.c: static const char *get_color_reset_code(void)\n     - \n     - static struct commit *interesting(struct prio_queue *queue)\n     - {\n     --\tfor (size_t i = 0; i < queue->nr; i++) {\n     -+\tfor (size_t i = queue->get_pending; i < queue->nr; i++) {\n     - \t\tstruct commit *commit = queue->array[i].data;\n     - \t\tif (commit->object.flags & UNINTERESTING)\n     - \t\t\tcontinue;\n      @@ builtin/show-branch.c: static void join_revs(struct prio_queue *queue,\n     - {\n     - \tint all_mask = ((1u << (REV_SHIFT + num_rev)) - 1);\n     - \tint all_revs = all_mask & ~((1u << REV_SHIFT) - 1);\n     -+\tstruct commit *commit;\n     - \n     --\twhile (queue->nr) {\n     -+\twhile ((commit = prio_queue_peek(queue))) {\n     + \twhile ((commit = prio_queue_peek(queue))) {\n       \t\tstruct commit_list *parents;\n       \t\tint still_interesting = !!interesting(queue);\n     --\t\tstruct commit *commit = prio_queue_peek(queue);\n      -\t\tbool get_pending = true;\n       \t\tint flags = commit->object.flags & all_mask;\n       \n     @@ builtin/show-branch.c: static void join_revs(struct prio_queue *queue,\n       \n       \t/*\n      \n     - ## commit-reach.c ##\n     -@@ commit-reach.c: int get_branch_base_for_tip(struct repository *r,\n     - \t\t\t    size_t bases_nr)\n     - {\n     - \tint best_index = -1;\n     --\tstruct commit *branch_point = NULL;\n     -+\tstruct commit *c, *branch_point = NULL;\n     - \tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n     - \tint found_missing_gen = 0;\n     - \n     -@@ commit-reach.c: int get_branch_base_for_tip(struct repository *r,\n     - \t\tprio_queue_put(&queue, c);\n     - \t}\n     - \n     --\twhile (queue.nr) {\n     --\t\tstruct commit *c = prio_queue_get(&queue);\n     -+\twhile ((c = prio_queue_get(&queue))) {\n     - \t\tint best_for_c = get_best(c);\n     - \t\tint best_for_p, positive;\n     - \t\tstruct commit *parent;\n     -\n       ## commit.c ##\n      @@ commit.c: void commit_list_sort_by_date(struct commit_list **list)\n       struct commit *pop_most_recent_commit(struct prio_queue *queue,\n     @@ commit.c: void commit_list_sort_by_date(struct commit_list **list)\n       }\n       \n      \n     - ## pack-bitmap-write.c ##\n     -@@ pack-bitmap-write.c: static int fill_bitmap_commit(struct bitmap_writer *writer,\n     - \t\t\t      struct bitmap_index *old_bitmap,\n     - \t\t\t      const uint32_t *mapping)\n     - {\n     -+\tstruct commit *c;\n     - \tint found;\n     - \tuint32_t pos;\n     - \tif (!ent->bitmap)\n     -@@ pack-bitmap-write.c: static int fill_bitmap_commit(struct bitmap_writer *writer,\n     - \n     - \tprio_queue_put(queue, commit);\n     - \n     --\twhile (queue->nr) {\n     -+\twhile ((c = prio_queue_get(queue))) {\n     - \t\tstruct commit_list *p;\n     --\t\tstruct commit *c = prio_queue_get(queue);\n     - \n     - \t\tif (old_bitmap && mapping) {\n     - \t\t\tstruct ewah_bitmap *old;\n     -\n       ## prio-queue.c ##\n      @@ prio-queue.c: void clear_prio_queue(struct prio_queue *queue)\n     - \tqueue->nr = 0;\n     + \tqueue->nr_ = 0;\n       \tqueue->alloc = 0;\n       \tqueue->insertion_ctr = 0;\n      +\tqueue->get_pending = 0;\n     @@ prio-queue.c: void clear_prio_queue(struct prio_queue *queue)\n      +{\n      +\tsize_t ix, child;\n      +\n     -+\tfor (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {\n     -+\t\tchild = ix * 2 + 1;\n     -+\t\tif (child + 1 < queue->nr &&\n     ++\t/* Push down the one at the root */\n     ++\tfor (ix = 0; ix * 2 + 1 < queue->nr_; ix = child) {\n     ++\t\tchild = ix * 2 + 1; /* left */\n     ++\t\tif (child + 1 < queue->nr_ &&\n      +\t\t    compare(queue, child, child + 1) >= 0)\n     -+\t\t\tchild++;\n     ++\t\t\tchild++; /* use right child */\n     ++\n      +\t\tif (compare(queue, ix, child) <= 0)\n      +\t\t\tbreak;\n     ++\n      +\t\tswap(queue, child, ix);\n      +\t}\n     ++}\n     ++\n     ++static inline void flush_get(struct prio_queue *queue)\n     ++{\n     ++\tif (!queue->get_pending)\n     ++\t\treturn;\n     ++\tqueue->get_pending = 0;\n     ++\tqueue->array[0] = queue->array[--queue->nr_];\n     ++\tsift_down_root(queue);\n       }\n       \n       void prio_queue_put(struct prio_queue *queue, void *thing)\n       {\n       \tsize_t ix, parent;\n       \n     --\t/* Append at the end */\n      +\tif (queue->get_pending) {\n      +\t\tqueue->get_pending = 0;\n      +\t\tqueue->array[0].ctr = queue->insertion_ctr++;\n     @@ prio-queue.c: void clear_prio_queue(struct prio_queue *queue)\n      +\t\treturn;\n      +\t}\n      +\n     - \tALLOC_GROW(queue->array, queue->nr + 1, queue->alloc);\n     - \tqueue->array[queue->nr].ctr = queue->insertion_ctr++;\n     - \tqueue->array[queue->nr].data = thing;\n     - \tqueue->nr++;\n     - \tif (!queue->compare)\n     --\t\treturn; /* LIFO */\n     -+\t\treturn;\n     - \n     --\t/* Bubble up the new one */\n     - \tfor (ix = queue->nr - 1; ix; ix = parent) {\n     - \t\tparent = (ix - 1) / 2;\n     - \t\tif (compare(queue, parent, ix) <= 0)\n     - \t\t\tbreak;\n     --\n     - \t\tswap(queue, parent, ix);\n     + \t/* Append at the end */\n     + \tALLOC_GROW(queue->array, queue->nr_ + 1, queue->alloc);\n     + \tqueue->array[queue->nr_].ctr = queue->insertion_ctr++;\n     +@@ prio-queue.c: void prio_queue_put(struct prio_queue *queue, void *thing)\n       \t}\n       }\n       \n     @@ prio-queue.c: void clear_prio_queue(struct prio_queue *queue)\n      -\tsize_t ix, child;\n      -\n      -\t/* Push down the one at the root */\n     --\tfor (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {\n     +-\tfor (ix = 0; ix * 2 + 1 < queue->nr_; ix = child) {\n      -\t\tchild = ix * 2 + 1; /* left */\n     --\t\tif (child + 1 < queue->nr &&\n     +-\t\tif (child + 1 < queue->nr_ &&\n      -\t\t    compare(queue, child, child + 1) >= 0)\n      -\t\t\tchild++; /* use right child */\n      -\n     @@ prio-queue.c: void clear_prio_queue(struct prio_queue *queue)\n       {\n      -\tvoid *result;\n      -\n     - \tif (!queue->nr)\n     +-\tif (!queue->nr_)\n     ++\tif (queue->nr_ <= queue->get_pending) {\n     ++\t\tqueue->nr_ = 0;\n     ++\t\tqueue->get_pending = 0;\n       \t\treturn NULL;\n     ++\t}\n       \tif (!queue->compare)\n     --\t\treturn queue->array[--queue->nr].data; /* LIFO */\n     --\n     + \t\treturn queue->array[--queue->nr_].data; /* LIFO */\n     + \n      -\tresult = queue->array[0].data;\n     --\tif (!--queue->nr)\n     +-\tif (!--queue->nr_)\n      -\t\treturn result;\n     -+\t\treturn queue->array[--queue->nr].data;\n     -+\n     -+\tif (queue->get_pending) {\n     -+\t\tif (!--queue->nr) {\n     -+\t\t\tqueue->get_pending = 0;\n     -+\t\t\treturn NULL;\n     -+\t\t}\n     -+\t\tqueue->array[0] = queue->array[queue->nr];\n     -+\t\tsift_down_root(queue);\n     -+\t}\n     ++\tflush_get(queue);\n       \n     --\tqueue->array[0] = queue->array[queue->nr];\n     +-\tqueue->array[0] = queue->array[queue->nr_];\n      -\tsift_down_root(queue);\n      -\treturn result;\n      +\tqueue->get_pending = 1;\n     @@ prio-queue.c: void clear_prio_queue(struct prio_queue *queue)\n       }\n       \n       void *prio_queue_peek(struct prio_queue *queue)\n     -@@ prio-queue.c: void *prio_queue_peek(struct prio_queue *queue)\n     + {\n     +-\tif (!queue->nr_)\n     ++\tif (queue->nr_ <= queue->get_pending) {\n     ++\t\tqueue->nr_ = 0;\n     ++\t\tqueue->get_pending = 0;\n       \t\treturn NULL;\n     ++\t}\n       \tif (!queue->compare)\n     - \t\treturn queue->array[queue->nr - 1].data;\n     + \t\treturn queue->array[queue->nr_ - 1].data;\n      -\treturn queue->array[0].data;\n      -}\n       \n      -void prio_queue_replace(struct prio_queue *queue, void *thing)\n      -{\n     --\tif (!queue->nr) {\n     +-\tif (!queue->nr_) {\n      -\t\tprio_queue_put(queue, thing);\n      -\t} else if (!queue->compare) {\n     --\t\tqueue->array[queue->nr - 1].ctr = queue->insertion_ctr++;\n     --\t\tqueue->array[queue->nr - 1].data = thing;\n     +-\t\tqueue->array[queue->nr_ - 1].ctr = queue->insertion_ctr++;\n     +-\t\tqueue->array[queue->nr_ - 1].data = thing;\n      -\t} else {\n      -\t\tqueue->array[0].ctr = queue->insertion_ctr++;\n      -\t\tqueue->array[0].data = thing;\n     -+\tif (queue->get_pending) {\n     -+\t\tqueue->get_pending = 0;\n     -+\t\tif (!--queue->nr)\n     -+\t\t\treturn NULL;\n     -+\t\tqueue->array[0] = queue->array[queue->nr];\n     - \t\tsift_down_root(queue);\n     - \t}\n     +-\t\tsift_down_root(queue);\n     +-\t}\n     ++\tflush_get(queue);\n      +\n      +\treturn queue->array[0].data;\n       }\n      \n       ## prio-queue.h ##\n      @@ prio-queue.h: struct prio_queue {\n     + \tprio_queue_compare_fn compare;\n     + \tsize_t insertion_ctr;\n       \tvoid *cb_data;\n     - \tsize_t alloc, nr;\n     +-\tsize_t alloc, nr_;\n     ++\tsize_t alloc, nr_; /* use prio_queue_size() for logical count */\n       \tstruct prio_queue_entry *array;\n      +\tunsigned get_pending;\n       };\n       \n       /*\n     -@@ prio-queue.h: void *prio_queue_get(struct prio_queue *);\n     -  */\n     - void *prio_queue_peek(struct prio_queue *);\n     +@@ prio-queue.h: void *prio_queue_peek(struct prio_queue *);\n     + \n     + static inline size_t prio_queue_size(const struct prio_queue *queue)\n     + {\n     +-\treturn queue->nr_;\n     ++\treturn queue->nr_ - queue->get_pending;\n     + }\n     + \n     + #define prio_queue_for_each(queue, it) \\\n     +-\tfor (size_t pq_ix_ = 0; \\\n     ++\tfor (size_t pq_ix_ = (queue)->get_pending; \\\n     + \t     pq_ix_ < (queue)->nr_ && ((it) = (queue)->array[pq_ix_].data, 1); \\\n     + \t     pq_ix_++)\n       \n      -/*\n      - * Replace the \"thing\" that compares the smallest with a new \"thing\",\n     @@ prio-queue.h: void *prio_queue_get(struct prio_queue *);\n      - * empty.\n      - */\n      -void prio_queue_replace(struct prio_queue *queue, void *thing);\n     -+static inline size_t prio_queue_size(struct prio_queue *queue)\n     -+{\n     -+\treturn queue->nr - queue->get_pending;\n     -+}\n     - \n     +-\n       void clear_prio_queue(struct prio_queue *);\n       \n     -\n     - ## revision.c ##\n     -@@ revision.c: static int limit_list(struct rev_info *revs)\n     - \tstruct commit_list *original_list = revs->commits;\n     - \tstruct commit_list *newlist = NULL;\n     - \tstruct commit_list **p = &newlist;\n     --\tstruct commit *interesting_cache = NULL;\n     -+\tstruct commit *commit, *interesting_cache = NULL;\n     - \tstruct prio_queue queue = { .compare = compare_commits_by_commit_date };\n     - \n     - \tif (revs->ancestry_path_implicit_bottoms) {\n     -@@ revision.c: static int limit_list(struct rev_info *revs)\n     - \t\tprio_queue_put(&queue, commit);\n     - \t}\n     - \n     --\twhile (queue.nr) {\n     --\t\tstruct commit *commit = prio_queue_get(&queue);\n     -+\twhile ((commit = prio_queue_get(&queue))) {\n     - \t\tstruct object *obj = &commit->object;\n     - \n     - \t\tif (commit == interesting_cache)\n     + /* Reverse the LIFO elements */\n      \n       ## t/unit-tests/u-prio-queue.c ##\n      @@ t/unit-tests/u-prio-queue.c: static void test_prio_queue(int *input, size_t input_size,\n     @@ t/unit-tests/u-prio-queue.c: static void test_prio_queue(int *input, size_t inpu\n       \t\t\tbreak;\n       \t\tdefault:\n       \t\t\tprio_queue_put(&pq, &input[i]);\n     -\n     - ## walker.c ##\n     -@@ walker.c: static struct prio_queue complete = { compare_commits_by_commit_date };\n     - static int process_commit(struct walker *walker, struct commit *commit)\n     - {\n     - \tstruct commit_list *parents;\n     -+\tstruct commit *item;\n     - \n     - \tif (repo_parse_commit(the_repository, commit))\n     - \t\treturn -1;\n     - \n     --\twhile (complete.nr) {\n     --\t\tstruct commit *item = prio_queue_peek(&complete);\n     -+\twhile ((item = prio_queue_peek(&complete))) {\n     - \t\tif (item->date < commit->date)\n     - \t\t\tbreak;\n     - \t\tpop_most_recent_commit(&complete, COMPLETE);\n\n-- \ngitgitgadget\n"},{"id":"544961","messageId":"d0f22946610492695d42b6f98368157625b246a2.1780945851.git.gitgitgadget@gmail.com","threadId":"65764","inReplyTo":"pull.2140.v4.git.1780945851.gitgitgadget@gmail.com","subject":"[PATCH v4 1/2] prio-queue: rename .nr to .nr_ and add accessor helpers","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-06-08T19:10:50Z","receivedAt":"2026-06-08T19:10:56Z","isPatch":true,"body":"From: Kristofer Karlsson <krka@spotify.com>\n\nRename the .nr member to .nr_ so that callers outside prio-queue.c\nthat directly reference .nr get a compilation error.  This catches\nboth existing misuse and future in-flight topics.\n\nAdd prio_queue_size() for callers that need to know the element count\nand prio_queue_for_each() for callers that need to walk all elements.\n\nConvert all external .nr users:\n - Loop conditions: use prio_queue_size(), prio_queue_get(), or\n   prio_queue_peek() as the loop condition\n - Array iterations: use prio_queue_for_each()\n\nSigned-off-by: Kristofer Karlsson <krka@spotify.com>\n---\n builtin/describe.c      | 11 ++++++++---\n builtin/last-modified.c |  7 +++----\n builtin/show-branch.c   | 13 ++++++-------\n commit-reach.c          | 14 +++++++-------\n fetch-pack.c            |  4 ++--\n negotiator/default.c    |  4 +++-\n negotiator/skipping.c   | 12 +++++++-----\n object-name.c           |  2 +-\n pack-bitmap-write.c     | 10 +++++-----\n path-walk.c             |  8 ++++----\n prio-queue.c            | 38 +++++++++++++++++++-------------------\n prio-queue.h            | 12 +++++++++++-\n revision.c              | 16 +++++++---------\n walker.c                |  4 ++--\n 14 files changed, 85 insertions(+), 70 deletions(-)\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 1c47d7c0b7..8e88bdeea6 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -278,7 +278,7 @@ static void lazy_queue_put(struct lazy_queue *queue, void *thing)\n \n static bool lazy_queue_empty(const struct lazy_queue *queue)\n {\n-\treturn queue->queue.nr == (queue->get_pending ? 1 : 0);\n+\treturn prio_queue_size(&queue->queue) == (queue->get_pending ? 1 : 0);\n }\n \n static void lazy_queue_clear(struct lazy_queue *queue)\n@@ -292,9 +292,14 @@ static unsigned long finish_depth_computation(struct lazy_queue *queue,\n {\n \tunsigned long seen_commits = 0;\n \tstruct oidset unflagged = OIDSET_INIT;\n+\tstruct commit *commit;\n+\tint skip = queue->get_pending ? 1 : 0;\n \n-\tfor (size_t i = queue->get_pending ? 1 : 0; i < queue->queue.nr; i++) {\n-\t\tstruct commit *commit = queue->queue.array[i].data;\n+\tprio_queue_for_each(&queue->queue, commit) {\n+\t\tif (skip) {\n+\t\t\tskip = 0;\n+\t\t\tcontinue;\n+\t\t}\n \t\tif (!(commit->object.flags & best->flag_within))\n \t\t\toidset_insert(&unflagged, &commit->object.oid);\n \t}\ndiff --git a/builtin/last-modified.c b/builtin/last-modified.c\nindex 8900ceece1..5478182f2e 100644\n--- a/builtin/last-modified.c\n+++ b/builtin/last-modified.c\n@@ -344,6 +344,7 @@ static void process_parent(struct last_modified *lm,\n static int last_modified_run(struct last_modified *lm)\n {\n \tint max_count, queue_popped = 0;\n+\tstruct commit *c, *n;\n \tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n \tstruct prio_queue not_queue = { compare_commits_by_gen_then_commit_date };\n \tstruct commit_list *list;\n@@ -389,10 +390,9 @@ static int last_modified_run(struct last_modified *lm)\n \t\t}\n \t}\n \n-\twhile (queue.nr) {\n+\twhile ((c = prio_queue_get(&queue))) {\n \t\tint parent_i;\n \t\tstruct commit_list *p;\n-\t\tstruct commit *c = prio_queue_get(&queue);\n \t\tstruct bitmap *active_c = active_paths_for(lm, c);\n \n \t\tif ((0 <= max_count && max_count < ++queue_popped) ||\n@@ -416,9 +416,8 @@ static int last_modified_run(struct last_modified *lm)\n \t\t */\n \t\trepo_parse_commit(lm->rev.repo, c);\n \n-\t\twhile (not_queue.nr) {\n+\t\twhile ((n = prio_queue_get(&not_queue))) {\n \t\t\tstruct commit_list *np;\n-\t\t\tstruct commit *n = prio_queue_get(&not_queue);\n \n \t\t\trepo_parse_commit(lm->rev.repo, n);\n \ndiff --git a/builtin/show-branch.c b/builtin/show-branch.c\nindex f02831b085..8846f2376f 100644\n--- a/builtin/show-branch.c\n+++ b/builtin/show-branch.c\n@@ -62,11 +62,10 @@ static const char *get_color_reset_code(void)\n \n static struct commit *interesting(struct prio_queue *queue)\n {\n-\tfor (size_t i = 0; i < queue->nr; i++) {\n-\t\tstruct commit *commit = queue->array[i].data;\n-\t\tif (commit->object.flags & UNINTERESTING)\n-\t\t\tcontinue;\n-\t\treturn commit;\n+\tstruct commit *commit;\n+\tprio_queue_for_each(queue, commit) {\n+\t\tif (!(commit->object.flags & UNINTERESTING))\n+\t\t\treturn commit;\n \t}\n \treturn NULL;\n }\n@@ -228,11 +227,11 @@ static void join_revs(struct prio_queue *queue,\n {\n \tint all_mask = ((1u << (REV_SHIFT + num_rev)) - 1);\n \tint all_revs = all_mask & ~((1u << REV_SHIFT) - 1);\n+\tstruct commit *commit;\n \n-\twhile (queue->nr) {\n+\twhile ((commit = prio_queue_peek(queue))) {\n \t\tstruct commit_list *parents;\n \t\tint still_interesting = !!interesting(queue);\n-\t\tstruct commit *commit = prio_queue_peek(queue);\n \t\tbool get_pending = true;\n \t\tint flags = commit->object.flags & all_mask;\n \ndiff --git a/commit-reach.c b/commit-reach.c\nindex 9b3ea46d6f..a849de653e 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -41,8 +41,8 @@ static int compare_commits_by_gen(const void *_a, const void *_b)\n \n static int queue_has_nonstale(struct prio_queue *queue)\n {\n-\tfor (size_t i = 0; i < queue->nr; i++) {\n-\t\tstruct commit *commit = queue->array[i].data;\n+\tstruct commit *commit;\n+\tprio_queue_for_each(queue, commit) {\n \t\tif (!(commit->object.flags & STALE))\n \t\t\treturn 1;\n \t}\n@@ -1070,6 +1070,7 @@ void ahead_behind(struct repository *r,\n \t\t  struct ahead_behind_count *counts, size_t counts_nr)\n {\n \tstruct prio_queue queue = { .compare = compare_commits_by_gen_then_commit_date };\n+\tvoid *entry;\n \tsize_t width = DIV_ROUND_UP(commits_nr, BITS_IN_EWORD);\n \n \tif (!commits_nr || !counts_nr)\n@@ -1135,8 +1136,8 @@ void ahead_behind(struct repository *r,\n \n \t/* STALE is used here, PARENT2 is used by insert_no_dup(). */\n \trepo_clear_commit_marks(r, PARENT2 | STALE);\n-\tfor (size_t i = 0; i < queue.nr; i++)\n-\t\tfree_bit_array(queue.array[i].data);\n+\tprio_queue_for_each(&queue, entry)\n+\t\tfree_bit_array(entry);\n \tclear_bit_arrays(&bit_arrays);\n \tclear_prio_queue(&queue);\n }\n@@ -1269,7 +1270,7 @@ int get_branch_base_for_tip(struct repository *r,\n \t\t\t    size_t bases_nr)\n {\n \tint best_index = -1;\n-\tstruct commit *branch_point = NULL;\n+\tstruct commit *c, *branch_point = NULL;\n \tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n \tint found_missing_gen = 0;\n \n@@ -1322,8 +1323,7 @@ int get_branch_base_for_tip(struct repository *r,\n \t\tprio_queue_put(&queue, c);\n \t}\n \n-\twhile (queue.nr) {\n-\t\tstruct commit *c = prio_queue_get(&queue);\n+\twhile ((c = prio_queue_get(&queue))) {\n \t\tint best_for_c = get_best(c);\n \t\tint best_for_p, positive;\n \t\tstruct commit *parent;\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex 120e01f3cf..29c41132ee 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -662,8 +662,8 @@ static int mark_complete_oid(const struct reference *ref, void *cb_data UNUSED)\n static void mark_recent_complete_commits(struct fetch_pack_args *args,\n \t\t\t\t\t timestamp_t cutoff)\n {\n-\twhile (complete.nr) {\n-\t\tstruct commit *item = prio_queue_peek(&complete);\n+\tstruct commit *item;\n+\twhile ((item = prio_queue_peek(&complete))) {\n \t\tif (item->date < cutoff)\n \t\t\tbreak;\n \t\tprint_verbose(args, _(\"Marking %s as complete\"),\ndiff --git a/negotiator/default.c b/negotiator/default.c\nindex 78d58d57ce..19cdf3808c 100644\n--- a/negotiator/default.c\n+++ b/negotiator/default.c\n@@ -113,10 +113,12 @@ static const struct object_id *get_rev(struct negotiation_state *ns)\n \t\tunsigned int mark;\n \t\tstruct commit_list *parents;\n \n-\t\tif (ns->rev_list.nr == 0 || ns->non_common_revs == 0)\n+\t\tif (ns->non_common_revs == 0)\n \t\t\treturn NULL;\n \n \t\tcommit = prio_queue_get(&ns->rev_list);\n+\t\tif (!commit)\n+\t\t\treturn NULL;\n \t\trepo_parse_commit(the_repository, commit);\n \t\tparents = commit->parents;\n \ndiff --git a/negotiator/skipping.c b/negotiator/skipping.c\nindex 68c9b3b997..db90fa77b5 100644\n--- a/negotiator/skipping.c\n+++ b/negotiator/skipping.c\n@@ -143,8 +143,7 @@ static int push_parent(struct data *data, struct entry *entry,\n \t\t/*\n \t\t * Find the existing entry and use it.\n \t\t */\n-\t\tfor (size_t i = 0; i < data->rev_list.nr; i++) {\n-\t\t\tparent_entry = data->rev_list.array[i].data;\n+\t\tprio_queue_for_each(&data->rev_list, parent_entry) {\n \t\t\tif (parent_entry->commit == to_push)\n \t\t\t\tgoto parent_found;\n \t\t}\n@@ -181,10 +180,12 @@ static const struct object_id *get_rev(struct data *data)\n \t\tstruct commit_list *p;\n \t\tint parent_pushed = 0;\n \n-\t\tif (data->rev_list.nr == 0 || data->non_common_revs == 0)\n+\t\tif (data->non_common_revs == 0)\n \t\t\treturn NULL;\n \n \t\tentry = prio_queue_get(&data->rev_list);\n+\t\tif (!entry)\n+\t\t\treturn NULL;\n \t\tcommit = entry->commit;\n \t\tcommit->object.flags |= POPPED;\n \t\tif (!(commit->object.flags & COMMON))\n@@ -253,8 +254,9 @@ static void have_sent(struct fetch_negotiator *n, struct commit *c)\n static void release(struct fetch_negotiator *n)\n {\n \tstruct data *data = n->data;\n-\tfor (size_t i = 0; i < data->rev_list.nr; i++)\n-\t\tfree(data->rev_list.array[i].data);\n+\tvoid *entry;\n+\tprio_queue_for_each(&data->rev_list, entry)\n+\t\tfree(entry);\n \tclear_prio_queue(&data->rev_list);\n \tFREE_AND_NULL(data);\n }\ndiff --git a/object-name.c b/object-name.c\nindex 9ac86f19c7..2fedfe1761 100644\n--- a/object-name.c\n+++ b/object-name.c\n@@ -1208,7 +1208,7 @@ static int get_oid_oneline(struct repository *r,\n \t\tl->item->object.flags |= ONELINE_SEEN;\n \t\tprio_queue_put(&copy, l->item);\n \t}\n-\twhile (copy.nr) {\n+\twhile (prio_queue_size(&copy)) {\n \t\tconst char *p, *buf;\n \t\tstruct commit *commit;\n \t\tint matches;\ndiff --git a/pack-bitmap-write.c b/pack-bitmap-write.c\nindex 1c8070f99c..ed9714b135 100644\n--- a/pack-bitmap-write.c\n+++ b/pack-bitmap-write.c\n@@ -513,6 +513,8 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,\n \t\t\t      struct bitmap_index *old_bitmap,\n \t\t\t      const uint32_t *mapping)\n {\n+\tstruct commit *c;\n+\tstruct tree *tree;\n \tint found;\n \tuint32_t pos;\n \tif (!ent->bitmap)\n@@ -520,9 +522,8 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,\n \n \tprio_queue_put(queue, commit);\n \n-\twhile (queue->nr) {\n+\twhile ((c = prio_queue_get(queue))) {\n \t\tstruct commit_list *p;\n-\t\tstruct commit *c = prio_queue_get(queue);\n \n \t\tif (old_bitmap && mapping) {\n \t\t\tstruct ewah_bitmap *old;\n@@ -574,9 +575,8 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,\n \t\t}\n \t}\n \n-\twhile (tree_queue->nr) {\n-\t\tif (fill_bitmap_tree(writer, ent->bitmap,\n-\t\t\t\t     prio_queue_get(tree_queue)) < 0)\n+\twhile ((tree = prio_queue_get(tree_queue))) {\n+\t\tif (fill_bitmap_tree(writer, ent->bitmap, tree) < 0)\n \t\t\treturn -1;\n \t}\n \treturn 0;\ndiff --git a/path-walk.c b/path-walk.c\nindex 94ff90bd15..cf3b2d0765 100644\n--- a/path-walk.c\n+++ b/path-walk.c\n@@ -699,6 +699,7 @@ int walk_objects_by_path(struct path_walk_info *info)\n \tint ret;\n \tsize_t commits_nr = 0, paths_nr = 0;\n \tstruct commit *c;\n+\tchar *path;\n \tstruct type_and_oid_list *root_tree_list;\n \tstruct type_and_oid_list *commit_list;\n \tstruct path_walk_context ctx = {\n@@ -808,8 +809,7 @@ int walk_objects_by_path(struct path_walk_info *info)\n \tfree(commit_list);\n \n \ttrace2_region_enter(\"path-walk\", \"path-walk\", info->revs->repo);\n-\twhile (!ret && ctx.path_stack.nr) {\n-\t\tchar *path = prio_queue_get(&ctx.path_stack);\n+\twhile (!ret && (path = prio_queue_get(&ctx.path_stack))) {\n \t\tpaths_nr++;\n \n \t\tret = walk_path(&ctx, path);\n@@ -821,12 +821,12 @@ int walk_objects_by_path(struct path_walk_info *info)\n \tif (!strmap_empty(&ctx.paths_to_lists)) {\n \t\tstruct hashmap_iter iter;\n \t\tstruct strmap_entry *entry;\n+\t\tchar *path;\n \n \t\tstrmap_for_each_entry(&ctx.paths_to_lists, &iter, entry)\n \t\t\tpush_to_stack(&ctx, entry->key);\n \n-\t\twhile (!ret && ctx.path_stack.nr) {\n-\t\t\tchar *path = prio_queue_get(&ctx.path_stack);\n+\t\twhile (!ret && (path = prio_queue_get(&ctx.path_stack))) {\n \t\t\tpaths_nr++;\n \n \t\t\tret = walk_path(&ctx, path);\ndiff --git a/prio-queue.c b/prio-queue.c\nindex 9748528ce6..ead4faf4bb 100644\n--- a/prio-queue.c\n+++ b/prio-queue.c\n@@ -22,16 +22,16 @@ void prio_queue_reverse(struct prio_queue *queue)\n \n \tif (queue->compare)\n \t\tBUG(\"prio_queue_reverse() on non-LIFO queue\");\n-\tif (!queue->nr)\n+\tif (!queue->nr_)\n \t\treturn;\n-\tfor (i = 0; i < (j = (queue->nr - 1) - i); i++)\n+\tfor (i = 0; i < (j = (queue->nr_ - 1) - i); i++)\n \t\tswap(queue, i, j);\n }\n \n void clear_prio_queue(struct prio_queue *queue)\n {\n \tFREE_AND_NULL(queue->array);\n-\tqueue->nr = 0;\n+\tqueue->nr_ = 0;\n \tqueue->alloc = 0;\n \tqueue->insertion_ctr = 0;\n }\n@@ -41,15 +41,15 @@ void prio_queue_put(struct prio_queue *queue, void *thing)\n \tsize_t ix, parent;\n \n \t/* Append at the end */\n-\tALLOC_GROW(queue->array, queue->nr + 1, queue->alloc);\n-\tqueue->array[queue->nr].ctr = queue->insertion_ctr++;\n-\tqueue->array[queue->nr].data = thing;\n-\tqueue->nr++;\n+\tALLOC_GROW(queue->array, queue->nr_ + 1, queue->alloc);\n+\tqueue->array[queue->nr_].ctr = queue->insertion_ctr++;\n+\tqueue->array[queue->nr_].data = thing;\n+\tqueue->nr_++;\n \tif (!queue->compare)\n \t\treturn; /* LIFO */\n \n \t/* Bubble up the new one */\n-\tfor (ix = queue->nr - 1; ix; ix = parent) {\n+\tfor (ix = queue->nr_ - 1; ix; ix = parent) {\n \t\tparent = (ix - 1) / 2;\n \t\tif (compare(queue, parent, ix) <= 0)\n \t\t\tbreak;\n@@ -63,9 +63,9 @@ static void sift_down_root(struct prio_queue *queue)\n \tsize_t ix, child;\n \n \t/* Push down the one at the root */\n-\tfor (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {\n+\tfor (ix = 0; ix * 2 + 1 < queue->nr_; ix = child) {\n \t\tchild = ix * 2 + 1; /* left */\n-\t\tif (child + 1 < queue->nr &&\n+\t\tif (child + 1 < queue->nr_ &&\n \t\t    compare(queue, child, child + 1) >= 0)\n \t\t\tchild++; /* use right child */\n \n@@ -80,36 +80,36 @@ void *prio_queue_get(struct prio_queue *queue)\n {\n \tvoid *result;\n \n-\tif (!queue->nr)\n+\tif (!queue->nr_)\n \t\treturn NULL;\n \tif (!queue->compare)\n-\t\treturn queue->array[--queue->nr].data; /* LIFO */\n+\t\treturn queue->array[--queue->nr_].data; /* LIFO */\n \n \tresult = queue->array[0].data;\n-\tif (!--queue->nr)\n+\tif (!--queue->nr_)\n \t\treturn result;\n \n-\tqueue->array[0] = queue->array[queue->nr];\n+\tqueue->array[0] = queue->array[queue->nr_];\n \tsift_down_root(queue);\n \treturn result;\n }\n \n void *prio_queue_peek(struct prio_queue *queue)\n {\n-\tif (!queue->nr)\n+\tif (!queue->nr_)\n \t\treturn NULL;\n \tif (!queue->compare)\n-\t\treturn queue->array[queue->nr - 1].data;\n+\t\treturn queue->array[queue->nr_ - 1].data;\n \treturn queue->array[0].data;\n }\n \n void prio_queue_replace(struct prio_queue *queue, void *thing)\n {\n-\tif (!queue->nr) {\n+\tif (!queue->nr_) {\n \t\tprio_queue_put(queue, thing);\n \t} else if (!queue->compare) {\n-\t\tqueue->array[queue->nr - 1].ctr = queue->insertion_ctr++;\n-\t\tqueue->array[queue->nr - 1].data = thing;\n+\t\tqueue->array[queue->nr_ - 1].ctr = queue->insertion_ctr++;\n+\t\tqueue->array[queue->nr_ - 1].data = thing;\n \t} else {\n \t\tqueue->array[0].ctr = queue->insertion_ctr++;\n \t\tqueue->array[0].data = thing;\ndiff --git a/prio-queue.h b/prio-queue.h\nindex da7fad2f1f..7f2aa986b1 100644\n--- a/prio-queue.h\n+++ b/prio-queue.h\n@@ -30,7 +30,7 @@ struct prio_queue {\n \tprio_queue_compare_fn compare;\n \tsize_t insertion_ctr;\n \tvoid *cb_data;\n-\tsize_t alloc, nr;\n+\tsize_t alloc, nr_;\n \tstruct prio_queue_entry *array;\n };\n \n@@ -52,6 +52,16 @@ void *prio_queue_get(struct prio_queue *);\n  */\n void *prio_queue_peek(struct prio_queue *);\n \n+static inline size_t prio_queue_size(const struct prio_queue *queue)\n+{\n+\treturn queue->nr_;\n+}\n+\n+#define prio_queue_for_each(queue, it) \\\n+\tfor (size_t pq_ix_ = 0; \\\n+\t     pq_ix_ < (queue)->nr_ && ((it) = (queue)->array[pq_ix_].data, 1); \\\n+\t     pq_ix_++)\n+\n /*\n  * Replace the \"thing\" that compares the smallest with a new \"thing\",\n  * like prio_queue_get()+prio_queue_put() would do, but in a more\ndiff --git a/revision.c b/revision.c\nindex 5693618be4..34e2d146f4 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -476,16 +476,15 @@ static struct commit *handle_commit(struct rev_info *revs,\n static int everybody_uninteresting(struct prio_queue *orig,\n \t\t\t\t   struct commit **interesting_cache)\n {\n-\tsize_t i;\n+\tstruct commit *commit;\n \n \tif (*interesting_cache) {\n-\t\tstruct commit *commit = *interesting_cache;\n+\t\tcommit = *interesting_cache;\n \t\tif (!(commit->object.flags & UNINTERESTING))\n \t\t\treturn 0;\n \t}\n \n-\tfor (i = 0; i < orig->nr; i++) {\n-\t\tstruct commit *commit = orig->array[i].data;\n+\tprio_queue_for_each(orig, commit) {\n \t\tif (commit->object.flags & UNINTERESTING)\n \t\t\tcontinue;\n \n@@ -1446,7 +1445,7 @@ static int limit_list(struct rev_info *revs)\n \tstruct commit_list *original_list = revs->commits;\n \tstruct commit_list *newlist = NULL;\n \tstruct commit_list **p = &newlist;\n-\tstruct commit *interesting_cache = NULL;\n+\tstruct commit *commit, *interesting_cache = NULL;\n \tstruct prio_queue queue = { .compare = compare_commits_by_commit_date };\n \n \tif (revs->ancestry_path_implicit_bottoms) {\n@@ -1461,8 +1460,7 @@ static int limit_list(struct rev_info *revs)\n \t\tprio_queue_put(&queue, commit);\n \t}\n \n-\twhile (queue.nr) {\n-\t\tstruct commit *commit = prio_queue_get(&queue);\n+\twhile ((commit = prio_queue_get(&queue))) {\n \t\tstruct object *obj = &commit->object;\n \n \t\tif (commit == interesting_cache)\n@@ -4028,8 +4026,8 @@ static enum rewrite_result rewrite_one_1(struct rev_info *revs,\n \n static void merge_queue_into_list(struct prio_queue *q, struct commit_list **list)\n {\n-\twhile (q->nr) {\n-\t\tstruct commit *item = prio_queue_peek(q);\n+\tstruct commit *item;\n+\twhile ((item = prio_queue_peek(q))) {\n \t\tstruct commit_list *p = *list;\n \n \t\tif (p && p->item->date >= item->date)\ndiff --git a/walker.c b/walker.c\nindex e98eb6da53..e3de77f092 100644\n--- a/walker.c\n+++ b/walker.c\n@@ -84,12 +84,12 @@ static struct prio_queue complete = { compare_commits_by_commit_date };\n static int process_commit(struct walker *walker, struct commit *commit)\n {\n \tstruct commit_list *parents;\n+\tstruct commit *item;\n \n \tif (repo_parse_commit(the_repository, commit))\n \t\treturn -1;\n \n-\twhile (complete.nr) {\n-\t\tstruct commit *item = prio_queue_peek(&complete);\n+\twhile ((item = prio_queue_peek(&complete))) {\n \t\tif (item->date < commit->date)\n \t\t\tbreak;\n \t\tpop_most_recent_commit(&complete, COMPLETE);\n-- \ngitgitgadget\n\n"},{"id":"544962","messageId":"a3f4cb57f2f8f90a8b93123b1b10b17a5be8bbb8.1780945851.git.gitgitgadget@gmail.com","threadId":"65764","inReplyTo":"pull.2140.v4.git.1780945851.gitgitgadget@gmail.com","subject":"[PATCH v4 2/2] prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-06-08T19:10:51Z","receivedAt":"2026-06-08T19:10:57Z","isPatch":true,"body":"From: Kristofer Karlsson <krka@spotify.com>\n\nDefer the actual removal in prio_queue_get() until the next\noperation.  If that next operation is a prio_queue_put(), the\nremoval and insertion are fused into a single replace — writing\nthe new element at the root and sifting it down — which avoids\na full remove-rebalance-insert cycle.\n\nThis matches the dominant usage pattern in git's commit traversal:\nget a commit, then put its parents.  The first parent insertion\nafter each get is now a replace operation automatically.\n\nThis generalizes the lazy_queue pattern from builtin/describe.c\n(introduced in 08bb69d70f) into prio_queue itself.  Three callers\nindependently implemented the same get+put fusion:\n\n  - builtin/describe.c had a full lazy_queue wrapper\n  - commit.c:pop_most_recent_commit() used peek+replace\n  - builtin/show-branch.c:join_revs() used peek+replace\n\nAll three now collapse to plain _get() and _put(), with the data\nstructure handling the fusion internally.  This simplifies callers\nand means every prio_queue user gets the optimization for free\nwithout needing to implement it manually.\n\nRemove prio_queue_replace() since no external callers remain.\n\nBenchmarked on a 1.8M-commit monorepo (30 interleaved runs,\npaired t-test, Xeon @ 2.20GHz):\n\nCode paths that previously did eager get+put (new optimization):\n\n  Command                       base    patched  change      p\n  merge-base --all A A~1000     3828ms  3725ms   -2.69%  0.0001\n  rev-list --count A~1000..A    3055ms  2986ms   -2.27%  0.0601\n  log --oneline A~1000..A       3408ms  3350ms   -1.71%  0.0482\n\nCode paths that already had manual get+put fusion (expect\nneutral — the optimization moves into prio_queue but the number\nof heap operations stays the same):\n\n  Command                       base    patched  change      p\n  show-branch A A~1000          9156ms  9127ms   -0.32%  0.3470\n  describe (4751 revs, 81K repo) 1983ms 1963ms  -1.02%  <0.001\n\nNo regressions in any scenario.\n\nSuggested-by: René Scharfe <l.s.r@web.de>\nSigned-off-by: Kristofer Karlsson <krka@spotify.com>\n---\n builtin/describe.c          | 75 +++++++-----------------------\n builtin/show-branch.c       | 11 ++---\n commit.c                    | 11 +----\n prio-queue.c                | 92 ++++++++++++++++++++-----------------\n prio-queue.h                | 15 ++----\n t/unit-tests/u-prio-queue.c |  6 +--\n 6 files changed, 78 insertions(+), 132 deletions(-)\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 8e88bdeea6..64424543ef 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -251,61 +251,19 @@ static int compare_pt(const void *a_, const void *b_)\n \treturn 0;\n }\n \n-struct lazy_queue {\n-\tstruct prio_queue queue;\n-\tbool get_pending;\n-};\n-\n-#define LAZY_QUEUE_INIT { { compare_commits_by_commit_date }, false }\n-\n-static void *lazy_queue_get(struct lazy_queue *queue)\n-{\n-\tif (queue->get_pending)\n-\t\tprio_queue_get(&queue->queue);\n-\telse\n-\t\tqueue->get_pending = true;\n-\treturn prio_queue_peek(&queue->queue);\n-}\n-\n-static void lazy_queue_put(struct lazy_queue *queue, void *thing)\n-{\n-\tif (queue->get_pending)\n-\t\tprio_queue_replace(&queue->queue, thing);\n-\telse\n-\t\tprio_queue_put(&queue->queue, thing);\n-\tqueue->get_pending = false;\n-}\n-\n-static bool lazy_queue_empty(const struct lazy_queue *queue)\n-{\n-\treturn prio_queue_size(&queue->queue) == (queue->get_pending ? 1 : 0);\n-}\n-\n-static void lazy_queue_clear(struct lazy_queue *queue)\n-{\n-\tclear_prio_queue(&queue->queue);\n-\tqueue->get_pending = false;\n-}\n-\n-static unsigned long finish_depth_computation(struct lazy_queue *queue,\n+static unsigned long finish_depth_computation(struct prio_queue *queue,\n \t\t\t\t\t      struct possible_tag *best)\n {\n \tunsigned long seen_commits = 0;\n \tstruct oidset unflagged = OIDSET_INIT;\n-\tstruct commit *commit;\n-\tint skip = queue->get_pending ? 1 : 0;\n+\tstruct commit *c;\n \n-\tprio_queue_for_each(&queue->queue, commit) {\n-\t\tif (skip) {\n-\t\t\tskip = 0;\n-\t\t\tcontinue;\n-\t\t}\n-\t\tif (!(commit->object.flags & best->flag_within))\n-\t\t\toidset_insert(&unflagged, &commit->object.oid);\n+\tprio_queue_for_each(queue, c) {\n+\t\tif (!(c->object.flags & best->flag_within))\n+\t\t\toidset_insert(&unflagged, &c->object.oid);\n \t}\n \n-\twhile (!lazy_queue_empty(queue)) {\n-\t\tstruct commit *c = lazy_queue_get(queue);\n+\twhile ((c = prio_queue_get(queue))) {\n \t\tstruct commit_list *parents = c->parents;\n \t\tseen_commits++;\n \t\tif (c->object.flags & best->flag_within) {\n@@ -321,7 +279,7 @@ static unsigned long finish_depth_computation(struct lazy_queue *queue,\n \t\t\trepo_parse_commit(the_repository, p);\n \t\t\tseen = p->object.flags & SEEN;\n \t\t\tif (!seen)\n-\t\t\t\tlazy_queue_put(queue, p);\n+\t\t\t\tprio_queue_put(queue, p);\n \t\t\tflag_before = p->object.flags & best->flag_within;\n \t\t\tp->object.flags |= c->object.flags;\n \t\t\tflag_after = p->object.flags & best->flag_within;\n@@ -369,8 +327,8 @@ static void append_suffix(int depth, const struct object_id *oid, struct strbuf\n \n static void describe_commit(struct commit *cmit, struct strbuf *dst)\n {\n-\tstruct commit *gave_up_on = NULL;\n-\tstruct lazy_queue queue = LAZY_QUEUE_INIT;\n+\tstruct commit *c, *gave_up_on = NULL;\n+\tstruct prio_queue queue = { compare_commits_by_commit_date };\n \tstruct commit_name *n;\n \tstruct possible_tag all_matches[MAX_TAGS];\n \tunsigned int match_cnt = 0, annotated_cnt = 0, cur_match;\n@@ -412,9 +370,8 @@ static void describe_commit(struct commit *cmit, struct strbuf *dst)\n \t}\n \n \tcmit->object.flags = SEEN;\n-\tlazy_queue_put(&queue, cmit);\n-\twhile (!lazy_queue_empty(&queue)) {\n-\t\tstruct commit *c = lazy_queue_get(&queue);\n+\tprio_queue_put(&queue, cmit);\n+\twhile ((c = prio_queue_get(&queue))) {\n \t\tstruct commit_list *parents = c->parents;\n \t\tstruct commit_name **slot;\n \n@@ -448,7 +405,7 @@ static void describe_commit(struct commit *cmit, struct strbuf *dst)\n \t\t\t\tt->depth++;\n \t\t}\n \t\t/* Stop if last remaining path already covered by best candidate(s) */\n-\t\tif (annotated_cnt && lazy_queue_empty(&queue)) {\n+\t\tif (annotated_cnt && !prio_queue_size(&queue)) {\n \t\t\tint best_depth = INT_MAX;\n \t\t\tunsigned best_within = 0;\n \t\t\tfor (cur_match = 0; cur_match < match_cnt; cur_match++) {\n@@ -471,7 +428,7 @@ static void describe_commit(struct commit *cmit, struct strbuf *dst)\n \t\t\tstruct commit *p = parents->item;\n \t\t\trepo_parse_commit(the_repository, p);\n \t\t\tif (!(p->object.flags & SEEN))\n-\t\t\t\tlazy_queue_put(&queue, p);\n+\t\t\t\tprio_queue_put(&queue, p);\n \t\t\tp->object.flags |= c->object.flags;\n \t\t\tparents = parents->next;\n \n@@ -486,7 +443,7 @@ static void describe_commit(struct commit *cmit, struct strbuf *dst)\n \t\t\tstrbuf_add_unique_abbrev(dst, cmit_oid, abbrev);\n \t\t\tif (suffix)\n \t\t\t\tstrbuf_addstr(dst, suffix);\n-\t\t\tlazy_queue_clear(&queue);\n+\t\t\tclear_prio_queue(&queue);\n \t\t\treturn;\n \t\t}\n \t\tif (unannotated_cnt)\n@@ -502,11 +459,11 @@ static void describe_commit(struct commit *cmit, struct strbuf *dst)\n \tQSORT(all_matches, match_cnt, compare_pt);\n \n \tif (gave_up_on) {\n-\t\tlazy_queue_put(&queue, gave_up_on);\n+\t\tprio_queue_put(&queue, gave_up_on);\n \t\tseen_commits--;\n \t}\n \tseen_commits += finish_depth_computation(&queue, &all_matches[0]);\n-\tlazy_queue_clear(&queue);\n+\tclear_prio_queue(&queue);\n \n \tif (debug) {\n \t\tstatic int label_width = -1;\ndiff --git a/builtin/show-branch.c b/builtin/show-branch.c\nindex 8846f2376f..2435e8aeda 100644\n--- a/builtin/show-branch.c\n+++ b/builtin/show-branch.c\n@@ -232,12 +232,13 @@ static void join_revs(struct prio_queue *queue,\n \twhile ((commit = prio_queue_peek(queue))) {\n \t\tstruct commit_list *parents;\n \t\tint still_interesting = !!interesting(queue);\n-\t\tbool get_pending = true;\n \t\tint flags = commit->object.flags & all_mask;\n \n \t\tif (!still_interesting && extra <= 0)\n \t\t\tbreak;\n \n+\t\tprio_queue_get(queue);\n+\n \t\tmark_seen(commit, seen_p);\n \t\tif ((flags & all_revs) == all_revs)\n \t\t\tflags |= UNINTERESTING;\n@@ -253,14 +254,8 @@ static void join_revs(struct prio_queue *queue,\n \t\t\tif (mark_seen(p, seen_p) && !still_interesting)\n \t\t\t\textra--;\n \t\t\tp->object.flags |= flags;\n-\t\t\tif (get_pending)\n-\t\t\t\tprio_queue_replace(queue, p);\n-\t\t\telse\n-\t\t\t\tprio_queue_put(queue, p);\n-\t\t\tget_pending = false;\n+\t\t\tprio_queue_put(queue, p);\n \t\t}\n-\t\tif (get_pending)\n-\t\t\tprio_queue_get(queue);\n \t}\n \n \t/*\ndiff --git a/commit.c b/commit.c\nindex fd8723502e..976bfc4618 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -795,24 +795,17 @@ void commit_list_sort_by_date(struct commit_list **list)\n struct commit *pop_most_recent_commit(struct prio_queue *queue,\n \t\t\t\t      unsigned int mark)\n {\n-\tstruct commit *ret = prio_queue_peek(queue);\n-\tint get_pending = 1;\n+\tstruct commit *ret = prio_queue_get(queue);\n \tstruct commit_list *parents = ret->parents;\n \n \twhile (parents) {\n \t\tstruct commit *commit = parents->item;\n \t\tif (!repo_parse_commit(the_repository, commit) && !(commit->object.flags & mark)) {\n \t\t\tcommit->object.flags |= mark;\n-\t\t\tif (get_pending)\n-\t\t\t\tprio_queue_replace(queue, commit);\n-\t\t\telse\n-\t\t\t\tprio_queue_put(queue, commit);\n-\t\t\tget_pending = 0;\n+\t\t\tprio_queue_put(queue, commit);\n \t\t}\n \t\tparents = parents->next;\n \t}\n-\tif (get_pending)\n-\t\tprio_queue_get(queue);\n \treturn ret;\n }\n \ndiff --git a/prio-queue.c b/prio-queue.c\nindex ead4faf4bb..199775d5af 100644\n--- a/prio-queue.c\n+++ b/prio-queue.c\n@@ -34,12 +34,48 @@ void clear_prio_queue(struct prio_queue *queue)\n \tqueue->nr_ = 0;\n \tqueue->alloc = 0;\n \tqueue->insertion_ctr = 0;\n+\tqueue->get_pending = 0;\n+}\n+\n+static void sift_down_root(struct prio_queue *queue)\n+{\n+\tsize_t ix, child;\n+\n+\t/* Push down the one at the root */\n+\tfor (ix = 0; ix * 2 + 1 < queue->nr_; ix = child) {\n+\t\tchild = ix * 2 + 1; /* left */\n+\t\tif (child + 1 < queue->nr_ &&\n+\t\t    compare(queue, child, child + 1) >= 0)\n+\t\t\tchild++; /* use right child */\n+\n+\t\tif (compare(queue, ix, child) <= 0)\n+\t\t\tbreak;\n+\n+\t\tswap(queue, child, ix);\n+\t}\n+}\n+\n+static inline void flush_get(struct prio_queue *queue)\n+{\n+\tif (!queue->get_pending)\n+\t\treturn;\n+\tqueue->get_pending = 0;\n+\tqueue->array[0] = queue->array[--queue->nr_];\n+\tsift_down_root(queue);\n }\n \n void prio_queue_put(struct prio_queue *queue, void *thing)\n {\n \tsize_t ix, parent;\n \n+\tif (queue->get_pending) {\n+\t\tqueue->get_pending = 0;\n+\t\tqueue->array[0].ctr = queue->insertion_ctr++;\n+\t\tqueue->array[0].data = thing;\n+\t\tsift_down_root(queue);\n+\t\treturn;\n+\t}\n+\n \t/* Append at the end */\n \tALLOC_GROW(queue->array, queue->nr_ + 1, queue->alloc);\n \tqueue->array[queue->nr_].ctr = queue->insertion_ctr++;\n@@ -58,61 +94,33 @@ void prio_queue_put(struct prio_queue *queue, void *thing)\n \t}\n }\n \n-static void sift_down_root(struct prio_queue *queue)\n-{\n-\tsize_t ix, child;\n-\n-\t/* Push down the one at the root */\n-\tfor (ix = 0; ix * 2 + 1 < queue->nr_; ix = child) {\n-\t\tchild = ix * 2 + 1; /* left */\n-\t\tif (child + 1 < queue->nr_ &&\n-\t\t    compare(queue, child, child + 1) >= 0)\n-\t\t\tchild++; /* use right child */\n-\n-\t\tif (compare(queue, ix, child) <= 0)\n-\t\t\tbreak;\n-\n-\t\tswap(queue, child, ix);\n-\t}\n-}\n-\n void *prio_queue_get(struct prio_queue *queue)\n {\n-\tvoid *result;\n-\n-\tif (!queue->nr_)\n+\tif (queue->nr_ <= queue->get_pending) {\n+\t\tqueue->nr_ = 0;\n+\t\tqueue->get_pending = 0;\n \t\treturn NULL;\n+\t}\n \tif (!queue->compare)\n \t\treturn queue->array[--queue->nr_].data; /* LIFO */\n \n-\tresult = queue->array[0].data;\n-\tif (!--queue->nr_)\n-\t\treturn result;\n+\tflush_get(queue);\n \n-\tqueue->array[0] = queue->array[queue->nr_];\n-\tsift_down_root(queue);\n-\treturn result;\n+\tqueue->get_pending = 1;\n+\treturn queue->array[0].data;\n }\n \n void *prio_queue_peek(struct prio_queue *queue)\n {\n-\tif (!queue->nr_)\n+\tif (queue->nr_ <= queue->get_pending) {\n+\t\tqueue->nr_ = 0;\n+\t\tqueue->get_pending = 0;\n \t\treturn NULL;\n+\t}\n \tif (!queue->compare)\n \t\treturn queue->array[queue->nr_ - 1].data;\n-\treturn queue->array[0].data;\n-}\n \n-void prio_queue_replace(struct prio_queue *queue, void *thing)\n-{\n-\tif (!queue->nr_) {\n-\t\tprio_queue_put(queue, thing);\n-\t} else if (!queue->compare) {\n-\t\tqueue->array[queue->nr_ - 1].ctr = queue->insertion_ctr++;\n-\t\tqueue->array[queue->nr_ - 1].data = thing;\n-\t} else {\n-\t\tqueue->array[0].ctr = queue->insertion_ctr++;\n-\t\tqueue->array[0].data = thing;\n-\t\tsift_down_root(queue);\n-\t}\n+\tflush_get(queue);\n+\n+\treturn queue->array[0].data;\n }\ndiff --git a/prio-queue.h b/prio-queue.h\nindex 7f2aa986b1..570b48e648 100644\n--- a/prio-queue.h\n+++ b/prio-queue.h\n@@ -30,8 +30,9 @@ struct prio_queue {\n \tprio_queue_compare_fn compare;\n \tsize_t insertion_ctr;\n \tvoid *cb_data;\n-\tsize_t alloc, nr_;\n+\tsize_t alloc, nr_; /* use prio_queue_size() for logical count */\n \tstruct prio_queue_entry *array;\n+\tunsigned get_pending;\n };\n \n /*\n@@ -54,22 +55,14 @@ void *prio_queue_peek(struct prio_queue *);\n \n static inline size_t prio_queue_size(const struct prio_queue *queue)\n {\n-\treturn queue->nr_;\n+\treturn queue->nr_ - queue->get_pending;\n }\n \n #define prio_queue_for_each(queue, it) \\\n-\tfor (size_t pq_ix_ = 0; \\\n+\tfor (size_t pq_ix_ = (queue)->get_pending; \\\n \t     pq_ix_ < (queue)->nr_ && ((it) = (queue)->array[pq_ix_].data, 1); \\\n \t     pq_ix_++)\n \n-/*\n- * Replace the \"thing\" that compares the smallest with a new \"thing\",\n- * like prio_queue_get()+prio_queue_put() would do, but in a more\n- * efficient way.  Does the same as prio_queue_put() if the queue is\n- * empty.\n- */\n-void prio_queue_replace(struct prio_queue *queue, void *thing);\n-\n void clear_prio_queue(struct prio_queue *);\n \n /* Reverse the LIFO elements */\ndiff --git a/t/unit-tests/u-prio-queue.c b/t/unit-tests/u-prio-queue.c\nindex 63e58114ae..af3e0b8598 100644\n--- a/t/unit-tests/u-prio-queue.c\n+++ b/t/unit-tests/u-prio-queue.c\n@@ -53,13 +53,13 @@ static void test_prio_queue(int *input, size_t input_size,\n \t\t\tprio_queue_reverse(&pq);\n \t\t\tbreak;\n \t\tcase REPLACE:\n-\t\t\tpeek = prio_queue_peek(&pq);\n+\t\t\tget = prio_queue_get(&pq);\n \t\t\tcl_assert(i + 1 < input_size);\n \t\t\tcl_assert(input[i + 1] >= 0);\n \t\t\tcl_assert(j < result_size);\n-\t\t\tcl_assert_equal_i(result[j], show(peek));\n+\t\t\tcl_assert_equal_i(result[j], show(get));\n \t\t\tj++;\n-\t\t\tprio_queue_replace(&pq, &input[++i]);\n+\t\t\tprio_queue_put(&pq, &input[++i]);\n \t\t\tbreak;\n \t\tdefault:\n \t\t\tprio_queue_put(&pq, &input[i]);\n-- \ngitgitgadget\n"},{"id":"546811","messageId":"xmqqh5mjrbgq.fsf@gitster.g","threadId":"65764","inReplyTo":"pull.2140.v4.git.1780945851.gitgitgadget@gmail.com","subject":"Re: [PATCH v4 0/2] prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-06-30T20:59:33Z","receivedAt":"2026-06-30T20:59:35Z","isPatch":true,"body":"\"Kristofer Karlsson via GitGitGadget\" <gitgitgadget@gmail.com>\nwrites:\n\n> Rene's lazy_queue wrapper in describe.c was a clever optimization -- by\n> deferring the get, a following put becomes a simple replace, avoiding a full\n> remove-rebalance-insert cycle.\n>\n> It turns out this pattern is so common in git's traversal code that it makes\n> sense to fold it into prio_queue itself. Gets and puts are interleaved in\n> virtually every commit walk, so the fusion is essentially always a win.\n>\n> This is mostly a code simplification -- three callers had independently\n> reimplemented the same optimization, and they all collapse to plain get+put\n> now. The 1.7-2.7% speedup on traversal-heavy workloads is a nice bonus.\n>\n> More details and benchmark numbers in the commit message.\n>\n> Related to but independent of the cascade sift-down work in\n> kk/prio-queue-cascade-sift -- the two can land in either order.\n>\n> Changes in v4:\n>\n>  * Thanks Junio for review, applied all suggestions.\n>\n>  * Renamed .nr_internal to .nr_\n>\n>  * Restored flush_get() as a static inline helper instead of inlining the\n>    flush logic into get() and peek().\n>\n>  * Guard empty-queue check with nr_ <= get_pending.\n>\n>  * Flipped commit order: the rename/accessor commit is now first, and the\n>    behavioral fusion change is second. This was partly messy -- the first\n>    rename commit introduces some ugly intermediate code (e.g. describe.c's\n>    prio_queue_for_each with a skip variable) that gets cleaned up in commit\n>    2 when the lazy get makes it unnecessary.\n\nSo, this is the \"other\" topic that we would want to merge first\nbefore the kk/prio-queue-cascade-sift topic.  This round looks good\nto me.\n\nThanks.\n"},{"id":"546812","messageId":"CAL71e4MMg-AZY0QDtQoCBW063c9VzgtKuNYz+41FC9cmFdOszw@mail.gmail.com","threadId":"65764","inReplyTo":"xmqqh5mjrbgq.fsf@gitster.g","subject":"Re: [PATCH v4 0/2] prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-06-30T21:16:30Z","receivedAt":"2026-06-30T21:16:43Z","isPatch":true,"body":"On Tue, 30 Jun 2026 at 22:59, Junio C Hamano <gitster@pobox.com> wrote:\n>\n> So, this is the \"other\" topic that we would want to merge first\n> before the kk/prio-queue-cascade-sift topic.  This round looks good\n> to me.\n\nI want to acknowledge that I was too vague in my previous message[1],\nI should be more explicit when referencing patch series.\n\nIf this gets promoted I will revisit the other series [1] to either verify\nthat it still gives a relevant boost or if it should be dropped -- both would be\ngood outcomes.\n\nThanks for looking at it again,\nKristofer\n\n[1] https://lore.kernel.org/git/CAL71e4MYNiScZjTwkApjDAjRh2LM0_SP59h5HCTywV-Pua03tw@mail.gmail.com/\n"}]}