The quilt patch titled
Subject: lib min_heap: optimize number of comparisons in min_heapify()
has been removed from the -mm tree. Its filename was
lib-min_heap-optimize-number-of-comparisons-in-min_heapify.patch
This patch was dropped because it was merged into the mm-hotfixes-stable branch
of git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
------------------------------------------------------
From: Kuan-Wei Chiu <visitorckw@xxxxxxxxx>
Subject: lib min_heap: optimize number of comparisons in min_heapify()
Date: Wed, 10 Jan 2024 16:12:13 +0800
Optimize the min_heapify() function, resulting in a significant reduction
of approximately 50% in the number of comparisons for large random inputs,
while maintaining identical results.
The current implementation performs two comparisons per level to identify
the minimum among three elements. In contrast, the proposed bottom-up
variation uses only one comparison per level to assess two children until
reaching the leaves. Then, it sifts up until the correct position is
determined.
Typically, the process of sifting down proceeds to the leaf level,
resulting in O(1) secondary comparisons instead of log2(n). This
optimization significantly reduces the number of costly indirect function
calls and improves overall performance.
Link: https://lkml.kernel.org/r/20240110081213.2289636-3-visitorckw@xxxxxxxxx
Signed-off-by: Kuan-Wei Chiu <visitorckw@xxxxxxxxx>
Acked-by: Ian Rogers <irogers@xxxxxxxxxx>
Cc: Adrian Hunter <adrian.hunter@xxxxxxxxx>
Cc: Alexander Shishkin <alexander.shishkin@xxxxxxxxxxxxxxx>
Cc: Arnaldo Carvalho de Melo <acme@xxxxxxxxxx>
Cc: Ingo Molnar <mingo@xxxxxxxxxx>
Cc: Jiri Olsa <jolsa@xxxxxxxxxx>
Cc: Mark Rutland <mark.rutland@xxxxxxx>
Cc: Namhyung Kim <namhyung@xxxxxxxxxx>
Cc: Peter Zijlstra <peterz@xxxxxxxxxxxxx>
Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
---
include/linux/min_heap.h | 40 +++++++++++++++++++------------------
1 file changed, 21 insertions(+), 19 deletions(-)
--- a/include/linux/min_heap.h~lib-min_heap-optimize-number-of-comparisons-in-min_heapify
+++ a/include/linux/min_heap.h
@@ -35,31 +35,33 @@ static __always_inline
void min_heapify(struct min_heap *heap, int pos,
const struct min_heap_callbacks *func)
{
- void *left, *right, *parent, *smallest;
+ void *left, *right;
void *data = heap->data;
+ void *root = data + pos * func->elem_size;
+ int i = pos, j;
+ /* Find the sift-down path all the way to the leaves. */
for (;;) {
- if (pos * 2 + 1 >= heap->nr)
+ if (i * 2 + 2 >= heap->nr)
break;
+ left = data + (i * 2 + 1) * func->elem_size;
+ right = data + (i * 2 + 2) * func->elem_size;
+ i = func->less(left, right) ? i * 2 + 1 : i * 2 + 2;
+ }
- left = data + ((pos * 2 + 1) * func->elem_size);
- parent = data + (pos * func->elem_size);
- smallest = parent;
- if (func->less(left, smallest))
- smallest = left;
+ /* Special case for the last leaf with no sibling. */
+ if (i * 2 + 2 == heap->nr)
+ i = i * 2 + 1;
- if (pos * 2 + 2 < heap->nr) {
- right = data + ((pos * 2 + 2) * func->elem_size);
- if (func->less(right, smallest))
- smallest = right;
- }
- if (smallest == parent)
- break;
- func->swp(smallest, parent);
- if (smallest == left)
- pos = (pos * 2) + 1;
- else
- pos = (pos * 2) + 2;
+ /* Backtrack to the correct location. */
+ while (i != pos && func->less(root, data + i * func->elem_size))
+ i = (i - 1) / 2;
+
+ /* Shift the element into its correct place. */
+ j = i;
+ while (i != pos) {
+ i = (i - 1) / 2;
+ func->swp(data + i * func->elem_size, data + j * func->elem_size);
}
}
_
Patches currently in -mm which might be from visitorckw@xxxxxxxxx are
