Re: [PATCH] prio-queue: use cascade-down sift for faster extract-min
- From
Kristofer Karlsson <krka@spotify.com>
- Date
- Jun 1, 2026, 06:21 UTC
- Message-ID
- <CAL71e4PjZz-BLpRzXd9MXnoWzHHGHzTYyGw0xM9ntg+iRATN2Q@mail.gmail.com>
- In-Reply-To
- <xmqq5x42aipu.fsf@gitster.g>
Thanks for the quick and very valid feedback! I already started investigating - I think I was too quick (and wrong) when I reasoned about the replace operation.I will rework it a bit and come back with a patch version 2 soon that ensures that neither get and replace have regressed in any way.
- Kristofer
On Mon, 1 Jun 2026 at 08:16, Junio C Hamano <gitster@pobox.com> wrote:
Show 79 quoted lines
>
> "Kristofer Karlsson via GitGitGadget" <gitgitgadget@gmail.com>
> writes:
>
> > 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 ...
>
> > + 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