From: Kristofer Karlsson Date: Fri, 10 Jul 2026 17:28:43 GMT Subject: Re: [PATCH v3 2/2] prio-queue: use cascade for unfused gets Message-ID: In-Reply-To: <10fad562-90b8-4feb-b7ab-d61015872127@web.de> On Fri, 10 Jul 2026 at 18:37, René Scharfe wrote: > > 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