* [PATCH v3 0/2] prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion
From: Kristofer Karlsson via GitGitGadget @ 2026-06-07 11:43 UTC (permalink / raw)
To: git; +Cc: René Scharfe, Kristofer Karlsson, Kristofer Karlsson
In-Reply-To: <pull.2140.v2.git.1780772477.gitgitgadget@gmail.com>
Rene's lazy_queue wrapper in describe.c was a clever optimization -- by
deferring the get, a following put becomes a simple replace, avoiding a full
remove-rebalance-insert cycle.
It turns out this pattern is so common in git's traversal code that it makes
sense to fold it into prio_queue itself. Gets and puts are interleaved in
virtually every commit walk, so the fusion is essentially always a win.
This is mostly a code simplification -- three callers had independently
reimplemented the same optimization, and they all collapse to plain get+put
now. The 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 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: fold lazy_queue into prio_queue for automatic get+put
fusion
prio-queue: rename .nr to .nr_internal to prevent direct access
builtin/describe.c | 70 ++++++------------------
builtin/last-modified.c | 7 +--
builtin/show-branch.c | 24 +++-----
commit-reach.c | 24 ++++----
commit.c | 11 +---
fetch-pack.c | 4 +-
negotiator/default.c | 4 +-
negotiator/skipping.c | 12 ++--
object-name.c | 2 +-
pack-bitmap-write.c | 10 ++--
path-walk.c | 8 +--
prio-queue.c | 106 +++++++++++++++++++-----------------
prio-queue.h | 19 ++++---
revision.c | 16 +++---
t/unit-tests/u-prio-queue.c | 6 +-
walker.c | 4 +-
16 files changed, 144 insertions(+), 183 deletions(-)
base-commit: 9ac3f193c05c2237e2b14ebaa1149e9fc8a1abe0
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2140%2Fspkrka%2Flazy-prio-queue-pr-v3
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2140/spkrka/lazy-prio-queue-pr-v3
Pull-Request: https://github.com/gitgitgadget/git/pull/2140
Range-diff vs v2:
1: 29af24445e ! 1: e882206d29 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.c:pop_most_recent_commit() reimplements the same
- get_pending flag with peek+replace
- - builtin/show-branch.c:join_revs() used the same peek+replace
- pattern
+ - 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.
+ 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 (10-15 interleaved runs, 1 warmup):
+ Benchmarked on a large monorepo (30 interleaved runs,
+ paired t-test, Xeon @ 2.20GHz):
- Command base patched speedup
- merge-base --all A A~1000 3.88s 3.77s 1.03x
- rev-list --count A~1000..A 3.57s 3.43s 1.04x
- log --oneline A~1000..A 3.70s 3.49s 1.06x
- rev-parse :/pattern 365ms 364ms 1.00x
- describe HEAD (linux.git) 184ms 190ms 1.00x
+ 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 ##
@@ prio-queue.c: void clear_prio_queue(struct prio_queue *queue)
+ queue->get_pending = 0;
+}
+
-+static void sift_down_root(struct prio_queue *queue);
-+
-+static inline void flush_get(struct prio_queue *queue)
++static void sift_down_root(struct prio_queue *queue)
+{
-+ if (!queue->get_pending)
-+ return;
-+ queue->get_pending = 0;
-+ if (!--queue->nr)
-+ return;
-+ queue->array[0] = queue->array[queue->nr];
-+ sift_down_root(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++;
@@ prio-queue.c: void clear_prio_queue(struct prio_queue *queue)
+ return;
+ }
+
- /* Append at the end */
ALLOC_GROW(queue->array, queue->nr + 1, queue->alloc);
queue->array[queue->nr].ctr = queue->insertion_ctr++;
-@@ prio-queue.c: static void sift_down_root(struct prio_queue *queue)
+ 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;
-+ flush_get(queue);
-
+-
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)
- 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;
@@ prio-queue.c: static void sift_down_root(struct prio_queue *queue)
}
void *prio_queue_peek(struct prio_queue *queue)
- {
-+ flush_get(queue);
-+
- if (!queue->nr)
+@@ prio-queue.c: 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;
- }
--
+- return queue->array[0].data;
+-}
+
-void prio_queue_replace(struct prio_queue *queue, void *thing)
-{
- if (!queue->nr) {
@@ prio-queue.c: static void sift_down_root(struct prio_queue *queue)
- } else {
- queue->array[0].ctr = queue->insertion_ctr++;
- queue->array[0].data = thing;
-- sift_down_root(queue);
-- }
--}
++ 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;
+ }
## prio-queue.h ##
@@ prio-queue.h: struct prio_queue {
2: bb8b0f78f1 ! 2: 033215e304 prio-queue: rename .nr to .nr_internal to prevent direct access
@@ prio-queue.c: void prio_queue_reverse(struct prio_queue *queue)
queue->alloc = 0;
queue->insertion_ctr = 0;
queue->get_pending = 0;
-@@ prio-queue.c: static inline void flush_get(struct prio_queue *queue)
- if (!queue->get_pending)
- return;
- queue->get_pending = 0;
-- if (!--queue->nr)
-+ if (!--queue->nr_internal)
- return;
-- queue->array[0] = queue->array[queue->nr];
-+ queue->array[0] = queue->array[queue->nr_internal];
- sift_down_root(queue);
- }
+@@ 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;
}
- /* 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++;
if (!queue->compare)
- return; /* LIFO */
+- return;
++ 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) {
parent = (ix - 1) / 2;
if (compare(queue, parent, ix) <= 0)
break;
-@@ 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_internal; ix = child) {
- child = ix * 2 + 1; /* left */
-- if (child + 1 < queue->nr &&
-+ if (child + 1 < queue->nr_internal &&
- compare(queue, child, child + 1) >= 0)
- child++; /* use right child */
++
+ swap(queue, parent, ix);
+ }
+ }
-@@ prio-queue.c: void *prio_queue_get(struct prio_queue *queue)
+ void *prio_queue_get(struct prio_queue *queue)
{
- flush_get(queue);
-
- if (!queue->nr)
+ if (!queue->nr_internal)
return NULL;
if (!queue->compare)
-- return queue->array[--queue->nr].data; /* LIFO */
+- return queue->array[--queue->nr].data;
+ return queue->array[--queue->nr_internal].data; /* LIFO */
- queue->get_pending = 1;
- return queue->array[0].data;
-@@ prio-queue.c: void *prio_queue_peek(struct prio_queue *queue)
- {
- flush_get(queue);
+ 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)
+
+ 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;
- return queue->array[0].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);
+ }
+
## prio-queue.h ##
@@ prio-queue.h: struct prio_queue {
--
gitgitgadget
^ permalink raw reply
* Re: [PATCH v2 0/2] prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion
From: Kristofer Karlsson @ 2026-06-07 9:30 UTC (permalink / raw)
To: René Scharfe; +Cc: Kristofer Karlsson via GitGitGadget, git
In-Reply-To: <fe20bde6-9e86-4162-9bbd-af4d058e499e@web.de>
On Sun, 7 Jun 2026 at 09:30, René Scharfe <l.s.r@web.de> wrote:
>
> Calling flush_get() later, when we know that we have items and a
> compare function, is cleaner, as we never need it in LIFO mode, and
> is also slightly faster (patch below).
Thanks for the benchmark and the suggestion to move flush_get()
below the LIFO check - that's cleaner since LIFO never sets
get_pending.
One edge case to note: without a second !nr_internal check after
flush_get(), two consecutive get() calls on a single-element queue
will return stale data instead of NULL. I went a step further and
inlined the flush logic directly into get()/peek(), which also
removes the forward declaration.
> Still there's this 1% performance gap to the current code that I
> don't understand. Do you see it as well?
Yes, I saw a similar trend on my laptop (Core Ultra 7 155U),
but with very high variance - the results were too noisy to be
conclusive even with 20+ runs.
On an idle server (Xeon @ 2.20GHz) with much lower variance, all
three variants (v2 as posted, your patch, and the inlined version)
came out ~1.3% faster than the baseline across 30 interleaved
runs (p < 0.01). So it seems CPU-dependent - possibly branch
prediction or code alignment differences between microarchitectures.
Results from the idle server (30 interleaved runs, paired t-test):
Variant Avg SE vs baseline 95% CI p
-------------- ---------- -------- ------------ ---------------- ----------
baseline 2002.5ms 9.2ms (baseline)
v2-posted 1976.6ms 3.2ms -1.29% -41 to -11ms 0.0019
v2-rene 1977.7ms 3.1ms -1.24% -42 to -8ms 0.0071
v2-latest 1975.3ms 1.8ms -1.36% -46 to -9ms 0.0069
baseline: 9ac3f193c0 (The 11th batch)
v2-posted: v2 as sent to the list
v2-rene: v2 + your flush_get patch
v2-latest: v2 + inlined flush (for v3)
Will send a v3 with the inlined flush shortly.
- Kristofer
^ permalink raw reply
* Re: [PATCH v2 0/2] prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion
From: René Scharfe @ 2026-06-07 7:30 UTC (permalink / raw)
To: Kristofer Karlsson via GitGitGadget, git; +Cc: Kristofer Karlsson
In-Reply-To: <pull.2140.v2.git.1780772477.gitgitgadget@gmail.com>
On 6/6/26 9:01 PM, Kristofer Karlsson via GitGitGadget wrote:
> Rene's lazy_queue wrapper in describe.c was a clever optimization -- by
> deferring the get, a following put becomes a simple replace, avoiding a full
> remove-rebalance-insert cycle.
>
> It turns out this pattern is so common in git's traversal code that it makes
> sense to fold it into prio_queue itself. Gets and puts are interleaved in
> virtually every commit walk, so the fusion is essentially always a win.
>
> This is mostly a code simplification -- three callers had independently
> reimplemented the same optimization, and they all collapse to plain get+put
> now. The 3-6% speedup on traversal-heavy workloads is a nice bonus.
>
> More details and benchmark numbers in the commit message. Benchmarks were
> run on next which includes kk/commit-reach-optim -- those results represent
> the more realistic end state.
>
> Related to but independent of the cascade sift-down work in
> kk/prio-queue-cascade-sift -- the two can land in either order.
>
> Changes since v1:
>
> * Added a second commit that renames .nr to .nr_internal so that direct
> access from outside prio-queue.c is a compile error. Verified that after
> the rename, only prio-queue.c references nr_internal.
>
> * Added prio_queue_for_each() macro for callers that need to walk all
> elements (describe.c, show-branch.c, commit-reach.c, revision.c,
> negotiator/skipping.c).
>
> * Converted remaining .nr loop conditions to use
> prio_queue_get()/prio_queue_peek() as the loop condition, or
> prio_queue_size() where get/peek isn't suitable.
>
> * Fixed several callers missed in v1 (object-name.c, fetch-pack.c,
> path-walk.c, pack-bitmap-write.c, negotiator/default.c,
> negotiator/skipping.c, revision.c, builtin/last-modified.c).
>
> Kristofer Karlsson (2):
> prio-queue: fold lazy_queue into prio_queue for automatic get+put
> fusion
> prio-queue: rename .nr to .nr_internal to prevent direct access
>
> builtin/describe.c | 70 ++++++++-------------------------
> builtin/last-modified.c | 7 ++--
> builtin/show-branch.c | 24 +++++-------
> commit-reach.c | 24 ++++++------
> commit.c | 11 +-----
> fetch-pack.c | 4 +-
> negotiator/default.c | 4 +-
> negotiator/skipping.c | 12 +++---
> object-name.c | 2 +-
> pack-bitmap-write.c | 10 ++---
> path-walk.c | 8 ++--
> prio-queue.c | 77 ++++++++++++++++++++-----------------
> prio-queue.h | 19 +++++----
> revision.c | 16 ++++----
> t/unit-tests/u-prio-queue.c | 6 +--
> walker.c | 4 +-
> 16 files changed, 129 insertions(+), 169 deletions(-)
>
>
> base-commit: 9ac3f193c05c2237e2b14ebaa1149e9fc8a1abe0
> Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2140%2Fspkrka%2Flazy-prio-queue-pr-v2
> Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2140/spkrka/lazy-prio-queue-pr-v2
> Pull-Request: https://github.com/gitgitgadget/git/pull/2140
>
> Range-diff vs v1:
>
> 1: 29af24445e = 1: 29af24445e prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion
> -: ---------- > 2: bb8b0f78f1 prio-queue: rename .nr to .nr_internal to prevent direct access
>
My earlier attempt in <90270818-c52b-4611-8da2-6cee20628fc2@web.de>
copied the last item to the root and decreased .nr, to allow callers to
scan items and get their count directly.
Checking emptiness by doing the existing calls of prio_queue_peek() and
prio_queue_get() a bit earlier and scanning using a foreach macro are
fine as well and arguably cleaner, at the low cost of having to change
all the callers.
The result is faster than my attempt, but still slower than the current
code in the describe benchmark from 30598ccc4d (describe: use oidset in
finish_depth_computation(), 2025-09-02):
Benchmark 1: ./git_main describe $(git rev-list v2.41.0..v2.47.0)
Time (mean ± σ): 601.7 ms ± 1.9 ms [User: 538.6 ms, System: 47.3 ms]
Range (min … max): 599.3 ms … 606.5 ms 10 runs
Benchmark 2: ./git_auto_replace describe $(git rev-list v2.41.0..v2.47.0)
Time (mean ± σ): 618.0 ms ± 1.1 ms [User: 554.5 ms, System: 47.6 ms]
Range (min … max): 616.7 ms … 620.2 ms 10 runs
Benchmark 3: ./git_fold describe $(git rev-list v2.41.0..v2.47.0)
Time (mean ± σ): 609.9 ms ± 0.8 ms [User: 546.7 ms, System: 47.4 ms]
Range (min … max): 608.8 ms … 611.2 ms 10 runs
Benchmark 4: ./git describe $(git rev-list v2.41.0..v2.47.0)
Time (mean ± σ): 606.1 ms ± 1.2 ms [User: 543.7 ms, System: 46.7 ms]
Range (min … max): 604.7 ms … 609.1 ms 10 runs
Summary
./git_main describe $(git rev-list v2.41.0..v2.47.0) ran
1.01 ± 0.00 times faster than ./git describe $(git rev-list v2.41.0..v2.47.0)
1.01 ± 0.00 times faster than ./git_fold describe $(git rev-list v2.41.0..v2.47.0)
1.03 ± 0.00 times faster than ./git_auto_replace describe $(git rev-list v2.41.0..v2.47.0)
git_auto_replace: <90270818-c52b-4611-8da2-6cee20628fc2@web.de> and
revert of 08bb69d70f (describe: use prio_queue_replace(), 2025-08-03)
git_fold: this series
git: this series and the patch below
My attempt leaves performance on the table by using a bool. Using
an unsigned for the flag is measurably faster -- but still slower
than your series here.
Calling flush_get() later, when we know that we have items and a
compare function, is cleaner, as we never need it in LIFO mode, and
is also slightly faster (patch below).
Still there's this 1% performance gap to the current code that I
don't understand. Do you see it as well?
René
---
prio-queue.c | 7 +++----
1 file changed, 3 insertions(+), 4 deletions(-)
diff --git a/prio-queue.c b/prio-queue.c
index d11ca6ac36..45709187d3 100644
--- a/prio-queue.c
+++ b/prio-queue.c
@@ -100,24 +100,23 @@ static void sift_down_root(struct prio_queue *queue)
void *prio_queue_get(struct prio_queue *queue)
{
- flush_get(queue);
-
if (!queue->nr_internal)
return NULL;
if (!queue->compare)
return queue->array[--queue->nr_internal].data; /* LIFO */
+ flush_get(queue);
queue->get_pending = 1;
return queue->array[0].data;
}
void *prio_queue_peek(struct prio_queue *queue)
{
- flush_get(queue);
-
if (!queue->nr_internal)
return NULL;
if (!queue->compare)
return queue->array[queue->nr_internal - 1].data;
+
+ flush_get(queue);
return queue->array[0].data;
}
^ permalink raw reply related
* Re: [PATCH v2] prio-queue: use cascade-down for faster extract-min
From: René Scharfe @ 2026-06-07 7:30 UTC (permalink / raw)
To: Kristofer Karlsson; +Cc: Kristofer Karlsson via GitGitGadget, git
In-Reply-To: <CAL71e4PV-1aDvn1JnweMa3OR1xxB75fWjzJOBvM54KOWqC0stw@mail.gmail.com>
On 6/5/26 10:39 PM, Kristofer Karlsson wrote:
> I did some more benchmarking to understand how these approaches
> interact, with four variants based on origin/next on my large monorepo:
>
> 1. base: next as-is
> 2. cascade: base + sift_up_rebalance from this patch (v2)
> 3. lazy-fold: base + lazy get fusion folded into prio_queue
> 4. cascade+lazy: both combined
>
> Note that alt 3 is not yet shared with the mailing list so it's hard for you
> to reason about it, though it's quite straightforward. I will submit a new
> patch for that one soon, not necessarily with the primary goal to merge it,
> but rather show how it is implemented.
>
> merge-base --all master master~1000:
> base 4.27s
> cascade 4.07s (1.05x)
> lazy-fold 4.12s (1.03x)
> cascade+lazy 4.01s (1.06x)
>
> rev-list --count master~1000..master:
> base 3.60s
> cascade 3.35s (1.08x)
> lazy-fold 3.37s (1.07x)
> cascade+lazy 3.30s (1.09x)
>
> So both optimizations are valuable both on their own, and when combined,
> which I think helps to reason about it. This cascading sift seems to have a
> larger effect, but folding lazy_queue into prio_queue also speeds up other
> use cases and simplifies the code a bit.
Right. I was wondering, though: Why is sift-down so much faster than
cascade in the describe benchmark from 30598ccc4d (describe: use oidset
in finish_depth_computation(), 2025-09-02)?
I think I mostly understand it now: cascade is better in prio_queue_get()
because the sift-down item is from the bottom and will likely end up back
at the bottom, just of a different branch of the heap. Thus a sift-down
costs 3 compares times the number of levels, while a cascade costs just
2 compares times the number of levels and there is likely little to no
need to sift it back up.
For prio_queue_replace() we sift down a random item, though; we don't
know where it will end up. If it belongs at the very top then sift-down
just needs 3 compares, while cascade needs 2 compares times the number
of levels to bring the hole down and the same to bring the item up.
Below is a diff on top of your second cascade patch to use sift-down
only for the root and cascade otherwise. It comes remarkably close to
the performance of a full sift-down. I don't know how to find the
optimal number of levels to try sift-down before switching to cascade
for a given random item, though.
So I guess we keep the full sift-down for prio_queue_replace(), knowing
that sometimes we have a lot of items that end up at or close to the
root of the heap.
Benchmark 1: ./git_main describe $(git rev-list v2.41.0..v2.47.0)
Time (mean ± σ): 602.4 ms ± 1.2 ms [User: 539.2 ms, System: 47.7 ms]
Range (min … max): 600.5 ms … 604.7 ms 10 runs
Benchmark 2: ./git_cascade1 describe $(git rev-list v2.41.0..v2.47.0)
Time (mean ± σ): 993.9 ms ± 1.7 ms [User: 930.2 ms, System: 48.2 ms]
Range (min … max): 991.1 ms … 996.6 ms 10 runs
Benchmark 3: ./git_cascade2 describe $(git rev-list v2.41.0..v2.47.0)
Time (mean ± σ): 602.4 ms ± 1.7 ms [User: 539.1 ms, System: 47.6 ms]
Range (min … max): 599.9 ms … 606.2 ms 10 runs
Benchmark 4: ./git describe $(git rev-list v2.41.0..v2.47.0)
Time (mean ± σ): 625.4 ms ± 1.7 ms [User: 561.8 ms, System: 48.0 ms]
Range (min … max): 623.4 ms … 627.9 ms 10 runs
Summary
./git_main describe $(git rev-list v2.41.0..v2.47.0) ran
1.00 ± 0.00 times faster than ./git_cascade2 describe $(git rev-list v2.41.0..v2.47.0)
1.04 ± 0.00 times faster than ./git describe $(git rev-list v2.41.0..v2.47.0)
1.65 ± 0.00 times faster than ./git_cascade1 describe $(git rev-list v2.41.0..v2.47.0)
git_main and git_cascade2 (your v2): sift-down
git_cascade1 (your v1): cascade
git (your v2 and the patch below): sift-down for root then cascade
René
diff --git a/prio-queue.c b/prio-queue.c
index 66d445b078..4d7debc2ba 100644
--- a/prio-queue.c
+++ b/prio-queue.c
@@ -58,30 +58,12 @@ void prio_queue_put(struct prio_queue *queue, void *thing)
}
}
-static void sift_down_root(struct prio_queue *queue)
+static void sift_up_rebalance(struct prio_queue *queue, size_t ix)
{
- 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 void sift_up_rebalance(struct prio_queue *queue)
-{
- size_t ix, child;
+ size_t child;
/* Cascade: promote smaller child at each level. */
- for (ix = 0; (child = ix * 2 + 1) < queue->nr; ix = child) {
+ for (; (child = ix * 2 + 1) < queue->nr; ix = child) {
if (child + 1 < queue->nr &&
compare(queue, child, child + 1) >= 0)
child++;
@@ -112,7 +94,7 @@ void *prio_queue_get(struct prio_queue *queue)
if (!--queue->nr)
return result;
- sift_up_rebalance(queue);
+ sift_up_rebalance(queue, 0);
return result;
}
@@ -132,9 +114,20 @@ void prio_queue_replace(struct prio_queue *queue, void *thing)
} else if (!queue->compare) {
queue->array[queue->nr - 1].ctr = queue->insertion_ctr++;
queue->array[queue->nr - 1].data = thing;
+ } else if (queue->nr < 3) {
+ prio_queue_get(queue);
+ prio_queue_put(queue, thing);
} else {
- queue->array[0].ctr = queue->insertion_ctr++;
+ size_t child = compare(queue, 1, 2) <= 0 ? 1 : 2;
+ queue->array[0].ctr = queue->insertion_ctr;
queue->array[0].data = thing;
- sift_down_root(queue);
+ if (compare(queue, 0, child) <= 0) {
+ queue->insertion_ctr++;
+ } else {
+ queue->array[0] = queue->array[child];
+ queue->nr--;
+ sift_up_rebalance(queue, child);
+ prio_queue_put(queue, thing);
+ }
}
}
^ permalink raw reply related
* Re: [PATCH v3] doc: fix typos via codespell
From: Johannes Schindelin @ 2026-06-06 20:23 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Andrew Kreimer, git
In-Reply-To: <xmqqzf1dujtf.fsf@gitster.g>
Hi Junio,
On Sat, 6 Jun 2026, Junio C Hamano wrote:
> Andrew Kreimer <algonell@gmail.com> writes:
>
> > There are some typos in the documentation, comments, etc.
> > Fix them via codespell.
>
> [...]
>
> I'll squash the fix-up I already had into [v2] that I have queued,
> which should be sufficient to get to the state this [v3] should have
> been, I think.
The mechanical nature of these fixes explains another issue: One typo fix
touched two test fixtures which might seem harmless at first, but those
fixtures are littered with checksums that relied on the original
(misspelled) form.
Please adopt this follow-up into ak/typofixes:
-- snipsnap --
From 54aa4f7f7adf0c0e02b5463b5f7f64547e80cbce Mon Sep 17 00:00:00 2001
From: Johannes Schindelin <johannes.schindelin@gmx.de>
Date: Sat, 6 Jun 2026 22:09:04 +0200
Subject: [PATCH] svn-test-dumps: restore checksums after the `hapenning` typo
fix
b8b38eee85 (doc: fix typos via codespell, 2026-05-31) ran codespell
against the entire tree and rewrote `hapenning` to `happening`
inside the body of `t/t9150/svk-merge.dump` and
`t/t9151/svn-mergeinfo.dump`. Both files are Subversion dump
files: each `Node-path:` block embeds `Text-content-md5` /
`Text-content-sha1` for the new content and, on copy operations,
`Text-copy-source-md5` / `Text-copy-source-sha1` for the source
content as observed at the cited revision. None of those
checksums were updated, so loading the dumps with svnadmin 1.14.5
(present in `ubuntu:rolling`'s CI image) fails immediately with
`E200014: Checksum mismatch for '/trunk/Makefile'` and the two
tests stop before any of the assertions they actually exercise can
run. The CI failure has been visible on every `seen`-based
linux-sha256 / linux-reftable build since 2026-06-02 (the first
run that picked up b8b38eee85).
Because `happening` and `hapenning` have the same length, no
header byte counts need updating; only the embedded checksums do.
Recompute the MD5 and SHA1 of every text body in the two dumps,
and for every `Node-copyfrom-path` consult the path's most
recently defined content to refresh the corresponding
`Text-copy-source-md5` / `Text-copy-source-sha1`. After this,
`svnadmin load -q` accepts both dumps cleanly and t9150 and t9151
get past their setup steps.
This commit only touches the two dump files; the typo correction
in their surrounding human-readable comment is preserved.
Assisted-by: Opus 4.7
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
---
t/t9150/svk-merge.dump | 10 ++++----
t/t9151/svn-mergeinfo.dump | 48 +++++++++++++++++++-------------------
2 files changed, 29 insertions(+), 29 deletions(-)
diff --git a/t/t9150/svk-merge.dump b/t/t9150/svk-merge.dump
index 6a8ac81b11e6..3c46afc18a65 100644
--- a/t/t9150/svk-merge.dump
+++ b/t/t9150/svk-merge.dump
@@ -71,7 +71,7 @@ Node-kind: file
Node-action: add
Prop-content-length: 10
Text-content-length: 2401
-Text-content-md5: bfd8ff778d1492dc6758567373176a89
+Text-content-md5: d6a3917748b0c09ad85c2783f1d4dac1
Content-length: 2411
PROPS-END
@@ -201,7 +201,7 @@ Node-path: branches/left/Makefile
Node-kind: file
Node-action: change
Text-content-length: 2465
-Text-content-md5: 16e38d9753b061731650561ce01b1195
+Text-content-md5: 3f413450a7a26596d9e512ee385a9b19
Content-length: 2465
# -DCOLLISION_CHECK if you believe that SHA1's
@@ -305,7 +305,7 @@ Node-path: trunk/Makefile
Node-kind: file
Node-action: change
Text-content-length: 2521
-Text-content-md5: 0668418a621333f4aa8b6632cd63e2a0
+Text-content-md5: 89788781014278d76ff23648b8b08b2d
Content-length: 2521
# -DCOLLISION_CHECK if you believe that SHA1's
@@ -412,7 +412,7 @@ Node-path: branches/left/Makefile
Node-kind: file
Node-action: change
Text-content-length: 2593
-Text-content-md5: 5ccff689fb290e00b85fe18ee50c54ba
+Text-content-md5: 706d73919e6f319a0e624aa50c8b8b38
Content-length: 2593
# -DCOLLISION_CHECK if you believe that SHA1's
@@ -529,7 +529,7 @@ Node-path: trunk/Makefile
Node-kind: file
Node-action: change
Text-content-length: 2713
-Text-content-md5: 0afbe34f244cd662b1f97d708c687f90
+Text-content-md5: 1c05266da99e8f01a5ccf816be47a484
Content-length: 2713
# -DCOLLISION_CHECK if you believe that SHA1's
diff --git a/t/t9151/svn-mergeinfo.dump b/t/t9151/svn-mergeinfo.dump
index d5e169563745..ad741400104e 100644
--- a/t/t9151/svn-mergeinfo.dump
+++ b/t/t9151/svn-mergeinfo.dump
@@ -80,8 +80,8 @@ Node-kind: file
Node-action: add
Prop-content-length: 10
Text-content-length: 2401
-Text-content-md5: bfd8ff778d1492dc6758567373176a89
-Text-content-sha1: 103205ce331f7d64086dba497574734f78439590
+Text-content-md5: d6a3917748b0c09ad85c2783f1d4dac1
+Text-content-sha1: 9ffe895eb95d4a7c2ee2712dcf7a13637edee6a9
Content-length: 2411
PROPS-END
@@ -194,8 +194,8 @@ Node-kind: file
Node-action: add
Node-copyfrom-rev: 2
Node-copyfrom-path: trunk/Makefile
-Text-copy-source-md5: bfd8ff778d1492dc6758567373176a89
-Text-copy-source-sha1: 103205ce331f7d64086dba497574734f78439590
+Text-copy-source-md5: d6a3917748b0c09ad85c2783f1d4dac1
+Text-copy-source-sha1: 9ffe895eb95d4a7c2ee2712dcf7a13637edee6a9
Revision-number: 4
@@ -228,8 +228,8 @@ Node-kind: file
Node-action: add
Node-copyfrom-rev: 2
Node-copyfrom-path: trunk/Makefile
-Text-copy-source-md5: bfd8ff778d1492dc6758567373176a89
-Text-copy-source-sha1: 103205ce331f7d64086dba497574734f78439590
+Text-copy-source-md5: d6a3917748b0c09ad85c2783f1d4dac1
+Text-copy-source-sha1: 9ffe895eb95d4a7c2ee2712dcf7a13637edee6a9
Revision-number: 5
@@ -254,8 +254,8 @@ Node-path: branches/left/Makefile
Node-kind: file
Node-action: change
Text-content-length: 2465
-Text-content-md5: 16e38d9753b061731650561ce01b1195
-Text-content-sha1: 36da4b84ea9b64218ab48171dfc5c48ae025f38b
+Text-content-md5: 3f413450a7a26596d9e512ee385a9b19
+Text-content-sha1: b3cd389d63c5e3af4fe22b7464cf97968662ad1a
Content-length: 2465
# -DCOLLISION_CHECK if you believe that SHA1's
@@ -359,8 +359,8 @@ Node-path: branches/right/Makefile
Node-kind: file
Node-action: change
Text-content-length: 2521
-Text-content-md5: 0668418a621333f4aa8b6632cd63e2a0
-Text-content-sha1: 4f29afd038e52f45acb5ef8c41acfc70062a741a
+Text-content-md5: 89788781014278d76ff23648b8b08b2d
+Text-content-sha1: f52afb2d6230e5a418416b77c3c9ad610edfd202
Content-length: 2521
# -DCOLLISION_CHECK if you believe that SHA1's
@@ -467,8 +467,8 @@ Node-path: branches/left/Makefile
Node-kind: file
Node-action: change
Text-content-length: 2529
-Text-content-md5: f6b197cc3f2e89a83e545d4bb003de73
-Text-content-sha1: 2f656677cfec0bceec85e53036ffb63e25126f8e
+Text-content-md5: abcac8d04eb061b0a3053e359e44a2a0
+Text-content-sha1: 866caf95e04809a5ed897aea41075b24833612ea
Content-length: 2529
# -DCOLLISION_CHECK if you believe that SHA1's
@@ -572,8 +572,8 @@ Node-path: branches/left/Makefile
Node-kind: file
Node-action: change
Text-content-length: 2593
-Text-content-md5: 5ccff689fb290e00b85fe18ee50c54ba
-Text-content-sha1: a13de8e23f1483efca3e57b2b64b0ae6f740ce10
+Text-content-md5: 706d73919e6f319a0e624aa50c8b8b38
+Text-content-sha1: 9992d5a9aea960c7856ef6a9364aedd5b710ef53
Content-length: 2593
# -DCOLLISION_CHECK if you believe that SHA1's
@@ -689,8 +689,8 @@ Node-kind: file
Node-action: add
Node-copyfrom-rev: 8
Node-copyfrom-path: branches/left/Makefile
-Text-copy-source-md5: 5ccff689fb290e00b85fe18ee50c54ba
-Text-copy-source-sha1: a13de8e23f1483efca3e57b2b64b0ae6f740ce10
+Text-copy-source-md5: 706d73919e6f319a0e624aa50c8b8b38
+Text-copy-source-sha1: 9992d5a9aea960c7856ef6a9364aedd5b710ef53
@@ -761,8 +761,8 @@ Node-path: trunk/Makefile
Node-kind: file
Node-action: change
Text-content-length: 2593
-Text-content-md5: 5ccff689fb290e00b85fe18ee50c54ba
-Text-content-sha1: a13de8e23f1483efca3e57b2b64b0ae6f740ce10
+Text-content-md5: 706d73919e6f319a0e624aa50c8b8b38
+Text-content-sha1: 9992d5a9aea960c7856ef6a9364aedd5b710ef53
Content-length: 2593
# -DCOLLISION_CHECK if you believe that SHA1's
@@ -942,8 +942,8 @@ Node-path: trunk/Makefile
Node-kind: file
Node-action: change
Text-content-length: 2713
-Text-content-md5: 0afbe34f244cd662b1f97d708c687f90
-Text-content-sha1: 46d9377d783e67a9b581da110352e799517c8a14
+Text-content-md5: 1c05266da99e8f01a5ccf816be47a484
+Text-content-sha1: 0cba212974e2b288389d73317f3220be11158e00
Content-length: 2713
# -DCOLLISION_CHECK if you believe that SHA1's
@@ -1166,8 +1166,8 @@ Node-path: branches/left-sub/Makefile
Node-kind: file
Node-action: change
Text-content-length: 2713
-Text-content-md5: 0afbe34f244cd662b1f97d708c687f90
-Text-content-sha1: 46d9377d783e67a9b581da110352e799517c8a14
+Text-content-md5: 1c05266da99e8f01a5ccf816be47a484
+Text-content-sha1: 0cba212974e2b288389d73317f3220be11158e00
Content-length: 2713
# -DCOLLISION_CHECK if you believe that SHA1's
@@ -1408,8 +1408,8 @@ Node-path: branches/left/Makefile
Node-kind: file
Node-action: change
Text-content-length: 2713
-Text-content-md5: 0afbe34f244cd662b1f97d708c687f90
-Text-content-sha1: 46d9377d783e67a9b581da110352e799517c8a14
+Text-content-md5: 1c05266da99e8f01a5ccf816be47a484
+Text-content-sha1: 0cba212974e2b288389d73317f3220be11158e00
Content-length: 2713
# -DCOLLISION_CHECK if you believe that SHA1's
--
2.54.0.windows.1.10.gd5b8d9bb7af0
^ permalink raw reply related
* [PATCH v2 2/2] prio-queue: rename .nr to .nr_internal to prevent direct access
From: Kristofer Karlsson via GitGitGadget @ 2026-06-06 19:01 UTC (permalink / raw)
To: git
Cc: René Scharfe, Kristofer Karlsson, Kristofer Karlsson,
Kristofer Karlsson
In-Reply-To: <pull.2140.v2.git.1780772477.gitgitgadget@gmail.com>
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 | 32 ++++++++++++++++----------------
prio-queue.h | 9 +++++++--
revision.c | 11 +++++------
13 files changed, 68 insertions(+), 60 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 1407f2f801..d11ca6ac36 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;
@@ -44,9 +44,9 @@ static inline void flush_get(struct prio_queue *queue)
if (!queue->get_pending)
return;
queue->get_pending = 0;
- if (!--queue->nr)
+ if (!--queue->nr_internal)
return;
- queue->array[0] = queue->array[queue->nr];
+ queue->array[0] = queue->array[queue->nr_internal];
sift_down_root(queue);
}
@@ -63,15 +63,15 @@ void prio_queue_put(struct prio_queue *queue, void *thing)
}
/* 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_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; /* LIFO */
/* Bubble up the new one */
- for (ix = queue->nr - 1; ix; ix = parent) {
+ for (ix = queue->nr_internal - 1; ix; ix = parent) {
parent = (ix - 1) / 2;
if (compare(queue, parent, ix) <= 0)
break;
@@ -85,9 +85,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_internal; ix = child) {
child = ix * 2 + 1; /* left */
- if (child + 1 < queue->nr &&
+ if (child + 1 < queue->nr_internal &&
compare(queue, child, child + 1) >= 0)
child++; /* use right child */
@@ -102,10 +102,10 @@ void *prio_queue_get(struct prio_queue *queue)
{
flush_get(queue);
- if (!queue->nr)
+ if (!queue->nr_internal)
return NULL;
if (!queue->compare)
- return queue->array[--queue->nr].data; /* LIFO */
+ return queue->array[--queue->nr_internal].data; /* LIFO */
queue->get_pending = 1;
return queue->array[0].data;
@@ -115,9 +115,9 @@ void *prio_queue_peek(struct prio_queue *queue)
{
flush_get(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;
return queue->array[0].data;
}
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
* [PATCH v2 1/2] prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion
From: Kristofer Karlsson via GitGitGadget @ 2026-06-06 19:01 UTC (permalink / raw)
To: git
Cc: René Scharfe, Kristofer Karlsson, Kristofer Karlsson,
Kristofer Karlsson
In-Reply-To: <pull.2140.v2.git.1780772477.gitgitgadget@gmail.com>
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() reimplements the same
get_pending flag with peek+replace
- builtin/show-branch.c:join_revs() used the same peek+replace
pattern
All three now collapse to plain _get() and _put(),
with the data structure handling the fusion internally.
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 (10-15 interleaved runs, 1 warmup):
Command base patched speedup
merge-base --all A A~1000 3.88s 3.77s 1.03x
rev-list --count A~1000..A 3.57s 3.43s 1.04x
log --oneline A~1000..A 3.70s 3.49s 1.06x
rev-parse :/pattern 365ms 364ms 1.00x
describe HEAD (linux.git) 184ms 190ms 1.00x
No regressions in any scenario.
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 | 49 +++++++++++++++------------
prio-queue.h | 12 +++----
revision.c | 5 ++-
t/unit-tests/u-prio-queue.c | 6 ++--
walker.c | 4 +--
11 files changed, 68 insertions(+), 116 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..1407f2f801 100644
--- a/prio-queue.c
+++ b/prio-queue.c
@@ -34,12 +34,34 @@ 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);
+
+static inline void flush_get(struct prio_queue *queue)
+{
+ if (!queue->get_pending)
+ return;
+ queue->get_pending = 0;
+ if (!--queue->nr)
+ return;
+ 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++;
@@ -78,41 +100,24 @@ static void sift_down_root(struct prio_queue *queue)
void *prio_queue_get(struct prio_queue *queue)
{
- void *result;
+ flush_get(queue);
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;
-
- 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)
{
+ flush_get(queue);
+
if (!queue->nr)
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);
- }
-}
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
* [PATCH v2 0/2] prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion
From: Kristofer Karlsson via GitGitGadget @ 2026-06-06 19:01 UTC (permalink / raw)
To: git; +Cc: René Scharfe, Kristofer Karlsson, Kristofer Karlsson
In-Reply-To: <pull.2140.git.1780757885582.gitgitgadget@gmail.com>
Rene's lazy_queue wrapper in describe.c was a clever optimization -- by
deferring the get, a following put becomes a simple replace, avoiding a full
remove-rebalance-insert cycle.
It turns out this pattern is so common in git's traversal code that it makes
sense to fold it into prio_queue itself. Gets and puts are interleaved in
virtually every commit walk, so the fusion is essentially always a win.
This is mostly a code simplification -- three callers had independently
reimplemented the same optimization, and they all collapse to plain get+put
now. The 3-6% speedup on traversal-heavy workloads is a nice bonus.
More details and benchmark numbers in the commit message. Benchmarks were
run on next which includes kk/commit-reach-optim -- those results represent
the more realistic end state.
Related to but independent of the cascade sift-down work in
kk/prio-queue-cascade-sift -- the two can land in either order.
Changes since v1:
* Added a second commit that renames .nr to .nr_internal so that direct
access from outside prio-queue.c is a compile error. Verified that after
the rename, only prio-queue.c references nr_internal.
* Added prio_queue_for_each() macro for callers that need to walk all
elements (describe.c, show-branch.c, commit-reach.c, revision.c,
negotiator/skipping.c).
* Converted remaining .nr loop conditions to use
prio_queue_get()/prio_queue_peek() as the loop condition, or
prio_queue_size() where get/peek isn't suitable.
* Fixed several callers missed in v1 (object-name.c, fetch-pack.c,
path-walk.c, pack-bitmap-write.c, negotiator/default.c,
negotiator/skipping.c, revision.c, builtin/last-modified.c).
Kristofer Karlsson (2):
prio-queue: fold lazy_queue into prio_queue for automatic get+put
fusion
prio-queue: rename .nr to .nr_internal to prevent direct access
builtin/describe.c | 70 ++++++++-------------------------
builtin/last-modified.c | 7 ++--
builtin/show-branch.c | 24 +++++-------
commit-reach.c | 24 ++++++------
commit.c | 11 +-----
fetch-pack.c | 4 +-
negotiator/default.c | 4 +-
negotiator/skipping.c | 12 +++---
object-name.c | 2 +-
pack-bitmap-write.c | 10 ++---
path-walk.c | 8 ++--
prio-queue.c | 77 ++++++++++++++++++++-----------------
prio-queue.h | 19 +++++----
revision.c | 16 ++++----
t/unit-tests/u-prio-queue.c | 6 +--
walker.c | 4 +-
16 files changed, 129 insertions(+), 169 deletions(-)
base-commit: 9ac3f193c05c2237e2b14ebaa1149e9fc8a1abe0
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2140%2Fspkrka%2Flazy-prio-queue-pr-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2140/spkrka/lazy-prio-queue-pr-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/2140
Range-diff vs v1:
1: 29af24445e = 1: 29af24445e prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion
-: ---------- > 2: bb8b0f78f1 prio-queue: rename .nr to .nr_internal to prevent direct access
--
gitgitgadget
^ permalink raw reply
* Re: [PATCH] prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion
From: Kristofer Karlsson @ 2026-06-06 17:24 UTC (permalink / raw)
To: Junio C Hamano
Cc: Kristofer Karlsson via GitGitGadget, git, René Scharfe
In-Reply-To: <xmqqqzmjbpfp.fsf@gitster.g>
Junio C Hamano <gitster@pobox.com> writes:
> How can we be sure that all such users of prio_queue has been
> converted? Are direct references to .nr member, outside of the
> prio-queue.c implementation, all now suspect?
You're right, and the patch is thus broken in its current state.
I did a rename of .nr to ._nr on the branch and rebuilt -- that
immediately found several callers I missed:
- object-name.c: get_oid_oneline()
(like you also found)
- fetch-pack.c: mark_recent_complete_commits()
- builtin/last-modified.c: last_modified_run()
- path-walk.c: walk_objects_by_path()
- commit-reach.c: queue_has_nonstale()
The describe.c and show-branch.c callers already compensate for
get_pending in their iteration bounds, but they still reach into
.nr directly.
> Perhaps the member should be renamed to catch in-flight topics
> that add more users of prio-queue that peek into the .nr member,
> or something like that.
Agreed, that's the right fix. I looked for existing ways of marking
fields as private, internal or hidden but the only thing I found was
the convention of using a code comment: /* for internal use only */
I will apply a rename and submit a v2. Perhaps something like
nr_internal to make it look less like a public API.
^ permalink raw reply
* Re: [PATCH] prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion
From: Junio C Hamano @ 2026-06-06 16:31 UTC (permalink / raw)
To: Kristofer Karlsson via GitGitGadget
Cc: git, René Scharfe, Kristofer Karlsson
In-Reply-To: <pull.2140.git.1780757885582.gitgitgadget@gmail.com>
"Kristofer Karlsson via GitGitGadget" <gitgitgadget@gmail.com>
writes:
> Add prio_queue_size() for callers that need the logical element
> count, since the physical nr may temporarily include a
> pending-removal element.
Many code paths used to learn how many elements it logically has by
directly peeking into .nr member of the prio_queue struct. Now they
should call this new helper function, and you converted some in this
patch.
How can we be sure that all such users of prio_queue has been
converted? Are direct references to .nr member, outside of the
prio-queue.c implementation, all now suspect?
For example, object-name.c:get_oid_oneline() uses a prio-queue
"copy", and loops "while (copy.nr)". In the loop, it calls
pop_most_recent_commit(), which does a get followed by put of its
parents. If the get become hanging (e.g., root commit, causing no
_put() performed in pop_most_recent_commit()), would copy.nr still
remain 1 but logically no elements remain in the queue.
There seem to be other direct peeking of .nr member remaining in the
code. Perhaps the member should be renamed to catch in-flight
topics that add more users of prio-queue that peek into the .nr
member, or something like that.
^ permalink raw reply
* [PATCH] prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion
From: Kristofer Karlsson via GitGitGadget @ 2026-06-06 14:58 UTC (permalink / raw)
To: git; +Cc: René Scharfe, 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() reimplements the same
get_pending flag with peek+replace
- builtin/show-branch.c:join_revs() used the same peek+replace
pattern
All three now collapse to plain _get() and _put(),
with the data structure handling the fusion internally.
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 (10-15 interleaved runs, 1 warmup):
Command base patched speedup
merge-base --all A A~1000 3.88s 3.77s 1.03x
rev-list --count A~1000..A 3.57s 3.43s 1.04x
log --oneline A~1000..A 3.70s 3.49s 1.06x
rev-parse :/pattern 365ms 364ms 1.00x
describe HEAD (linux.git) 184ms 190ms 1.00x
No regressions in any scenario.
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
prio-queue: fold lazy_queue into prio_queue for automatic get+put fusion
Rene's lazy_queue wrapper in describe.c was a clever optimization -- by
deferring the get, a following put becomes a simple replace, avoiding a
full remove-rebalance-insert cycle.
It turns out this pattern is so common in git's traversal code that it
makes sense to fold it into prio_queue itself. Gets and puts are
interleaved in virtually every commit walk, so the fusion is essentially
always a win.
This is mostly a code simplification -- three callers had independently
reimplemented the same optimization, and they all collapse to plain
get+put now. The 3-6% speedup on traversal-heavy workloads is a nice
bonus.
More details and benchmark numbers in the commit message. Benchmarks
were run on next which includes kk/commit-reach-optim -- those results
represent the more realistic end state.
Related to but independent of the cascade sift-down work in
kk/prio-queue-cascade-sift -- the two can land in either order.
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2140%2Fspkrka%2Flazy-prio-queue-pr-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2140/spkrka/lazy-prio-queue-pr-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/2140
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 | 49 +++++++++++++++------------
prio-queue.h | 12 +++----
revision.c | 5 ++-
t/unit-tests/u-prio-queue.c | 6 ++--
walker.c | 4 +--
11 files changed, 68 insertions(+), 116 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..1407f2f801 100644
--- a/prio-queue.c
+++ b/prio-queue.c
@@ -34,12 +34,34 @@ 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);
+
+static inline void flush_get(struct prio_queue *queue)
+{
+ if (!queue->get_pending)
+ return;
+ queue->get_pending = 0;
+ if (!--queue->nr)
+ return;
+ 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++;
@@ -78,41 +100,24 @@ static void sift_down_root(struct prio_queue *queue)
void *prio_queue_get(struct prio_queue *queue)
{
- void *result;
+ flush_get(queue);
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;
-
- 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)
{
+ flush_get(queue);
+
if (!queue->nr)
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);
- }
-}
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);
base-commit: 9ac3f193c05c2237e2b14ebaa1149e9fc8a1abe0
--
gitgitgadget
^ permalink raw reply related
* [PATCH v1 0/1] environment: move protect_hfs and protect_ntfs
From: Tian Yuchen @ 2026-06-06 14:34 UTC (permalink / raw)
To: git
Cc: christian, phillip.wood123, Tian Yuchen, Christian Couder,
Ayush Chandekar, Olamide Caleb Bello
In-Reply-To: <20260606143412.15443-1-cat@malon.dev>
Hi everyone,
This series continues the ongoing libification effort by moving the
global **filesystem** variables, protect_hfs and protect_ntfs, into
struct repo_config_values.
Place them within the **per-repository** configuration structure
aligns with our goal of removing global states.
RFC Questions:
1. Should we keep PROTECT_HFS_DEFAULT and PROTECT_NTFS_DEFAULT
in repo_config_values_init()?
void repo_config_values_init(struct repo_config_values *cfg)
{
cfg->attributes_file = NULL;
cfg->apply_sparse_checkout = 0;
cfg->protect_hfs = PROTECT_HFS_DEFAULT;
cfg->protect_ntfs = PROTECT_NTFS_DEFAULT;
cfg->branch_track = BRANCH_TRACK_REMOTE;
}
Or is it better if they are used anywhere other than in environment.c?
If so...
2. Is it worth introducing a Macro or Getter for safe access?
((the_repository->gitdir ? repo_config_values(the_repository)->protect_hfs : 0))
The current approach looks verbose and lacks readability, and
hard-coded 0 and 1 are used as fallback values. I wonder if a macro or a
getter could be introduced, for example...
#define SAFE_PROTECT_HFS(repo) \
(((repo) && (repo)->gitdir && (repo) == the_repository) ? \
repo_config_values(repo)->protect_hfs : PROTECT_HFS_DEFAULT)
...to improve the coding style a bit. Although I am aware that introducing
new macros is generally frowned upon, I would still like to know which
parts this might make difficult to maintain.
3. Note that Derrick attempted to use get_int_config_global to wrap
this kind of Filesystem Level global variables. This approach bypassed
struct repository, did not actually eliminate global state, and the
reviewer politely rejected it. Nevertheless, I am still curious as
to whether this approach might still be inspiring today.
https://lore.kernel.org/git/a42dd9397d07b2dc4a0d7e75bfe1af2e46cad262.1685716420.git.gitgitgadget@gmail.com/
Thanks!
Mentored-by: Christian Couder <christian.couder@gmail.com>
Mentored-by: Ayush Chandekar <ayu.chandekar@gmail.com>
Mentored-by: Olamide Caleb Bello <belkid98@gmail.com>
Signed-off-by: Tian Yuchen <cat@malon.dev>
Tian Yuchen (1):
environment.c: move 'protect_hfs' and 'protect_ntfs' into
'repo_config_values'
compat/mingw.c | 2 +-
environment.c | 8 ++++----
environment.h | 4 ++--
read-cache.c | 7 ++++---
t/helper/test-path-utils.c | 26 ++++++++++++++++----------
5 files changed, 27 insertions(+), 20 deletions(-)
--
2.43.0
^ permalink raw reply
* [PATCH v1 1/1] environment.c: move 'protect_hfs' and 'protect_ntfs' into 'repo_config_values'
From: Tian Yuchen @ 2026-06-06 14:34 UTC (permalink / raw)
To: git
Cc: christian, phillip.wood123, Tian Yuchen, Christian Couder,
Ayush Chandekar, Olamide Caleb Bello
Move the global 'protect_hfs' and 'protect_ntfs' configurations
into the repository-specific 'repo_config_values' struct.
This will help with the elimination of 'the_repository'
For now, associated functions access this configuration by
explicitly falling back to 'the_repository', which needs to
be addressed in the future.
Note: In 't/helper/test-path-utils.c', there is a function
'protect_ntfs_hfs_benchmark()' where these two global
variables are used as loop iterators. New local variables
have been created to replace them.
Mentored-by: Christian Couder <christian.couder@gmail.com>
Mentored-by: Ayush Chandekar <ayu.chandekar@gmail.com>
Mentored-by: Olamide Caleb Bello <belkid98@gmail.com>
Signed-off-by: Tian Yuchen <cat@malon.dev>
---
compat/mingw.c | 2 +-
environment.c | 8 ++++----
environment.h | 4 ++--
read-cache.c | 7 ++++---
t/helper/test-path-utils.c | 26 ++++++++++++++++----------
5 files changed, 27 insertions(+), 20 deletions(-)
diff --git a/compat/mingw.c b/compat/mingw.c
index aa7525f419..c77696ba8a 100644
--- a/compat/mingw.c
+++ b/compat/mingw.c
@@ -3392,7 +3392,7 @@ int is_valid_win32_path(const char *path, int allow_literal_nul)
const char *p = path;
int preceding_space_or_period = 0, i = 0, periods = 0;
- if (!protect_ntfs)
+ if (!(the_repository->gitdir ? repo_config_values(the_repository)->protect_ntfs : 1))
return 1;
skip_dos_drive_prefix((char **)&path);
diff --git a/environment.c b/environment.c
index fc3ed8bb1c..0730bfcbba 100644
--- a/environment.c
+++ b/environment.c
@@ -82,12 +82,10 @@ unsigned long pack_size_limit_cfg;
#ifndef PROTECT_HFS_DEFAULT
#define PROTECT_HFS_DEFAULT 0
#endif
-int protect_hfs = PROTECT_HFS_DEFAULT;
#ifndef PROTECT_NTFS_DEFAULT
#define PROTECT_NTFS_DEFAULT 1
#endif
-int protect_ntfs = PROTECT_NTFS_DEFAULT;
/*
* The character that begins a commented line in user-editable file
@@ -541,12 +539,12 @@ int git_default_core_config(const char *var, const char *value,
}
if (!strcmp(var, "core.protecthfs")) {
- protect_hfs = git_config_bool(var, value);
+ cfg->protect_hfs = git_config_bool(var, value);
return 0;
}
if (!strcmp(var, "core.protectntfs")) {
- protect_ntfs = git_config_bool(var, value);
+ cfg->protect_ntfs = git_config_bool(var, value);
return 0;
}
@@ -720,5 +718,7 @@ void repo_config_values_init(struct repo_config_values *cfg)
{
cfg->attributes_file = NULL;
cfg->apply_sparse_checkout = 0;
+ cfg->protect_hfs = PROTECT_HFS_DEFAULT;
+ cfg->protect_ntfs = PROTECT_NTFS_DEFAULT;
cfg->branch_track = BRANCH_TRACK_REMOTE;
}
diff --git a/environment.h b/environment.h
index 9eb97b3869..d48fd2719c 100644
--- a/environment.h
+++ b/environment.h
@@ -91,6 +91,8 @@ struct repo_config_values {
/* section "core" config values */
char *attributes_file;
int apply_sparse_checkout;
+ int protect_hfs;
+ int protect_ntfs;
/* section "branch" config values */
enum branch_track branch_track;
@@ -173,8 +175,6 @@ extern int pack_compression_level;
extern unsigned long pack_size_limit_cfg;
extern int precomposed_unicode;
-extern int protect_hfs;
-extern int protect_ntfs;
extern int core_sparse_checkout_cone;
extern int sparse_expect_files_outside_of_patterns;
diff --git a/read-cache.c b/read-cache.c
index 21829102ae..b64a5629ef 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -1002,7 +1002,7 @@ static enum verify_path_result verify_path_internal(const char *path,
return PATH_OK;
if (is_dir_sep(c)) {
inside:
- if (protect_hfs) {
+ if ((the_repository->gitdir ? repo_config_values(the_repository)->protect_hfs : 0)) {
if (is_hfs_dotgit(path))
return PATH_INVALID;
@@ -1011,7 +1011,7 @@ static enum verify_path_result verify_path_internal(const char *path,
return PATH_INVALID;
}
}
- if (protect_ntfs) {
+ if ((the_repository->gitdir ? repo_config_values(the_repository)->protect_ntfs : 1)) {
#if defined GIT_WINDOWS_NATIVE || defined __CYGWIN__
if (c == '\\')
return PATH_INVALID;
@@ -1035,7 +1035,8 @@ static enum verify_path_result verify_path_internal(const char *path,
if (c == '\0')
return S_ISDIR(mode) ? PATH_DIR_WITH_SEP :
PATH_INVALID;
- } else if (c == '\\' && protect_ntfs) {
+ } else if (c == '\\' &&
+ (the_repository->gitdir ? repo_config_values(the_repository)->protect_ntfs : 1)) {
if (is_ntfs_dotgit(path))
return PATH_INVALID;
if (S_ISLNK(mode)) {
diff --git a/t/helper/test-path-utils.c b/t/helper/test-path-utils.c
index 15eb44485c..4455a68903 100644
--- a/t/helper/test-path-utils.c
+++ b/t/helper/test-path-utils.c
@@ -250,6 +250,7 @@ static int protect_ntfs_hfs_benchmark(int argc, const char **argv)
double m[3][2], v[3][2];
uint64_t cumul;
double cumul2;
+ int ntfs, hfs;
if (argc > 1 && !strcmp(argv[1], "--with-symlink-mode")) {
file_mode = 0120000;
@@ -275,9 +276,14 @@ static int protect_ntfs_hfs_benchmark(int argc, const char **argv)
while (len > 0)
names[i][--len] = (char)(' ' + (my_random() % ('\x7f' - ' ')));
}
-
- for (protect_ntfs = 0; protect_ntfs < 2; protect_ntfs++)
- for (protect_hfs = 0; protect_hfs < 2; protect_hfs++) {
+
+ if (!the_repository->gitdir)
+ the_repository->gitdir = xstrdup(".git");
+
+ for (ntfs = 0; ntfs < 2; ntfs++)
+ for (hfs = 0; hfs < 2; hfs++) {
+ repo_config_values(the_repository)->protect_ntfs = ntfs;
+ repo_config_values(the_repository)->protect_hfs = hfs;
cumul = 0;
cumul2 = 0;
for (i = 0; i < repetitions; i++) {
@@ -285,18 +291,18 @@ static int protect_ntfs_hfs_benchmark(int argc, const char **argv)
for (j = 0; j < nr; j++)
verify_path(names[j], file_mode);
end = getnanotime();
- printf("protect_ntfs = %d, protect_hfs = %d: %lfms\n", protect_ntfs, protect_hfs, (end-begin) / (double)1e6);
+ printf("protect_ntfs = %d, protect_hfs = %d: %lfms\n", ntfs, hfs, (end-begin) / (double)1e6);
cumul += end - begin;
cumul2 += (end - begin) * (end - begin);
}
- m[protect_ntfs][protect_hfs] = cumul / (double)repetitions;
- v[protect_ntfs][protect_hfs] = my_sqrt(cumul2 / (double)repetitions - m[protect_ntfs][protect_hfs] * m[protect_ntfs][protect_hfs]);
- printf("mean: %lfms, stddev: %lfms\n", m[protect_ntfs][protect_hfs] / (double)1e6, v[protect_ntfs][protect_hfs] / (double)1e6);
+ m[ntfs][hfs] = cumul / (double)repetitions;
+ v[ntfs][hfs] = my_sqrt(cumul2 / (double)repetitions - m[ntfs][hfs] * m[ntfs][hfs]);
+ printf("mean: %lfms, stddev: %lfms\n", m[ntfs][hfs] / (double)1e6, v[ntfs][hfs] / (double)1e6);
}
- for (protect_ntfs = 0; protect_ntfs < 2; protect_ntfs++)
- for (protect_hfs = 0; protect_hfs < 2; protect_hfs++)
- printf("ntfs=%d/hfs=%d: %lf%% slower\n", protect_ntfs, protect_hfs, (m[protect_ntfs][protect_hfs] - m[0][0]) * 100 / m[0][0]);
+ for (ntfs = 0; ntfs < 2; ntfs++)
+ for (hfs = 0; hfs < 2; hfs++)
+ printf("ntfs=%d/hfs=%d: %lf%% slower\n", ntfs, hfs, (m[ntfs][hfs] - m[0][0]) * 100 / m[0][0]);
return 0;
}
--
2.43.0
^ permalink raw reply related
* Re: [PATCH v6 00/10] parseopt: add subcommand autocorrection
From: Junio C Hamano @ 2026-06-06 14:23 UTC (permalink / raw)
To: Jiamu Sun; +Cc: git, Aaron Plattner, Karthik Nayak
In-Reply-To: <SY0P300MB0801E50FCB7EB2F45CD15208CE042@SY0P300MB0801.AUSP300.PROD.OUTLOOK.COM>
Jiamu Sun <39@barroit.sh> writes:
> On Mon, May 11, 2026 at 12:03:12PM +0900, Junio C Hamano wrote:
>> I've been carrying the following fix on top of these series since
>> Apr 23 when the topic was merged to 'seen'. Can you fix these up at
>> the source, so that we can move forward with this topic?
>>
>> Thanks.
>
> Sorry for the delay. This email didn't reach my inbox.
>
> By the time I saw this fix, I had already sent v6. Should I resend v6
> with this fix squashed in, or bump to v7?
Sorry for the delay; this exchange fell through the cracks, and then
I no longer recall exactly what the "fix" was. If your v6 still
lacks the "fix" I gave (sorry but I do not remember what it was, and
I am away from my desk), then please do incorporate and send an
updated one as v7. Hopefully it would be the final edition, unless
there are other issues outstanding.
Thanks.
^ permalink raw reply
* Re: [PATCH v4] git-gui: silence install recipes under "make -s"
From: Johannes Sixt @ 2026-06-06 11:47 UTC (permalink / raw)
To: Harald Nordgren; +Cc: git, Harald Nordgren via GitGitGadget
In-Reply-To: <pull.2318.v4.git.git.1780742303298.gitgitgadget@gmail.com>
Thanks, queued.
-- Hannes
^ permalink raw reply
* [PATCH v4] git-gui: silence install recipes under "make -s"
From: Harald Nordgren via GitGitGadget @ 2026-06-06 10:38 UTC (permalink / raw)
To: git; +Cc: Johannes Sixt, Harald Nordgren, Harald Nordgren
In-Reply-To: <pull.2318.v3.git.git.1780555730228.gitgitgadget@gmail.com>
From: Harald Nordgren <haraldnordgren@gmail.com>
Several install and uninstall recipes embed "echo" calls that fire as
part of the recipe itself, so the install banners (DEST, INSTALL,
LINK, REMOVE) were visible whenever the variables expand non-empty.
Guard the whole "ifndef V" block on "-s" so the loud variants are
selected only when "-s" is absent and V=1 is unset. The existing
"-s" check also had its findstring arguments in the wrong order
(needle "-s" never fit in haystack "s"), so swap them while moving
the check to wrap the block.
Signed-off-by: Harald Nordgren <haraldnordgren@gmail.com>
---
git-gui: silence install recipes under "make -s"
Change sign-off email from work email to correct personal email.
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-2318%2FHaraldNordgren%2Fgit-gui-respect-silent-flag-v4
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-2318/HaraldNordgren/git-gui-respect-silent-flag-v4
Pull-Request: https://github.com/git/git/pull/2318
Range-diff vs v3:
1: 1375fdc1aa ! 1: 27d9fcf26b git-gui: silence install recipes under "make -s"
@@ Commit message
(needle "-s" never fit in haystack "s"), so swap them while moving
the check to wrap the block.
- Signed-off-by: Harald Nordgren <harald.nordgren@kostdoktorn.se>
+ Signed-off-by: Harald Nordgren <haraldnordgren@gmail.com>
## git-gui/Makefile ##
@@ git-gui/Makefile: REMOVE_F0 = $(RM_RF) # space is required here
git-gui/Makefile | 6 ++----
1 file changed, 2 insertions(+), 4 deletions(-)
diff --git a/git-gui/Makefile b/git-gui/Makefile
index ca01068810..d33204e875 100644
--- a/git-gui/Makefile
+++ b/git-gui/Makefile
@@ -64,6 +64,7 @@ REMOVE_F0 = $(RM_RF) # space is required here
REMOVE_F1 =
CLEAN_DST = true
+ifneq ($(findstring s,$(firstword -$(MAKEFLAGS))),s)
ifndef V
QUIET = @
QUIET_GEN = $(QUIET)echo ' ' GEN '$@' &&
@@ -89,6 +90,7 @@ ifndef V
REMOVE_F0 = dst=
REMOVE_F1 = && echo ' ' REMOVE `basename "$$dst"` && $(RM_RF) "$$dst"
endif
+endif
TCLTK_PATH ?= wish
ifeq (./,$(dir $(TCLTK_PATH)))
@@ -97,10 +99,6 @@ else
TCL_PATH ?= $(dir $(TCLTK_PATH))$(notdir $(subst wish,tclsh,$(TCLTK_PATH)))
endif
-ifeq ($(findstring $(firstword -$(MAKEFLAGS)),s),s)
-QUIET_GEN =
-endif
-
-include config.mak
DESTDIR_SQ = $(subst ','\'',$(DESTDIR))
base-commit: 9ac3f193c05c2237e2b14ebaa1149e9fc8a1abe0
--
gitgitgadget
^ permalink raw reply related
* Re: [PATCH v3] git-gui: silence install recipes under "make -s"
From: Johannes Sixt @ 2026-06-06 9:38 UTC (permalink / raw)
To: Harald Nordgren; +Cc: git, Harald Nordgren via GitGitGadget
In-Reply-To: <pull.2318.v3.git.git.1780555730228.gitgitgadget@gmail.com>
Am 04.06.26 um 08:48 schrieb Harald Nordgren via GitGitGadget:
> From: Harald Nordgren <haraldnordgren@gmail.com>
>
> Several install and uninstall recipes embed "echo" calls that fire as
> part of the recipe itself, so the install banners (DEST, INSTALL,
> LINK, REMOVE) were visible whenever the variables expand non-empty.
>
> Guard the whole "ifndef V" block on "-s" so the loud variants are
> selected only when "-s" is absent and V=1 is unset. The existing
> "-s" check also had its findstring arguments in the wrong order
> (needle "-s" never fit in haystack "s"), so swap them while moving
> the check to wrap the block.
>
> Signed-off-by: Harald Nordgren <harald.nordgren@kostdoktorn.se>
The new text looks good. However, the email addresses of author and
signer-off are different. They should be the same. I notice that you use
the gmail address in both places in other patch submissions, so I can
use that if you agree (and you don't need to send another round).
-- Hannes
^ permalink raw reply
* Re: [PATCH v3] index-pack: retain child bases in delta cache
From: Arijit Banerjee @ 2026-06-05 21:18 UTC (permalink / raw)
To: Jeff King
Cc: Arijit Banerjee via GitGitGadget, git,
Ævar Arnfjörð Bjarmason, Junio C Hamano,
Derrick Stolee, Arijit Banerjee
In-Reply-To: <20260604071204.GA3196596@coredump.intra.peff.net>
Apologies, my earlier replies were sent through GitHub's notification
emails and appeared only as PR comments, so they did not reach the mailing
list.
On Thu, Jun 4, 2026, Jeff King wrote:
> So I am happy with either v2 or v3.
I also did not see a meaningful performance difference between v2 and v3.
I am happy with either direction and defer to the maintainers on whether
v3's more precise release is worth the added complexity.
On Wed, Jun 3, 2026, Derrick Stolee wrote:
> Did you see any evidence that this change has the intended effect of
> reducing process memory proactively instead of relying on cache evictions?
I do not have strong RSS evidence. The spot checks showed no meaningful RSS
change, and max RSS is not a good signal here because free_base_data()
lowers Git's internal base_cache_used accounting but may not return pages
to the OS or reduce the recorded peak.
The evidence for v3 is therefore structural: it releases the cached data
once all direct children have been dispatched and retain_data reaches zero,
rather than waiting for cache-pressure eviction.
Thanks,
Arijit
^ permalink raw reply
* Re: [PATCH v2] prio-queue: use cascade-down for faster extract-min
From: Kristofer Karlsson @ 2026-06-05 20:39 UTC (permalink / raw)
To: René Scharfe; +Cc: Kristofer Karlsson via GitGitGadget, git
In-Reply-To: <CAL71e4Ob-B5MJ5DPY+_tzpj6nyrbQ5WutxED2T93SWJV6kJGPA@mail.gmail.com>
I did some more benchmarking to understand how these approaches
interact, with four variants based on origin/next on my large monorepo:
1. base: next as-is
2. cascade: base + sift_up_rebalance from this patch (v2)
3. lazy-fold: base + lazy get fusion folded into prio_queue
4. cascade+lazy: both combined
Note that alt 3 is not yet shared with the mailing list so it's hard for you
to reason about it, though it's quite straightforward. I will submit a new
patch for that one soon, not necessarily with the primary goal to merge it,
but rather show how it is implemented.
merge-base --all master master~1000:
base 4.27s
cascade 4.07s (1.05x)
lazy-fold 4.12s (1.03x)
cascade+lazy 4.01s (1.06x)
rev-list --count master~1000..master:
base 3.60s
cascade 3.35s (1.08x)
lazy-fold 3.37s (1.07x)
cascade+lazy 3.30s (1.09x)
So both optimizations are valuable both on their own, and when combined,
which I think helps to reason about it. This cascading sift seems to have a
larger effect, but folding lazy_queue into prio_queue also speeds up other
use cases and simplifies the code a bit.
Based on this, my (very subjective) approach would be:
1. Land this cascade patch first since it's a pure algorithmic improvement,
2. Follow up with a separate patch that folds lazy_queue into
prio_queue. Will post it separately soon, as I mentioned.
- Kristofer
^ permalink raw reply
* Re: [PATCH 0/2] worktree: copy-on-write creation and shared-branch worktrees
From: brian m. carlson @ 2026-06-05 19:59 UTC (permalink / raw)
To: Jason Newton via GitGitGadget; +Cc: git, Jason Newton
In-Reply-To: <pull.2317.git.git.1780685368.gitgitgadget@gmail.com>
[-- Attachment #1: Type: text/plain, Size: 2933 bytes --]
On 2026-06-05 at 18:49:26, Jason Newton via GitGitGadget wrote:
> When many worktrees share one repository -- e .g. a fleet of agents each
> needing an isolated checkout -- "git worktree add" is costly at scale.
> Objects are shared via the common dir, but the working tree is not: each add
> rewrites every tracked file, so N worktrees cost N full checkouts of disk
> and I/O. And a branch can only be checked out in one worktree.
>
> Patch 1 adds "git worktree add --reflink": on a copy-on-write filesystem it
> populates the new worktree by reflinking the current worktree's files and
> index, then "git reset --hard" rewrites only the paths that differ from . A
> reflink_file() helper in copy.c uses FICLONE (Linux) and clonefile()
> (macOS); elsewhere (other filesystems, Windows) it is probed up front and
> falls back to a normal checkout. Defaulting is via the worktree.reflink
> config (true/false/auto); --no-reflink overrides.
Windows apparently has CoW functionality if you use ReFS. I believe Git
LFS has code to do this and you may be interested in checking it out.
Also, how does this work if worktree A is dirty (but `git update-index`
and `git status` have not been run) when the reflink occurs? Does B
have stale files from the working tree? If not, how do we plan on
detecting that? (While I'm curious, this should also be explained in
your commit message because we want to know that you have thought about
this problem and have a good answer for it.)
I was curious as to how this would work with containers, which typically
use overlayfs, but some searching reveals that overlayfs does indeed
support reflinks. Thanks for the opportunity to learn something new
today.
> Patch 2 lets a branch be checked out in several worktrees, for parallel work
> on one checkout. A branch mid-rebase or mid-bisect elsewhere is still
> refused.
So how does this work if you have two worktrees for the same branch, A
and B, and A commits, and then B does? What we don't want to happen is
that because B's worktree is not up to date, it effectively reverts the
changes that A made when adding objects to the index to commit. (Again,
this is a good thing to explain in your commit message, since reviewers
will be curious.)
My personal approach, if I needed many worktrees of the same commit,
would be to create many refs pointing to the same object ID and check
those out. `git update-ref` can perform a single ref transaction with
many refs, which is especially efficient with reftable. That would
avoid the need for multiple checkout support, although I could still see
the utility of reflinking if it can be done safely. If that's a
solution that you think would be valuable, you could propose it as a FAQ
entry or an edit to the manual page, since I'm sure there are other
people with your use case.
--
brian m. carlson (they/them)
Toronto, Ontario, CA
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 325 bytes --]
^ permalink raw reply
* [PATCH 2/2] worktree: allow sharing a checked-out branch across worktrees
From: Jason Newton via GitGitGadget @ 2026-06-05 18:49 UTC (permalink / raw)
To: git; +Cc: Jason Newton, Jason Newton
In-Reply-To: <pull.2317.git.git.1780685368.gitgitgadget@gmail.com>
From: Jason Newton <nevion@gmail.com>
When spinning up several worktrees on the same checkout for parallel
work (for example a fleet of agents working from one branch), git's
refusal to check out a branch that is already checked out elsewhere is
just in the way. The restriction exists to stop two worktrees from
moving the same branch underneath each other, but plain parallel
checkouts do not need that protection.
Drop the restriction: "git worktree add <branch>" now checks out a
branch even if it is in use by another worktree. The genuinely
dangerous case is kept -- a branch that another worktree is in the
middle of rebasing or bisecting is still refused, because a second
checkout could corrupt that operation. die_if_branch_busy() performs
that narrower check in place of the old die_if_checked_out(). The
separate guard against force-updating (e.g. with -B) a branch in use
elsewhere is left untouched.
Signed-off-by: Jason Newton <nevion@gmail.com>
---
Documentation/git-worktree.adoc | 17 +++++++++--------
builtin/worktree.c | 30 +++++++++++++++++++++++++++++-
t/t2400-worktree-add.sh | 31 ++++++++++++++++++++++++-------
3 files changed, 62 insertions(+), 16 deletions(-)
diff --git a/Documentation/git-worktree.adoc b/Documentation/git-worktree.adoc
index 1ca81718b7..cc4c91b787 100644
--- a/Documentation/git-worktree.adoc
+++ b/Documentation/git-worktree.adoc
@@ -93,8 +93,9 @@ then, as a convenience, the new worktree is associated with a branch (call
it _<branch>_) named after `$(basename <path>)`. If _<branch>_ doesn't
exist, a new branch based on `HEAD` is automatically created as if
`-b <branch>` was given. If _<branch>_ does exist, it will be checked out
-in the new worktree, if it's not checked out anywhere else, otherwise the
-command will refuse to create the worktree (unless `--force` is used).
+in the new worktree, even if it is already checked out in another worktree.
+(A branch that another worktree is in the middle of rebasing or bisecting is
+refused unless `--force` is used.)
+
If _<commit-ish>_ is omitted, neither `--detach`, or `--orphan` is
used, and there are no valid local branches (or remote branches if
@@ -177,12 +178,12 @@ OPTIONS
`-f`::
`--force`::
- By default, `add` refuses to create a new worktree when
- _<commit-ish>_ is a branch name and is already checked out by
- another worktree, or if _<path>_ is already assigned to some
- worktree but is missing (for instance, if _<path>_ was deleted
- manually). This option overrides these safeguards. To add a missing but
- locked worktree path, specify `--force` twice.
+ `add` refuses to create a new worktree when _<commit-ish>_ is a
+ branch that another worktree is in the middle of rebasing or
+ bisecting, or if _<path>_ is already assigned to some worktree but
+ is missing (for instance, if _<path>_ was deleted manually). This
+ option overrides these safeguards. To add a missing but locked
+ worktree path, specify `--force` twice.
+
`move` refuses to move a locked worktree unless `--force` is specified
twice. If the destination is already assigned to some other worktree but is
diff --git a/builtin/worktree.c b/builtin/worktree.c
index 973da33051..b457b015d1 100644
--- a/builtin/worktree.c
+++ b/builtin/worktree.c
@@ -648,6 +648,34 @@ static void setup_alternate_ref_dir(struct worktree *wt, const char *wt_git_path
strbuf_release(&sb);
}
+/*
+ * Checking out a branch that is already checked out in another worktree is
+ * fine -- it is exactly what you want when spinning up several worktrees on
+ * the same checkout for parallel work. The one case that is still unsafe is a
+ * branch that another worktree is in the middle of rebasing or bisecting,
+ * since a second checkout could corrupt that operation, so refuse only that.
+ */
+static void die_if_branch_busy(const char *branch)
+{
+ struct worktree **worktrees = get_worktrees();
+ int i;
+
+ for (i = 0; worktrees[i]; i++) {
+ const struct worktree *wt = worktrees[i];
+
+ if (is_worktree_being_rebased(wt, branch) ||
+ is_worktree_being_bisected(wt, branch)) {
+ const char *shortname = branch;
+
+ skip_prefix(branch, "refs/heads/", &shortname);
+ die(_("'%s' is already used by worktree at '%s'"),
+ shortname, wt->path);
+ }
+ }
+
+ free_worktrees(worktrees);
+}
+
static int add_worktree(const char *path, const char *refname,
const struct add_opts *opts)
{
@@ -675,7 +703,7 @@ static int add_worktree(const char *path, const char *refname,
refs_ref_exists(get_main_ref_store(the_repository), symref.buf)) {
is_branch = 1;
if (!opts->force)
- die_if_checked_out(symref.buf, 0);
+ die_if_branch_busy(symref.buf);
}
commit = lookup_commit_reference_by_name(refname);
if (!commit && !opts->orphan)
diff --git a/t/t2400-worktree-add.sh b/t/t2400-worktree-add.sh
index 56fb79179a..6a1eb72ac7 100755
--- a/t/t2400-worktree-add.sh
+++ b/t/t2400-worktree-add.sh
@@ -40,10 +40,24 @@ test_expect_success '"add" using - shorthand' '
test_cmp expect actual
'
-test_expect_success '"add" refuses to checkout locked branch' '
- test_must_fail git worktree add zere main &&
- test_path_is_missing zere &&
- test_path_is_missing .git/worktrees/zere
+test_expect_success '"add" can check out a branch in use by another worktree' '
+ test_when_finished "git worktree remove -f zere || :" &&
+ git worktree add zere main &&
+ echo refs/heads/main >expect &&
+ git -C zere symbolic-ref HEAD >actual &&
+ test_cmp expect actual
+'
+
+test_expect_success 'the same branch can be checked out in several worktrees' '
+ test_when_finished "git worktree remove -f shared1 || :; git worktree remove -f shared2 || :" &&
+ git branch -f sharedbr main &&
+ git worktree add shared1 sharedbr &&
+ git worktree add shared2 sharedbr &&
+ echo refs/heads/sharedbr >expect &&
+ git -C shared1 symbolic-ref HEAD >actual &&
+ test_cmp expect actual &&
+ git -C shared2 symbolic-ref HEAD >actual &&
+ test_cmp expect actual
'
test_expect_success 'checking out paths not complaining about linked checkouts' '
@@ -304,10 +318,13 @@ test_expect_success '"add" checks out existing branch of dwimd name' '
)
'
-test_expect_success '"add <path>" dwim fails with checked out branch' '
+test_expect_success '"add <path>" dwim shares a checked out branch' '
git checkout -b test-branch &&
- test_must_fail git worktree add test-branch &&
- test_path_is_missing test-branch
+ git worktree add test-branch &&
+ echo refs/heads/test-branch >expect &&
+ git -C test-branch symbolic-ref HEAD >actual &&
+ test_cmp expect actual &&
+ git worktree remove test-branch
'
test_expect_success '"add --force" with existing dwimd name doesnt die' '
--
gitgitgadget
^ permalink raw reply related
* [PATCH 1/2] worktree: add --reflink for copy-on-write worktree creation
From: Jason Newton via GitGitGadget @ 2026-06-05 18:49 UTC (permalink / raw)
To: git; +Cc: Jason Newton, Jason Newton
In-Reply-To: <pull.2317.git.git.1780685368.gitgitgadget@gmail.com>
From: Jason Newton <nevion@gmail.com>
Creating many worktrees from the same base -- for example to run a
fleet of automated agents in parallel -- is expensive today: every
"git worktree add" materializes the entire working tree by writing
each tracked file out from the object store. The objects are shared
via the common directory, but the working tree is not: N worktrees
mean N full checkouts on disk and N times the file I/O.
Add a "--reflink" option that, on copy-on-write filesystems, populates
the new worktree by reflinking the current worktree's files and index
instead. The subsequent "git reset --hard" then only rewrites the
paths that actually differ between the current worktree and
<commit-ish>; everything else (including untracked files such as build
outputs) keeps sharing storage with the source until modified. Because
the cloned index still carries the source files' stat data, it is
refreshed against the reflinked files first so that reset recognizes
the unchanged paths as up to date and leaves them sharing extents
rather than rewriting them.
The clones are made by a new reflink_file() helper in copy.c, which
uses the FICLONE ioctl on Linux and clonefile() on macOS and reports
an error otherwise so callers fall back to a normal copy. Support is
probed up front; when unavailable -- including on filesystems without
copy-on-write and on platforms such as Windows that lack a reflink
primitive -- "--reflink" transparently falls back to an ordinary
checkout, so the worst case is no slower than today rather than a
byte-for-byte copy of the source tree. The directory walk skips the
new worktree itself when it lives inside the source one, and preserves
symlinks and modes.
The behavior can be made the default with the worktree.reflink
configuration ("true", "false" or "auto", the last suppressing the
unsupported-filesystem warning), and turned off per-invocation with
--no-reflink. A configured default degrades quietly in modes that
cannot reflink (--orphan, --no-checkout) instead of erroring, so
enabling it never breaks those commands. The checkout step continues
to honor checkout.workers, so parallel checkout composes with
--reflink for the paths that do need rewriting.
Signed-off-by: Jason Newton <nevion@gmail.com>
---
Documentation/config/worktree.adoc | 10 ++
Documentation/git-worktree.adoc | 30 +++-
builtin/worktree.c | 227 ++++++++++++++++++++++++++++-
copy.c | 65 +++++++++
copy.h | 13 ++
t/t2400-worktree-add.sh | 88 +++++++++++
6 files changed, 431 insertions(+), 2 deletions(-)
diff --git a/Documentation/config/worktree.adoc b/Documentation/config/worktree.adoc
index a248076ea5..d3a03c86d4 100644
--- a/Documentation/config/worktree.adoc
+++ b/Documentation/config/worktree.adoc
@@ -17,3 +17,13 @@
Note that setting `worktree.useRelativePaths` to "`true`" implies enabling the
`extensions.relativeWorktrees` config (see linkgit:git-config[1]),
thus making it incompatible with older versions of Git.
+
+`worktree.reflink`::
+ Controls whether `git worktree add` populates new worktrees with
+ copy-on-write (reflink) clones, as if `--reflink` had been given
+ (see linkgit:git-worktree[1]). May be set to "`true`", "`false`"
+ (the default), or "`auto`". With "`true`", a filesystem that does
+ not support reflinks produces a warning before falling back to an
+ ordinary checkout; with "`auto`", the fallback is silent. An
+ explicit `--reflink` or `--no-reflink` on the command line
+ overrides this setting.
diff --git a/Documentation/git-worktree.adoc b/Documentation/git-worktree.adoc
index fbf8426cd9..1ca81718b7 100644
--- a/Documentation/git-worktree.adoc
+++ b/Documentation/git-worktree.adoc
@@ -10,7 +10,7 @@ SYNOPSIS
--------
[synopsis]
git worktree add [-f] [--detach] [--checkout] [--lock [--reason <string>]]
- [--orphan] [(-b | -B) <new-branch>] <path> [<commit-ish>]
+ [--orphan] [--reflink] [(-b | -B) <new-branch>] <path> [<commit-ish>]
git worktree list [-v | --porcelain [-z]]
git worktree lock [--reason <string>] <worktree>
git worktree move <worktree> <new-path>
@@ -213,6 +213,34 @@ To remove a locked worktree, specify `--force` twice.
such as configuring sparse-checkout. See "Sparse checkout"
in linkgit:git-read-tree[1].
+`--reflink`::
+`--no-reflink`::
+ Populate the new worktree by creating copy-on-write (reflink)
+ clones of the current worktree's files and index instead of
+ writing every file out from the object store. The checkout that
+ follows then only has to rewrite the paths that actually differ
+ between the current worktree and _<commit-ish>_; everything else
+ (including untracked files such as build outputs) keeps sharing
+ storage with the source worktree until modified. This makes
+ `add` much faster and far cheaper on disk when creating many
+ worktrees from the same base. `--no-reflink` forces an ordinary
+ checkout, overriding the `worktree.reflink` configuration.
++
+Reflinks require a copy-on-write filesystem (for example btrfs, XFS,
+bcachefs or ZFS on Linux, or APFS on macOS). On filesystems or platforms
+that do not support reflinks, `--reflink` transparently falls back to an
+ordinary checkout. Because the source worktree's untracked and ignored
+files are cloned as well, only use `--reflink` when that is acceptable.
++
+This option cannot be combined with `--no-checkout` or `--orphan`. It can
+be enabled by default with the `worktree.reflink` configuration; see
+linkgit:git-config[1].
++
+The checkout that populates a new worktree also honors the
+`checkout.workers` configuration (see linkgit:git-config[1]), so setting it
+parallelizes the file writes and can further speed up `add`, with or
+without `--reflink`.
+
`--guess-remote`::
`--no-guess-remote`::
With `worktree add <path>`, without _<commit-ish>_, instead
diff --git a/builtin/worktree.c b/builtin/worktree.c
index d21c43fde3..973da33051 100644
--- a/builtin/worktree.c
+++ b/builtin/worktree.c
@@ -30,7 +30,7 @@
#define BUILTIN_WORKTREE_ADD_USAGE \
N_("git worktree add [-f] [--detach] [--checkout] [--lock [--reason <string>]]\n" \
- " [--orphan] [(-b | -B) <new-branch>] <path> [<commit-ish>]")
+ " [--orphan] [--reflink] [(-b | -B) <new-branch>] <path> [<commit-ish>]")
#define BUILTIN_WORKTREE_LIST_USAGE \
N_("git worktree list [-v | --porcelain [-z]]")
@@ -47,6 +47,11 @@
#define BUILTIN_WORKTREE_UNLOCK_USAGE \
N_("git worktree unlock <worktree>")
+/* values for add_opts.reflink and the worktree.reflink config */
+#define REFLINK_OFF 0
+#define REFLINK_ON 1 /* warn and fall back if unsupported */
+#define REFLINK_AUTO 2 /* silently fall back if unsupported */
+
#define WORKTREE_ADD_DWIM_ORPHAN_INFER_TEXT \
_("No possible source branch, inferring '--orphan'")
@@ -123,6 +128,7 @@ struct add_opts {
int checkout;
int orphan;
int relative_paths;
+ int reflink;
const char *keep_locked;
};
@@ -130,6 +136,7 @@ static int show_only;
static int verbose;
static int guess_remote;
static int use_relative_paths;
+static int reflink_config = REFLINK_OFF;
static timestamp_t expire;
static int git_worktree_config(const char *var, const char *value,
@@ -141,6 +148,13 @@ static int git_worktree_config(const char *var, const char *value,
} else if (!strcmp(var, "worktree.userelativepaths")) {
use_relative_paths = git_config_bool(var, value);
return 0;
+ } else if (!strcmp(var, "worktree.reflink")) {
+ if (value && !strcmp(value, "auto"))
+ reflink_config = REFLINK_AUTO;
+ else
+ reflink_config = git_config_bool(var, value) ?
+ REFLINK_ON : REFLINK_OFF;
+ return 0;
}
return git_default_config(var, value, ctx, cb);
@@ -397,6 +411,182 @@ worktree_copy_cleanup:
free(to_file);
}
+/*
+ * Probe whether the filesystem backing "dir" supports reflinks. We do this
+ * once up front so that, on filesystems without copy-on-write support (or on
+ * platforms such as Windows that lack a reflink primitive entirely), we can
+ * fall back to a normal checkout instead of byte-copying the whole source
+ * working tree -- which would include untracked files and be slower than the
+ * checkout we are trying to avoid.
+ */
+static int reflink_supported(const char *dir)
+{
+ struct strbuf src = STRBUF_INIT, dst = STRBUF_INIT;
+ int fd, ok = 0;
+
+ strbuf_addf(&src, "%s/.git-reflink-probe-src", dir);
+ strbuf_addf(&dst, "%s/.git-reflink-probe-dst", dir);
+
+ fd = open(src.buf, O_WRONLY | O_CREAT | O_TRUNC, 0600);
+ if (fd >= 0) {
+ write_in_full(fd, "x", 1);
+ close(fd);
+ if (!reflink_file(dst.buf, src.buf, 0600))
+ ok = 1;
+ unlink(dst.buf);
+ }
+ unlink(src.buf);
+
+ strbuf_release(&src);
+ strbuf_release(&dst);
+ return ok;
+}
+
+/*
+ * Reflink a single regular file, falling back to a regular copy when the
+ * clone fails for this particular file (for example across mount points).
+ */
+static int reflink_or_copy(const char *dst, const char *src, int mode)
+{
+ if (!reflink_file(dst, src, mode))
+ return 0;
+ return copy_file(dst, src, mode);
+}
+
+/*
+ * Recursively copy the working-tree directory "src" into "dst" using reflinks
+ * for regular files. Directory entries that resolve to the destination
+ * worktree itself (identified by skip_dev/skip_ino, which matters when the new
+ * worktree lives inside the source one) and the top-level ".git" gitfile are
+ * skipped.
+ */
+static int reflink_tree(const char *src, const char *dst,
+ dev_t skip_dev, ino_t skip_ino, int top)
+{
+ struct strbuf s = STRBUF_INIT, d = STRBUF_INIT;
+ DIR *dir;
+ struct dirent *de;
+ int ret = 0;
+
+ dir = opendir(src);
+ if (!dir)
+ return error_errno(_("could not open directory '%s'"), src);
+
+ while (!ret && (de = readdir(dir))) {
+ struct stat st;
+
+ if (is_dot_or_dotdot(de->d_name))
+ continue;
+ if (top && !strcmp(de->d_name, ".git"))
+ continue;
+
+ strbuf_reset(&s);
+ strbuf_addf(&s, "%s/%s", src, de->d_name);
+ strbuf_reset(&d);
+ strbuf_addf(&d, "%s/%s", dst, de->d_name);
+
+ if (lstat(s.buf, &st)) {
+ ret = error_errno(_("could not stat '%s'"), s.buf);
+ break;
+ }
+
+ if (S_ISDIR(st.st_mode)) {
+ /* never recurse into the new worktree itself */
+ if (st.st_dev == skip_dev && st.st_ino == skip_ino)
+ continue;
+ if (mkdir(d.buf, st.st_mode & 07777) && errno != EEXIST) {
+ ret = error_errno(_("could not create directory '%s'"), d.buf);
+ break;
+ }
+ ret = reflink_tree(s.buf, d.buf, skip_dev, skip_ino, 0);
+ } else if (S_ISLNK(st.st_mode)) {
+ struct strbuf link = STRBUF_INIT;
+
+ if (strbuf_readlink(&link, s.buf, st.st_size))
+ ret = error_errno(_("could not read symlink '%s'"), s.buf);
+ else if (symlink(link.buf, d.buf))
+ ret = error_errno(_("could not create symlink '%s'"), d.buf);
+ strbuf_release(&link);
+ } else if (S_ISREG(st.st_mode)) {
+ if (reflink_or_copy(d.buf, s.buf, st.st_mode))
+ ret = error_errno(_("could not copy '%s' to '%s'"),
+ s.buf, d.buf);
+ }
+ /* silently skip fifos, sockets and device nodes */
+ }
+
+ closedir(dir);
+ strbuf_release(&s);
+ strbuf_release(&d);
+ return ret;
+}
+
+/*
+ * Populate the new worktree at "path" by reflinking the current worktree's
+ * files and index. The subsequent "git reset --hard" then only has to rewrite
+ * the paths that actually differ between the source and <commit-ish>, leaving
+ * everything else sharing storage with the source. Returns 1 when reflinks are
+ * unavailable so the caller can fall back to a plain checkout.
+ */
+static int reflink_worktree(const char *path, const char *wt_git_dir,
+ const struct add_opts *opts, struct strvec *child_env)
+{
+ const char *src_wt = the_repository->worktree;
+ char *src_index = NULL, *dst_index = NULL;
+ struct stat dst_st;
+ int ret = 0;
+
+ if (!src_wt)
+ return error(_("--reflink needs a source working tree, but this "
+ "repository does not have one"));
+
+ if (!reflink_supported(path)) {
+ /* In auto mode the fallback is expected, so stay quiet. */
+ if (!opts->quiet && opts->reflink != REFLINK_AUTO)
+ warning(_("the filesystem at '%s' does not support reflinks; "
+ "falling back to a regular checkout"), path);
+ return 1;
+ }
+
+ if (stat(path, &dst_st))
+ return error_errno(_("could not stat '%s'"), path);
+
+ if ((ret = reflink_tree(src_wt, path, dst_st.st_dev, dst_st.st_ino, 1)))
+ return ret;
+
+ /*
+ * Clone the source index so the following reset sees the source's
+ * state and only materializes the differences to <commit-ish>.
+ */
+ src_index = repo_git_path(the_repository, "index");
+ dst_index = xstrfmt("%s/index", wt_git_dir);
+ if (!access(src_index, F_OK) &&
+ reflink_or_copy(dst_index, src_index, 0666)) {
+ ret = error_errno(_("could not copy index to '%s'"), dst_index);
+ goto out;
+ }
+
+ /*
+ * The cloned index still carries the source files' stat information.
+ * Refresh it against the freshly reflinked files so that "git reset"
+ * recognizes unchanged paths as up to date and leaves them sharing
+ * storage instead of rewriting (and thus un-sharing) them.
+ */
+ if (!access(dst_index, F_OK)) {
+ struct child_process cp = CHILD_PROCESS_INIT;
+ cp.git_cmd = 1;
+ strvec_pushl(&cp.args, "update-index", "-q", "--refresh", NULL);
+ strvec_pushv(&cp.env, child_env->v);
+ /* a dirty working tree is not an error here */
+ run_command(&cp);
+ }
+
+out:
+ free(src_index);
+ free(dst_index);
+ return ret;
+}
+
static int checkout_worktree(const struct add_opts *opts,
struct strvec *child_env)
{
@@ -589,6 +779,20 @@ static int add_worktree(const char *path, const char *refname,
(ret = make_worktree_orphan(refname, opts, &child_env)))
goto done;
+ /*
+ * When --reflink is requested and the filesystem supports it, copy the
+ * current worktree (and its index) into the new one using copy-on-write
+ * clones. checkout_worktree() then only rewrites the paths that differ
+ * from <commit-ish>. reflink_worktree() returns 1 when reflinks are not
+ * available, in which case we just do an ordinary checkout below.
+ */
+ if (opts->checkout && opts->reflink) {
+ ret = reflink_worktree(path, sb_repo.buf, opts, &child_env);
+ if (ret < 0)
+ goto done;
+ ret = 0;
+ }
+
if (opts->checkout &&
(ret = checkout_worktree(opts, &child_env)))
goto done;
@@ -801,6 +1005,7 @@ static int add(int ac, const char **av, const char *prefix,
const char *lock_reason = NULL;
int keep_locked = 0;
int used_new_branch_options;
+ int reflink_cli = -1;
struct option options[] = {
OPT__FORCE(&opts.force,
N_("checkout <branch> even if already checked out in other worktree"),
@@ -823,6 +1028,8 @@ static int add(int ac, const char **av, const char *prefix,
N_("try to match the new branch name with a remote-tracking branch")),
OPT_BOOL(0, "relative-paths", &opts.relative_paths,
N_("use relative paths for worktrees")),
+ OPT_BOOL(0, "reflink", &reflink_cli,
+ N_("populate the worktree using copy-on-write clones when supported")),
OPT_END()
};
int ret;
@@ -842,6 +1049,24 @@ static int add(int ac, const char **av, const char *prefix,
if (opts.orphan && !opts.checkout)
die(_("options '%s' and '%s' cannot be used together"),
"--orphan", "--no-checkout");
+
+ /*
+ * Resolve whether to reflink: an explicit --reflink/--no-reflink on
+ * the command line wins, otherwise fall back to the worktree.reflink
+ * configuration (which may select the "auto" mode).
+ */
+ opts.reflink = (reflink_cli != -1) ? reflink_cli : reflink_config;
+ if (opts.reflink && (opts.orphan || !opts.checkout)) {
+ /*
+ * Reflinking is incompatible with these; only complain when it
+ * was explicitly requested, otherwise quietly do a plain
+ * checkout so a configured default does not break these modes.
+ */
+ if (reflink_cli == REFLINK_ON)
+ die(_("options '%s' and '%s' cannot be used together"),
+ "--reflink", opts.orphan ? "--orphan" : "--no-checkout");
+ opts.reflink = REFLINK_OFF;
+ }
if (opts.orphan && ac == 2)
die(_("option '%s' and commit-ish cannot be used together"),
"--orphan");
diff --git a/copy.c b/copy.c
index b668209b6c..d2c8ce5209 100644
--- a/copy.c
+++ b/copy.c
@@ -7,6 +7,21 @@
#include "strbuf.h"
#include "abspath.h"
+#if defined(__linux__)
+#include <sys/ioctl.h>
+/*
+ * FICLONE lives in <linux/fs.h>, but including that header tends to clash
+ * with the libc headers git already pulls in, so define it ourselves if it
+ * is missing. The value is part of the stable kernel uapi.
+ */
+#ifndef FICLONE
+#define FICLONE _IOW(0x94, 9, int)
+#endif
+#elif defined(__APPLE__)
+#include <sys/attr.h>
+#include <sys/clonefile.h>
+#endif
+
int copy_fd(int ifd, int ofd)
{
while (1) {
@@ -72,3 +87,53 @@ int copy_file_with_time(const char *dst, const char *src, int mode)
return copy_times(dst, src);
return status;
}
+
+int reflink_file(const char *dst, const char *src, int mode)
+{
+#if defined(__APPLE__)
+ /*
+ * clonefile() refuses to operate when the destination exists and
+ * copies the source's permissions for us, so "mode" is unused here.
+ */
+ (void)mode;
+ if (clonefile(src, dst, 0) < 0)
+ return -1;
+ if (adjust_shared_perm(the_repository, dst))
+ return -1;
+ return 0;
+#elif defined(__linux__)
+ int fdi, fdo, status;
+
+ mode = (mode & 0111) ? 0777 : 0666;
+ if ((fdi = open(src, O_RDONLY)) < 0)
+ return -1;
+ if ((fdo = open(dst, O_WRONLY | O_CREAT | O_EXCL, mode)) < 0) {
+ int saved = errno;
+ close(fdi);
+ errno = saved;
+ return -1;
+ }
+ status = ioctl(fdo, FICLONE, fdi);
+ close(fdi);
+ if (status < 0) {
+ int saved = errno;
+ close(fdo);
+ /* we created an empty file above; do not leave it behind */
+ unlink(dst);
+ errno = saved;
+ return -1;
+ }
+ if (close(fdo) != 0)
+ return -1;
+ if (adjust_shared_perm(the_repository, dst))
+ return -1;
+ return 0;
+#else
+ /* No reflink support on this platform (e.g. Windows). */
+ (void)dst;
+ (void)src;
+ (void)mode;
+ errno = ENOSYS;
+ return -1;
+#endif
+}
diff --git a/copy.h b/copy.h
index 2af77cba86..a8646f7ff5 100644
--- a/copy.h
+++ b/copy.h
@@ -7,4 +7,17 @@ int copy_fd(int ifd, int ofd);
int copy_file(const char *dst, const char *src, int mode);
int copy_file_with_time(const char *dst, const char *src, int mode);
+/*
+ * Create "dst" as a copy-on-write (reflink) clone of the regular file
+ * "src", so that the two files share their data blocks until one of
+ * them is modified. "dst" must not already exist.
+ *
+ * This only succeeds on filesystems that support block cloning (e.g.
+ * btrfs, XFS or bcachefs on Linux, APFS on macOS). When the platform or
+ * filesystem does not support reflinks, -1 is returned with errno set to
+ * ENOSYS (or the underlying error). Callers are expected to fall back to
+ * copy_file() in that case. Returns 0 on success.
+ */
+int reflink_file(const char *dst, const char *src, int mode);
+
#endif /* COPY_H */
diff --git a/t/t2400-worktree-add.sh b/t/t2400-worktree-add.sh
index 58b4445cc4..56fb79179a 100755
--- a/t/t2400-worktree-add.sh
+++ b/t/t2400-worktree-add.sh
@@ -1248,4 +1248,92 @@ test_expect_success 'relative worktree sets extension config' '
test_cmp_config -C repo true extensions.relativeworktrees
'
+test_expect_success '--reflink produces a correct checkout on any filesystem' '
+ test_when_finished "rm -rf reflinkrepo" &&
+ git init reflinkrepo &&
+ (
+ cd reflinkrepo &&
+ test_commit base file.txt base &&
+ test_commit next file.txt next &&
+ git worktree add --reflink wt -b reflinkbr base &&
+ echo base >expect &&
+ test_cmp expect wt/file.txt &&
+ git -C wt status --porcelain >status &&
+ test_must_be_empty status
+ )
+'
+
+test_expect_success '--reflink rejects incompatible options' '
+ test_must_fail git worktree add --reflink --no-checkout wt-bad HEAD 2>err &&
+ test_grep "cannot be used together" err &&
+ test_must_fail git worktree add --reflink --orphan wt-bad2 2>err &&
+ test_grep "cannot be used together" err
+'
+
+test_expect_success 'worktree.reflink config drives a correct checkout' '
+ test_when_finished "rm -rf reflinkcfg" &&
+ git init reflinkcfg &&
+ (
+ cd reflinkcfg &&
+ test_commit cfg file.txt value &&
+ git -c worktree.reflink=true worktree add wt HEAD &&
+ echo value >expect &&
+ test_cmp expect wt/file.txt
+ )
+'
+
+test_expect_success 'worktree.reflink=auto does not break --orphan' '
+ test_when_finished "rm -rf reflinkorphan" &&
+ git init reflinkorphan &&
+ (
+ cd reflinkorphan &&
+ test_commit base file.txt value &&
+ git -c worktree.reflink=auto worktree add --orphan wt &&
+ git -C wt symbolic-ref --short HEAD >actual &&
+ echo wt >expect &&
+ test_cmp expect actual
+ )
+'
+
+test_expect_success '--no-reflink overrides worktree.reflink' '
+ test_when_finished "rm -rf reflinkoff" &&
+ git init reflinkoff &&
+ (
+ cd reflinkoff &&
+ test_commit base file.txt value &&
+ git -c worktree.reflink=true worktree add --no-reflink wt HEAD &&
+ echo value >expect &&
+ test_cmp expect wt/file.txt
+ )
+'
+
+# Reflinks are only available on copy-on-write filesystems (btrfs, XFS,
+# bcachefs, APFS, ...). Where they are unavailable, --reflink transparently
+# falls back to a regular checkout, which the test above already covers.
+test_lazy_prereq REFLINK '
+ echo probe >reflink-src &&
+ cp --reflink=always reflink-src reflink-dst 2>/dev/null
+'
+
+test_expect_success REFLINK '--reflink carries untracked files and reconciles changes' '
+ test_when_finished "rm -rf cowrepo" &&
+ git init cowrepo &&
+ (
+ cd cowrepo &&
+ test_commit same same.txt content &&
+ test_commit old change.txt old-value &&
+ test_commit new change.txt new-value &&
+ echo artifact >untracked.bin &&
+ git worktree add --reflink wt -b cowbr old &&
+ echo content >expect &&
+ test_cmp expect wt/same.txt &&
+ echo old-value >expect &&
+ test_cmp expect wt/change.txt &&
+ echo artifact >expect &&
+ test_cmp expect wt/untracked.bin &&
+ git -C wt status --porcelain >status &&
+ grep "?? untracked.bin" status
+ )
+'
+
test_done
--
gitgitgadget
^ permalink raw reply related
* [PATCH 0/2] worktree: copy-on-write creation and shared-branch worktrees
From: Jason Newton via GitGitGadget @ 2026-06-05 18:49 UTC (permalink / raw)
To: git; +Cc: Jason Newton
When many worktrees share one repository -- e .g. a fleet of agents each
needing an isolated checkout -- "git worktree add" is costly at scale.
Objects are shared via the common dir, but the working tree is not: each add
rewrites every tracked file, so N worktrees cost N full checkouts of disk
and I/O. And a branch can only be checked out in one worktree.
Patch 1 adds "git worktree add --reflink": on a copy-on-write filesystem it
populates the new worktree by reflinking the current worktree's files and
index, then "git reset --hard" rewrites only the paths that differ from . A
reflink_file() helper in copy.c uses FICLONE (Linux) and clonefile()
(macOS); elsewhere (other filesystems, Windows) it is probed up front and
falls back to a normal checkout. Defaulting is via the worktree.reflink
config (true/false/auto); --no-reflink overrides.
Patch 2 lets a branch be checked out in several worktrees, for parallel work
on one checkout. A branch mid-rebase or mid-bisect elsewhere is still
refused.
Benchmark (Linux-kernel fork, 93k files, ~33 GB tree incl. build output,
btrfs): a normal add allocates ~0.9 GB of real disk per worktree (~5.3 GB
for four, linear); --reflink allocates ~0 at any count and also carries the
untracked build tree. ("Real disk" = btrfs exclusive bytes.)
worktree-reflink-bench
[https://github.com/user-attachments/assets/e3e721c8-2206-4b78-ad08-21677ef30753]
Note: patch 2 changes a default (same-branch checkout now allowed); two
t2400 assertions were updated accordingly.
Jason Newton (2):
worktree: add --reflink for copy-on-write worktree creation
worktree: allow sharing a checked-out branch across worktrees
Documentation/config/worktree.adoc | 10 ++
Documentation/git-worktree.adoc | 47 +++++-
builtin/worktree.c | 257 ++++++++++++++++++++++++++++-
copy.c | 65 ++++++++
copy.h | 13 ++
t/t2400-worktree-add.sh | 119 ++++++++++++-
6 files changed, 493 insertions(+), 18 deletions(-)
base-commit: c69baaf57ba26cf117c2b6793802877f19738b0d
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-2317%2Fnevion%2Fworktree-reflink-cow-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-2317/nevion/worktree-reflink-cow-v1
Pull-Request: https://github.com/git/git/pull/2317
--
gitgitgadget
^ permalink raw reply
* [PATCH v13 6/6] branch: add --dry-run for --prune-merged
From: Harald Nordgren via GitGitGadget @ 2026-06-05 18:35 UTC (permalink / raw)
To: git
Cc: Kristoffer Haugsbakk, Johannes Sixt, Phillip Wood,
Harald Nordgren, Harald Nordgren
In-Reply-To: <pull.2285.v13.git.git.1780684553.gitgitgadget@gmail.com>
From: Harald Nordgren <haraldnordgren@gmail.com>
With --dry-run, --prune-merged prints the local branches it would
delete, one "Would delete branch <name>" line each, and exits
without touching any ref. The same filtering applies, so the output
is exactly the set that the real run would delete.
--dry-run is only meaningful together with --prune-merged and is
rejected otherwise.
Signed-off-by: Harald Nordgren <haraldnordgren@gmail.com>
---
Documentation/git-branch.adoc | 8 ++++++-
builtin/branch.c | 13 ++++++++---
t/t3200-branch.sh | 44 +++++++++++++++++++++++++++++++++++
3 files changed, 61 insertions(+), 4 deletions(-)
diff --git a/Documentation/git-branch.adoc b/Documentation/git-branch.adoc
index 5c43dc55a8..1f49a831fd 100644
--- a/Documentation/git-branch.adoc
+++ b/Documentation/git-branch.adoc
@@ -25,7 +25,7 @@ git branch (-m|-M) [<old-branch>] <new-branch>
git branch (-c|-C) [<old-branch>] <new-branch>
git branch (-d|-D) [-r] <branch-name>...
git branch --edit-description [<branch-name>]
-git branch --prune-merged <branch>...
+git branch [--dry-run] --prune-merged <branch>...
DESCRIPTION
-----------
@@ -226,6 +226,12 @@ Branches refused by the "fully merged" safety check are listed as
warnings and skipped; pass them to `git branch -D` explicitly if
you want them gone.
+`--dry-run`::
+ With `--prune-merged`, print which branches would be
+ deleted and exit without touching any ref. Useful for
+ sanity-checking a wide pattern like `'origin/*'` before
+ committing to the deletion.
+
`-v`::
`-vv`::
`--verbose`::
diff --git a/builtin/branch.c b/builtin/branch.c
index be4218ded3..98e56d4ff8 100644
--- a/builtin/branch.c
+++ b/builtin/branch.c
@@ -715,7 +715,7 @@ static int parse_opt_forked(const struct option *opt, const char *arg, int unset
}
static int prune_merged_branches(int argc, const char **argv,
- int quiet)
+ int quiet, int dry_run)
{
struct ref_store *refs = get_main_ref_store(the_repository);
struct ref_filter filter = REF_FILTER_INIT;
@@ -775,7 +775,8 @@ static int prune_merged_branches(int argc, const char **argv,
FILTER_REFS_BRANCHES,
DELETE_BRANCH_WARN_ONLY |
DELETE_BRANCH_NO_HEAD_FALLBACK |
- (quiet ? DELETE_BRANCH_QUIET : 0));
+ (quiet ? DELETE_BRANCH_QUIET : 0) |
+ (dry_run ? DELETE_BRANCH_DRY_RUN : 0));
strvec_clear(&deletable);
ref_array_clear(&candidates);
@@ -825,6 +826,7 @@ int cmd_branch(int argc,
int delete = 0, rename = 0, copy = 0, list = 0,
unset_upstream = 0, show_current = 0, edit_description = 0;
int prune_merged = 0;
+ int dry_run = 0;
const char *new_upstream = NULL;
int noncreate_actions = 0;
/* possible options */
@@ -880,6 +882,8 @@ int cmd_branch(int argc,
N_("edit the description for the branch")),
OPT_BOOL(0, "prune-merged", &prune_merged,
N_("delete local branches whose upstream matches <branch> and is merged")),
+ OPT_BOOL(0, "dry-run", &dry_run,
+ N_("with --prune-merged, only print which branches would be deleted")),
OPT__FORCE(&force, N_("force creation, move/rename, deletion"), PARSE_OPT_NOCOMPLETE),
OPT_MERGED(&filter, N_("print only branches that are merged")),
OPT_NO_MERGED(&filter, N_("print only branches that are not merged")),
@@ -942,6 +946,9 @@ int cmd_branch(int argc,
if (noncreate_actions > 1)
usage_with_options(builtin_branch_usage, options);
+ if (dry_run && !prune_merged)
+ die(_("--dry-run requires --prune-merged"));
+
if (recurse_submodules_explicit) {
if (!submodule_propagate_branches)
die(_("branch with --recurse-submodules can only be used if submodule.propagateBranches is enabled"));
@@ -981,7 +988,7 @@ int cmd_branch(int argc,
(quiet ? DELETE_BRANCH_QUIET : 0));
goto out;
} else if (prune_merged) {
- ret = prune_merged_branches(argc, argv, quiet);
+ ret = prune_merged_branches(argc, argv, quiet, dry_run);
goto out;
} else if (show_current) {
print_current_branch_name();
diff --git a/t/t3200-branch.sh b/t/t3200-branch.sh
index 3f7b1fc3d6..305c0141fc 100755
--- a/t/t3200-branch.sh
+++ b/t/t3200-branch.sh
@@ -2040,4 +2040,48 @@ test_expect_success 'branch -d still deletes a pruneMerged=false branch' '
test_must_fail git -C pm-optout-d rev-parse --verify refs/heads/one
'
+test_expect_success '--prune-merged --dry-run lists but does not delete' '
+ test_when_finished "rm -rf pm-dry" &&
+ git clone pm-upstream pm-dry &&
+ git -C pm-dry remote add fork ../pm-fork &&
+ test_config -C pm-dry remote.pushDefault fork &&
+ test_config -C pm-dry push.default current &&
+ git -C pm-dry branch one one-commit &&
+ git -C pm-dry branch --set-upstream-to=origin/next one &&
+ git -C pm-dry branch two two-commit &&
+ git -C pm-dry branch --set-upstream-to=origin/next two &&
+
+ git -C pm-dry branch --dry-run --prune-merged "origin/*" >actual &&
+ test_grep "Would delete branch one " actual &&
+ test_grep "Would delete branch two " actual &&
+
+ git -C pm-dry rev-parse --verify refs/heads/one &&
+ git -C pm-dry rev-parse --verify refs/heads/two
+'
+
+test_expect_success '--prune-merged --dry-run only lists branches the live run would delete' '
+ test_when_finished "rm -rf pm-dry-mixed" &&
+ git clone pm-upstream pm-dry-mixed &&
+ git -C pm-dry-mixed remote add fork ../pm-fork &&
+ test_config -C pm-dry-mixed remote.pushDefault fork &&
+ test_config -C pm-dry-mixed push.default current &&
+ git -C pm-dry-mixed checkout -b wip origin/next &&
+ git -C pm-dry-mixed branch --set-upstream-to=origin/next wip &&
+ test_commit -C pm-dry-mixed local-only &&
+ git -C pm-dry-mixed checkout - &&
+ git -C pm-dry-mixed branch merged one-commit &&
+ git -C pm-dry-mixed branch --set-upstream-to=origin/next merged &&
+
+ git -C pm-dry-mixed branch --dry-run --prune-merged "origin/*" >out &&
+ test_grep "Would delete branch merged" out &&
+ test_grep ! "Would delete branch wip" out &&
+ git -C pm-dry-mixed rev-parse --verify refs/heads/wip &&
+ git -C pm-dry-mixed rev-parse --verify refs/heads/merged
+'
+
+test_expect_success '--dry-run without --prune-merged is rejected' '
+ test_must_fail git -C forked branch --dry-run 2>err &&
+ test_grep "requires --prune-merged" err
+'
+
test_done
--
gitgitgadget
^ permalink raw reply related
* [PATCH v13 5/6] branch: add branch.<name>.pruneMerged opt-out
From: Harald Nordgren via GitGitGadget @ 2026-06-05 18:35 UTC (permalink / raw)
To: git
Cc: Kristoffer Haugsbakk, Johannes Sixt, Phillip Wood,
Harald Nordgren, Harald Nordgren
In-Reply-To: <pull.2285.v13.git.git.1780684553.gitgitgadget@gmail.com>
From: Harald Nordgren <haraldnordgren@gmail.com>
Setting branch.<name>.pruneMerged=false exempts that branch from
"git branch --prune-merged", which is useful for a topic you want
to keep developing after an early round of it has been merged
upstream. Unless --quiet is given, each skip is reported so the
user knows why their topic was kept.
Explicit deletion with "git branch -d" still uses the normal merge
check and ignores this setting.
Signed-off-by: Harald Nordgren <haraldnordgren@gmail.com>
---
Documentation/config/branch.adoc | 7 +++++++
Documentation/git-branch.adoc | 5 +++--
builtin/branch.c | 14 ++++++++++++++
t/t3200-branch.sh | 30 ++++++++++++++++++++++++++++++
4 files changed, 54 insertions(+), 2 deletions(-)
diff --git a/Documentation/config/branch.adoc b/Documentation/config/branch.adoc
index a4db9fa5c8..6c1b5bb9cd 100644
--- a/Documentation/config/branch.adoc
+++ b/Documentation/config/branch.adoc
@@ -102,3 +102,10 @@ for details).
`git branch --edit-description`. Branch description is
automatically added to the `format-patch` cover letter or
`request-pull` summary.
+
+`branch.<name>.pruneMerged`::
+ If set to `false`, branch _<name>_ is exempt from
+ `git branch --prune-merged`. Useful for a topic branch you
+ intend to develop further after an initial round has been
+ merged upstream. Defaults to true. Explicit deletion via
+ `git branch -d` is unaffected.
diff --git a/Documentation/git-branch.adoc b/Documentation/git-branch.adoc
index fdaccc9662..5c43dc55a8 100644
--- a/Documentation/git-branch.adoc
+++ b/Documentation/git-branch.adoc
@@ -217,9 +217,10 @@ the upstream refs refreshed.
+
A branch is left alone if any of the following holds:
its upstream no longer resolves locally; it is checked out in any
-worktree; or its push destination (`<branch>@{push}`) equals its
+worktree; its push destination (`<branch>@{push}`) equals its
upstream (`<branch>@{upstream}`), so it cannot be distinguished
-from a freshly pulled trunk that just looks "fully merged".
+from a freshly pulled trunk that just looks "fully merged"; or
+`branch.<name>.pruneMerged` is set to `false`.
+
Branches refused by the "fully merged" safety check are listed as
warnings and skipped; pass them to `git branch -D` explicitly if
diff --git a/builtin/branch.c b/builtin/branch.c
index 7a26447b2a..be4218ded3 100644
--- a/builtin/branch.c
+++ b/builtin/branch.c
@@ -739,6 +739,8 @@ static int prune_merged_branches(int argc, const char **argv,
const char *short_name;
struct branch *branch;
const char *upstream, *push;
+ struct strbuf key = STRBUF_INIT;
+ int opt_out;
if (!skip_prefix(full_name, "refs/heads/", &short_name))
continue;
@@ -753,6 +755,18 @@ static int prune_merged_branches(int argc, const char **argv,
if (!push || !strcmp(push, upstream))
continue;
+ strbuf_addf(&key, "branch.%s.prunemerged", short_name);
+ if (!repo_config_get_bool(the_repository, key.buf, &opt_out) &&
+ !opt_out) {
+ if (!quiet)
+ fprintf(stderr,
+ _("Skipping '%s' (branch.%s.pruneMerged is false)\n"),
+ short_name, short_name);
+ strbuf_release(&key);
+ continue;
+ }
+ strbuf_release(&key);
+
strvec_push(&deletable, short_name);
}
diff --git a/t/t3200-branch.sh b/t/t3200-branch.sh
index 27ea1319bb..3f7b1fc3d6 100755
--- a/t/t3200-branch.sh
+++ b/t/t3200-branch.sh
@@ -2010,4 +2010,34 @@ test_expect_success '--prune-merged takes positional <branch> arguments' '
test_must_fail git -C pm-positional rev-parse --verify refs/heads/two
'
+test_expect_success '--prune-merged honours branch.<name>.pruneMerged=false' '
+ test_when_finished "rm -rf pm-optout" &&
+ git clone pm-upstream pm-optout &&
+ git -C pm-optout remote add fork ../pm-fork &&
+ test_config -C pm-optout remote.pushDefault fork &&
+ test_config -C pm-optout push.default current &&
+ git -C pm-optout branch one one-commit &&
+ git -C pm-optout branch --set-upstream-to=origin/next one &&
+ git -C pm-optout branch two two-commit &&
+ git -C pm-optout branch --set-upstream-to=origin/next two &&
+ test_config -C pm-optout branch.one.pruneMerged false &&
+
+ git -C pm-optout branch --prune-merged "origin/*" 2>err &&
+
+ git -C pm-optout rev-parse --verify refs/heads/one &&
+ test_must_fail git -C pm-optout rev-parse --verify refs/heads/two &&
+ test_grep "Skipping .one." err
+'
+
+test_expect_success 'branch -d still deletes a pruneMerged=false branch' '
+ test_when_finished "rm -rf pm-optout-d" &&
+ git clone pm-upstream pm-optout-d &&
+ git -C pm-optout-d branch one one-commit &&
+ git -C pm-optout-d branch --set-upstream-to=origin/next one &&
+ test_config -C pm-optout-d branch.one.pruneMerged false &&
+
+ git -C pm-optout-d branch -d one &&
+ test_must_fail git -C pm-optout-d rev-parse --verify refs/heads/one
+'
+
test_done
--
gitgitgadget
^ permalink raw reply related
page: next (older) | prev (newer) | latest
- recent:[subjects (threaded)|topics (new)|topics (active)]
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox