Re: [PATCH v3 2/2] prio-queue: use cascade for unfused gets

["René Scharfe" <l.s.r@web.de>]

On 7/8/26 7:49 PM, Kristofer Karlsson via GitGitGadget wrote:
> From: Kristofer Karlsson <krka@spotify.com>
> 
> When flush_get() removes the root without an immediate replacement,
> use a cascade-then-sift-up strategy instead of sift-down.
> 
> Standard sift-down places the last element at the root and sifts it
> down.  This needs two comparisons per level (pick the smaller child,
> then compare against the element), even though the displaced element
> almost always ends up near the bottom where it came from.
> 
> cascade_down() instead moves the vacancy down by promoting the
> smaller child at each level (one comparison per level), leaving the
> vacancy at a leaf.  The last element is then placed at the vacancy
> and sift_up() floats it to its correct position, which is typically
> very little work since it already belongs near the bottom.
> 
> This is the well-known "bottom-up" variant of sift-down [1].
> 
> [1] https://en.wikipedia.org/wiki/Heapsort#Bottom-up_heapsort

On an Apple M1 I get a 1% slowdown for bulk describe on Git's repo:

Benchmark 1: ./git_next describe $(git rev-list v2.41.0..v2.47.0)
  Time (mean ± σ):     939.5 ms ±   3.6 ms    [User: 576.8 ms, System: 65.0 ms]
  Range (min … max):   935.0 ms … 946.2 ms    10 runs

Benchmark 2: ./git describe $(git rev-list v2.41.0..v2.47.0)
  Time (mean ± σ):     945.5 ms ±   3.3 ms    [User: 581.6 ms, System: 67.5 ms]
  Range (min … max):   940.1 ms … 950.5 ms    10 runs

Summary
  ./git_next describe $(git rev-list v2.41.0..v2.47.0) ran
    1.01 ± 0.01 times faster than ./git describe $(git rev-list v2.41.0..v2.47.0)

... and on Linux's repo:

Benchmark 1: ./git_next -C ../linux describe $(git -C ../linux rev-list v4.0..v4.1)
  Time (mean ± σ):      4.880 s ±  0.014 s    [User: 3.914 s, System: 0.252 s]
  Range (min … max):    4.864 s …  4.905 s    10 runs

Benchmark 2: ./git -C ../linux describe $(git -C ../linux rev-list v4.0..v4.1)
  Time (mean ± σ):      4.917 s ±  0.011 s    [User: 3.948 s, System: 0.254 s]
  Range (min … max):    4.902 s …  4.938 s    10 runs

Summary
  ./git_next -C ../linux describe $(git -C ../linux rev-list v4.0..v4.1) ran
    1.01 ± 0.00 times faster than ./git -C ../linux describe $(git -C ../linux rev-list v4.0..v4.1)

I see a 1% slowdown on an Apple M5 as well in both cases.  I can't
reproduce it on a Ryzen laptop, but that's too noisy to measure 1%
changes anyway.

Checked the total number of prio_queue comparisons with the crude patch
below, and as expected they go down, from 70386235 to 60682175 for Git
and from 473983445 to 439809087 for Linux.  So there's less work to do,
still user time goes up -- no idea why.

Also this -- what's up with the system time here:

Benchmark 1: ./git_next rev-list --all --count
  Time (mean ± σ):     115.2 ms ±   0.8 ms    [User: 95.6 ms, System: 17.7 ms]
  Range (min … max):   113.0 ms … 117.1 ms    24 runs

Benchmark 2: ./git rev-list --all --count
  Time (mean ± σ):     116.5 ms ±   0.8 ms    [User: 95.4 ms, System: 19.0 ms]
  Range (min … max):   115.1 ms … 118.6 ms    24 runs

Summary
  ./git_next rev-list --all --count ran
    1.01 ± 0.01 times faster than ./git rev-list --all --count

But:

Benchmark 1: ./git_next -C ../linux rev-list --all --count
  Time (mean ± σ):     937.6 ms ±   2.2 ms    [User: 887.2 ms, System: 45.5 ms]
  Range (min … max):   933.2 ms … 939.9 ms    10 runs

