From: Kristofer Karlsson Date: Tue, 02 Jun 2026 22:40:55 GMT Subject: Re: [PATCH v2] prio-queue: use cascade-down for faster extract-min Message-ID: In-Reply-To: <90270818-c52b-4611-8da2-6cee20628fc2@web.de> On Tue, 2 Jun 2026 at 18:37, René Scharfe wrote: > > 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 pairs Results (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.24s rev-list --count master~1000..master (~3.8s workload): cascade-only 3.86s rene-lazy 3.75s cascade+lazy 3.74s The 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