From: René Scharfe Date: Wed, 08 Jul 2026 10:43:52 GMT Subject: Re: [PATCH v2] prio-queue: use cascade-down for faster extract-min Message-ID: <57bb0e9e-221d-4234-b5bc-a87610e8263c@web.de> In-Reply-To: On 7/6/26 11:52 PM, Kristofer Karlsson wrote: > On Sun, 7 Jun 2026 at 09:30, René Scharfe wrote: >> >> 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"); + fprintf(stderr, " or: test-tool prio-queue permute put \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);