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