From: René Scharfe Date: Sun, 07 Jun 2026 07:30:39 GMT Subject: Re: [PATCH v2] prio-queue: use cascade-down for faster extract-min Message-ID: <1aa5b755-0f74-46d5-bd6e-a9cb7f3fbb12@web.de> In-Reply-To: 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); + } } }