Benchmark 2: ./git -C ../linux rev-list --all --count
  Time (mean ± σ):     937.3 ms ±   1.7 ms    [User: 887.8 ms, System: 45.0 ms]
  Range (min … max):   934.6 ms … 940.3 ms    10 runs

Summary
  ./git -C ../linux rev-list --all --count ran
    1.00 ± 0.00 times faster than ./git_next -C ../linux rev-list --all --count

:-?

> Helped-by: Rene Scharfe <l.s.r@web.de>
> Signed-off-by: Kristofer Karlsson <krka@spotify.com>
> ---
>  prio-queue.c | 22 ++++++++++++++++++++--
>  1 file changed, 20 insertions(+), 2 deletions(-)
> 
> diff --git a/prio-queue.c b/prio-queue.c
> index 926fc04e85..230d6f5e33 100644
> --- a/prio-queue.c
> +++ b/prio-queue.c
> @@ -66,13 +66,31 @@ static void sift_down_root(struct prio_queue *queue)
>  	}
>  }
>  
> +/* Cascade vacancy toward a leaf, promoting the smaller child at each level */
> +static size_t cascade_down(struct prio_queue *queue)
> +{
> +	size_t ix, child;
> +
> +	for (ix = 0; (child = ix * 2 + 1) < queue->nr_; ix = child) {
> +		if (child + 1 < queue->nr_ &&
> +		    compare(queue, child, child + 1) >= 0)
> +			child++;
> +		queue->array[ix] = queue->array[child];
> +	}
> +	return ix;
> +}
> +
>  static inline void flush_get(struct prio_queue *queue)
>  {
> +	size_t ix;
> +
>  	if (!queue->get_pending)
>  		return;
>  	queue->get_pending = 0;
> -	queue->array[0] = queue->array[--queue->nr_];
> -	sift_down_root(queue);
> +	--queue->nr_;
> +	ix = cascade_down(queue);
> +	queue->array[ix] = queue->array[queue->nr_];
> +	sift_up(queue, ix);
>  }
>  
>  void prio_queue_put(struct prio_queue *queue, void *thing)

The patch looks fine, though.  It introduces struct assignments, but
they should be OK.  Tried replacing them with swap() instead (which
does a useless extra write), but that didn't change the performance
(still 1% slowdown).  Odd.

René


diff --git a/builtin/describe.c b/builtin/describe.c
index c0abc931a59..4a6ad976d30 100644
--- a/builtin/describe.c
+++ b/builtin/describe.c
@@ -791,5 +791,6 @@ int cmd_describe(int argc,
 		while (argc-- > 0)
 			describe(*argv++, argc == 0);
 	}
+	print_compares();
 	return 0;
 }
diff --git a/prio-queue.c b/prio-queue.c
index 199775d5afd..b0189bf80e6 100644
--- a/prio-queue.c
+++ b/prio-queue.c
@@ -1,6 +1,13 @@
 #include "git-compat-util.h"
 #include "prio-queue.h"
 
+static uintmax_t compares;
+
+void print_compares(void)
+{
+	fprintf(stderr, "compares: %lu\n", compares);
+}
+
 static inline int compare(struct prio_queue *queue, size_t i, size_t j)
 {
 	int cmp = queue->compare(queue->array[i].data, queue->array[j].data,
@@ -8,6 +15,7 @@ static inline int compare(struct prio_queue *queue, size_t i, size_t j)
 	if (!cmp)
 		cmp = (queue->array[i].ctr > queue->array[j].ctr) -
 		      (queue->array[i].ctr < queue->array[j].ctr);
+	compares++;
 	return cmp;
 }
 
diff --git a/prio-queue.h b/prio-queue.h
index 570b48e6485..e4cc0c4fb83 100644
--- a/prio-queue.h
+++ b/prio-queue.h
@@ -68,4 +68,6 @@ void clear_prio_queue(struct prio_queue *);
 /* Reverse the LIFO elements */
 void prio_queue_reverse(struct prio_queue *);
 
+void print_compares(void);
+
 #endif /* PRIO_QUEUE_H */