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

On Tue, 2 Jun 2026 at 18:37, René Scharfe [off-list ref] wrote:

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