Re: [PATCH v3 2/2] prio-queue: use cascade for unfused gets
- From
Kristofer Karlsson <krka@spotify.com>
- Date
- Jul 10, 2026, 17:28 UTC
- Message-ID
- <CAL71e4PRVYfUWc-c+6XHTwtADqrbub9ykbo+rPyramDhJw=Rfg@mail.gmail.com>
- In-Reply-To
- <10fad562-90b8-4feb-b7ab-d61015872127@web.de>
On Fri, 10 Jul 2026 at 18:37, René Scharfe <l.s.r@web.de> wrote:
Show 9 quoted lines
> > I see a 1% slowdown on an Apple M5 as well in both cases. I can't > reproduce it on a Ryzen laptop, but that's too noisy to measure 1% > changes anyway. > > Checked the total number of prio_queue comparisons with the crude patch > below, and as expected they go down, from 70386235 to 60682175 for Git > and from 473983445 to 439809087 for Linux. So there's less work to do, > still user time goes up -- no idea why.
[snip]
> The patch looks fine, though. It introduces struct assignments, but > they should be OK. Tried replacing them with swap() instead (which > does a useless extra write), but that didn't change the performance > (still 1% slowdown). Odd.
First of all, thanks again for the very comprehensive investigation on your own hardware!
I don't have any Apple machine to test on but I reran your exact operation on my machine (Lenovo Thinkpad Intel(R) Core(TM) Ultra 7 155U) and just saw noise.
As you say, this feels _logically_ better since it's fewer compares but perhaps this boils down to the cost difference between executing CPU operations versus memory access and the CPU cache?
My random guess: cascade_down() has fewer operations and compares but needs to visit all levels of the heap, while sift_down_root perhaps stops slightly earlier, so the memory region right before the end gets fewer visits and reduces pressure on the cache.
I have no idea if my guess is correct, it's maybe more subtle than that, but I think ultimately this points to the fact that while the change is a theoretical improvement, the real world hardware tradeoffs make it a non-obvious change.
I think this means we should simply drop the change and move on -- it produced bigger gains before making the lazy prio_queue the default, but now it seems like it is pure noise, unless the comparator function grows more expensive in the future.
Thanks, Kristofer