Re: [PATCH v2] prio-queue: use cascade-down for faster extract-min
- From
Kristofer Karlsson <krka@spotify.com>
- Date
- Jun 2, 2026, 22:40 UTC
- Message-ID
- <CAL71e4Ob-B5MJ5DPY+_tzpj6nyrbQ5WutxED2T93SWJV6kJGPA@mail.gmail.com>
- In-Reply-To
- <90270818-c52b-4611-8da2-6cee20628fc2@web.de>
On Tue, 2 Jun 2026 at 18:37, René Scharfe <l.s.r@web.de> wrote:
Show 10 quoted lines
> > Would you be interested in benchmarking the following patch for making > prio_queue_replace() unnecessary by doing its optimization > automatically? I get a 1% performance hit for the describe command > that I can't explain. And it leaves the heap unbalanced after a > prio_queue_get(), which complicates things, so I found it lacking. > But I wonder how it stacks up against your cascade approach for your > use case and if there's anything to salvage. > > René
Thank you for the detailed feedback and the patch! It was very helpful to have a concrete alternative to compare against.
I spent some time benchmarking the different approaches on a large monorepo with a wide DAG.
All measurements include the nonstale O(1) tracking from my other series as a common base, since that dominates the merge-base path.
The approaches I compared:
1. cascade-only: the sift_up_rebalance from this patch (v2)
2. rene-lazy: your deferred sift_down_root patch
3. cascade+lazy: cascade for unfused gets, lazy fusion for
get+put pairsResults (10 runs, 1 warmup, CPU pinned to performance):
merge-base --all master master~1000 (~4s workload):
cascade-only 4.18s (median)
rene-lazy 4.25s
cascade+lazy 4.24srev-list --count master~1000..master (~3.8s workload):
cascade-only 3.86s
rene-lazy 3.75s
cascade+lazy 3.74sThe lazy approaches show a small win on rev-list (~3%) where get+put pairs are common in limit_list. On merge-base --all, everything is within noise, the prio_queue is a small fraction of total runtime there. Combining cascade with lazy fusion didn't produce additional gains beyond what each gives individually.
Looking at your patch, I think the deferred sift-down logic is essentially the same optimization as the lazy_queue wrapper you wrote for describe.c - both defer the work from get and fuse it with a following put. So I'd be hesitant to add a second form of that deferral directly into prio_queue when lazy_queue already "owns" that responsibility as a wrapper.
That said, I think it would make sense to fold lazy_queue entirely into prio_queue. It's an optimization that never hurts as far as I can tell, and it would simplify several callers. pop_most_recent_commit and show-branch both independently re-implement the same peek+replace pattern that lazy_queue formalizes. Making it automatic in prio_queue would clean up all of them.
I have a local branch exploring that direction. Maybe it makes more sense to do the lazy_queue fold first, and then see if the cascade change is still worth adding on top?
Either way, I think the two directions are complementary - cascade reduces comparisons per sift, while lazy fusion can eliminate full rebalance cycles.
I'm on a company offsite now so I may be slow to answer, but I will definitely resume this when I get back home.
- Kristofer