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

Submitted-As: https://lore.kernel.org/git/pull.2132.v3.git.1783532989.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2132.git.1780250236304.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2132.v2.git.1780301856444.gitgitgadget@gmail.com