On Sat, 7 Jun 2026 at 09:30, Rene Scharfe [off-list ref] wrote:

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