From: Junio C Hamano Date: Mon, 08 Jun 2026 11:56:33 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> René Scharfe writes: > I think I mostly understand it now: cascade is better in prio_queue_get() > because the sift-down item is from the bottom and will likely end up back > at the bottom, just of a different branch of the heap. Thus a sift-down > costs 3 compares times the number of levels, while a cascade costs just > 2 compares times the number of levels and there is likely little to no > need to sift it back up. > > For prio_queue_replace() we sift down a random item, though; we don't > know where it will end up. If it belongs at the very top then sift-down > just needs 3 compares, while cascade needs 2 compares times the number > of levels to bring the hole down and the same to bring the item up. An excellent observation, showing clear and analytic mind. This is one of the reasons why I love reading review messages from you (and also explanation in the proposed commit log messages in your patches). Thanks.