Re: [PATCH v2] prio-queue: use cascade-down for faster extract-min
- From
Kristofer Karlsson <krka@spotify.com>
- Date
- Jun 5, 2026, 20:39 UTC
- Message-ID
- <CAL71e4PV-1aDvn1JnweMa3OR1xxB75fWjzJOBvM54KOWqC0stw@mail.gmail.com>
- 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