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

["Kristofer Karlsson via GitGitGadget" <gitgitgadget@gmail.com>]

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

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)
-- 
gitgitgadget