From: Kristofer Karlsson Date: Fri, 05 Jun 2026 20:39:32 GMT Subject: Re: [PATCH v2] prio-queue: use cascade-down for faster extract-min Message-ID: In-Reply-To: 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