From: Junio C Hamano Date: Mon, 01 Jun 2026 06:16:29 GMT Subject: Re: [PATCH] prio-queue: use cascade-down sift for faster extract-min Message-ID: In-Reply-To: "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