git/list[1] front-page[2] threads[3] people[4] search[5] about
 

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

Previous: René ScharfeNext: René Scharfe
Message 22 of 24 in “prio-queue: use cascade-down sift for faster extract-min”
  1. prio-queue: use cascade-down sift for faster extract-minKristofer Karlsson via GitGitGadget, May 31, 2026
  2. Junio C HamanoJun 1, 2026
  3. Junio C HamanoJun 1, 2026
  4. Kristofer KarlssonJun 1, 2026
  5. prio-queue: use cascade-down for faster extract-minKristofer Karlsson via GitGitGadget, Jun 1, 2026
  6. René ScharfeJun 2, 2026
  7. Kristofer KarlssonJun 2, 2026
  8. Kristofer KarlssonJun 5, 2026
  9. René ScharfeJun 7, 2026
  10. Kristofer KarlssonJun 7, 2026
  11. Junio C HamanoJun 29, 2026
  12. Junio C HamanoJun 8, 2026
  13. Kristofer KarlssonJul 6, 2026
  14. René ScharfeJul 8, 2026
  15. Kristofer KarlssonJul 8, 2026
  16. René ScharfeJul 8, 2026
  17. Kristofer KarlssonJul 8, 2026
  18. 0/2 prio-queue: use bottom-up sift for extract-minKristofer Karlsson via GitGitGadget, Jul 8, 2026
  19. 1/2 prio-queue: extract sift_up() from prio_queue_put()Kristofer Karlsson via GitGitGadget, Jul 8, 2026
  20. 2/2 prio-queue: use cascade for unfused getsKristofer Karlsson via GitGitGadget, Jul 8, 2026
  21. René ScharfeJul 10, 2026
  22. Kristofer KarlssonJul 10, 2026
  23. René ScharfeJul 10, 2026
  24. Kristofer KarlssonJul 10, 2026

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.