Re: [PATCH] prio-queue: use cascade-down sift for faster extract-min
- From
Junio C Hamano <gitster@pobox.com>
- Date
- Jun 1, 2026, 06:16 UTC
- Message-ID
- <xmqq5x42aipu.fsf@gitster.g>
- In-Reply-To
- <pull.2132.git.1780250236304.gitgitgadget@gmail.com>
"Kristofer Karlsson via GitGitGadget" <gitgitgadget@gmail.com> writes:
Show 21 quoted lines
> diff --git a/prio-queue.c b/prio-queue.c
> index 9748528ce6..18005c43c4 100644
> --- a/prio-queue.c
> +++ b/prio-queue.c
> @@ -62,17 +62,21 @@ static void sift_down_root(struct prio_queue *queue)
> {
> size_t ix, child;
>
> - /* Push down the one at the root */
> - for (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {
> - child = ix * 2 + 1; /* left */
> + for (ix = 0; (child = ix * 2 + 1) < queue->nr; ix = child) {
> if (child + 1 < queue->nr &&
> compare(queue, child, child + 1) >= 0)
> child++; /* use right child */
> + queue->array[ix] = queue->array[child];
> + }
>
> - if (compare(queue, ix, child) <= 0)
> + /* Place queue->array[queue->nr] (left by caller) and sift up. */
> + queue->array[ix] = queue->array[queue->nr];Here we always sift/bubble up the last element.
I am wondering if it makes sense to teach sift_down_root to take an extra argument, "struct prio_queue_entry entry" (passed by value) and sift/bubble it up, not always queue->array[queue->nr], and ...
Show 28 quoted lines
> + while (ix) {
> + size_t parent = (ix - 1) / 2;
> + if (compare(queue, parent, ix) <= 0)
> break;
> -
> - swap(queue, child, ix);
> + swap(queue, parent, ix);
> + ix = parent;
> }
> }
>
> @@ -89,7 +93,6 @@ void *prio_queue_get(struct prio_queue *queue)
> if (!--queue->nr)
> return result;
>
> - queue->array[0] = queue->array[queue->nr];
> sift_down_root(queue);
> return result;
> }
> @@ -111,8 +114,7 @@ void prio_queue_replace(struct prio_queue *queue, void *thing)
> queue->array[queue->nr - 1].ctr = queue->insertion_ctr++;
> queue->array[queue->nr - 1].data = thing;
> } else {
> - queue->array[0].ctr = queue->insertion_ctr++;
> - queue->array[0].data = thing;
> - sift_down_root(queue);
> + prio_queue_get(queue);
> + prio_queue_put(queue, thing);... update this part in the else clause to do something like
struct prio_queue_entry entry; entry.ctr = queue->insertion_ctr++; entry.data = thing; sift_down_root(queue, entry);
to retain the optimization? It would perform a single cascade-down sift, followed by a single sift-up, so it would save a comparison, a copy, and a swap in the worset case compared to the get+put sequence?
Of course, the original sift_down_root() caller (i.e. prio_queue_get()) needs to pass queue->array[queue->nr] as the second parameter to match.
> } > } > > base-commit: c69baaf57ba26cf117c2b6793802877f19738b0d