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

On Wed, 8 Jul 2026 at 12:44, René Scharfe [off-list ref] wrote:

tl;dr: Yes, please, but I'm biased.

The text size of prio-queue.o on Apple silicon increases from 1351 to
1563 bytes for me, 212 bytes or 16% more.  OK.

It makes intuitive sense to find the new position of the last item by
searching from the bottom up instead of from the top down.  Timings
confirm it.  Are there pathologic cases that perform worse, though?  I
don't see how to construct one.  It would require an unbalanced heap,
where the bottom items from one branch would rise high in other
branches.  Is this even possible?

Agreed, I also struggle to come up with such a case. Perhaps
theoretically possible to construct, but would not invalidate
the general heuristic?

For a full drain (only _get(), no _put()) of up to 12 items the answer
is no, at least.  Cascade never needs more comparisons for any
permutation; test code below.  Here are the aggregate numbers:

       next           cascade
    n  min max  mean  min max  mean
    2    0   0   0.0    0   0   0.0
    3    1   1   1.0    1   1   1.0
    4    3   3   3.0    3   3   3.0
    5    5   6   5.8    5   6   5.6
    6    7  10   8.7    7   9   8.0
    7   10  14  12.0    9  12  10.9
    8   14  18  16.3   12  16  13.9
    9   18  23  20.9   15  20  17.4
   10   22  29  25.5   18  24  20.7
   11   26  35  30.5   21  28  24.4
   12   30  41  35.5   24  33  27.9

I am sincerely grateful that you took the time to analyze it
to this level of detail. Very nice analysis and data!

sift_up_rebalance() is a combination of sift_down_root() with an empty
root and the bubble-up operation from prio_queue_put().  The latter can
easily be factored out into a sift-up function, reducing code
duplication.

Good point! I am not sure how messy this gets in practice, but I
will see if I can implement this split for the next patch.

Extending sift_down_root() to deal with an empty root would be easy as
well, but also a bit tricky to avoid pointless checks for each caller.
Not sure it's worth it.  Like this perhaps?

static inline size_t sift_down_root(struct prio_queue *queue, bool empty)
{
        size_t ix, child;

        /* Push down the one at the root */
        for (ix = 0; ix * 2 + 1 < queue->nr_; ix = child) {
                child = ix * 2 + 1; /* left */
                if (child + 1 < queue->nr_ &&
                    compare(queue, child, child + 1) >= 0)
                        child++; /* use right child */

                if (empty)
                        queue->array[ix] = queue->array[child];
                else if (compare(queue, ix, child) <= 0)
                        break;
                else
                        swap(queue, child, ix);
        }
        return ix;
}

Yes, something like that would work, but I agree -- ideally we
could have something that's even nicer and avoids the boolean flag
for split behavior.

Anyway, my point is that it's not "adding another sift function", but
remixing existing ones, which I only count as half. :)

I'd very much like to see this go in because it seems to be strictly
faster, makes intuitive sense and adds only little code.   I didn't
find this method used anywhere else, which is a warning sign, but I
can't find any catch.

Thanks, I think that is enough motivation for me to at least attempt
another version and then it will be easier to reason about dropping
or keeping.

I am not sure why it's a warning sign to have no other usages,
especially when it's a file local static function. I guess it could
be inlined instead (though I would not prefer that).

Thanks for the very thorough and insightful review,
Kristofer