On 7/6/26 11:52 PM, Kristofer Karlsson wrote:

On Sun, 7 Jun 2026 at 09:30, René Scharfe [off-list ref] wrote:

quoted

So I guess we keep the full sift-down for prio_queue_replace(), knowing
that sometimes we have a lot of items that end up at or close to the
root of the heap.

The lazy-fold series (kk/prio-queue-get-put-fusion) is in next now.
I rebased this cascade patch on top of it to check if it's still
useful.

With lazy-fold in place the regression scenario you identified
is resolved. The only remaining change is in flush_get(),
where unfused gets now cascade instead of sifting down:

  -    queue->array[0] = queue->array[--queue->nr_];
  -    sift_down_root(queue);
  +    --queue->nr_;
  +    sift_up_rebalance(queue);

plus the ~20-line sift_up_rebalance() implementation.

I benchmarked this on the linux kernel repo and on a large
merge-heavy repo.

The results are consistent: a real but small 1-2% end-to-end
improvement across commands. A prio-queue microbenchmark
would likely show a larger difference, but the queue
is only a fraction of the total work in any real git operation.

The lazy-fold optimization cannibalized some of the value here,
so cascade only helps the remaining unfused gets. As you observed,
cascade is better there, but there are fewer of them now that there
is more fusing happening.

I am on the fence about whether 1-2% end-to-end justifies adding
another sift function. If you (René and Junio) think the benefit
is too small for the code cost, I am happy to drop this patch.
Otherwise I can submit a small reroll on top of
kk/prio-queue-get-put-fusion (or rather next, in practice).

tl;dr: Yes, please, but I'm biased.

The text size of prio-queue.o on Apple silicon increases from 1351 to
1563 bytes for me, 212 bytes or 16% more.  OK.

It makes intuitive sense to find the new position of the last item by
searching from the bottom up instead of from the top down.  Timings
confirm it.  Are there pathologic cases that perform worse, though?  I
don't see how to construct one.  It would require an unbalanced heap,
where the bottom items from one branch would rise high in other
branches.  Is this even possible?

For a full drain (only _get(), no _put()) of up to 12 items the answer
is no, at least.  Cascade never needs more comparisons for any
permutation; test code below.  Here are the aggregate numbers:

       next           cascade
    n  min max  mean  min max  mean
    2    0   0   0.0    0   0   0.0
    3    1   1   1.0    1   1   1.0
    4    3   3   3.0    3   3   3.0
    5    5   6   5.8    5   6   5.6
    6    7  10   8.7    7   9   8.0
    7   10  14  12.0    9  12  10.9
    8   14  18  16.3   12  16  13.9
    9   18  23  20.9   15  20  17.4
   10   22  29  25.5   18  24  20.7
   11   26  35  30.5   21  28  24.4
   12   30  41  35.5   24  33  27.9

sift_up_rebalance() is a combination of sift_down_root() with an empty
root and the bubble-up operation from prio_queue_put().  The latter can
easily be factored out into a sift-up function, reducing code
duplication.

Extending sift_down_root() to deal with an empty root would be easy as
well, but also a bit tricky to avoid pointless checks for each caller.
Not sure it's worth it.  Like this perhaps?

static inline size_t sift_down_root(struct prio_queue *queue, bool empty)
{
        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 */
                if (child + 1 < queue->nr_ &&
                    compare(queue, child, child + 1) >= 0)
                        child++; /* use right child */

                if (empty)
                        queue->array[ix] = queue->array[child];
                else if (compare(queue, ix, child) <= 0)
                        break;
                else
                        swap(queue, child, ix);
        }
        return ix;
}

Anyway, my point is that it's not "adding another sift function", but
remixing existing ones, which I only count as half. :)

I'd very much like to see this go in because it seems to be strictly
faster, makes intuitive sense and adds only little code.   I didn't
find this method used anywhere else, which is a warning sign, but I
can't find any catch.

René


  $ for n in $(seq 2 2)
    do
        t/helper/test-tool prio-queue permute get $n |
        awk -v n=$n -v max=0 '
            {sum+=$2}
            max < $2 {max=$2}
            !min || min > $2 {min=$2}
            END {printf "%2d %3d %3d %5.1f \n", n, min, max, sum/NR}
        '
    done

---
 Makefile                   |  1 +
 t/helper/test-prio-queue.c | 91 ++++++++++++++++++++++++++++++++++++++++++++++
 t/helper/test-tool.c       |  1 +
 t/helper/test-tool.h       |  1 +
 4 files changed, 94 insertions(+)

diff --git a/Makefile b/Makefile
index 1f3f099f5c5..ba7d293cf5f 100644
--- a/Makefile
+++ b/Makefile

