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 5, 2026, 20:39 UTC
Message-ID
<CAL71e4PV-1aDvn1JnweMa3OR1xxB75fWjzJOBvM54KOWqC0stw@mail.gmail.com>
In-Reply-To
<CAL71e4Ob-B5MJ5DPY+_tzpj6nyrbQ5WutxED2T93SWJV6kJGPA@mail.gmail.com>

I did some more benchmarking to understand how these approaches interact, with four variants based on origin/next on my large monorepo:

  1. base: next as-is
  2. cascade: base + sift_up_rebalance from this patch (v2)
  3. lazy-fold: base + lazy get fusion folded into prio_queue
  4. cascade+lazy: both combined

Note that alt 3 is not yet shared with the mailing list so it's hard for you to reason about it, though it's quite straightforward. I will submit a new patch for that one soon, not necessarily with the primary goal to merge it, but rather show how it is implemented.

  merge-base --all master master~1000:
    base            4.27s
    cascade         4.07s  (1.05x)
    lazy-fold       4.12s  (1.03x)
    cascade+lazy    4.01s  (1.06x)
  rev-list --count master~1000..master:
    base            3.60s
    cascade         3.35s  (1.08x)
    lazy-fold       3.37s  (1.07x)
    cascade+lazy    3.30s  (1.09x)

So both optimizations are valuable both on their own, and when combined, which I think helps to reason about it. This cascading sift seems to have a larger effect, but folding lazy_queue into prio_queue also speeds up other use cases and simplifies the code a bit.

Based on this, my (very subjective) approach would be:
1. Land this cascade patch first since it's a pure algorithmic improvement,
2. Follow up with a separate patch that folds lazy_queue into
     prio_queue. Will post it separately soon, as I mentioned.
- Kristofer
Previous: Kristofer KarlssonNext: René Scharfe
Message 8 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.