[PATCH v3 0/2] prio-queue: use bottom-up sift for extract-min

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

This tweaks the prio_queue implementation to use a bottom-up approach
sifting for get [1].

In practice, the performance boost is small, but measurable for reasonably
large prio_queue:s (thousands of elements, not millions) but it should never
increase the work.

Minor note on v3: After the most recent discussion I am not 100% sure how to
reason about the value of this change - both the value gain and code cost
seem small, but since there was some interest and research done by René I
wanted to complete this v3 anyway so it can be properly discussed (though
still maybe ultimately closed).

Here's how it works:

Instead of placing the last element at the root and sifting it down with two
comparisons per level, cascade the vacancy down by promoting the smaller
child (one comparison per level), then place the last element at the vacancy
and sift it up. Since the displaced element is likely to belong near the
bottom of the heap, sift_up() typically does very little work.

sift_down_root() is kept as-is for the fused replace path in
prio_queue_put(), where the new element is arbitrary and may belong near the
root -- Rene's testing showed that cascade regresses on git-describe for
this reason.

Benchmarks (rev-list --all --count) on public repos confirm no regression on
git.git and linux.git. On a large example repo with thousands of active
branches the cascade yields a measurable (~2%) end-to-end improvement; the
gain is modest because the lazy-fold optimization (now in next) already
fuses most get+put pairs, leaving only the remaining unfused gets to benefit
from cascade.

René's exhaustive analysis [2] of all permutations up to n=12 confirms that
cascade never requires more comparisons than standard sift-down for a full
drain.

Note: sift_up() currently uses swap, matching the existing code style. It
could be further optimized to use copy (hold the element in a temp, shift
parents down, write once), but that would require changing compare() to
accept element values instead of array indices. Left for a potential
follow-up.

Changes since v2:

 * Rebased on kk/prio-queue-get-put-fusion (now in next).

 * Split into two commits - refactoring and then introducing cascade_down.

Changes since v1:

 * Kept sift_down_root() and prio_queue_replace() completely unchanged,
   preserving René's optimization that avoids the get+put overhead for
   replace. The cascade approach now only applies to prio_queue_get().

 * Extracted the new logic into a separate sift_up_rebalance() function
   rather than inlining it in prio_queue_get().

 * Updated benchmark numbers for ascending, descending and random insertion
   ordering. No regressions in any scenario.

[1] https://en.wikipedia.org/wiki/Heapsort#Bottom-up_heapsort [2]
https://lore.kernel.org/git/pull.2132.git.1780250236304.gitgitgadget@gmail.com/T/#m114df6e1c2845acbbc64d875ed7dc1d7d9193ed5

Kristofer Karlsson (2):
  prio-queue: extract sift_up() from prio_queue_put()
  prio-queue: use cascade for unfused gets

 prio-queue.c | 43 ++++++++++++++++++++++++++++++++-----------
 1 file changed, 32 insertions(+), 11 deletions(-)


base-commit: 00534a21ce949ef80a5b8b9d7fc20b7d381038e9
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2132%2Fspkrka%2Fcascade-sift-down-v3
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2132/spkrka/cascade-sift-down-v3
Pull-Request: https://github.com/gitgitgadget/git/pull/2132

