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 2, 2026, 22:40 UTC
Message-ID
<CAL71e4Ob-B5MJ5DPY+_tzpj6nyrbQ5WutxED2T93SWJV6kJGPA@mail.gmail.com>
In-Reply-To
<90270818-c52b-4611-8da2-6cee20628fc2@web.de>
On Tue, 2 Jun 2026 at 18:37, René Scharfe <l.s.r@web.de> wrote:
Show 10 quoted lines
>
> Would you be interested in benchmarking the following patch for making
> prio_queue_replace() unnecessary by doing its optimization
> automatically?  I get a 1% performance hit for the describe command
> that I can't explain.  And it leaves the heap unbalanced after a
> prio_queue_get(), which complicates things, so I found it lacking.
> But I wonder how it stacks up against your cascade approach for your
> use case and if there's anything to salvage.
>
> René

Thank you for the detailed feedback and the patch! It was very helpful to have a concrete alternative to compare against.

I spent some time benchmarking the different approaches on a large monorepo with a wide DAG.

All measurements include the nonstale O(1) tracking from my other series as a common base, since that dominates the merge-base path.

The approaches I compared:
  1. cascade-only: the sift_up_rebalance from this patch (v2)
  2. rene-lazy: your deferred sift_down_root patch
  3. cascade+lazy: cascade for unfused gets, lazy fusion for
     get+put pairs
Results (10 runs, 1 warmup, CPU pinned to performance):
  merge-base --all master master~1000 (~4s workload):
    cascade-only   4.18s (median)
    rene-lazy      4.25s
    cascade+lazy   4.24s
  rev-list --count master~1000..master (~3.8s workload):
    cascade-only   3.86s
    rene-lazy      3.75s
    cascade+lazy   3.74s

The lazy approaches show a small win on rev-list (~3%) where get+put pairs are common in limit_list. On merge-base --all, everything is within noise, the prio_queue is a small fraction of total runtime there. Combining cascade with lazy fusion didn't produce additional gains beyond what each gives individually.

Looking at your patch, I think the deferred sift-down logic is essentially the same optimization as the lazy_queue wrapper you wrote for describe.c - both defer the work from get and fuse it with a following put. So I'd be hesitant to add a second form of that deferral directly into prio_queue when lazy_queue already "owns" that responsibility as a wrapper.

That said, I think it would make sense to fold lazy_queue entirely into prio_queue. It's an optimization that never hurts as far as I can tell, and it would simplify several callers. pop_most_recent_commit and show-branch both independently re-implement the same peek+replace pattern that lazy_queue formalizes. Making it automatic in prio_queue would clean up all of them.

I have a local branch exploring that direction. Maybe it makes more sense to do the lazy_queue fold first, and then see if the cascade change is still worth adding on top?

Either way, I think the two directions are complementary - cascade reduces comparisons per sift, while lazy fusion can eliminate full rebalance cycles.

I'm on a company offsite now so I may be slow to answer, but I will definitely resume this when I get back home.

- Kristofer
Previous: René ScharfeNext: Kristofer Karlsson
Message 7 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.