From: Kristofer Karlsson Date: Wed, 08 Jul 2026 10:59:56 GMT Subject: Re: [PATCH v2] prio-queue: use cascade-down for faster extract-min Message-ID: In-Reply-To: <57bb0e9e-221d-4234-b5bc-a87610e8263c@web.de> On Wed, 8 Jul 2026 at 12:44, René Scharfe 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