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 [off-list ref] wrote:

"Kristofer Karlsson via GitGitGadget" [off-list ref]
writes:

quoted

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

+     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.

quoted

      }
 }

base-commit: c69baaf57ba26cf117c2b6793802877f19738b0d