Re: [PATCH] prio-queue: use cascade-down sift for faster extract-min
From: Junio C Hamano <hidden>
Date: 2026-06-01 06:16:31
"Kristofer Karlsson via GitGitGadget" [off-list ref] writes:
quoted hunk ↗ jump to hunk
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 ...
quoted hunk ↗ jump to hunk
+ 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