Re: [PATCH v3 0/2] prio-queue: use bottom-up sift for extract-min
- From
René Scharfe <l.s.r@web.de>
- Date
- Jul 10, 2026, 16:37 UTC
- Message-ID
- <dfab9ff4-fbfa-4ea2-bea3-09c1d1b1cc18@web.de>
- In-Reply-To
- <pull.2132.v3.git.1783532989.gitgitgadget@gmail.com>
On 7/8/26 7:49 PM, Kristofer Karlsson via GitGitGadget wrote:
Show 5 quoted lines
> 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.
René