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
Jul 8, 2026, 10:59 UTC
Message-ID
<CAL71e4NiSSRgxO_L7vb5=ohnchOCvuhEZwMc0Ls+Xu-Q+YytDg@mail.gmail.com>
In-Reply-To
<57bb0e9e-221d-4234-b5bc-a87610e8263c@web.de>
On Wed, 8 Jul 2026 at 12:44, René Scharfe <l.s.r@web.de> wrote:
Show 12 quoted lines
>
> 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?

Show 17 quoted lines
> 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.

Show 24 quoted lines
> 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.

Show 7 quoted lines
> 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

Previous: René ScharfeNext: René Scharfe
Message 15 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.