@@ -843,6 +843,7 @@ TEST_BUILTINS_OBJS += test-partial-clone.o
 TEST_BUILTINS_OBJS += test-path-utils.o
 TEST_BUILTINS_OBJS += test-path-walk.o
 TEST_BUILTINS_OBJS += test-pcre2-config.o
+TEST_BUILTINS_OBJS += test-prio-queue.o
 TEST_BUILTINS_OBJS += test-pkt-line.o
 TEST_BUILTINS_OBJS += test-proc-receive.o
 TEST_BUILTINS_OBJS += test-progress.o

diff --git a/t/helper/test-prio-queue.c b/t/helper/test-prio-queue.c
new file mode 100644
index 00000000000..c175021b12b
--- /dev/null
+++ b/t/helper/test-prio-queue.c

@@ -0,0 +1,91 @@
+#include "test-tool.h"
+#include "prio-queue.h"
+
+/* Generate all permutations using Heap's algorithm. */
+static int permute_ints(size_t n, void (*fn)(int *, size_t))
+{
+	int *arr;
+	size_t *c;
+
+	ALLOC_ARRAY(arr, n);
+	for (size_t i = 0; i < n; i++)
+		arr[i] = i + 1;
+	CALLOC_ARRAY(c, n);
+
+	fn(arr, n);
+	for (size_t i = 1; i < n; i++) {
+		if (c[i] < i) {
+			SWAP(arr[i & 1 ? c[i] : 0], arr[i]);
+			fn(arr, n);
+			c[i]++;
+			i = 0;
+		} else {
+			c[i] = 0;
+		}
+	}
+
+	free(arr);
+	free(c);
+
+	return 0;
+}
+
+static uintmax_t nr_of_compares;
+
+static int compare_ints(const void *a_, const void *b_, void *cb_data UNUSED)
+{
+	const int *a = a_;
+	const int *b = b_;
+	nr_of_compares++;
+	return *a - *b;
+}
+
+static void report(const char *name, const int *arr, size_t n)
+{
+	printf("%s %"PRIuMAX" for", name, nr_of_compares);
+	for (size_t i = 0; i < n; i++)
+		printf(" %d", arr[i]);
+	putchar('\n');
+}
+
+static void get_permutation(int *arr, size_t n)
+{
+	static struct prio_queue queue = { compare_ints };
+
+	for (size_t i = 0; i < n; i++)
+		prio_queue_put(&queue, &arr[i]);
+
+	nr_of_compares = 0;
+	for (size_t i = 0; i < n; i++)
+		prio_queue_get(&queue);
+
+	report("get", arr, n);
+}
+
+static void put_permutation(int *arr, size_t n)
+{
+	struct prio_queue queue = { compare_ints };
+
+	nr_of_compares = 0;
+	for (size_t i = 0; i < n; i++)
+		prio_queue_put(&queue, &arr[i]);
+
+	report("put", arr, n);
+
+	clear_prio_queue(&queue);
+}
+
+int cmd__prio_queue(int argc, const char **argv)
+{
+	if (argc == 4 && !strcmp(argv[1], "permute")) {
+		size_t n = strtoul(argv[3], NULL, 10);
+		if (!strcmp(argv[2], "get"))
+			return permute_ints(n, get_permutation);
+		if (!strcmp(argv[2], "put"))
+			return permute_ints(n, put_permutation);
+	}
+
+	fprintf(stderr, "usage: test-tool prio-queue permute get <n>\n");
+	fprintf(stderr, "   or: test-tool prio-queue permute put <n>\n");
+	return 129;
+}

diff --git a/t/helper/test-tool.c b/t/helper/test-tool.c
index b71a22b43bb..69352f541f4 100644
--- a/t/helper/test-tool.c
+++ b/t/helper/test-tool.c

@@ -57,6 +57,7 @@ static struct test_cmd cmds[] = {
 	{ "path-walk", cmd__path_walk },
 	{ "pcre2-config", cmd__pcre2_config },
 	{ "pkt-line", cmd__pkt_line },
+	{ "prio-queue", cmd__prio_queue },
 	{ "proc-receive", cmd__proc_receive },
 	{ "progress", cmd__progress },
 	{ "reach", cmd__reach },

diff --git a/t/helper/test-tool.h b/t/helper/test-tool.h
index f2885b33d58..ab0d3e01d1e 100644
--- a/t/helper/test-tool.h
+++ b/t/helper/test-tool.h

@@ -50,6 +50,7 @@ int cmd__path_utils(int argc, const char **argv);
 int cmd__path_walk(int argc, const char **argv);
 int cmd__pcre2_config(int argc, const char **argv);
 int cmd__pkt_line(int argc, const char **argv);
+int cmd__prio_queue(int argc, const char **argv);
 int cmd__proc_receive(int argc, const char **argv);
 int cmd__progress(int argc, const char **argv);
 int cmd__reach(int argc, const char **argv);