git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH v3 0/2] prio-queue: use bottom-up sift for extract-min

From
Kristofer Karlsson <krka@spotify.com>
Date
Jul 10, 2026, 17:40 UTC
Message-ID
<CAL71e4PvOdH9-aER35f=OAEurNzM-coYr64A7GPckZ9AYctMtw@mail.gmail.com>
In-Reply-To
<dfab9ff4-fbfa-4ea2-bea3-09c1d1b1cc18@web.de>
On Fri, 10 Jul 2026 at 18:37, René Scharfe <l.s.r@web.de> wrote:
Show 11 quoted lines
>
> On 7/8/26 7:49 PM, Kristofer Karlsson via GitGitGadget wrote:
> > Note: sift_up() currently uses swap, matching the existing code style. It
> > could be further optimized to use copy (hold the element in a temp, shift
> > parents down, write once), but that would require changing compare() to
> > accept element values instead of array indices. Left for a potential
> > follow-up.
>
> Same for sift_down_root(), I guess?  It could almost halve the number of
> writes, right?  I wonder how much of that benefit will be eaten by
> caching.

Hm yes indeed, I stopped looking past sift_up() when I realized I should not expand the scope of the change. But I think the CPU cache effectively makes the swap almost as cheap in practice.

- Kristofer
Previous: René Scharfe
Message 24 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.