Skip to contentSkip to conversation

lib min_heap: Min heap optimizations

PATCH RESEND Applied Kuan-Wei Chiu 1 participant 3 messages Jan 10, 2024 Min heap

lore
Share & tools
lore

Kuan-Wei Chiu

author maintainer
#0 lore raw

v2 cover lib min_heap: Min heap optimizations

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 RESEND:
- CC the mailing list

Changes in RESEND:
- CC performance events subsystem's maintainers and reviewers.

Changes in v2:
- Use a more consistent title: "min_heap:" -> "lib min_heap:"
- Refine commit messages

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(-)
Signature · 1 line
2.25.1
author maintainer
#1 lore raw

PATCH RESEND v2 1/2 lib min_heap: Optimize number of calls to min_heapify()

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.

---
 include/linux/min_heap.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
include/linux/min_heap.h +1 -1
index 44077837385f..18a581310eb3 100644
@@ -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);
 }
 
Signature · 1 line
2.25.1
author maintainer
#2 lore raw

PATCH RESEND v2 2/2 lib min_heap: Optimize number of comparisons in min_heapify()

In reply to Kuan-Wei Chiu

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.

---
 include/linux/min_heap.h | 42 +++++++++++++++++++++-------------------
 1 file changed, 22 insertions(+), 20 deletions(-)
include/linux/min_heap.h +22 -20
index 18a581310eb3..d52daf45861b 100644
@@ -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);
 	}
 }
 
Signature · 1 line
2.25.1