From: Junio C Hamano Date: Mon, 01 Jun 2026 00:09:29 GMT Subject: Re: [PATCH] prio-queue: use cascade-down sift for faster extract-min Message-ID: In-Reply-To: "Kristofer Karlsson via GitGitGadget" writes: I'll add René the recipients, as _replace() was added by him as optimization, so "this new one is functionally equivalent to the original" somewhat misses the point, even though we may all agree that the change is a very good one overall in the end when we look at the entire picture. > From: Kristofer Karlsson > > Replace the standard sift-down in prio_queue_get() with a > cascade-down approach. > > The standard approach places the last array element at the root, > then sifts it down. At each level this requires two comparisons > (left vs right child, then element vs winner) and, when the > element is larger, a swap (three 16-byte copies). > > The cascade approach instead promotes the smaller child into the > vacant root slot at each level — one comparison and one copy. > The vacancy sinks to a leaf, where the last array element is > placed and sifted up if needed — typically zero levels since the > last array element tends to be large. > > In the common case, work per extract drops from 2d comparisons > + 3d copies to d comparisons + d copies: roughly half the > comparisons and a third of the data movement. The sift-up phase > can add work when the last element is smaller than ancestors of > the leaf vacancy, but this is rare in practice. > > Simplify prio_queue_replace() to a plain get+put sequence. This > is semantically equivalent: the old implementation wrote to slot 0 > and sifted down, which has the same observable effect as removing > the root and inserting a new element. No caller observes queue > state between the two operations. The previous implementation > shared sift_down_root() with get, but the cascade approach no > longer accommodates that cleanly since sift_down_root() now > expects the element to reinsert at queue->array[queue->nr], left > there by prio_queue_get() after decrementing nr. This is fine in > practice: replace is only called from pop_most_recent_commit() > (fetch-pack, object-name, walker) and show-branch — none of > which appear in any hot path. > > A synthetic benchmark (10 rounds of 10M put+get cycles, ascending > integer keys, CPU-pinned, median of 3 runs, same compiler and > Makefile flags) shows consistent improvement across all queue > sizes, with no regressions: > > queue width baseline cascade speedup > ------------------------------------------------ > 10 4.32s 3.97s 1.09x > 100 7.95s 6.49s 1.23x > 1,000 11.30s 9.66s 1.17x > 10,000 16.34s 14.15s 1.16x > 100,000 21.43s 18.66s 1.15x > > With descending keys (worst case — the last element always sinks > to a leaf in both approaches) the cascade still wins slightly > (1-4%) by replacing swaps with copies, and never regresses. > > In end-to-end git commands the improvement is modest because > sift_down_root is only ~8% of total runtime. Profiling > rev-list --count on a 2.5M-commit monorepo shows sift_down_root > dropping from 8.2% to 0.4% of total runtime. The improvement > scales with DAG width: wider DAGs produce larger priority queues, > amplifying the per-level savings. In small or narrow repos the > queues stay shallow and the effect is negligible. > > Signed-off-by: Kristofer Karlsson > --- > prio-queue: use cascade-down sift for faster extract-min > > Hi, I am not sure this is just noise or not but I thought it at least > was interesting. > > I looked into the internals of prio_queue and found it was technically > doing too much work and could be simplified/optimized. I found I could > optimize it by ~20% for the common case (adding commits that would > typically end up far back in the queue) but only ~1% for the reverse > case (adding things to the front of the prio queue). The average speedup > is somewhere in between I suppose. That said, this is not really the > bottleneck so the overall boost seems to be around ~3-4% improvement for > repos with wide DAGs. > > I would normally classify this as not urgent or important, but I think > the advantage is that the change is very small and simple and it already > has good unit tests (t/unit-tests/u-prio-queue.c). > > With that said, here are the details: > > The prio_queue_get impl is based on removing the root entry, then moving > the very last element into the root slot, then sifting it down into the > right place. This uses both comparisons between sibling elements in the > heap as well as comparisons between the element to add and one of the > siblings. Then it uses swap operations to move things correctly. > > This patch instead promotes the smaller child upward at each level, > leaving a vacancy that sinks to a leaf, then places the removed element > there with a short sift-up to keep the heap balanced. > > We can analytically compare this - for a sift-distance of d we can > reason about the number of operations to execute. > > Before: 2d comparisons + 3d copies > After: d comparisons + d copies > > > After changing sift_down in this way, the replace operation can't simply > depend on it anymore, so I reimplemented it as a sequence of get + put. > This is technically correct but maybe not as efficient. However, I am > not sure that it matters, since I couldn't see any usage of the replace > operation in any hot path. > > Performance: Profiling git rev-list --count on a 2.5M-commit monorepo > shows sift_down_root dropping from 8.2% to 0.4% of total runtime, > effectively eliminated as significant overhead. > > Synthetic benchmark 10 rounds of 10M put+get cycles, CPU-pinned, median > of 3 runs, same compiler and Makefile flags. > > Ascending keys (git's typical pattern -- parents have lower priority > than children): > > queue width baseline patched speedup > 10 4.32s 3.97s 1.09x > 100 7.95s 6.49s 1.23x > 1,000 11.30s 9.66s 1.17x > 10,000 16.34s 14.15s 1.16x > 100,000 21.43s 18.66s 1.15x > > > Descending keys (worst case — last element always sinks to leaf in both > approaches): > > queue width baseline patched speedup > 10 4.84s 4.78s 1.01x > 100 9.43s 9.20s 1.03x > 1,000 15.28s 14.71s 1.04x > 10,000 23.61s 23.49s 1.01x > 100,000 29.16s 28.22s 1.03x > > > No regressions in any scenario. > > End-to-end benchmarks > > All benchmarks use a benchmark setup of 1 warmup run followed by 10 > timed runs. Each configuration is built from the same source tree and > tested on the same repo in alternating order. > > linux kernel (1.4M commits) — range v5.0..v6.0 (311K commits): > > Command baseline patched speedup > rev-list --count v5.0..v6.0 455ms 440ms 1.04x > > > I also ran it on git.git but did not see any performance diff at all, > due to the size and narrow DAG. > > The improvement scales with DAG width: wider DAGs produce larger > priority queues, amplifying the per-level savings. In small or narrow > repositories the priority queues stay shallow and the sift-down cost is > already negligible, so the change is not noticeable. > > Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2132%2Fspkrka%2Fcascade-sift-down-v1 > Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2132/spkrka/cascade-sift-down-v1 > Pull-Request: https://github.com/gitgitgadget/git/pull/2132 > > prio-queue.c | 22 ++++++++++++---------- > 1 file changed, 12 insertions(+), 10 deletions(-) > > diff --git a/prio-queue.c b/prio-queue.c > index 9748528ce6..18005c43c4 100644 > --- a/prio-queue.c > +++ b/prio-queue.c > @@ -62,17 +62,21 @@ 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 */ > + for (ix = 0; (child = ix * 2 + 1) < queue->nr; ix = child) { > if (child + 1 < queue->nr && > compare(queue, child, child + 1) >= 0) > child++; /* use right child */ > + queue->array[ix] = queue->array[child]; > + } > > - if (compare(queue, ix, child) <= 0) > + /* Place queue->array[queue->nr] (left by caller) and sift up. */ > + queue->array[ix] = queue->array[queue->nr]; > + while (ix) { > + size_t parent = (ix - 1) / 2; > + if (compare(queue, parent, ix) <= 0) > break; > - > - swap(queue, child, ix); > + swap(queue, parent, ix); > + ix = parent; > } > } > > @@ -89,7 +93,6 @@ void *prio_queue_get(struct prio_queue *queue) > if (!--queue->nr) > return result; > > - queue->array[0] = queue->array[queue->nr]; > sift_down_root(queue); > return result; > } > @@ -111,8 +114,7 @@ void prio_queue_replace(struct prio_queue *queue, void *thing) > queue->array[queue->nr - 1].ctr = queue->insertion_ctr++; > queue->array[queue->nr - 1].data = thing; > } else { > - queue->array[0].ctr = queue->insertion_ctr++; > - queue->array[0].data = thing; > - sift_down_root(queue); > + prio_queue_get(queue); > + prio_queue_put(queue, thing); > } > } > > base-commit: c69baaf57ba26cf117c2b6793802877f19738b0d