From: Kristofer Karlsson Date: Mon, 01 Jun 2026 06:21:57 GMT Subject: Re: [PATCH] prio-queue: use cascade-down sift for faster extract-min Message-ID: In-Reply-To: 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 wrote: > > "Kristofer Karlsson via GitGitGadget" > 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