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

Re: [PATCH v2] prio-queue: use cascade-down for faster extract-min

From
Kristofer Karlsson <krka@spotify.com>
Date
Jun 7, 2026, 12:07 UTC
Message-ID
<CAL71e4MYNiScZjTwkApjDAjRh2LM0_SP59h5HCTywV-Pua03tw@mail.gmail.com>
In-Reply-To
<1aa5b755-0f74-46d5-bd6e-a9cb7f3fbb12@web.de>
On Sat, 7 Jun 2026 at 09:30, Rene Scharfe <l.s.r@web.de> wrote:
Show 16 quoted lines
>
> Right.  I was wondering, though: Why is sift-down so much faster than
> cascade in the describe benchmark from 30598ccc4d (describe: use oidset
> in finish_depth_computation(), 2025-09-02)?
>
> I think I mostly understand it now: cascade is better in prio_queue_get()
> because the sift-down item is from the bottom and will likely end up back
> at the bottom, just of a different branch of the heap.  Thus a sift-down
> costs 3 compares times the number of levels, while a cascade costs just
> 2 compares times the number of levels and there is likely little to no
> need to sift it back up.
>
> For prio_queue_replace() we sift down a random item, though; we don't
> know where it will end up.  If it belongs at the very top then sift-down
> just needs 3 compares, while cascade needs 2 compares times the number
> of levels to bring the hole down and the same to bring the item up.

Yes, I think that reasoning is correct. It depends on where the item will land.

For get() the last array element came from the bottom of the heap and will almost certainly end up back near the bottom, so cascade's blind descent is a good default.

For replace() the new element is arbitrary -- in describe's pattern it often belongs near the root, so sift-down's early exit after 2-3 compares dominates.

Your benchmark confirms this: v2 (cascade only in get) matches the baseline exactly for describe, while the hybrid is 4% slower.

> So I guess we keep the full sift-down for prio_queue_replace(), knowing
> that sometimes we have a lot of items that end up at or close to the
> root of the heap.

Agreed. And with the lazy-fold series (v3 just sent), replace() is removed as a public API entirely. But the same principle applies to the fused replace path inside prio_queue_put(): when get_pending is set and a put arrives, we write the new element at the root and sift it down -- that path should keep sift-down for the same reason your analysis shows.

If (that's a big if) both my patches eventually land,
the split would be:
 - unfused get-flush (in get() and peek()): use cascade
 - fused replace (in put()): keep sift-down
Which is exactly the split your analysis predicts is optimal.

Now I am thinking it would be easier to reason about this if the other patch lands first, since the cascade change becomes simpler to evaluate when replace is already gone and only the unfused paths remain.

- Kristofer
Previous: René ScharfeNext: Junio C Hamano
Message 10 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.