From: Kristofer Karlsson Date: Mon, 06 Jul 2026 21:52:34 GMT Subject: Re: [PATCH v2] prio-queue: use cascade-down for faster extract-min Message-ID: In-Reply-To: <1aa5b755-0f74-46d5-bd6e-a9cb7f3fbb12@web.de> On Sun, 7 Jun 2026 at 09:30, René Scharfe wrote: > > So I guess we keep the full sift-down for prio_queue_replace(), knowing > that sometimes we have a lot of items that end up at or close to the > root of the heap. The lazy-fold series (kk/prio-queue-get-put-fusion) is in next now. I rebased this cascade patch on top of it to check if it's still useful. With lazy-fold in place the regression scenario you identified is resolved. The only remaining change is in flush_get(), where unfused gets now cascade instead of sifting down: - queue->array[0] = queue->array[--queue->nr_]; - sift_down_root(queue); + --queue->nr_; + sift_up_rebalance(queue); plus the ~20-line sift_up_rebalance() implementation. I benchmarked this on the linux kernel repo and on a large merge-heavy repo. The results are consistent: a real but small 1-2% end-to-end improvement across commands. A prio-queue microbenchmark would likely show a larger difference, but the queue is only a fraction of the total work in any real git operation. The lazy-fold optimization cannibalized some of the value here, so cascade only helps the remaining unfused gets. As you observed, cascade is better there, but there are fewer of them now that there is more fusing happening. I am on the fence about whether 1-2% end-to-end justifies adding another sift function. If you (René and Junio) think the benefit is too small for the code cost, I am happy to drop this patch. Otherwise I can submit a small reroll on top of kk/prio-queue-get-put-fusion (or rather next, in practice). Thanks, Kristofer