* [PATCH v3 1/2] prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion
2026-06-07 11:43 ` [PATCH v3 " Kristofer Karlsson via GitGitGadget
@ 2026-06-07 11:43 ` Kristofer Karlsson via GitGitGadget
2026-06-07 11:43 ` [PATCH v3 2/2] prio-queue: rename .nr to .nr_internal to prevent direct access Kristofer Karlsson via GitGitGadget
` (2 subsequent siblings)
3 siblings, 0 replies; 16+ messages in thread
From: Kristofer Karlsson via GitGitGadget @ 2026-06-07 11:43 UTC (permalink / raw)
To: git
Cc: René Scharfe, Kristofer Karlsson, Kristofer Karlsson,
Kristofer Karlsson
From: Kristofer Karlsson <krka@spotify.com>
Defer the actual removal in prio_queue_get() until the next
operation. If that next operation is a prio_queue_put(), the
removal and insertion are fused into a single replace, writing
the new element at the root and sifting it down which avoids
a full remove-rebalance-insert cycle.
This matches the dominant usage pattern in git's commit traversal:
get a commit, then put its parents. The first parent insertion
after each get is now a replace operation automatically.
This generalizes the lazy_queue pattern from builtin/describe.c
(introduced in 08bb69d70f) into prio_queue itself. Three callers
independently implemented the same get+put fusion:
- builtin/describe.c had a full lazy_queue wrapper
- commit.c:pop_most_recent_commit() used peek+replace
- builtin/show-branch.c:join_revs() used peek+replace
All three now collapse to plain _get() and _put(), with the data
structure handling the fusion internally. This simplifies callers
and means every prio_queue user gets the optimization for free
without needing to implement it manually.
Remove prio_queue_replace() since no external callers remain.
Add prio_queue_size() for callers that need the logical element
count, since the physical nr may temporarily include a
pending-removal element.
Benchmarked on a large monorepo (30 interleaved runs,
paired t-test, Xeon @ 2.20GHz):
Code paths that previously did eager get+put (new optimization):
Command base patched change p
merge-base --all A A~1000 3828ms 3725ms -2.69% 0.0001
rev-list --count A~1000..A 3055ms 2986ms -2.27% 0.0601
log --oneline A~1000..A 3408ms 3350ms -1.71% 0.0482
Code paths that already had manual get+put fusion (expect
neutral - the optimization moves into prio_queue but the number
of heap operations stays the same):
Command base patched change p
show-branch A A~1000 9156ms 9127ms -0.32% 0.3470
describe (git.git) 1983ms 1963ms -1.02% <0.001
No regressions in any scenario.
Suggested-by: René Scharfe <l.s.r@web.de>
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
builtin/describe.c | 67 +++++++---------------------
builtin/last-modified.c | 4 +-
builtin/show-branch.c | 17 +++----
commit-reach.c | 5 +--
commit.c | 11 +----
pack-bitmap-write.c | 4 +-
prio-queue.c | 88 ++++++++++++++++++-------------------
prio-queue.h | 12 +++--
revision.c | 5 +--
t/unit-tests/u-prio-queue.c | 6 +--
walker.c | 4 +-
11 files changed, 85 insertions(+), 138 deletions(-)
diff --git a/builtin/describe.c b/builtin/describe.c
index 1c47d7c0b7..85564f3487 100644
--- a/builtin/describe.c
+++ b/builtin/describe.c
@@ -251,56 +251,20 @@ static int compare_pt(const void *a_, const void *b_)
return 0;
}
-struct lazy_queue {
- struct prio_queue queue;
- bool get_pending;
-};
-
-#define LAZY_QUEUE_INIT { { compare_commits_by_commit_date }, false }
-
-static void *lazy_queue_get(struct lazy_queue *queue)
-{
- if (queue->get_pending)
- prio_queue_get(&queue->queue);
- else
- queue->get_pending = true;
- return prio_queue_peek(&queue->queue);
-}
-
-static void lazy_queue_put(struct lazy_queue *queue, void *thing)
-{
- if (queue->get_pending)
- prio_queue_replace(&queue->queue, thing);
- else
- prio_queue_put(&queue->queue, thing);
- queue->get_pending = false;
-}
-
-static bool lazy_queue_empty(const struct lazy_queue *queue)
-{
- return queue->queue.nr == (queue->get_pending ? 1 : 0);
-}
-
-static void lazy_queue_clear(struct lazy_queue *queue)
-{
- clear_prio_queue(&queue->queue);
- queue->get_pending = false;
-}
-
-static unsigned long finish_depth_computation(struct lazy_queue *queue,
+static unsigned long finish_depth_computation(struct prio_queue *queue,
struct possible_tag *best)
{
unsigned long seen_commits = 0;
struct oidset unflagged = OIDSET_INIT;
+ struct commit *c;
- for (size_t i = queue->get_pending ? 1 : 0; i < queue->queue.nr; i++) {
- struct commit *commit = queue->queue.array[i].data;
+ for (size_t i = queue->get_pending; i < queue->nr; i++) {
+ struct commit *commit = queue->array[i].data;
if (!(commit->object.flags & best->flag_within))
oidset_insert(&unflagged, &commit->object.oid);
}
- while (!lazy_queue_empty(queue)) {
- struct commit *c = lazy_queue_get(queue);
+ while ((c = prio_queue_get(queue))) {
struct commit_list *parents = c->parents;
seen_commits++;
if (c->object.flags & best->flag_within) {
@@ -316,7 +280,7 @@ static unsigned long finish_depth_computation(struct lazy_queue *queue,
repo_parse_commit(the_repository, p);
seen = p->object.flags & SEEN;
if (!seen)
- lazy_queue_put(queue, p);
+ prio_queue_put(queue, p);
flag_before = p->object.flags & best->flag_within;
p->object.flags |= c->object.flags;
flag_after = p->object.flags & best->flag_within;
@@ -364,8 +328,8 @@ static void append_suffix(int depth, const struct object_id *oid, struct strbuf
static void describe_commit(struct commit *cmit, struct strbuf *dst)
{
- struct commit *gave_up_on = NULL;
- struct lazy_queue queue = LAZY_QUEUE_INIT;
+ struct commit *c, *gave_up_on = NULL;
+ struct prio_queue queue = { compare_commits_by_commit_date };
struct commit_name *n;
struct possible_tag all_matches[MAX_TAGS];
unsigned int match_cnt = 0, annotated_cnt = 0, cur_match;
@@ -407,9 +371,8 @@ static void describe_commit(struct commit *cmit, struct strbuf *dst)
}
cmit->object.flags = SEEN;
- lazy_queue_put(&queue, cmit);
- while (!lazy_queue_empty(&queue)) {
- struct commit *c = lazy_queue_get(&queue);
+ prio_queue_put(&queue, cmit);
+ while ((c = prio_queue_get(&queue))) {
struct commit_list *parents = c->parents;
struct commit_name **slot;
@@ -443,7 +406,7 @@ static void describe_commit(struct commit *cmit, struct strbuf *dst)
t->depth++;
}
/* Stop if last remaining path already covered by best candidate(s) */
- if (annotated_cnt && lazy_queue_empty(&queue)) {
+ if (annotated_cnt && !prio_queue_size(&queue)) {
int best_depth = INT_MAX;
unsigned best_within = 0;
for (cur_match = 0; cur_match < match_cnt; cur_match++) {
@@ -466,7 +429,7 @@ static void describe_commit(struct commit *cmit, struct strbuf *dst)
struct commit *p = parents->item;
repo_parse_commit(the_repository, p);
if (!(p->object.flags & SEEN))
- lazy_queue_put(&queue, p);
+ prio_queue_put(&queue, p);
p->object.flags |= c->object.flags;
parents = parents->next;
@@ -481,7 +444,7 @@ static void describe_commit(struct commit *cmit, struct strbuf *dst)
strbuf_add_unique_abbrev(dst, cmit_oid, abbrev);
if (suffix)
strbuf_addstr(dst, suffix);
- lazy_queue_clear(&queue);
+ clear_prio_queue(&queue);
return;
}
if (unannotated_cnt)
@@ -497,11 +460,11 @@ static void describe_commit(struct commit *cmit, struct strbuf *dst)
QSORT(all_matches, match_cnt, compare_pt);
if (gave_up_on) {
- lazy_queue_put(&queue, gave_up_on);
+ prio_queue_put(&queue, gave_up_on);
seen_commits--;
}
seen_commits += finish_depth_computation(&queue, &all_matches[0]);
- lazy_queue_clear(&queue);
+ clear_prio_queue(&queue);
if (debug) {
static int label_width = -1;
diff --git a/builtin/last-modified.c b/builtin/last-modified.c
index 8900ceece1..df2a508244 100644
--- a/builtin/last-modified.c
+++ b/builtin/last-modified.c
@@ -344,6 +344,7 @@ static void process_parent(struct last_modified *lm,
static int last_modified_run(struct last_modified *lm)
{
int max_count, queue_popped = 0;
+ struct commit *c;
struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
struct prio_queue not_queue = { compare_commits_by_gen_then_commit_date };
struct commit_list *list;
@@ -389,10 +390,9 @@ static int last_modified_run(struct last_modified *lm)
}
}
- while (queue.nr) {
+ while ((c = prio_queue_get(&queue))) {
int parent_i;
struct commit_list *p;
- struct commit *c = prio_queue_get(&queue);
struct bitmap *active_c = active_paths_for(lm, c);
if ((0 <= max_count && max_count < ++queue_popped) ||
diff --git a/builtin/show-branch.c b/builtin/show-branch.c
index f02831b085..9f7f28f339 100644
--- a/builtin/show-branch.c
+++ b/builtin/show-branch.c
@@ -62,7 +62,7 @@ static const char *get_color_reset_code(void)
static struct commit *interesting(struct prio_queue *queue)
{
- for (size_t i = 0; i < queue->nr; i++) {
+ for (size_t i = queue->get_pending; i < queue->nr; i++) {
struct commit *commit = queue->array[i].data;
if (commit->object.flags & UNINTERESTING)
continue;
@@ -228,17 +228,18 @@ static void join_revs(struct prio_queue *queue,
{
int all_mask = ((1u << (REV_SHIFT + num_rev)) - 1);
int all_revs = all_mask & ~((1u << REV_SHIFT) - 1);
+ struct commit *commit;
- while (queue->nr) {
+ while ((commit = prio_queue_peek(queue))) {
struct commit_list *parents;
int still_interesting = !!interesting(queue);
- struct commit *commit = prio_queue_peek(queue);
- bool get_pending = true;
int flags = commit->object.flags & all_mask;
if (!still_interesting && extra <= 0)
break;
+ prio_queue_get(queue);
+
mark_seen(commit, seen_p);
if ((flags & all_revs) == all_revs)
flags |= UNINTERESTING;
@@ -254,14 +255,8 @@ static void join_revs(struct prio_queue *queue,
if (mark_seen(p, seen_p) && !still_interesting)
extra--;
p->object.flags |= flags;
- if (get_pending)
- prio_queue_replace(queue, p);
- else
- prio_queue_put(queue, p);
- get_pending = false;
+ prio_queue_put(queue, p);
}
- if (get_pending)
- prio_queue_get(queue);
}
/*
diff --git a/commit-reach.c b/commit-reach.c
index 9b3ea46d6f..0fec2f00be 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -1269,7 +1269,7 @@ int get_branch_base_for_tip(struct repository *r,
size_t bases_nr)
{
int best_index = -1;
- struct commit *branch_point = NULL;
+ struct commit *c, *branch_point = NULL;
struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
int found_missing_gen = 0;
@@ -1322,8 +1322,7 @@ int get_branch_base_for_tip(struct repository *r,
prio_queue_put(&queue, c);
}
- while (queue.nr) {
- struct commit *c = prio_queue_get(&queue);
+ while ((c = prio_queue_get(&queue))) {
int best_for_c = get_best(c);
int best_for_p, positive;
struct commit *parent;
diff --git a/commit.c b/commit.c
index fd8723502e..976bfc4618 100644
--- a/commit.c
+++ b/commit.c
@@ -795,24 +795,17 @@ void commit_list_sort_by_date(struct commit_list **list)
struct commit *pop_most_recent_commit(struct prio_queue *queue,
unsigned int mark)
{
- struct commit *ret = prio_queue_peek(queue);
- int get_pending = 1;
+ struct commit *ret = prio_queue_get(queue);
struct commit_list *parents = ret->parents;
while (parents) {
struct commit *commit = parents->item;
if (!repo_parse_commit(the_repository, commit) && !(commit->object.flags & mark)) {
commit->object.flags |= mark;
- if (get_pending)
- prio_queue_replace(queue, commit);
- else
- prio_queue_put(queue, commit);
- get_pending = 0;
+ prio_queue_put(queue, commit);
}
parents = parents->next;
}
- if (get_pending)
- prio_queue_get(queue);
return ret;
}
diff --git a/pack-bitmap-write.c b/pack-bitmap-write.c
index 1c8070f99c..f7c63e3027 100644
--- a/pack-bitmap-write.c
+++ b/pack-bitmap-write.c
@@ -513,6 +513,7 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,
struct bitmap_index *old_bitmap,
const uint32_t *mapping)
{
+ struct commit *c;
int found;
uint32_t pos;
if (!ent->bitmap)
@@ -520,9 +521,8 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,
prio_queue_put(queue, commit);
- while (queue->nr) {
+ while ((c = prio_queue_get(queue))) {
struct commit_list *p;
- struct commit *c = prio_queue_get(queue);
if (old_bitmap && mapping) {
struct ewah_bitmap *old;
diff --git a/prio-queue.c b/prio-queue.c
index 9748528ce6..a03c617470 100644
--- a/prio-queue.c
+++ b/prio-queue.c
@@ -34,64 +34,69 @@ void clear_prio_queue(struct prio_queue *queue)
queue->nr = 0;
queue->alloc = 0;
queue->insertion_ctr = 0;
+ queue->get_pending = 0;
+}
+
+static void sift_down_root(struct prio_queue *queue)
+{
+ size_t ix, child;
+
+ for (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {
+ child = ix * 2 + 1;
+ if (child + 1 < queue->nr &&
+ compare(queue, child, child + 1) >= 0)
+ child++;
+ if (compare(queue, ix, child) <= 0)
+ break;
+ swap(queue, child, ix);
+ }
}
void prio_queue_put(struct prio_queue *queue, void *thing)
{
size_t ix, parent;
- /* Append at the end */
+ if (queue->get_pending) {
+ queue->get_pending = 0;
+ queue->array[0].ctr = queue->insertion_ctr++;
+ queue->array[0].data = thing;
+ sift_down_root(queue);
+ return;
+ }
+
ALLOC_GROW(queue->array, queue->nr + 1, queue->alloc);
queue->array[queue->nr].ctr = queue->insertion_ctr++;
queue->array[queue->nr].data = thing;
queue->nr++;
if (!queue->compare)
- return; /* LIFO */
+ return;
- /* Bubble up the new one */
for (ix = queue->nr - 1; ix; ix = parent) {
parent = (ix - 1) / 2;
if (compare(queue, parent, ix) <= 0)
break;
-
swap(queue, parent, ix);
}
}
-static void sift_down_root(struct prio_queue *queue)
-{
- size_t ix, child;
-
- /* Push down the one at the root */
- for (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {
- child = ix * 2 + 1; /* left */
- if (child + 1 < queue->nr &&
- compare(queue, child, child + 1) >= 0)
- child++; /* use right child */
-
- if (compare(queue, ix, child) <= 0)
- break;
-
- swap(queue, child, ix);
- }
-}
-
void *prio_queue_get(struct prio_queue *queue)
{
- void *result;
-
if (!queue->nr)
return NULL;
if (!queue->compare)
- return queue->array[--queue->nr].data; /* LIFO */
-
- result = queue->array[0].data;
- if (!--queue->nr)
- return result;
+ return queue->array[--queue->nr].data;
+
+ if (queue->get_pending) {
+ if (!--queue->nr) {
+ queue->get_pending = 0;
+ return NULL;
+ }
+ queue->array[0] = queue->array[queue->nr];
+ sift_down_root(queue);
+ }
- queue->array[0] = queue->array[queue->nr];
- sift_down_root(queue);
- return result;
+ queue->get_pending = 1;
+ return queue->array[0].data;
}
void *prio_queue_peek(struct prio_queue *queue)
@@ -100,19 +105,14 @@ void *prio_queue_peek(struct prio_queue *queue)
return NULL;
if (!queue->compare)
return queue->array[queue->nr - 1].data;
- return queue->array[0].data;
-}
-void prio_queue_replace(struct prio_queue *queue, void *thing)
-{
- if (!queue->nr) {
- prio_queue_put(queue, thing);
- } else if (!queue->compare) {
- queue->array[queue->nr - 1].ctr = queue->insertion_ctr++;
- queue->array[queue->nr - 1].data = thing;
- } else {
- queue->array[0].ctr = queue->insertion_ctr++;
- queue->array[0].data = thing;
+ if (queue->get_pending) {
+ queue->get_pending = 0;
+ if (!--queue->nr)
+ return NULL;
+ queue->array[0] = queue->array[queue->nr];
sift_down_root(queue);
}
+
+ return queue->array[0].data;
}
diff --git a/prio-queue.h b/prio-queue.h
index da7fad2f1f..482ab5e71d 100644
--- a/prio-queue.h
+++ b/prio-queue.h
@@ -32,6 +32,7 @@ struct prio_queue {
void *cb_data;
size_t alloc, nr;
struct prio_queue_entry *array;
+ unsigned get_pending;
};
/*
@@ -52,13 +53,10 @@ void *prio_queue_get(struct prio_queue *);
*/
void *prio_queue_peek(struct prio_queue *);
-/*
- * Replace the "thing" that compares the smallest with a new "thing",
- * like prio_queue_get()+prio_queue_put() would do, but in a more
- * efficient way. Does the same as prio_queue_put() if the queue is
- * empty.
- */
-void prio_queue_replace(struct prio_queue *queue, void *thing);
+static inline size_t prio_queue_size(struct prio_queue *queue)
+{
+ return queue->nr - queue->get_pending;
+}
void clear_prio_queue(struct prio_queue *);
diff --git a/revision.c b/revision.c
index 5693618be4..8ce8ffa43d 100644
--- a/revision.c
+++ b/revision.c
@@ -1446,7 +1446,7 @@ static int limit_list(struct rev_info *revs)
struct commit_list *original_list = revs->commits;
struct commit_list *newlist = NULL;
struct commit_list **p = &newlist;
- struct commit *interesting_cache = NULL;
+ struct commit *commit, *interesting_cache = NULL;
struct prio_queue queue = { .compare = compare_commits_by_commit_date };
if (revs->ancestry_path_implicit_bottoms) {
@@ -1461,8 +1461,7 @@ static int limit_list(struct rev_info *revs)
prio_queue_put(&queue, commit);
}
- while (queue.nr) {
- struct commit *commit = prio_queue_get(&queue);
+ while ((commit = prio_queue_get(&queue))) {
struct object *obj = &commit->object;
if (commit == interesting_cache)
diff --git a/t/unit-tests/u-prio-queue.c b/t/unit-tests/u-prio-queue.c
index 63e58114ae..af3e0b8598 100644
--- a/t/unit-tests/u-prio-queue.c
+++ b/t/unit-tests/u-prio-queue.c
@@ -53,13 +53,13 @@ static void test_prio_queue(int *input, size_t input_size,
prio_queue_reverse(&pq);
break;
case REPLACE:
- peek = prio_queue_peek(&pq);
+ get = prio_queue_get(&pq);
cl_assert(i + 1 < input_size);
cl_assert(input[i + 1] >= 0);
cl_assert(j < result_size);
- cl_assert_equal_i(result[j], show(peek));
+ cl_assert_equal_i(result[j], show(get));
j++;
- prio_queue_replace(&pq, &input[++i]);
+ prio_queue_put(&pq, &input[++i]);
break;
default:
prio_queue_put(&pq, &input[i]);
diff --git a/walker.c b/walker.c
index e98eb6da53..e3de77f092 100644
--- a/walker.c
+++ b/walker.c
@@ -84,12 +84,12 @@ static struct prio_queue complete = { compare_commits_by_commit_date };
static int process_commit(struct walker *walker, struct commit *commit)
{
struct commit_list *parents;
+ struct commit *item;
if (repo_parse_commit(the_repository, commit))
return -1;
- while (complete.nr) {
- struct commit *item = prio_queue_peek(&complete);
+ while ((item = prio_queue_peek(&complete))) {
if (item->date < commit->date)
break;
pop_most_recent_commit(&complete, COMPLETE);
--
gitgitgadget
^ permalink raw reply related [flat|nested] 16+ messages in thread* [PATCH v3 2/2] prio-queue: rename .nr to .nr_internal to prevent direct access
2026-06-07 11:43 ` [PATCH v3 " Kristofer Karlsson via GitGitGadget
2026-06-07 11:43 ` [PATCH v3 1/2] " Kristofer Karlsson via GitGitGadget
@ 2026-06-07 11:43 ` Kristofer Karlsson via GitGitGadget
2026-06-08 13:36 ` [PATCH v3 0/2] prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion Junio C Hamano
2026-06-08 19:10 ` [PATCH v4 " Kristofer Karlsson via GitGitGadget
3 siblings, 0 replies; 16+ messages in thread
From: Kristofer Karlsson via GitGitGadget @ 2026-06-07 11:43 UTC (permalink / raw)
To: git
Cc: René Scharfe, Kristofer Karlsson, Kristofer Karlsson,
Kristofer Karlsson
From: Kristofer Karlsson <krka@spotify.com>
Rename the .nr member to .nr_internal so that callers outside
prio-queue.c that directly reference .nr get a compilation error.
This catches both existing misuse and future in-flight topics.
Add prio_queue_for_each() macro for callers that need to walk all
elements in the queue, accounting for the get_pending offset.
Convert all external .nr users:
- Loop conditions: use prio_queue_size(), prio_queue_get(), or
prio_queue_peek() as the loop condition
- Array iterations: use prio_queue_for_each()
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
builtin/describe.c | 7 +++---
builtin/last-modified.c | 5 ++---
builtin/show-branch.c | 9 ++++----
commit-reach.c | 19 +++++++++-------
fetch-pack.c | 4 ++--
negotiator/default.c | 4 +++-
negotiator/skipping.c | 12 ++++++-----
object-name.c | 2 +-
pack-bitmap-write.c | 6 +++---
path-walk.c | 8 +++----
prio-queue.c | 48 +++++++++++++++++++++++------------------
prio-queue.h | 9 ++++++--
revision.c | 11 +++++-----
13 files changed, 79 insertions(+), 65 deletions(-)
diff --git a/builtin/describe.c b/builtin/describe.c
index 85564f3487..64424543ef 100644
--- a/builtin/describe.c
+++ b/builtin/describe.c
@@ -258,10 +258,9 @@ static unsigned long finish_depth_computation(struct prio_queue *queue,
struct oidset unflagged = OIDSET_INIT;
struct commit *c;
- for (size_t i = queue->get_pending; i < queue->nr; i++) {
- struct commit *commit = queue->array[i].data;
- if (!(commit->object.flags & best->flag_within))
- oidset_insert(&unflagged, &commit->object.oid);
+ prio_queue_for_each(queue, c) {
+ if (!(c->object.flags & best->flag_within))
+ oidset_insert(&unflagged, &c->object.oid);
}
while ((c = prio_queue_get(queue))) {
diff --git a/builtin/last-modified.c b/builtin/last-modified.c
index df2a508244..5478182f2e 100644
--- a/builtin/last-modified.c
+++ b/builtin/last-modified.c
@@ -344,7 +344,7 @@ static void process_parent(struct last_modified *lm,
static int last_modified_run(struct last_modified *lm)
{
int max_count, queue_popped = 0;
- struct commit *c;
+ struct commit *c, *n;
struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
struct prio_queue not_queue = { compare_commits_by_gen_then_commit_date };
struct commit_list *list;
@@ -416,9 +416,8 @@ static int last_modified_run(struct last_modified *lm)
*/
repo_parse_commit(lm->rev.repo, c);
- while (not_queue.nr) {
+ while ((n = prio_queue_get(¬_queue))) {
struct commit_list *np;
- struct commit *n = prio_queue_get(¬_queue);
repo_parse_commit(lm->rev.repo, n);
diff --git a/builtin/show-branch.c b/builtin/show-branch.c
index 9f7f28f339..2435e8aeda 100644
--- a/builtin/show-branch.c
+++ b/builtin/show-branch.c
@@ -62,11 +62,10 @@ static const char *get_color_reset_code(void)
static struct commit *interesting(struct prio_queue *queue)
{
- for (size_t i = queue->get_pending; i < queue->nr; i++) {
- struct commit *commit = queue->array[i].data;
- if (commit->object.flags & UNINTERESTING)
- continue;
- return commit;
+ struct commit *commit;
+ prio_queue_for_each(queue, commit) {
+ if (!(commit->object.flags & UNINTERESTING))
+ return commit;
}
return NULL;
}
diff --git a/commit-reach.c b/commit-reach.c
index 0fec2f00be..dfe6016cb2 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -41,8 +41,8 @@ static int compare_commits_by_gen(const void *_a, const void *_b)
static int queue_has_nonstale(struct prio_queue *queue)
{
- for (size_t i = 0; i < queue->nr; i++) {
- struct commit *commit = queue->array[i].data;
+ struct commit *commit;
+ prio_queue_for_each(queue, commit) {
if (!(commit->object.flags & STALE))
return 1;
}
@@ -1069,6 +1069,7 @@ void ahead_behind(struct repository *r,
struct commit **commits, size_t commits_nr,
struct ahead_behind_count *counts, size_t counts_nr)
{
+ struct commit *c;
struct prio_queue queue = { .compare = compare_commits_by_gen_then_commit_date };
size_t width = DIV_ROUND_UP(commits_nr, BITS_IN_EWORD);
@@ -1085,17 +1086,19 @@ void ahead_behind(struct repository *r,
init_bit_arrays(&bit_arrays);
for (size_t i = 0; i < commits_nr; i++) {
- struct commit *c = commits[i];
- struct bitmap *bitmap = get_bit_array(c, width);
+ struct bitmap *bitmap;
+ c = commits[i];
+ bitmap = get_bit_array(c, width);
bitmap_set(bitmap, i);
insert_no_dup(&queue, c);
}
while (queue_has_nonstale(&queue)) {
- struct commit *c = prio_queue_get(&queue);
struct commit_list *p;
- struct bitmap *bitmap_c = get_bit_array(c, width);
+ struct bitmap *bitmap_c;
+ c = prio_queue_get(&queue);
+ bitmap_c = get_bit_array(c, width);
for (size_t i = 0; i < counts_nr; i++) {
int reach_from_tip = !!bitmap_get(bitmap_c, counts[i].tip_index);
@@ -1135,8 +1138,8 @@ void ahead_behind(struct repository *r,
/* STALE is used here, PARENT2 is used by insert_no_dup(). */
repo_clear_commit_marks(r, PARENT2 | STALE);
- for (size_t i = 0; i < queue.nr; i++)
- free_bit_array(queue.array[i].data);
+ prio_queue_for_each(&queue, c)
+ free_bit_array(c);
clear_bit_arrays(&bit_arrays);
clear_prio_queue(&queue);
}
diff --git a/fetch-pack.c b/fetch-pack.c
index 120e01f3cf..29c41132ee 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -662,8 +662,8 @@ static int mark_complete_oid(const struct reference *ref, void *cb_data UNUSED)
static void mark_recent_complete_commits(struct fetch_pack_args *args,
timestamp_t cutoff)
{
- while (complete.nr) {
- struct commit *item = prio_queue_peek(&complete);
+ struct commit *item;
+ while ((item = prio_queue_peek(&complete))) {
if (item->date < cutoff)
break;
print_verbose(args, _("Marking %s as complete"),
diff --git a/negotiator/default.c b/negotiator/default.c
index 78d58d57ce..19cdf3808c 100644
--- a/negotiator/default.c
+++ b/negotiator/default.c
@@ -113,10 +113,12 @@ static const struct object_id *get_rev(struct negotiation_state *ns)
unsigned int mark;
struct commit_list *parents;
- if (ns->rev_list.nr == 0 || ns->non_common_revs == 0)
+ if (ns->non_common_revs == 0)
return NULL;
commit = prio_queue_get(&ns->rev_list);
+ if (!commit)
+ return NULL;
repo_parse_commit(the_repository, commit);
parents = commit->parents;
diff --git a/negotiator/skipping.c b/negotiator/skipping.c
index 68c9b3b997..db90fa77b5 100644
--- a/negotiator/skipping.c
+++ b/negotiator/skipping.c
@@ -143,8 +143,7 @@ static int push_parent(struct data *data, struct entry *entry,
/*
* Find the existing entry and use it.
*/
- for (size_t i = 0; i < data->rev_list.nr; i++) {
- parent_entry = data->rev_list.array[i].data;
+ prio_queue_for_each(&data->rev_list, parent_entry) {
if (parent_entry->commit == to_push)
goto parent_found;
}
@@ -181,10 +180,12 @@ static const struct object_id *get_rev(struct data *data)
struct commit_list *p;
int parent_pushed = 0;
- if (data->rev_list.nr == 0 || data->non_common_revs == 0)
+ if (data->non_common_revs == 0)
return NULL;
entry = prio_queue_get(&data->rev_list);
+ if (!entry)
+ return NULL;
commit = entry->commit;
commit->object.flags |= POPPED;
if (!(commit->object.flags & COMMON))
@@ -253,8 +254,9 @@ static void have_sent(struct fetch_negotiator *n, struct commit *c)
static void release(struct fetch_negotiator *n)
{
struct data *data = n->data;
- for (size_t i = 0; i < data->rev_list.nr; i++)
- free(data->rev_list.array[i].data);
+ void *entry;
+ prio_queue_for_each(&data->rev_list, entry)
+ free(entry);
clear_prio_queue(&data->rev_list);
FREE_AND_NULL(data);
}
diff --git a/object-name.c b/object-name.c
index 9ac86f19c7..2fedfe1761 100644
--- a/object-name.c
+++ b/object-name.c
@@ -1208,7 +1208,7 @@ static int get_oid_oneline(struct repository *r,
l->item->object.flags |= ONELINE_SEEN;
prio_queue_put(©, l->item);
}
- while (copy.nr) {
+ while (prio_queue_size(©)) {
const char *p, *buf;
struct commit *commit;
int matches;
diff --git a/pack-bitmap-write.c b/pack-bitmap-write.c
index f7c63e3027..ed9714b135 100644
--- a/pack-bitmap-write.c
+++ b/pack-bitmap-write.c
@@ -514,6 +514,7 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,
const uint32_t *mapping)
{
struct commit *c;
+ struct tree *tree;
int found;
uint32_t pos;
if (!ent->bitmap)
@@ -574,9 +575,8 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,
}
}
- while (tree_queue->nr) {
- if (fill_bitmap_tree(writer, ent->bitmap,
- prio_queue_get(tree_queue)) < 0)
+ while ((tree = prio_queue_get(tree_queue))) {
+ if (fill_bitmap_tree(writer, ent->bitmap, tree) < 0)
return -1;
}
return 0;
diff --git a/path-walk.c b/path-walk.c
index 94ff90bd15..cf3b2d0765 100644
--- a/path-walk.c
+++ b/path-walk.c
@@ -699,6 +699,7 @@ int walk_objects_by_path(struct path_walk_info *info)
int ret;
size_t commits_nr = 0, paths_nr = 0;
struct commit *c;
+ char *path;
struct type_and_oid_list *root_tree_list;
struct type_and_oid_list *commit_list;
struct path_walk_context ctx = {
@@ -808,8 +809,7 @@ int walk_objects_by_path(struct path_walk_info *info)
free(commit_list);
trace2_region_enter("path-walk", "path-walk", info->revs->repo);
- while (!ret && ctx.path_stack.nr) {
- char *path = prio_queue_get(&ctx.path_stack);
+ while (!ret && (path = prio_queue_get(&ctx.path_stack))) {
paths_nr++;
ret = walk_path(&ctx, path);
@@ -821,12 +821,12 @@ int walk_objects_by_path(struct path_walk_info *info)
if (!strmap_empty(&ctx.paths_to_lists)) {
struct hashmap_iter iter;
struct strmap_entry *entry;
+ char *path;
strmap_for_each_entry(&ctx.paths_to_lists, &iter, entry)
push_to_stack(&ctx, entry->key);
- while (!ret && ctx.path_stack.nr) {
- char *path = prio_queue_get(&ctx.path_stack);
+ while (!ret && (path = prio_queue_get(&ctx.path_stack))) {
paths_nr++;
ret = walk_path(&ctx, path);
diff --git a/prio-queue.c b/prio-queue.c
index a03c617470..f96b810c15 100644
--- a/prio-queue.c
+++ b/prio-queue.c
@@ -22,16 +22,16 @@ void prio_queue_reverse(struct prio_queue *queue)
if (queue->compare)
BUG("prio_queue_reverse() on non-LIFO queue");
- if (!queue->nr)
+ if (!queue->nr_internal)
return;
- for (i = 0; i < (j = (queue->nr - 1) - i); i++)
+ for (i = 0; i < (j = (queue->nr_internal - 1) - i); i++)
swap(queue, i, j);
}
void clear_prio_queue(struct prio_queue *queue)
{
FREE_AND_NULL(queue->array);
- queue->nr = 0;
+ queue->nr_internal = 0;
queue->alloc = 0;
queue->insertion_ctr = 0;
queue->get_pending = 0;
@@ -41,13 +41,16 @@ static void sift_down_root(struct prio_queue *queue)
{
size_t ix, child;
- for (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {
- child = ix * 2 + 1;
- if (child + 1 < queue->nr &&
+ /* Push down the one at the root */
+ for (ix = 0; ix * 2 + 1 < queue->nr_internal; ix = child) {
+ child = ix * 2 + 1; /* left */
+ if (child + 1 < queue->nr_internal &&
compare(queue, child, child + 1) >= 0)
- child++;
+ child++; /* use right child */
+
if (compare(queue, ix, child) <= 0)
break;
+
swap(queue, child, ix);
}
}
@@ -64,34 +67,37 @@ void prio_queue_put(struct prio_queue *queue, void *thing)
return;
}
- ALLOC_GROW(queue->array, queue->nr + 1, queue->alloc);
- queue->array[queue->nr].ctr = queue->insertion_ctr++;
- queue->array[queue->nr].data = thing;
- queue->nr++;
+ /* Append at the end */
+ ALLOC_GROW(queue->array, queue->nr_internal + 1, queue->alloc);
+ queue->array[queue->nr_internal].ctr = queue->insertion_ctr++;
+ queue->array[queue->nr_internal].data = thing;
+ queue->nr_internal++;
if (!queue->compare)
- return;
+ return; /* LIFO */
- for (ix = queue->nr - 1; ix; ix = parent) {
+ /* Bubble up the new one */
+ for (ix = queue->nr_internal - 1; ix; ix = parent) {
parent = (ix - 1) / 2;
if (compare(queue, parent, ix) <= 0)
break;
+
swap(queue, parent, ix);
}
}
void *prio_queue_get(struct prio_queue *queue)
{
- if (!queue->nr)
+ if (!queue->nr_internal)
return NULL;
if (!queue->compare)
- return queue->array[--queue->nr].data;
+ return queue->array[--queue->nr_internal].data; /* LIFO */
if (queue->get_pending) {
- if (!--queue->nr) {
+ if (!--queue->nr_internal) {
queue->get_pending = 0;
return NULL;
}
- queue->array[0] = queue->array[queue->nr];
+ queue->array[0] = queue->array[queue->nr_internal];
sift_down_root(queue);
}
@@ -101,16 +107,16 @@ void *prio_queue_get(struct prio_queue *queue)
void *prio_queue_peek(struct prio_queue *queue)
{
- if (!queue->nr)
+ if (!queue->nr_internal)
return NULL;
if (!queue->compare)
- return queue->array[queue->nr - 1].data;
+ return queue->array[queue->nr_internal - 1].data;
if (queue->get_pending) {
queue->get_pending = 0;
- if (!--queue->nr)
+ if (!--queue->nr_internal)
return NULL;
- queue->array[0] = queue->array[queue->nr];
+ queue->array[0] = queue->array[queue->nr_internal];
sift_down_root(queue);
}
diff --git a/prio-queue.h b/prio-queue.h
index 482ab5e71d..f08ab87691 100644
--- a/prio-queue.h
+++ b/prio-queue.h
@@ -30,7 +30,7 @@ struct prio_queue {
prio_queue_compare_fn compare;
size_t insertion_ctr;
void *cb_data;
- size_t alloc, nr;
+ size_t alloc, nr_internal; /* use prio_queue_size() for logical count */
struct prio_queue_entry *array;
unsigned get_pending;
};
@@ -55,9 +55,14 @@ void *prio_queue_peek(struct prio_queue *);
static inline size_t prio_queue_size(struct prio_queue *queue)
{
- return queue->nr - queue->get_pending;
+ return queue->nr_internal - queue->get_pending;
}
+#define prio_queue_for_each(queue, it) \
+ for (size_t pq_ix_ = (queue)->get_pending; \
+ pq_ix_ < (queue)->nr_internal && ((it) = (queue)->array[pq_ix_].data, 1); \
+ pq_ix_++)
+
void clear_prio_queue(struct prio_queue *);
/* Reverse the LIFO elements */
diff --git a/revision.c b/revision.c
index 8ce8ffa43d..34e2d146f4 100644
--- a/revision.c
+++ b/revision.c
@@ -476,16 +476,15 @@ static struct commit *handle_commit(struct rev_info *revs,
static int everybody_uninteresting(struct prio_queue *orig,
struct commit **interesting_cache)
{
- size_t i;
+ struct commit *commit;
if (*interesting_cache) {
- struct commit *commit = *interesting_cache;
+ commit = *interesting_cache;
if (!(commit->object.flags & UNINTERESTING))
return 0;
}
- for (i = 0; i < orig->nr; i++) {
- struct commit *commit = orig->array[i].data;
+ prio_queue_for_each(orig, commit) {
if (commit->object.flags & UNINTERESTING)
continue;
@@ -4027,8 +4026,8 @@ static enum rewrite_result rewrite_one_1(struct rev_info *revs,
static void merge_queue_into_list(struct prio_queue *q, struct commit_list **list)
{
- while (q->nr) {
- struct commit *item = prio_queue_peek(q);
+ struct commit *item;
+ while ((item = prio_queue_peek(q))) {
struct commit_list *p = *list;
if (p && p->item->date >= item->date)
--
gitgitgadget
^ permalink raw reply related [flat|nested] 16+ messages in thread* Re: [PATCH v3 0/2] prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion
2026-06-07 11:43 ` [PATCH v3 " Kristofer Karlsson via GitGitGadget
2026-06-07 11:43 ` [PATCH v3 1/2] " Kristofer Karlsson via GitGitGadget
2026-06-07 11:43 ` [PATCH v3 2/2] prio-queue: rename .nr to .nr_internal to prevent direct access Kristofer Karlsson via GitGitGadget
@ 2026-06-08 13:36 ` Junio C Hamano
2026-06-08 19:10 ` [PATCH v4 " Kristofer Karlsson via GitGitGadget
3 siblings, 0 replies; 16+ messages in thread
From: Junio C Hamano @ 2026-06-08 13:36 UTC (permalink / raw)
To: Kristofer Karlsson via GitGitGadget
Cc: git, René Scharfe, Kristofer Karlsson
"Kristofer Karlsson via GitGitGadget" <gitgitgadget@gmail.com>
writes:
> Changes in v3:
>
> * Adopted Rene's suggestion to move the flush logic below the LIFO
> early-return (LIFO mode never sets get_pending, so flushing there is a
> no-op).
Sensible.
> * Went a step further and inlined the flush logic directly into get() and
> peek(), eliminating the flush_get() helper and its forward declaration of
> sift_down_root().
Hmph, unless there is a reason to allow the copies in get() and
peek() to deviate from each other, e.g., what flush_get() had to do
inside get() and peek() were slightly different, I am not sure if
this is a good move. I do not know if the slight difference of the
"inlined" logic we have in the patch between the one in get() and
the other one in peek() has merit, either. It certainly lets you
avoid an unnecessary clearing of the get_pending bit (when a get was
pending but the queue has more items to yield) immediately followed
by turning it back on again (which happens always unless the
function makes an early return for an empty queue) in get(), which
will never happen in flush() that will always clear the bit before
it returns, but is such an avoidance of an assignment really worth
it? I suspect that with the static inline version of flush_get(),
compilers are smart enough to optimize it away, but I dunno.
> void *prio_queue_get(struct prio_queue *queue)
> {
> if (!queue->nr)
> return NULL;
> if (!queue->compare)
> ++ return queue->array[--queue->nr].data;
> ++
> ++ if (queue->get_pending) {
> ++ if (!--queue->nr) {
> ++ queue->get_pending = 0;
> ++ return NULL;
> ++ }
> ++ queue->array[0] = queue->array[queue->nr];
> ++ sift_down_root(queue);
> ++ }
> +
The above is from [1/2] (this is a minor point, but flipping the
order of two patches to make the "nr_internal clean-up" as a
preliminary step might have made commenting on this part easier to
read). I wondered if it is easier to understand if the first early
return is guarded by a conditional that takes get_pending into
account.
if (queue->nr_internal <= queue->get_pending)
return NULL;
As I said, since the above hunk is immediately followed by an
unconditional assignment of "queue->get_pending = 1", clearing
get_pending = 0 only when we leave inside the if() block works as an
optimization that is not available on the peek() side. But with the
"ah the queue is empty already, the queue->ne == 1 is due to the
lazy get that did not rebalance" tweak, it would become unneeded, I
think.
> + void *prio_queue_peek(struct prio_queue *queue)
> + {
> + if (!queue->nr_internal)
> return NULL;
> if (!queue->compare)
> + return queue->array[queue->nr_internal - 1].data;
> +
> + if (queue->get_pending) {
> + queue->get_pending = 0;
> +- if (!--queue->nr)
> ++ if (!--queue->nr_internal)
> + return NULL;
> +- queue->array[0] = queue->array[queue->nr];
> ++ queue->array[0] = queue->array[queue->nr_internal];
> + sift_down_root(queue);
> + }
This is from [2/2]; the same
if (queue->nr_internal <= queue->get_pending)
return NULL;
applies here, I think.
^ permalink raw reply [flat|nested] 16+ messages in thread* [PATCH v4 0/2] prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion
2026-06-07 11:43 ` [PATCH v3 " Kristofer Karlsson via GitGitGadget
` (2 preceding siblings ...)
2026-06-08 13:36 ` [PATCH v3 0/2] prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion Junio C Hamano
@ 2026-06-08 19:10 ` Kristofer Karlsson via GitGitGadget
2026-06-08 19:10 ` [PATCH v4 1/2] prio-queue: rename .nr to .nr_ and add accessor helpers Kristofer Karlsson via GitGitGadget
2026-06-08 19:10 ` [PATCH v4 2/2] prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion Kristofer Karlsson via GitGitGadget
3 siblings, 2 replies; 16+ messages in thread
From: Kristofer Karlsson via GitGitGadget @ 2026-06-08 19:10 UTC (permalink / raw)
To: git; +Cc: René Scharfe, Kristofer Karlsson, Kristofer Karlsson
Rene's lazy_queue wrapper in describe.c was a clever optimization -- by
deferring the get, a following put becomes a simple replace, avoiding a full
remove-rebalance-insert cycle.
It turns out this pattern is so common in git's traversal code that it makes
sense to fold it into prio_queue itself. Gets and puts are interleaved in
virtually every commit walk, so the fusion is essentially always a win.
This is mostly a code simplification -- three callers had independently
reimplemented the same optimization, and they all collapse to plain get+put
now. The 1.7-2.7% speedup on traversal-heavy workloads is a nice bonus.
More details and benchmark numbers in the commit message.
Related to but independent of the cascade sift-down work in
kk/prio-queue-cascade-sift -- the two can land in either order.
Changes in v4:
* Thanks Junio for review, applied all suggestions.
* Renamed .nr_internal to .nr_
* Restored flush_get() as a static inline helper instead of inlining the
flush logic into get() and peek().
* Guard empty-queue check with nr_ <= get_pending.
* Flipped commit order: the rename/accessor commit is now first, and the
behavioral fusion change is second. This was partly messy -- the first
rename commit introduces some ugly intermediate code (e.g. describe.c's
prio_queue_for_each with a skip variable) that gets cleaned up in commit
2 when the lazy get makes it unnecessary.
Changes in v3:
* Adopted Rene's suggestion to move the flush logic below the LIFO
early-return (LIFO mode never sets get_pending, so flushing there is a
no-op).
* Went a step further and inlined the flush logic directly into get() and
peek(), eliminating the flush_get() helper and its forward declaration of
sift_down_root().
* Updated benchmark numbers with more rigorous methodology: 30 interleaved
runs with paired t-test on an idle server. Split results into code paths
that already had manual fusion (neutral) vs code paths that benefit from
the new automatic fusion (1.7-2.7% improvement).
Changes in v2:
* Added a second commit that renames .nr to .nr_internal so that direct
access from outside prio-queue.c is a compile error. Verified that after
the rename, only prio-queue.c references nr_internal.
* Added prio_queue_for_each() macro for callers that need to walk all
elements (describe.c, show-branch.c, commit-reach.c, revision.c,
negotiator/skipping.c).
* Converted remaining .nr loop conditions to use
prio_queue_get()/prio_queue_peek() as the loop condition, or
prio_queue_size() where get/peek isn't suitable.
* Fixed several callers missed in v1 (object-name.c, fetch-pack.c,
path-walk.c, pack-bitmap-write.c, negotiator/default.c,
negotiator/skipping.c, revision.c, builtin/last-modified.c).
Kristofer Karlsson (2):
prio-queue: rename .nr to .nr_ and add accessor helpers
prio-queue: fold lazy_queue into prio_queue for automatic get+put
fusion
builtin/describe.c | 70 ++++++-----------------
builtin/last-modified.c | 7 +--
builtin/show-branch.c | 24 +++-----
commit-reach.c | 14 ++---
commit.c | 11 +---
fetch-pack.c | 4 +-
negotiator/default.c | 4 +-
negotiator/skipping.c | 12 ++--
object-name.c | 2 +-
pack-bitmap-write.c | 10 ++--
path-walk.c | 8 +--
prio-queue.c | 110 +++++++++++++++++++-----------------
prio-queue.h | 19 ++++---
revision.c | 16 +++---
t/unit-tests/u-prio-queue.c | 6 +-
walker.c | 4 +-
16 files changed, 141 insertions(+), 180 deletions(-)
base-commit: 9ac3f193c05c2237e2b14ebaa1149e9fc8a1abe0
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2140%2Fspkrka%2Flazy-prio-queue-pr-v4
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2140/spkrka/lazy-prio-queue-pr-v4
Pull-Request: https://github.com/gitgitgadget/git/pull/2140
Range-diff vs v3:
2: 033215e304 ! 1: d0f2294661 prio-queue: rename .nr to .nr_internal to prevent direct access
@@ Metadata
Author: Kristofer Karlsson <krka@spotify.com>
## Commit message ##
- prio-queue: rename .nr to .nr_internal to prevent direct access
+ prio-queue: rename .nr to .nr_ and add accessor helpers
- Rename the .nr member to .nr_internal so that callers outside
- prio-queue.c that directly reference .nr get a compilation error.
- This catches both existing misuse and future in-flight topics.
+ Rename the .nr member to .nr_ so that callers outside prio-queue.c
+ that directly reference .nr get a compilation error. This catches
+ both existing misuse and future in-flight topics.
- Add prio_queue_for_each() macro for callers that need to walk all
- elements in the queue, accounting for the get_pending offset.
+ Add prio_queue_size() for callers that need to know the element count
+ and prio_queue_for_each() for callers that need to walk all elements.
Convert all external .nr users:
- Loop conditions: use prio_queue_size(), prio_queue_get(), or
@@ Commit message
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
## builtin/describe.c ##
-@@ builtin/describe.c: static unsigned long finish_depth_computation(struct prio_queue *queue,
- struct oidset unflagged = OIDSET_INIT;
- struct commit *c;
+@@ builtin/describe.c: static void lazy_queue_put(struct lazy_queue *queue, void *thing)
-- for (size_t i = queue->get_pending; i < queue->nr; i++) {
-- struct commit *commit = queue->array[i].data;
-- if (!(commit->object.flags & best->flag_within))
-- oidset_insert(&unflagged, &commit->object.oid);
-+ prio_queue_for_each(queue, c) {
-+ if (!(c->object.flags & best->flag_within))
-+ oidset_insert(&unflagged, &c->object.oid);
- }
+ static bool lazy_queue_empty(const struct lazy_queue *queue)
+ {
+- return queue->queue.nr == (queue->get_pending ? 1 : 0);
++ return prio_queue_size(&queue->queue) == (queue->get_pending ? 1 : 0);
+ }
- while ((c = prio_queue_get(queue))) {
+ static void lazy_queue_clear(struct lazy_queue *queue)
+@@ builtin/describe.c: static unsigned long finish_depth_computation(struct lazy_queue *queue,
+ {
+ unsigned long seen_commits = 0;
+ struct oidset unflagged = OIDSET_INIT;
++ struct commit *commit;
++ int skip = queue->get_pending ? 1 : 0;
+
+- for (size_t i = queue->get_pending ? 1 : 0; i < queue->queue.nr; i++) {
+- struct commit *commit = queue->queue.array[i].data;
++ prio_queue_for_each(&queue->queue, commit) {
++ if (skip) {
++ skip = 0;
++ continue;
++ }
+ if (!(commit->object.flags & best->flag_within))
+ oidset_insert(&unflagged, &commit->object.oid);
+ }
## builtin/last-modified.c ##
@@ builtin/last-modified.c: static void process_parent(struct last_modified *lm,
static int last_modified_run(struct last_modified *lm)
{
int max_count, queue_popped = 0;
-- struct commit *c;
+ struct commit *c, *n;
struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
struct prio_queue not_queue = { compare_commits_by_gen_then_commit_date };
struct commit_list *list;
+@@ builtin/last-modified.c: static int last_modified_run(struct last_modified *lm)
+ }
+ }
+
+- while (queue.nr) {
++ while ((c = prio_queue_get(&queue))) {
+ int parent_i;
+ struct commit_list *p;
+- struct commit *c = prio_queue_get(&queue);
+ struct bitmap *active_c = active_paths_for(lm, c);
+
+ if ((0 <= max_count && max_count < ++queue_popped) ||
@@ builtin/last-modified.c: static int last_modified_run(struct last_modified *lm)
*/
repo_parse_commit(lm->rev.repo, c);
@@ builtin/show-branch.c: static const char *get_color_reset_code(void)
static struct commit *interesting(struct prio_queue *queue)
{
-- for (size_t i = queue->get_pending; i < queue->nr; i++) {
+- for (size_t i = 0; i < queue->nr; i++) {
- struct commit *commit = queue->array[i].data;
- if (commit->object.flags & UNINTERESTING)
- continue;
@@ builtin/show-branch.c: static const char *get_color_reset_code(void)
}
return NULL;
}
+@@ builtin/show-branch.c: static void join_revs(struct prio_queue *queue,
+ {
+ int all_mask = ((1u << (REV_SHIFT + num_rev)) - 1);
+ int all_revs = all_mask & ~((1u << REV_SHIFT) - 1);
++ struct commit *commit;
+
+- while (queue->nr) {
++ while ((commit = prio_queue_peek(queue))) {
+ struct commit_list *parents;
+ int still_interesting = !!interesting(queue);
+- struct commit *commit = prio_queue_peek(queue);
+ bool get_pending = true;
+ int flags = commit->object.flags & all_mask;
+
## commit-reach.c ##
@@ commit-reach.c: static int compare_commits_by_gen(const void *_a, const void *_b)
@@ commit-reach.c: static int compare_commits_by_gen(const void *_a, const void *_b
return 1;
}
@@ commit-reach.c: void ahead_behind(struct repository *r,
- struct commit **commits, size_t commits_nr,
struct ahead_behind_count *counts, size_t counts_nr)
{
-+ struct commit *c;
struct prio_queue queue = { .compare = compare_commits_by_gen_then_commit_date };
++ void *entry;
size_t width = DIV_ROUND_UP(commits_nr, BITS_IN_EWORD);
-@@ commit-reach.c: void ahead_behind(struct repository *r,
- init_bit_arrays(&bit_arrays);
-
- for (size_t i = 0; i < commits_nr; i++) {
-- struct commit *c = commits[i];
-- struct bitmap *bitmap = get_bit_array(c, width);
-+ struct bitmap *bitmap;
-+ c = commits[i];
-+ bitmap = get_bit_array(c, width);
-
- bitmap_set(bitmap, i);
- insert_no_dup(&queue, c);
- }
-
- while (queue_has_nonstale(&queue)) {
-- struct commit *c = prio_queue_get(&queue);
- struct commit_list *p;
-- struct bitmap *bitmap_c = get_bit_array(c, width);
-+ struct bitmap *bitmap_c;
-+ c = prio_queue_get(&queue);
-+ bitmap_c = get_bit_array(c, width);
-
- for (size_t i = 0; i < counts_nr; i++) {
- int reach_from_tip = !!bitmap_get(bitmap_c, counts[i].tip_index);
+ if (!commits_nr || !counts_nr)
@@ commit-reach.c: void ahead_behind(struct repository *r,
/* STALE is used here, PARENT2 is used by insert_no_dup(). */
repo_clear_commit_marks(r, PARENT2 | STALE);
- for (size_t i = 0; i < queue.nr; i++)
- free_bit_array(queue.array[i].data);
-+ prio_queue_for_each(&queue, c)
-+ free_bit_array(c);
++ prio_queue_for_each(&queue, entry)
++ free_bit_array(entry);
clear_bit_arrays(&bit_arrays);
clear_prio_queue(&queue);
}
+@@ commit-reach.c: int get_branch_base_for_tip(struct repository *r,
+ size_t bases_nr)
+ {
+ int best_index = -1;
+- struct commit *branch_point = NULL;
++ struct commit *c, *branch_point = NULL;
+ struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
+ int found_missing_gen = 0;
+
+@@ commit-reach.c: int get_branch_base_for_tip(struct repository *r,
+ prio_queue_put(&queue, c);
+ }
+
+- while (queue.nr) {
+- struct commit *c = prio_queue_get(&queue);
++ while ((c = prio_queue_get(&queue))) {
+ int best_for_c = get_best(c);
+ int best_for_p, positive;
+ struct commit *parent;
## fetch-pack.c ##
@@ fetch-pack.c: static int mark_complete_oid(const struct reference *ref, void *cb_data UNUSED)
@@ object-name.c: static int get_oid_oneline(struct repository *r,
## pack-bitmap-write.c ##
@@ pack-bitmap-write.c: static int fill_bitmap_commit(struct bitmap_writer *writer,
+ struct bitmap_index *old_bitmap,
const uint32_t *mapping)
{
- struct commit *c;
++ struct commit *c;
+ struct tree *tree;
int found;
uint32_t pos;
if (!ent->bitmap)
@@ pack-bitmap-write.c: static int fill_bitmap_commit(struct bitmap_writer *writer,
+
+ prio_queue_put(queue, commit);
+
+- while (queue->nr) {
++ while ((c = prio_queue_get(queue))) {
+ struct commit_list *p;
+- struct commit *c = prio_queue_get(queue);
+
+ if (old_bitmap && mapping) {
+ struct ewah_bitmap *old;
+@@ pack-bitmap-write.c: static int fill_bitmap_commit(struct bitmap_writer *writer,
}
}
@@ prio-queue.c: void prio_queue_reverse(struct prio_queue *queue)
if (queue->compare)
BUG("prio_queue_reverse() on non-LIFO queue");
- if (!queue->nr)
-+ if (!queue->nr_internal)
++ if (!queue->nr_)
return;
- for (i = 0; i < (j = (queue->nr - 1) - i); i++)
-+ for (i = 0; i < (j = (queue->nr_internal - 1) - i); i++)
++ for (i = 0; i < (j = (queue->nr_ - 1) - i); i++)
swap(queue, i, j);
}
@@ prio-queue.c: void prio_queue_reverse(struct prio_queue *queue)
{
FREE_AND_NULL(queue->array);
- queue->nr = 0;
-+ queue->nr_internal = 0;
++ queue->nr_ = 0;
queue->alloc = 0;
queue->insertion_ctr = 0;
- queue->get_pending = 0;
-@@ prio-queue.c: static void sift_down_root(struct prio_queue *queue)
- {
- size_t ix, child;
-
-- for (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {
-- child = ix * 2 + 1;
-- if (child + 1 < queue->nr &&
-+ /* Push down the one at the root */
-+ for (ix = 0; ix * 2 + 1 < queue->nr_internal; ix = child) {
-+ child = ix * 2 + 1; /* left */
-+ if (child + 1 < queue->nr_internal &&
- compare(queue, child, child + 1) >= 0)
-- child++;
-+ child++; /* use right child */
-+
- if (compare(queue, ix, child) <= 0)
- break;
-+
- swap(queue, child, ix);
- }
}
@@ prio-queue.c: void prio_queue_put(struct prio_queue *queue, void *thing)
- return;
- }
+ size_t ix, parent;
+ /* Append at the end */
- ALLOC_GROW(queue->array, queue->nr + 1, queue->alloc);
- queue->array[queue->nr].ctr = queue->insertion_ctr++;
- queue->array[queue->nr].data = thing;
- queue->nr++;
-+ /* Append at the end */
-+ ALLOC_GROW(queue->array, queue->nr_internal + 1, queue->alloc);
-+ queue->array[queue->nr_internal].ctr = queue->insertion_ctr++;
-+ queue->array[queue->nr_internal].data = thing;
-+ queue->nr_internal++;
++ ALLOC_GROW(queue->array, queue->nr_ + 1, queue->alloc);
++ queue->array[queue->nr_].ctr = queue->insertion_ctr++;
++ queue->array[queue->nr_].data = thing;
++ queue->nr_++;
if (!queue->compare)
-- return;
-+ return; /* LIFO */
+ return; /* LIFO */
+ /* Bubble up the new one */
- for (ix = queue->nr - 1; ix; ix = parent) {
-+ /* Bubble up the new one */
-+ for (ix = queue->nr_internal - 1; ix; ix = parent) {
++ for (ix = queue->nr_ - 1; ix; ix = parent) {
parent = (ix - 1) / 2;
if (compare(queue, parent, ix) <= 0)
break;
-+
- swap(queue, parent, ix);
- }
- }
+@@ prio-queue.c: static void sift_down_root(struct prio_queue *queue)
+ size_t ix, child;
+
+ /* Push down the one at the root */
+- for (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {
++ for (ix = 0; ix * 2 + 1 < queue->nr_; ix = child) {
+ child = ix * 2 + 1; /* left */
+- if (child + 1 < queue->nr &&
++ if (child + 1 < queue->nr_ &&
+ compare(queue, child, child + 1) >= 0)
+ child++; /* use right child */
- void *prio_queue_get(struct prio_queue *queue)
+@@ prio-queue.c: void *prio_queue_get(struct prio_queue *queue)
{
+ void *result;
+
- if (!queue->nr)
-+ if (!queue->nr_internal)
++ if (!queue->nr_)
return NULL;
if (!queue->compare)
-- return queue->array[--queue->nr].data;
-+ return queue->array[--queue->nr_internal].data; /* LIFO */
-
- if (queue->get_pending) {
-- if (!--queue->nr) {
-+ if (!--queue->nr_internal) {
- queue->get_pending = 0;
- return NULL;
- }
-- queue->array[0] = queue->array[queue->nr];
-+ queue->array[0] = queue->array[queue->nr_internal];
- sift_down_root(queue);
- }
-
-@@ prio-queue.c: void *prio_queue_get(struct prio_queue *queue)
+- return queue->array[--queue->nr].data; /* LIFO */
++ return queue->array[--queue->nr_].data; /* LIFO */
+
+ result = queue->array[0].data;
+- if (!--queue->nr)
++ if (!--queue->nr_)
+ return result;
+
+- queue->array[0] = queue->array[queue->nr];
++ queue->array[0] = queue->array[queue->nr_];
+ sift_down_root(queue);
+ return result;
+ }
void *prio_queue_peek(struct prio_queue *queue)
{
- if (!queue->nr)
-+ if (!queue->nr_internal)
++ if (!queue->nr_)
return NULL;
if (!queue->compare)
- return queue->array[queue->nr - 1].data;
-+ return queue->array[queue->nr_internal - 1].data;
-
- if (queue->get_pending) {
- queue->get_pending = 0;
-- if (!--queue->nr)
-+ if (!--queue->nr_internal)
- return NULL;
-- queue->array[0] = queue->array[queue->nr];
-+ queue->array[0] = queue->array[queue->nr_internal];
- sift_down_root(queue);
- }
++ return queue->array[queue->nr_ - 1].data;
+ return queue->array[0].data;
+ }
+ void prio_queue_replace(struct prio_queue *queue, void *thing)
+ {
+- if (!queue->nr) {
++ if (!queue->nr_) {
+ prio_queue_put(queue, thing);
+ } else if (!queue->compare) {
+- queue->array[queue->nr - 1].ctr = queue->insertion_ctr++;
+- queue->array[queue->nr - 1].data = thing;
++ queue->array[queue->nr_ - 1].ctr = queue->insertion_ctr++;
++ queue->array[queue->nr_ - 1].data = thing;
+ } else {
+ queue->array[0].ctr = queue->insertion_ctr++;
+ queue->array[0].data = thing;
## prio-queue.h ##
@@ prio-queue.h: struct prio_queue {
@@ prio-queue.h: struct prio_queue {
size_t insertion_ctr;
void *cb_data;
- size_t alloc, nr;
-+ size_t alloc, nr_internal; /* use prio_queue_size() for logical count */
++ size_t alloc, nr_;
struct prio_queue_entry *array;
- unsigned get_pending;
};
-@@ prio-queue.h: void *prio_queue_peek(struct prio_queue *);
- static inline size_t prio_queue_size(struct prio_queue *queue)
- {
-- return queue->nr - queue->get_pending;
-+ return queue->nr_internal - queue->get_pending;
- }
+@@ prio-queue.h: void *prio_queue_get(struct prio_queue *);
+ */
+ void *prio_queue_peek(struct prio_queue *);
++static inline size_t prio_queue_size(const struct prio_queue *queue)
++{
++ return queue->nr_;
++}
++
+#define prio_queue_for_each(queue, it) \
-+ for (size_t pq_ix_ = (queue)->get_pending; \
-+ pq_ix_ < (queue)->nr_internal && ((it) = (queue)->array[pq_ix_].data, 1); \
++ for (size_t pq_ix_ = 0; \
++ pq_ix_ < (queue)->nr_ && ((it) = (queue)->array[pq_ix_].data, 1); \
+ pq_ix_++)
+
- void clear_prio_queue(struct prio_queue *);
-
- /* Reverse the LIFO elements */
+ /*
+ * Replace the "thing" that compares the smallest with a new "thing",
+ * like prio_queue_get()+prio_queue_put() would do, but in a more
## revision.c ##
@@ revision.c: static struct commit *handle_commit(struct rev_info *revs,
@@ revision.c: static struct commit *handle_commit(struct rev_info *revs,
if (commit->object.flags & UNINTERESTING)
continue;
+@@ revision.c: static int limit_list(struct rev_info *revs)
+ struct commit_list *original_list = revs->commits;
+ struct commit_list *newlist = NULL;
+ struct commit_list **p = &newlist;
+- struct commit *interesting_cache = NULL;
++ struct commit *commit, *interesting_cache = NULL;
+ struct prio_queue queue = { .compare = compare_commits_by_commit_date };
+
+ if (revs->ancestry_path_implicit_bottoms) {
+@@ revision.c: static int limit_list(struct rev_info *revs)
+ prio_queue_put(&queue, commit);
+ }
+
+- while (queue.nr) {
+- struct commit *commit = prio_queue_get(&queue);
++ while ((commit = prio_queue_get(&queue))) {
+ struct object *obj = &commit->object;
+
+ if (commit == interesting_cache)
@@ revision.c: static enum rewrite_result rewrite_one_1(struct rev_info *revs,
static void merge_queue_into_list(struct prio_queue *q, struct commit_list **list)
@@ revision.c: static enum rewrite_result rewrite_one_1(struct rev_info *revs,
struct commit_list *p = *list;
if (p && p->item->date >= item->date)
+
+ ## walker.c ##
+@@ walker.c: static struct prio_queue complete = { compare_commits_by_commit_date };
+ static int process_commit(struct walker *walker, struct commit *commit)
+ {
+ struct commit_list *parents;
++ struct commit *item;
+
+ if (repo_parse_commit(the_repository, commit))
+ return -1;
+
+- while (complete.nr) {
+- struct commit *item = prio_queue_peek(&complete);
++ while ((item = prio_queue_peek(&complete))) {
+ if (item->date < commit->date)
+ break;
+ pop_most_recent_commit(&complete, COMPLETE);
1: e882206d29 ! 2: a3f4cb57f2 prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion
@@ Commit message
Defer the actual removal in prio_queue_get() until the next
operation. If that next operation is a prio_queue_put(), the
- removal and insertion are fused into a single replace, writing
- the new element at the root and sifting it down which avoids
+ removal and insertion are fused into a single replace — writing
+ the new element at the root and sifting it down — which avoids
a full remove-rebalance-insert cycle.
This matches the dominant usage pattern in git's commit traversal:
- get a commit, then put its parents. The first parent insertion
+ get a commit, then put its parents. The first parent insertion
after each get is now a replace operation automatically.
This generalizes the lazy_queue pattern from builtin/describe.c
- (introduced in 08bb69d70f) into prio_queue itself. Three callers
+ (introduced in 08bb69d70f) into prio_queue itself. Three callers
independently implemented the same get+put fusion:
- builtin/describe.c had a full lazy_queue wrapper
@@ Commit message
- builtin/show-branch.c:join_revs() used peek+replace
All three now collapse to plain _get() and _put(), with the data
- structure handling the fusion internally. This simplifies callers
+ structure handling the fusion internally. This simplifies callers
and means every prio_queue user gets the optimization for free
without needing to implement it manually.
Remove prio_queue_replace() since no external callers remain.
- Add prio_queue_size() for callers that need the logical element
- count, since the physical nr may temporarily include a
- pending-removal element.
- Benchmarked on a large monorepo (30 interleaved runs,
+ Benchmarked on a 1.8M-commit monorepo (30 interleaved runs,
paired t-test, Xeon @ 2.20GHz):
Code paths that previously did eager get+put (new optimization):
- Command base patched change p
+ Command base patched change p
merge-base --all A A~1000 3828ms 3725ms -2.69% 0.0001
rev-list --count A~1000..A 3055ms 2986ms -2.27% 0.0601
log --oneline A~1000..A 3408ms 3350ms -1.71% 0.0482
Code paths that already had manual get+put fusion (expect
- neutral - the optimization moves into prio_queue but the number
+ neutral — the optimization moves into prio_queue but the number
of heap operations stays the same):
- Command base patched change p
- show-branch A A~1000 9156ms 9127ms -0.32% 0.3470
- describe (git.git) 1983ms 1963ms -1.02% <0.001
+ Command base patched change p
+ show-branch A A~1000 9156ms 9127ms -0.32% 0.3470
+ describe (4751 revs, 81K repo) 1983ms 1963ms -1.02% <0.001
No regressions in any scenario.
@@ builtin/describe.c: static int compare_pt(const void *a_, const void *b_)
-
-static bool lazy_queue_empty(const struct lazy_queue *queue)
-{
-- return queue->queue.nr == (queue->get_pending ? 1 : 0);
+- return prio_queue_size(&queue->queue) == (queue->get_pending ? 1 : 0);
-}
-
-static void lazy_queue_clear(struct lazy_queue *queue)
@@ builtin/describe.c: static int compare_pt(const void *a_, const void *b_)
{
unsigned long seen_commits = 0;
struct oidset unflagged = OIDSET_INIT;
+- struct commit *commit;
+- int skip = queue->get_pending ? 1 : 0;
+ struct commit *c;
-- for (size_t i = queue->get_pending ? 1 : 0; i < queue->queue.nr; i++) {
-- struct commit *commit = queue->queue.array[i].data;
-+ for (size_t i = queue->get_pending; i < queue->nr; i++) {
-+ struct commit *commit = queue->array[i].data;
- if (!(commit->object.flags & best->flag_within))
- oidset_insert(&unflagged, &commit->object.oid);
+- prio_queue_for_each(&queue->queue, commit) {
+- if (skip) {
+- skip = 0;
+- continue;
+- }
+- if (!(commit->object.flags & best->flag_within))
+- oidset_insert(&unflagged, &commit->object.oid);
++ prio_queue_for_each(queue, c) {
++ if (!(c->object.flags & best->flag_within))
++ oidset_insert(&unflagged, &c->object.oid);
}
- while (!lazy_queue_empty(queue)) {
@@ builtin/describe.c: static void describe_commit(struct commit *cmit, struct strb
if (debug) {
static int label_width = -1;
- ## builtin/last-modified.c ##
-@@ builtin/last-modified.c: static void process_parent(struct last_modified *lm,
- static int last_modified_run(struct last_modified *lm)
- {
- int max_count, queue_popped = 0;
-+ struct commit *c;
- struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
- struct prio_queue not_queue = { compare_commits_by_gen_then_commit_date };
- struct commit_list *list;
-@@ builtin/last-modified.c: static int last_modified_run(struct last_modified *lm)
- }
- }
-
-- while (queue.nr) {
-+ while ((c = prio_queue_get(&queue))) {
- int parent_i;
- struct commit_list *p;
-- struct commit *c = prio_queue_get(&queue);
- struct bitmap *active_c = active_paths_for(lm, c);
-
- if ((0 <= max_count && max_count < ++queue_popped) ||
-
## builtin/show-branch.c ##
-@@ builtin/show-branch.c: static const char *get_color_reset_code(void)
-
- static struct commit *interesting(struct prio_queue *queue)
- {
-- for (size_t i = 0; i < queue->nr; i++) {
-+ for (size_t i = queue->get_pending; i < queue->nr; i++) {
- struct commit *commit = queue->array[i].data;
- if (commit->object.flags & UNINTERESTING)
- continue;
@@ builtin/show-branch.c: static void join_revs(struct prio_queue *queue,
- {
- int all_mask = ((1u << (REV_SHIFT + num_rev)) - 1);
- int all_revs = all_mask & ~((1u << REV_SHIFT) - 1);
-+ struct commit *commit;
-
-- while (queue->nr) {
-+ while ((commit = prio_queue_peek(queue))) {
+ while ((commit = prio_queue_peek(queue))) {
struct commit_list *parents;
int still_interesting = !!interesting(queue);
-- struct commit *commit = prio_queue_peek(queue);
- bool get_pending = true;
int flags = commit->object.flags & all_mask;
@@ builtin/show-branch.c: static void join_revs(struct prio_queue *queue,
/*
- ## commit-reach.c ##
-@@ commit-reach.c: int get_branch_base_for_tip(struct repository *r,
- size_t bases_nr)
- {
- int best_index = -1;
-- struct commit *branch_point = NULL;
-+ struct commit *c, *branch_point = NULL;
- struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
- int found_missing_gen = 0;
-
-@@ commit-reach.c: int get_branch_base_for_tip(struct repository *r,
- prio_queue_put(&queue, c);
- }
-
-- while (queue.nr) {
-- struct commit *c = prio_queue_get(&queue);
-+ while ((c = prio_queue_get(&queue))) {
- int best_for_c = get_best(c);
- int best_for_p, positive;
- struct commit *parent;
-
## commit.c ##
@@ commit.c: void commit_list_sort_by_date(struct commit_list **list)
struct commit *pop_most_recent_commit(struct prio_queue *queue,
@@ commit.c: void commit_list_sort_by_date(struct commit_list **list)
}
- ## pack-bitmap-write.c ##
-@@ pack-bitmap-write.c: static int fill_bitmap_commit(struct bitmap_writer *writer,
- struct bitmap_index *old_bitmap,
- const uint32_t *mapping)
- {
-+ struct commit *c;
- int found;
- uint32_t pos;
- if (!ent->bitmap)
-@@ pack-bitmap-write.c: static int fill_bitmap_commit(struct bitmap_writer *writer,
-
- prio_queue_put(queue, commit);
-
-- while (queue->nr) {
-+ while ((c = prio_queue_get(queue))) {
- struct commit_list *p;
-- struct commit *c = prio_queue_get(queue);
-
- if (old_bitmap && mapping) {
- struct ewah_bitmap *old;
-
## prio-queue.c ##
@@ prio-queue.c: void clear_prio_queue(struct prio_queue *queue)
- queue->nr = 0;
+ queue->nr_ = 0;
queue->alloc = 0;
queue->insertion_ctr = 0;
+ queue->get_pending = 0;
@@ prio-queue.c: void clear_prio_queue(struct prio_queue *queue)
+{
+ size_t ix, child;
+
-+ for (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {
-+ child = ix * 2 + 1;
-+ if (child + 1 < queue->nr &&
++ /* Push down the one at the root */
++ for (ix = 0; ix * 2 + 1 < queue->nr_; ix = child) {
++ child = ix * 2 + 1; /* left */
++ if (child + 1 < queue->nr_ &&
+ compare(queue, child, child + 1) >= 0)
-+ child++;
++ child++; /* use right child */
++
+ if (compare(queue, ix, child) <= 0)
+ break;
++
+ swap(queue, child, ix);
+ }
++}
++
++static inline void flush_get(struct prio_queue *queue)
++{
++ if (!queue->get_pending)
++ return;
++ queue->get_pending = 0;
++ queue->array[0] = queue->array[--queue->nr_];
++ sift_down_root(queue);
}
void prio_queue_put(struct prio_queue *queue, void *thing)
{
size_t ix, parent;
-- /* Append at the end */
+ if (queue->get_pending) {
+ queue->get_pending = 0;
+ queue->array[0].ctr = queue->insertion_ctr++;
@@ prio-queue.c: void clear_prio_queue(struct prio_queue *queue)
+ return;
+ }
+
- ALLOC_GROW(queue->array, queue->nr + 1, queue->alloc);
- queue->array[queue->nr].ctr = queue->insertion_ctr++;
- queue->array[queue->nr].data = thing;
- queue->nr++;
- if (!queue->compare)
-- return; /* LIFO */
-+ return;
-
-- /* Bubble up the new one */
- for (ix = queue->nr - 1; ix; ix = parent) {
- parent = (ix - 1) / 2;
- if (compare(queue, parent, ix) <= 0)
- break;
--
- swap(queue, parent, ix);
+ /* Append at the end */
+ ALLOC_GROW(queue->array, queue->nr_ + 1, queue->alloc);
+ queue->array[queue->nr_].ctr = queue->insertion_ctr++;
+@@ prio-queue.c: void prio_queue_put(struct prio_queue *queue, void *thing)
}
}
@@ prio-queue.c: void clear_prio_queue(struct prio_queue *queue)
- size_t ix, child;
-
- /* Push down the one at the root */
-- for (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {
+- for (ix = 0; ix * 2 + 1 < queue->nr_; ix = child) {
- child = ix * 2 + 1; /* left */
-- if (child + 1 < queue->nr &&
+- if (child + 1 < queue->nr_ &&
- compare(queue, child, child + 1) >= 0)
- child++; /* use right child */
-
@@ prio-queue.c: void clear_prio_queue(struct prio_queue *queue)
{
- void *result;
-
- if (!queue->nr)
+- if (!queue->nr_)
++ if (queue->nr_ <= queue->get_pending) {
++ queue->nr_ = 0;
++ queue->get_pending = 0;
return NULL;
++ }
if (!queue->compare)
-- return queue->array[--queue->nr].data; /* LIFO */
--
+ return queue->array[--queue->nr_].data; /* LIFO */
+
- result = queue->array[0].data;
-- if (!--queue->nr)
+- if (!--queue->nr_)
- return result;
-+ return queue->array[--queue->nr].data;
-+
-+ if (queue->get_pending) {
-+ if (!--queue->nr) {
-+ queue->get_pending = 0;
-+ return NULL;
-+ }
-+ queue->array[0] = queue->array[queue->nr];
-+ sift_down_root(queue);
-+ }
++ flush_get(queue);
-- queue->array[0] = queue->array[queue->nr];
+- queue->array[0] = queue->array[queue->nr_];
- sift_down_root(queue);
- return result;
+ queue->get_pending = 1;
@@ prio-queue.c: void clear_prio_queue(struct prio_queue *queue)
}
void *prio_queue_peek(struct prio_queue *queue)
-@@ prio-queue.c: void *prio_queue_peek(struct prio_queue *queue)
+ {
+- if (!queue->nr_)
++ if (queue->nr_ <= queue->get_pending) {
++ queue->nr_ = 0;
++ queue->get_pending = 0;
return NULL;
++ }
if (!queue->compare)
- return queue->array[queue->nr - 1].data;
+ return queue->array[queue->nr_ - 1].data;
- return queue->array[0].data;
-}
-void prio_queue_replace(struct prio_queue *queue, void *thing)
-{
-- if (!queue->nr) {
+- if (!queue->nr_) {
- prio_queue_put(queue, thing);
- } else if (!queue->compare) {
-- queue->array[queue->nr - 1].ctr = queue->insertion_ctr++;
-- queue->array[queue->nr - 1].data = thing;
+- queue->array[queue->nr_ - 1].ctr = queue->insertion_ctr++;
+- queue->array[queue->nr_ - 1].data = thing;
- } else {
- queue->array[0].ctr = queue->insertion_ctr++;
- queue->array[0].data = thing;
-+ if (queue->get_pending) {
-+ queue->get_pending = 0;
-+ if (!--queue->nr)
-+ return NULL;
-+ queue->array[0] = queue->array[queue->nr];
- sift_down_root(queue);
- }
+- sift_down_root(queue);
+- }
++ flush_get(queue);
+
+ return queue->array[0].data;
}
## prio-queue.h ##
@@ prio-queue.h: struct prio_queue {
+ prio_queue_compare_fn compare;
+ size_t insertion_ctr;
void *cb_data;
- size_t alloc, nr;
+- size_t alloc, nr_;
++ size_t alloc, nr_; /* use prio_queue_size() for logical count */
struct prio_queue_entry *array;
+ unsigned get_pending;
};
/*
-@@ prio-queue.h: void *prio_queue_get(struct prio_queue *);
- */
- void *prio_queue_peek(struct prio_queue *);
+@@ prio-queue.h: void *prio_queue_peek(struct prio_queue *);
+
+ static inline size_t prio_queue_size(const struct prio_queue *queue)
+ {
+- return queue->nr_;
++ return queue->nr_ - queue->get_pending;
+ }
+
+ #define prio_queue_for_each(queue, it) \
+- for (size_t pq_ix_ = 0; \
++ for (size_t pq_ix_ = (queue)->get_pending; \
+ pq_ix_ < (queue)->nr_ && ((it) = (queue)->array[pq_ix_].data, 1); \
+ pq_ix_++)
-/*
- * Replace the "thing" that compares the smallest with a new "thing",
@@ prio-queue.h: void *prio_queue_get(struct prio_queue *);
- * empty.
- */
-void prio_queue_replace(struct prio_queue *queue, void *thing);
-+static inline size_t prio_queue_size(struct prio_queue *queue)
-+{
-+ return queue->nr - queue->get_pending;
-+}
-
+-
void clear_prio_queue(struct prio_queue *);
-
- ## revision.c ##
-@@ revision.c: static int limit_list(struct rev_info *revs)
- struct commit_list *original_list = revs->commits;
- struct commit_list *newlist = NULL;
- struct commit_list **p = &newlist;
-- struct commit *interesting_cache = NULL;
-+ struct commit *commit, *interesting_cache = NULL;
- struct prio_queue queue = { .compare = compare_commits_by_commit_date };
-
- if (revs->ancestry_path_implicit_bottoms) {
-@@ revision.c: static int limit_list(struct rev_info *revs)
- prio_queue_put(&queue, commit);
- }
-
-- while (queue.nr) {
-- struct commit *commit = prio_queue_get(&queue);
-+ while ((commit = prio_queue_get(&queue))) {
- struct object *obj = &commit->object;
-
- if (commit == interesting_cache)
+ /* Reverse the LIFO elements */
## t/unit-tests/u-prio-queue.c ##
@@ t/unit-tests/u-prio-queue.c: static void test_prio_queue(int *input, size_t input_size,
@@ t/unit-tests/u-prio-queue.c: static void test_prio_queue(int *input, size_t inpu
break;
default:
prio_queue_put(&pq, &input[i]);
-
- ## walker.c ##
-@@ walker.c: static struct prio_queue complete = { compare_commits_by_commit_date };
- static int process_commit(struct walker *walker, struct commit *commit)
- {
- struct commit_list *parents;
-+ struct commit *item;
-
- if (repo_parse_commit(the_repository, commit))
- return -1;
-
-- while (complete.nr) {
-- struct commit *item = prio_queue_peek(&complete);
-+ while ((item = prio_queue_peek(&complete))) {
- if (item->date < commit->date)
- break;
- pop_most_recent_commit(&complete, COMPLETE);
--
gitgitgadget
^ permalink raw reply [flat|nested] 16+ messages in thread* [PATCH v4 1/2] prio-queue: rename .nr to .nr_ and add accessor helpers
2026-06-08 19:10 ` [PATCH v4 " Kristofer Karlsson via GitGitGadget
@ 2026-06-08 19:10 ` Kristofer Karlsson via GitGitGadget
2026-06-08 19:10 ` [PATCH v4 2/2] prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion Kristofer Karlsson via GitGitGadget
1 sibling, 0 replies; 16+ messages in thread
From: Kristofer Karlsson via GitGitGadget @ 2026-06-08 19:10 UTC (permalink / raw)
To: git
Cc: René Scharfe, Kristofer Karlsson, Kristofer Karlsson,
Kristofer Karlsson
From: Kristofer Karlsson <krka@spotify.com>
Rename the .nr member to .nr_ so that callers outside prio-queue.c
that directly reference .nr get a compilation error. This catches
both existing misuse and future in-flight topics.
Add prio_queue_size() for callers that need to know the element count
and prio_queue_for_each() for callers that need to walk all elements.
Convert all external .nr users:
- Loop conditions: use prio_queue_size(), prio_queue_get(), or
prio_queue_peek() as the loop condition
- Array iterations: use prio_queue_for_each()
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
builtin/describe.c | 11 ++++++++---
builtin/last-modified.c | 7 +++----
builtin/show-branch.c | 13 ++++++-------
commit-reach.c | 14 +++++++-------
fetch-pack.c | 4 ++--
negotiator/default.c | 4 +++-
negotiator/skipping.c | 12 +++++++-----
object-name.c | 2 +-
pack-bitmap-write.c | 10 +++++-----
path-walk.c | 8 ++++----
prio-queue.c | 38 +++++++++++++++++++-------------------
prio-queue.h | 12 +++++++++++-
revision.c | 16 +++++++---------
walker.c | 4 ++--
14 files changed, 85 insertions(+), 70 deletions(-)
diff --git a/builtin/describe.c b/builtin/describe.c
index 1c47d7c0b7..8e88bdeea6 100644
--- a/builtin/describe.c
+++ b/builtin/describe.c
@@ -278,7 +278,7 @@ static void lazy_queue_put(struct lazy_queue *queue, void *thing)
static bool lazy_queue_empty(const struct lazy_queue *queue)
{
- return queue->queue.nr == (queue->get_pending ? 1 : 0);
+ return prio_queue_size(&queue->queue) == (queue->get_pending ? 1 : 0);
}
static void lazy_queue_clear(struct lazy_queue *queue)
@@ -292,9 +292,14 @@ static unsigned long finish_depth_computation(struct lazy_queue *queue,
{
unsigned long seen_commits = 0;
struct oidset unflagged = OIDSET_INIT;
+ struct commit *commit;
+ int skip = queue->get_pending ? 1 : 0;
- for (size_t i = queue->get_pending ? 1 : 0; i < queue->queue.nr; i++) {
- struct commit *commit = queue->queue.array[i].data;
+ prio_queue_for_each(&queue->queue, commit) {
+ if (skip) {
+ skip = 0;
+ continue;
+ }
if (!(commit->object.flags & best->flag_within))
oidset_insert(&unflagged, &commit->object.oid);
}
diff --git a/builtin/last-modified.c b/builtin/last-modified.c
index 8900ceece1..5478182f2e 100644
--- a/builtin/last-modified.c
+++ b/builtin/last-modified.c
@@ -344,6 +344,7 @@ static void process_parent(struct last_modified *lm,
static int last_modified_run(struct last_modified *lm)
{
int max_count, queue_popped = 0;
+ struct commit *c, *n;
struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
struct prio_queue not_queue = { compare_commits_by_gen_then_commit_date };
struct commit_list *list;
@@ -389,10 +390,9 @@ static int last_modified_run(struct last_modified *lm)
}
}
- while (queue.nr) {
+ while ((c = prio_queue_get(&queue))) {
int parent_i;
struct commit_list *p;
- struct commit *c = prio_queue_get(&queue);
struct bitmap *active_c = active_paths_for(lm, c);
if ((0 <= max_count && max_count < ++queue_popped) ||
@@ -416,9 +416,8 @@ static int last_modified_run(struct last_modified *lm)
*/
repo_parse_commit(lm->rev.repo, c);
- while (not_queue.nr) {
+ while ((n = prio_queue_get(¬_queue))) {
struct commit_list *np;
- struct commit *n = prio_queue_get(¬_queue);
repo_parse_commit(lm->rev.repo, n);
diff --git a/builtin/show-branch.c b/builtin/show-branch.c
index f02831b085..8846f2376f 100644
--- a/builtin/show-branch.c
+++ b/builtin/show-branch.c
@@ -62,11 +62,10 @@ static const char *get_color_reset_code(void)
static struct commit *interesting(struct prio_queue *queue)
{
- for (size_t i = 0; i < queue->nr; i++) {
- struct commit *commit = queue->array[i].data;
- if (commit->object.flags & UNINTERESTING)
- continue;
- return commit;
+ struct commit *commit;
+ prio_queue_for_each(queue, commit) {
+ if (!(commit->object.flags & UNINTERESTING))
+ return commit;
}
return NULL;
}
@@ -228,11 +227,11 @@ static void join_revs(struct prio_queue *queue,
{
int all_mask = ((1u << (REV_SHIFT + num_rev)) - 1);
int all_revs = all_mask & ~((1u << REV_SHIFT) - 1);
+ struct commit *commit;
- while (queue->nr) {
+ while ((commit = prio_queue_peek(queue))) {
struct commit_list *parents;
int still_interesting = !!interesting(queue);
- struct commit *commit = prio_queue_peek(queue);
bool get_pending = true;
int flags = commit->object.flags & all_mask;
diff --git a/commit-reach.c b/commit-reach.c
index 9b3ea46d6f..a849de653e 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -41,8 +41,8 @@ static int compare_commits_by_gen(const void *_a, const void *_b)
static int queue_has_nonstale(struct prio_queue *queue)
{
- for (size_t i = 0; i < queue->nr; i++) {
- struct commit *commit = queue->array[i].data;
+ struct commit *commit;
+ prio_queue_for_each(queue, commit) {
if (!(commit->object.flags & STALE))
return 1;
}
@@ -1070,6 +1070,7 @@ void ahead_behind(struct repository *r,
struct ahead_behind_count *counts, size_t counts_nr)
{
struct prio_queue queue = { .compare = compare_commits_by_gen_then_commit_date };
+ void *entry;
size_t width = DIV_ROUND_UP(commits_nr, BITS_IN_EWORD);
if (!commits_nr || !counts_nr)
@@ -1135,8 +1136,8 @@ void ahead_behind(struct repository *r,
/* STALE is used here, PARENT2 is used by insert_no_dup(). */
repo_clear_commit_marks(r, PARENT2 | STALE);
- for (size_t i = 0; i < queue.nr; i++)
- free_bit_array(queue.array[i].data);
+ prio_queue_for_each(&queue, entry)
+ free_bit_array(entry);
clear_bit_arrays(&bit_arrays);
clear_prio_queue(&queue);
}
@@ -1269,7 +1270,7 @@ int get_branch_base_for_tip(struct repository *r,
size_t bases_nr)
{
int best_index = -1;
- struct commit *branch_point = NULL;
+ struct commit *c, *branch_point = NULL;
struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
int found_missing_gen = 0;
@@ -1322,8 +1323,7 @@ int get_branch_base_for_tip(struct repository *r,
prio_queue_put(&queue, c);
}
- while (queue.nr) {
- struct commit *c = prio_queue_get(&queue);
+ while ((c = prio_queue_get(&queue))) {
int best_for_c = get_best(c);
int best_for_p, positive;
struct commit *parent;
diff --git a/fetch-pack.c b/fetch-pack.c
index 120e01f3cf..29c41132ee 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -662,8 +662,8 @@ static int mark_complete_oid(const struct reference *ref, void *cb_data UNUSED)
static void mark_recent_complete_commits(struct fetch_pack_args *args,
timestamp_t cutoff)
{
- while (complete.nr) {
- struct commit *item = prio_queue_peek(&complete);
+ struct commit *item;
+ while ((item = prio_queue_peek(&complete))) {
if (item->date < cutoff)
break;
print_verbose(args, _("Marking %s as complete"),
diff --git a/negotiator/default.c b/negotiator/default.c
index 78d58d57ce..19cdf3808c 100644
--- a/negotiator/default.c
+++ b/negotiator/default.c
@@ -113,10 +113,12 @@ static const struct object_id *get_rev(struct negotiation_state *ns)
unsigned int mark;
struct commit_list *parents;
- if (ns->rev_list.nr == 0 || ns->non_common_revs == 0)
+ if (ns->non_common_revs == 0)
return NULL;
commit = prio_queue_get(&ns->rev_list);
+ if (!commit)
+ return NULL;
repo_parse_commit(the_repository, commit);
parents = commit->parents;
diff --git a/negotiator/skipping.c b/negotiator/skipping.c
index 68c9b3b997..db90fa77b5 100644
--- a/negotiator/skipping.c
+++ b/negotiator/skipping.c
@@ -143,8 +143,7 @@ static int push_parent(struct data *data, struct entry *entry,
/*
* Find the existing entry and use it.
*/
- for (size_t i = 0; i < data->rev_list.nr; i++) {
- parent_entry = data->rev_list.array[i].data;
+ prio_queue_for_each(&data->rev_list, parent_entry) {
if (parent_entry->commit == to_push)
goto parent_found;
}
@@ -181,10 +180,12 @@ static const struct object_id *get_rev(struct data *data)
struct commit_list *p;
int parent_pushed = 0;
- if (data->rev_list.nr == 0 || data->non_common_revs == 0)
+ if (data->non_common_revs == 0)
return NULL;
entry = prio_queue_get(&data->rev_list);
+ if (!entry)
+ return NULL;
commit = entry->commit;
commit->object.flags |= POPPED;
if (!(commit->object.flags & COMMON))
@@ -253,8 +254,9 @@ static void have_sent(struct fetch_negotiator *n, struct commit *c)
static void release(struct fetch_negotiator *n)
{
struct data *data = n->data;
- for (size_t i = 0; i < data->rev_list.nr; i++)
- free(data->rev_list.array[i].data);
+ void *entry;
+ prio_queue_for_each(&data->rev_list, entry)
+ free(entry);
clear_prio_queue(&data->rev_list);
FREE_AND_NULL(data);
}
diff --git a/object-name.c b/object-name.c
index 9ac86f19c7..2fedfe1761 100644
--- a/object-name.c
+++ b/object-name.c
@@ -1208,7 +1208,7 @@ static int get_oid_oneline(struct repository *r,
l->item->object.flags |= ONELINE_SEEN;
prio_queue_put(©, l->item);
}
- while (copy.nr) {
+ while (prio_queue_size(©)) {
const char *p, *buf;
struct commit *commit;
int matches;
diff --git a/pack-bitmap-write.c b/pack-bitmap-write.c
index 1c8070f99c..ed9714b135 100644
--- a/pack-bitmap-write.c
+++ b/pack-bitmap-write.c
@@ -513,6 +513,8 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,
struct bitmap_index *old_bitmap,
const uint32_t *mapping)
{
+ struct commit *c;
+ struct tree *tree;
int found;
uint32_t pos;
if (!ent->bitmap)
@@ -520,9 +522,8 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,
prio_queue_put(queue, commit);
- while (queue->nr) {
+ while ((c = prio_queue_get(queue))) {
struct commit_list *p;
- struct commit *c = prio_queue_get(queue);
if (old_bitmap && mapping) {
struct ewah_bitmap *old;
@@ -574,9 +575,8 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,
}
}
- while (tree_queue->nr) {
- if (fill_bitmap_tree(writer, ent->bitmap,
- prio_queue_get(tree_queue)) < 0)
+ while ((tree = prio_queue_get(tree_queue))) {
+ if (fill_bitmap_tree(writer, ent->bitmap, tree) < 0)
return -1;
}
return 0;
diff --git a/path-walk.c b/path-walk.c
index 94ff90bd15..cf3b2d0765 100644
--- a/path-walk.c
+++ b/path-walk.c
@@ -699,6 +699,7 @@ int walk_objects_by_path(struct path_walk_info *info)
int ret;
size_t commits_nr = 0, paths_nr = 0;
struct commit *c;
+ char *path;
struct type_and_oid_list *root_tree_list;
struct type_and_oid_list *commit_list;
struct path_walk_context ctx = {
@@ -808,8 +809,7 @@ int walk_objects_by_path(struct path_walk_info *info)
free(commit_list);
trace2_region_enter("path-walk", "path-walk", info->revs->repo);
- while (!ret && ctx.path_stack.nr) {
- char *path = prio_queue_get(&ctx.path_stack);
+ while (!ret && (path = prio_queue_get(&ctx.path_stack))) {
paths_nr++;
ret = walk_path(&ctx, path);
@@ -821,12 +821,12 @@ int walk_objects_by_path(struct path_walk_info *info)
if (!strmap_empty(&ctx.paths_to_lists)) {
struct hashmap_iter iter;
struct strmap_entry *entry;
+ char *path;
strmap_for_each_entry(&ctx.paths_to_lists, &iter, entry)
push_to_stack(&ctx, entry->key);
- while (!ret && ctx.path_stack.nr) {
- char *path = prio_queue_get(&ctx.path_stack);
+ while (!ret && (path = prio_queue_get(&ctx.path_stack))) {
paths_nr++;
ret = walk_path(&ctx, path);
diff --git a/prio-queue.c b/prio-queue.c
index 9748528ce6..ead4faf4bb 100644
--- a/prio-queue.c
+++ b/prio-queue.c
@@ -22,16 +22,16 @@ void prio_queue_reverse(struct prio_queue *queue)
if (queue->compare)
BUG("prio_queue_reverse() on non-LIFO queue");
- if (!queue->nr)
+ if (!queue->nr_)
return;
- for (i = 0; i < (j = (queue->nr - 1) - i); i++)
+ for (i = 0; i < (j = (queue->nr_ - 1) - i); i++)
swap(queue, i, j);
}
void clear_prio_queue(struct prio_queue *queue)
{
FREE_AND_NULL(queue->array);
- queue->nr = 0;
+ queue->nr_ = 0;
queue->alloc = 0;
queue->insertion_ctr = 0;
}
@@ -41,15 +41,15 @@ void prio_queue_put(struct prio_queue *queue, void *thing)
size_t ix, parent;
/* Append at the end */
- ALLOC_GROW(queue->array, queue->nr + 1, queue->alloc);
- queue->array[queue->nr].ctr = queue->insertion_ctr++;
- queue->array[queue->nr].data = thing;
- queue->nr++;
+ ALLOC_GROW(queue->array, queue->nr_ + 1, queue->alloc);
+ queue->array[queue->nr_].ctr = queue->insertion_ctr++;
+ queue->array[queue->nr_].data = thing;
+ queue->nr_++;
if (!queue->compare)
return; /* LIFO */
/* Bubble up the new one */
- for (ix = queue->nr - 1; ix; ix = parent) {
+ for (ix = queue->nr_ - 1; ix; ix = parent) {
parent = (ix - 1) / 2;
if (compare(queue, parent, ix) <= 0)
break;
@@ -63,9 +63,9 @@ static void sift_down_root(struct prio_queue *queue)
size_t ix, child;
/* Push down the one at the root */
- for (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {
+ for (ix = 0; ix * 2 + 1 < queue->nr_; ix = child) {
child = ix * 2 + 1; /* left */
- if (child + 1 < queue->nr &&
+ if (child + 1 < queue->nr_ &&
compare(queue, child, child + 1) >= 0)
child++; /* use right child */
@@ -80,36 +80,36 @@ void *prio_queue_get(struct prio_queue *queue)
{
void *result;
- if (!queue->nr)
+ if (!queue->nr_)
return NULL;
if (!queue->compare)
- return queue->array[--queue->nr].data; /* LIFO */
+ return queue->array[--queue->nr_].data; /* LIFO */
result = queue->array[0].data;
- if (!--queue->nr)
+ if (!--queue->nr_)
return result;
- queue->array[0] = queue->array[queue->nr];
+ queue->array[0] = queue->array[queue->nr_];
sift_down_root(queue);
return result;
}
void *prio_queue_peek(struct prio_queue *queue)
{
- if (!queue->nr)
+ if (!queue->nr_)
return NULL;
if (!queue->compare)
- return queue->array[queue->nr - 1].data;
+ return queue->array[queue->nr_ - 1].data;
return queue->array[0].data;
}
void prio_queue_replace(struct prio_queue *queue, void *thing)
{
- if (!queue->nr) {
+ if (!queue->nr_) {
prio_queue_put(queue, thing);
} else if (!queue->compare) {
- queue->array[queue->nr - 1].ctr = queue->insertion_ctr++;
- queue->array[queue->nr - 1].data = thing;
+ queue->array[queue->nr_ - 1].ctr = queue->insertion_ctr++;
+ queue->array[queue->nr_ - 1].data = thing;
} else {
queue->array[0].ctr = queue->insertion_ctr++;
queue->array[0].data = thing;
diff --git a/prio-queue.h b/prio-queue.h
index da7fad2f1f..7f2aa986b1 100644
--- a/prio-queue.h
+++ b/prio-queue.h
@@ -30,7 +30,7 @@ struct prio_queue {
prio_queue_compare_fn compare;
size_t insertion_ctr;
void *cb_data;
- size_t alloc, nr;
+ size_t alloc, nr_;
struct prio_queue_entry *array;
};
@@ -52,6 +52,16 @@ void *prio_queue_get(struct prio_queue *);
*/
void *prio_queue_peek(struct prio_queue *);
+static inline size_t prio_queue_size(const struct prio_queue *queue)
+{
+ return queue->nr_;
+}
+
+#define prio_queue_for_each(queue, it) \
+ for (size_t pq_ix_ = 0; \
+ pq_ix_ < (queue)->nr_ && ((it) = (queue)->array[pq_ix_].data, 1); \
+ pq_ix_++)
+
/*
* Replace the "thing" that compares the smallest with a new "thing",
* like prio_queue_get()+prio_queue_put() would do, but in a more
diff --git a/revision.c b/revision.c
index 5693618be4..34e2d146f4 100644
--- a/revision.c
+++ b/revision.c
@@ -476,16 +476,15 @@ static struct commit *handle_commit(struct rev_info *revs,
static int everybody_uninteresting(struct prio_queue *orig,
struct commit **interesting_cache)
{
- size_t i;
+ struct commit *commit;
if (*interesting_cache) {
- struct commit *commit = *interesting_cache;
+ commit = *interesting_cache;
if (!(commit->object.flags & UNINTERESTING))
return 0;
}
- for (i = 0; i < orig->nr; i++) {
- struct commit *commit = orig->array[i].data;
+ prio_queue_for_each(orig, commit) {
if (commit->object.flags & UNINTERESTING)
continue;
@@ -1446,7 +1445,7 @@ static int limit_list(struct rev_info *revs)
struct commit_list *original_list = revs->commits;
struct commit_list *newlist = NULL;
struct commit_list **p = &newlist;
- struct commit *interesting_cache = NULL;
+ struct commit *commit, *interesting_cache = NULL;
struct prio_queue queue = { .compare = compare_commits_by_commit_date };
if (revs->ancestry_path_implicit_bottoms) {
@@ -1461,8 +1460,7 @@ static int limit_list(struct rev_info *revs)
prio_queue_put(&queue, commit);
}
- while (queue.nr) {
- struct commit *commit = prio_queue_get(&queue);
+ while ((commit = prio_queue_get(&queue))) {
struct object *obj = &commit->object;
if (commit == interesting_cache)
@@ -4028,8 +4026,8 @@ static enum rewrite_result rewrite_one_1(struct rev_info *revs,
static void merge_queue_into_list(struct prio_queue *q, struct commit_list **list)
{
- while (q->nr) {
- struct commit *item = prio_queue_peek(q);
+ struct commit *item;
+ while ((item = prio_queue_peek(q))) {
struct commit_list *p = *list;
if (p && p->item->date >= item->date)
diff --git a/walker.c b/walker.c
index e98eb6da53..e3de77f092 100644
--- a/walker.c
+++ b/walker.c
@@ -84,12 +84,12 @@ static struct prio_queue complete = { compare_commits_by_commit_date };
static int process_commit(struct walker *walker, struct commit *commit)
{
struct commit_list *parents;
+ struct commit *item;
if (repo_parse_commit(the_repository, commit))
return -1;
- while (complete.nr) {
- struct commit *item = prio_queue_peek(&complete);
+ while ((item = prio_queue_peek(&complete))) {
if (item->date < commit->date)
break;
pop_most_recent_commit(&complete, COMPLETE);
--
gitgitgadget
^ permalink raw reply related [flat|nested] 16+ messages in thread* [PATCH v4 2/2] prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion
2026-06-08 19:10 ` [PATCH v4 " Kristofer Karlsson via GitGitGadget
2026-06-08 19:10 ` [PATCH v4 1/2] prio-queue: rename .nr to .nr_ and add accessor helpers Kristofer Karlsson via GitGitGadget
@ 2026-06-08 19:10 ` Kristofer Karlsson via GitGitGadget
1 sibling, 0 replies; 16+ messages in thread
From: Kristofer Karlsson via GitGitGadget @ 2026-06-08 19:10 UTC (permalink / raw)
To: git
Cc: René Scharfe, Kristofer Karlsson, Kristofer Karlsson,
Kristofer Karlsson
From: Kristofer Karlsson <krka@spotify.com>
Defer the actual removal in prio_queue_get() until the next
operation. If that next operation is a prio_queue_put(), the
removal and insertion are fused into a single replace — writing
the new element at the root and sifting it down — which avoids
a full remove-rebalance-insert cycle.
This matches the dominant usage pattern in git's commit traversal:
get a commit, then put its parents. The first parent insertion
after each get is now a replace operation automatically.
This generalizes the lazy_queue pattern from builtin/describe.c
(introduced in 08bb69d70f) into prio_queue itself. Three callers
independently implemented the same get+put fusion:
- builtin/describe.c had a full lazy_queue wrapper
- commit.c:pop_most_recent_commit() used peek+replace
- builtin/show-branch.c:join_revs() used peek+replace
All three now collapse to plain _get() and _put(), with the data
structure handling the fusion internally. This simplifies callers
and means every prio_queue user gets the optimization for free
without needing to implement it manually.
Remove prio_queue_replace() since no external callers remain.
Benchmarked on a 1.8M-commit monorepo (30 interleaved runs,
paired t-test, Xeon @ 2.20GHz):
Code paths that previously did eager get+put (new optimization):
Command base patched change p
merge-base --all A A~1000 3828ms 3725ms -2.69% 0.0001
rev-list --count A~1000..A 3055ms 2986ms -2.27% 0.0601
log --oneline A~1000..A 3408ms 3350ms -1.71% 0.0482
Code paths that already had manual get+put fusion (expect
neutral — the optimization moves into prio_queue but the number
of heap operations stays the same):
Command base patched change p
show-branch A A~1000 9156ms 9127ms -0.32% 0.3470
describe (4751 revs, 81K repo) 1983ms 1963ms -1.02% <0.001
No regressions in any scenario.
Suggested-by: René Scharfe <l.s.r@web.de>
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
builtin/describe.c | 75 +++++++-----------------------
builtin/show-branch.c | 11 ++---
commit.c | 11 +----
prio-queue.c | 92 ++++++++++++++++++++-----------------
prio-queue.h | 15 ++----
t/unit-tests/u-prio-queue.c | 6 +--
6 files changed, 78 insertions(+), 132 deletions(-)
diff --git a/builtin/describe.c b/builtin/describe.c
index 8e88bdeea6..64424543ef 100644
--- a/builtin/describe.c
+++ b/builtin/describe.c
@@ -251,61 +251,19 @@ static int compare_pt(const void *a_, const void *b_)
return 0;
}
-struct lazy_queue {
- struct prio_queue queue;
- bool get_pending;
-};
-
-#define LAZY_QUEUE_INIT { { compare_commits_by_commit_date }, false }
-
-static void *lazy_queue_get(struct lazy_queue *queue)
-{
- if (queue->get_pending)
- prio_queue_get(&queue->queue);
- else
- queue->get_pending = true;
- return prio_queue_peek(&queue->queue);
-}
-
-static void lazy_queue_put(struct lazy_queue *queue, void *thing)
-{
- if (queue->get_pending)
- prio_queue_replace(&queue->queue, thing);
- else
- prio_queue_put(&queue->queue, thing);
- queue->get_pending = false;
-}
-
-static bool lazy_queue_empty(const struct lazy_queue *queue)
-{
- return prio_queue_size(&queue->queue) == (queue->get_pending ? 1 : 0);
-}
-
-static void lazy_queue_clear(struct lazy_queue *queue)
-{
- clear_prio_queue(&queue->queue);
- queue->get_pending = false;
-}
-
-static unsigned long finish_depth_computation(struct lazy_queue *queue,
+static unsigned long finish_depth_computation(struct prio_queue *queue,
struct possible_tag *best)
{
unsigned long seen_commits = 0;
struct oidset unflagged = OIDSET_INIT;
- struct commit *commit;
- int skip = queue->get_pending ? 1 : 0;
+ struct commit *c;
- prio_queue_for_each(&queue->queue, commit) {
- if (skip) {
- skip = 0;
- continue;
- }
- if (!(commit->object.flags & best->flag_within))
- oidset_insert(&unflagged, &commit->object.oid);
+ prio_queue_for_each(queue, c) {
+ if (!(c->object.flags & best->flag_within))
+ oidset_insert(&unflagged, &c->object.oid);
}
- while (!lazy_queue_empty(queue)) {
- struct commit *c = lazy_queue_get(queue);
+ while ((c = prio_queue_get(queue))) {
struct commit_list *parents = c->parents;
seen_commits++;
if (c->object.flags & best->flag_within) {
@@ -321,7 +279,7 @@ static unsigned long finish_depth_computation(struct lazy_queue *queue,
repo_parse_commit(the_repository, p);
seen = p->object.flags & SEEN;
if (!seen)
- lazy_queue_put(queue, p);
+ prio_queue_put(queue, p);
flag_before = p->object.flags & best->flag_within;
p->object.flags |= c->object.flags;
flag_after = p->object.flags & best->flag_within;
@@ -369,8 +327,8 @@ static void append_suffix(int depth, const struct object_id *oid, struct strbuf
static void describe_commit(struct commit *cmit, struct strbuf *dst)
{
- struct commit *gave_up_on = NULL;
- struct lazy_queue queue = LAZY_QUEUE_INIT;
+ struct commit *c, *gave_up_on = NULL;
+ struct prio_queue queue = { compare_commits_by_commit_date };
struct commit_name *n;
struct possible_tag all_matches[MAX_TAGS];
unsigned int match_cnt = 0, annotated_cnt = 0, cur_match;
@@ -412,9 +370,8 @@ static void describe_commit(struct commit *cmit, struct strbuf *dst)
}
cmit->object.flags = SEEN;
- lazy_queue_put(&queue, cmit);
- while (!lazy_queue_empty(&queue)) {
- struct commit *c = lazy_queue_get(&queue);
+ prio_queue_put(&queue, cmit);
+ while ((c = prio_queue_get(&queue))) {
struct commit_list *parents = c->parents;
struct commit_name **slot;
@@ -448,7 +405,7 @@ static void describe_commit(struct commit *cmit, struct strbuf *dst)
t->depth++;
}
/* Stop if last remaining path already covered by best candidate(s) */
- if (annotated_cnt && lazy_queue_empty(&queue)) {
+ if (annotated_cnt && !prio_queue_size(&queue)) {
int best_depth = INT_MAX;
unsigned best_within = 0;
for (cur_match = 0; cur_match < match_cnt; cur_match++) {
@@ -471,7 +428,7 @@ static void describe_commit(struct commit *cmit, struct strbuf *dst)
struct commit *p = parents->item;
repo_parse_commit(the_repository, p);
if (!(p->object.flags & SEEN))
- lazy_queue_put(&queue, p);
+ prio_queue_put(&queue, p);
p->object.flags |= c->object.flags;
parents = parents->next;
@@ -486,7 +443,7 @@ static void describe_commit(struct commit *cmit, struct strbuf *dst)
strbuf_add_unique_abbrev(dst, cmit_oid, abbrev);
if (suffix)
strbuf_addstr(dst, suffix);
- lazy_queue_clear(&queue);
+ clear_prio_queue(&queue);
return;
}
if (unannotated_cnt)
@@ -502,11 +459,11 @@ static void describe_commit(struct commit *cmit, struct strbuf *dst)
QSORT(all_matches, match_cnt, compare_pt);
if (gave_up_on) {
- lazy_queue_put(&queue, gave_up_on);
+ prio_queue_put(&queue, gave_up_on);
seen_commits--;
}
seen_commits += finish_depth_computation(&queue, &all_matches[0]);
- lazy_queue_clear(&queue);
+ clear_prio_queue(&queue);
if (debug) {
static int label_width = -1;
diff --git a/builtin/show-branch.c b/builtin/show-branch.c
index 8846f2376f..2435e8aeda 100644
--- a/builtin/show-branch.c
+++ b/builtin/show-branch.c
@@ -232,12 +232,13 @@ static void join_revs(struct prio_queue *queue,
while ((commit = prio_queue_peek(queue))) {
struct commit_list *parents;
int still_interesting = !!interesting(queue);
- bool get_pending = true;
int flags = commit->object.flags & all_mask;
if (!still_interesting && extra <= 0)
break;
+ prio_queue_get(queue);
+
mark_seen(commit, seen_p);
if ((flags & all_revs) == all_revs)
flags |= UNINTERESTING;
@@ -253,14 +254,8 @@ static void join_revs(struct prio_queue *queue,
if (mark_seen(p, seen_p) && !still_interesting)
extra--;
p->object.flags |= flags;
- if (get_pending)
- prio_queue_replace(queue, p);
- else
- prio_queue_put(queue, p);
- get_pending = false;
+ prio_queue_put(queue, p);
}
- if (get_pending)
- prio_queue_get(queue);
}
/*
diff --git a/commit.c b/commit.c
index fd8723502e..976bfc4618 100644
--- a/commit.c
+++ b/commit.c
@@ -795,24 +795,17 @@ void commit_list_sort_by_date(struct commit_list **list)
struct commit *pop_most_recent_commit(struct prio_queue *queue,
unsigned int mark)
{
- struct commit *ret = prio_queue_peek(queue);
- int get_pending = 1;
+ struct commit *ret = prio_queue_get(queue);
struct commit_list *parents = ret->parents;
while (parents) {
struct commit *commit = parents->item;
if (!repo_parse_commit(the_repository, commit) && !(commit->object.flags & mark)) {
commit->object.flags |= mark;
- if (get_pending)
- prio_queue_replace(queue, commit);
- else
- prio_queue_put(queue, commit);
- get_pending = 0;
+ prio_queue_put(queue, commit);
}
parents = parents->next;
}
- if (get_pending)
- prio_queue_get(queue);
return ret;
}
diff --git a/prio-queue.c b/prio-queue.c
index ead4faf4bb..199775d5af 100644
--- a/prio-queue.c
+++ b/prio-queue.c
@@ -34,12 +34,48 @@ void clear_prio_queue(struct prio_queue *queue)
queue->nr_ = 0;
queue->alloc = 0;
queue->insertion_ctr = 0;
+ queue->get_pending = 0;
+}
+
+static void sift_down_root(struct prio_queue *queue)
+{
+ size_t ix, child;
+
+ /* Push down the one at the root */
+ for (ix = 0; ix * 2 + 1 < queue->nr_; ix = child) {
+ child = ix * 2 + 1; /* left */
+ if (child + 1 < queue->nr_ &&
+ compare(queue, child, child + 1) >= 0)
+ child++; /* use right child */
+
+ if (compare(queue, ix, child) <= 0)
+ break;
+
+ swap(queue, child, ix);
+ }
+}
+
+static inline void flush_get(struct prio_queue *queue)
+{
+ if (!queue->get_pending)
+ return;
+ queue->get_pending = 0;
+ queue->array[0] = queue->array[--queue->nr_];
+ sift_down_root(queue);
}
void prio_queue_put(struct prio_queue *queue, void *thing)
{
size_t ix, parent;
+ if (queue->get_pending) {
+ queue->get_pending = 0;
+ queue->array[0].ctr = queue->insertion_ctr++;
+ queue->array[0].data = thing;
+ sift_down_root(queue);
+ return;
+ }
+
/* Append at the end */
ALLOC_GROW(queue->array, queue->nr_ + 1, queue->alloc);
queue->array[queue->nr_].ctr = queue->insertion_ctr++;
@@ -58,61 +94,33 @@ void prio_queue_put(struct prio_queue *queue, void *thing)
}
}
-static void sift_down_root(struct prio_queue *queue)
-{
- size_t ix, child;
-
- /* Push down the one at the root */
- for (ix = 0; ix * 2 + 1 < queue->nr_; ix = child) {
- child = ix * 2 + 1; /* left */
- if (child + 1 < queue->nr_ &&
- compare(queue, child, child + 1) >= 0)
- child++; /* use right child */
-
- if (compare(queue, ix, child) <= 0)
- break;
-
- swap(queue, child, ix);
- }
-}
-
void *prio_queue_get(struct prio_queue *queue)
{
- void *result;
-
- if (!queue->nr_)
+ if (queue->nr_ <= queue->get_pending) {
+ queue->nr_ = 0;
+ queue->get_pending = 0;
return NULL;
+ }
if (!queue->compare)
return queue->array[--queue->nr_].data; /* LIFO */
- result = queue->array[0].data;
- if (!--queue->nr_)
- return result;
+ flush_get(queue);
- queue->array[0] = queue->array[queue->nr_];
- sift_down_root(queue);
- return result;
+ queue->get_pending = 1;
+ return queue->array[0].data;
}
void *prio_queue_peek(struct prio_queue *queue)
{
- if (!queue->nr_)
+ if (queue->nr_ <= queue->get_pending) {
+ queue->nr_ = 0;
+ queue->get_pending = 0;
return NULL;
+ }
if (!queue->compare)
return queue->array[queue->nr_ - 1].data;
- return queue->array[0].data;
-}
-void prio_queue_replace(struct prio_queue *queue, void *thing)
-{
- if (!queue->nr_) {
- prio_queue_put(queue, thing);
- } else if (!queue->compare) {
- queue->array[queue->nr_ - 1].ctr = queue->insertion_ctr++;
- queue->array[queue->nr_ - 1].data = thing;
- } else {
- queue->array[0].ctr = queue->insertion_ctr++;
- queue->array[0].data = thing;
- sift_down_root(queue);
- }
+ flush_get(queue);
+
+ return queue->array[0].data;
}
diff --git a/prio-queue.h b/prio-queue.h
index 7f2aa986b1..570b48e648 100644
--- a/prio-queue.h
+++ b/prio-queue.h
@@ -30,8 +30,9 @@ struct prio_queue {
prio_queue_compare_fn compare;
size_t insertion_ctr;
void *cb_data;
- size_t alloc, nr_;
+ size_t alloc, nr_; /* use prio_queue_size() for logical count */
struct prio_queue_entry *array;
+ unsigned get_pending;
};
/*
@@ -54,22 +55,14 @@ void *prio_queue_peek(struct prio_queue *);
static inline size_t prio_queue_size(const struct prio_queue *queue)
{
- return queue->nr_;
+ return queue->nr_ - queue->get_pending;
}
#define prio_queue_for_each(queue, it) \
- for (size_t pq_ix_ = 0; \
+ for (size_t pq_ix_ = (queue)->get_pending; \
pq_ix_ < (queue)->nr_ && ((it) = (queue)->array[pq_ix_].data, 1); \
pq_ix_++)
-/*
- * Replace the "thing" that compares the smallest with a new "thing",
- * like prio_queue_get()+prio_queue_put() would do, but in a more
- * efficient way. Does the same as prio_queue_put() if the queue is
- * empty.
- */
-void prio_queue_replace(struct prio_queue *queue, void *thing);
-
void clear_prio_queue(struct prio_queue *);
/* Reverse the LIFO elements */
diff --git a/t/unit-tests/u-prio-queue.c b/t/unit-tests/u-prio-queue.c
index 63e58114ae..af3e0b8598 100644
--- a/t/unit-tests/u-prio-queue.c
+++ b/t/unit-tests/u-prio-queue.c
@@ -53,13 +53,13 @@ static void test_prio_queue(int *input, size_t input_size,
prio_queue_reverse(&pq);
break;
case REPLACE:
- peek = prio_queue_peek(&pq);
+ get = prio_queue_get(&pq);
cl_assert(i + 1 < input_size);
cl_assert(input[i + 1] >= 0);
cl_assert(j < result_size);
- cl_assert_equal_i(result[j], show(peek));
+ cl_assert_equal_i(result[j], show(get));
j++;
- prio_queue_replace(&pq, &input[++i]);
+ prio_queue_put(&pq, &input[++i]);
break;
default:
prio_queue_put(&pq, &input[i]);
--
gitgitgadget
^ permalink raw reply related [flat|nested] 16+ messages in thread