Range-diff vs v2:

 -:  ---------- > 1:  ec6a448563 prio-queue: extract sift_up() from prio_queue_put()
 1:  6051d44e59 ! 2:  89a22c6a75 prio-queue: use cascade-down for faster extract-min
     @@ Metadata
      Author: Kristofer Karlsson <krka@spotify.com>
      
       ## Commit message ##
     -    prio-queue: use cascade-down for faster extract-min
     +    prio-queue: use cascade for unfused gets
      
     -    Add sift_up_rebalance(), an alternative to sift_down_root() that
     -    halves the number of comparisons per extract-min.
     +    When flush_get() removes the root without an immediate replacement,
     +    use a cascade-then-sift-up strategy instead of sift-down.
      
     -    The standard extract places the last array element at the root and
     -    sifts it down.  At each level this requires two comparisons (left
     -    vs right child, then element vs winner) and a swap.
     +    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.
      
     -    sift_up_rebalance() instead promotes the smaller child into the
     -    root slot at each level — one comparison and one copy — until the
     -    vacancy reaches a leaf.  The last array element is placed at the
     -    vacancy and sifted up to restore heap order.  In practice the
     -    sift-up rarely moves more than a level or two because the last
     -    array element tends to be large.
     +    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.
      
     -    Work per extract drops from 2d comparisons + d swaps to
     -    d comparisons + d copies + a short sift-up.
     +    This is the well-known "bottom-up" variant of sift-down [1].
      
     -    prio_queue_get() now calls sift_up_rebalance() instead of placing
     -    the last element at root and calling sift_down_root().
     -
     -    sift_down_root() and prio_queue_replace() are left unchanged.
     -
     -    Synthetic benchmark (10 rounds of 10M put+get cycles, CPU-pinned,
     -    same compiler and Makefile flags):
     -
     -    Ascending keys (git's typical pattern — parents have lower
     -    priority than children):
     -
     -      queue width  baseline  patched  speedup
     -               10     4.39s    3.91s    1.12x
     -              100     9.10s    6.61s    1.38x
     -            1,000    11.84s    9.25s    1.28x
     -           10,000    17.50s   13.92s    1.26x
     -          100,000    23.97s   20.19s    1.19x
     -
     -    Descending keys (worst case — last element always sinks to leaf):
     -
     -      queue width  baseline  patched  speedup
     -               10     4.94s    4.95s    1.00x
     -              100     9.75s    9.42s    1.03x
     -            1,000    15.01s   15.29s    0.98x
     -           10,000    24.79s   23.88s    1.04x
     -          100,000    29.69s   28.24s    1.05x
     -
     -    Random keys:
     -
     -      queue width  baseline  patched  speedup
     -               10     5.05s    4.99s    1.01x
     -              100     9.90s    9.50s    1.04x
     -            1,000    15.35s   14.77s    1.04x
     -           10,000    25.35s   24.21s    1.05x
     -          100,000    65.71s   63.38s    1.04x
     -
     -    No regressions in any scenario.
     -
     -    End-to-end benchmark on the linux kernel repo (1.4M commits,
     -    range v5.0..v6.0, 311K commits, 20 interleaved runs, 1 warmup):
     -
     -      Command                      baseline  patched  speedup
     -      rev-list --count v5.0..v6.0    484ms     474ms    1.02x
     -
     -    The improvement scales with DAG width: wider DAGs produce larger
     -    priority queues, amplifying the per-level savings.  In small or
     -    narrow repositories the queues stay shallow and the sift-down
     -    cost is already negligible.
     +    [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 ##
     @@ prio-queue.c: static void sift_down_root(struct prio_queue *queue)
       	}
       }
       
     -+static void sift_up_rebalance(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;
      +
     -+	/* Cascade: promote smaller child at each level. */
     -+	for (ix = 0; (child = ix * 2 + 1) < queue->nr; ix = child) {
     -+		if (child + 1 < queue->nr &&
     ++	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];
      +	}
     -+
     -+	/* Place the last element at the vacancy and sift up. */
     -+	queue->array[ix] = queue->array[queue->nr];
     -+	while (ix) {
     -+		size_t parent = (ix - 1) / 2;
     -+		if (compare(queue, parent, ix) <= 0)
     -+			break;
     -+		swap(queue, parent, ix);
     -+		ix = parent;
     -+	}
     ++	return ix;
      +}
      +
     - void *prio_queue_get(struct prio_queue *queue)
     + static inline void flush_get(struct prio_queue *queue)
       {
     - 	void *result;
     -@@ prio-queue.c: void *prio_queue_get(struct prio_queue *queue)
     - 	if (!--queue->nr)
     - 		return result;
     - 
     --	queue->array[0] = queue->array[queue->nr];
     ++	size_t ix;
     ++
     + 	if (!queue->get_pending)
     + 		return;
     + 	queue->get_pending = 0;
     +-	queue->array[0] = queue->array[--queue->nr_];
      -	sift_down_root(queue);
     -+	sift_up_rebalance(queue);
     - 	return result;
     ++	--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