Hello,
The purpose of this patch series is to enhance the existing min heap
implementation. The optimization focuses on both the heap construction
process and the number of comparisons made during the heapify
operation.
Thanks,
Kuan-Wei Chiu
---
Changes in v2:
- Use a more consistent title: "min_heap:" -> "lib min_heap:"
- Refine commit messages
v1: https://lkml.kernel.org/[email protected]
Kuan-Wei Chiu (2):
lib min_heap: Optimize number of calls to min_heapify()
lib min_heap: Optimize number of comparisons in min_heapify()
include/linux/min_heap.h | 44 +++++++++++++++++++++-------------------
1 file changed, 23 insertions(+), 21 deletions(-)
--
2.25.1
Improve the heap construction process by reducing unnecessary heapify
operations. Specifically, adjust the starting condition from n / 2 to
n / 2 - 1 in the loop that iterates over all non-leaf elements.
Signed-off-by: Kuan-Wei Chiu <[email protected]>
---
include/linux/min_heap.h | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h
index 44077837385f..18a581310eb3 100644
--- a/include/linux/min_heap.h
+++ b/include/linux/min_heap.h
@@ -70,7 +70,7 @@ void min_heapify_all(struct min_heap *heap,
{
int i;
- for (i = heap->nr / 2; i >= 0; i--)
+ for (i = heap->nr / 2 - 1; i >= 0; i--)
min_heapify(heap, i, func);
}
--
2.25.1
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.
Signed-off-by: Kuan-Wei Chiu <[email protected]>
---
include/linux/min_heap.h | 42 +++++++++++++++++++++-------------------
1 file changed, 22 insertions(+), 20 deletions(-)
diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h
index 18a581310eb3..d52daf45861b 100644
--- a/include/linux/min_heap.h
+++ b/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;
-
- 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;
+ /* Special case for the last leaf with no sibling. */
+ if (i * 2 + 2 == heap->nr)
+ i = i * 2 + 1;
+
+ /* 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);
}
}
--
2.25.1
On Thu, 4 Jan 2024 04:52:57 +0800 Kuan-Wei Chiu <[email protected]> wrote:
> Hello,
>
> The purpose of this patch series is to enhance the existing min heap
> implementation. The optimization focuses on both the heap construction
> process and the number of comparisons made during the heapify
> operation.
>
The patches look nice, but the only user of this code is
kernel/events/core.c and the developers of that code aren't cc'ed, so
please rectify that.
Has Ian commented on these changes?
The amount of inlining in min_heap.h is amazing. Was there some
special reason for this? It makes min_heap somewhat unsuitable for
more general use.