[PATCH 0/2] min_heap: Min heap optimizations

[PATCH 0/2] min_heap: Min heap optimizations

[Kuan-Wei Chiu]

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.

Kuan-Wei Chiu (2):
  min_heap: Optimize number of calls to min_heapify()
  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

[PATCH 1/2] min_heap: Optimize number of calls to min_heapify()

[Kuan-Wei Chiu]

This patch improves the heap construction process by reducing
unnecessary heapify operations. Specifically, it adjusts 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 <visitorckw@gmail.com>
---
 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

[PATCH 2/2] min_heap: Optimize number of comparisons in min_heapify()

[Kuan-Wei Chiu]

This patch optimizes 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 <visitorckw@gmail.com>
---
 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

Re: [PATCH 0/2] min_heap: Min heap optimizations

[Ian Rogers]

On Wed, Dec 20, 2023 at 12:32 AM Kuan-Wei Chiu <visitorckw@gmail.com> 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.
>
> Kuan-Wei Chiu (2):
>   min_heap: Optimize number of calls to min_heapify()
>   min_heap: Optimize number of comparisons in min_heapify()

Thanks Kuan-Wei,

The patch series looks good to me. Given the extra conditions should
there be some updates to:
https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/lib/test_min_heap.c
to ensure coverage?

Thanks,
Ian

>
>  include/linux/min_heap.h | 44 +++++++++++++++++++++-------------------
>  1 file changed, 23 insertions(+), 21 deletions(-)
>
> --
> 2.25.1
>

Re: [PATCH 0/2] min_heap: Min heap optimizations

[Kuan-Wei Chiu]

On Wed, Jan 03, 2024 at 09:56:29AM -0800, Ian Rogers wrote:
> On Wed, Dec 20, 2023 at 12:32 AM Kuan-Wei Chiu <visitorckw@gmail.com> 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.
> >
> > Kuan-Wei Chiu (2):
> >   min_heap: Optimize number of calls to min_heapify()
> >   min_heap: Optimize number of comparisons in min_heapify()
> 
> Thanks Kuan-Wei,
> 
> The patch series looks good to me. Given the extra conditions should
> there be some updates to:
> https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/lib/test_min_heap.c
> to ensure coverage?
>
Hi Ian,

Thank you for your review.

The current min_heap test is sufficient to cover all the code changes
introduced by this patch series, even when only tested with a known
set of values copied from the data.

Additionally, I'm unsure if the commit message title prefix I used is
correct. Perhaps I should use "lib:" instead of "min_heap:"?

Best regards,
Kuan-Wei Chiu

Re: [PATCH 0/2] min_heap: Min heap optimizations

[Ian Rogers]

On Wed, Jan 3, 2024 at 12:08 PM Kuan-Wei Chiu <visitorckw@gmail.com> wrote:
>
> On Wed, Jan 03, 2024 at 09:56:29AM -0800, Ian Rogers wrote:
> > On Wed, Dec 20, 2023 at 12:32 AM Kuan-Wei Chiu <visitorckw@gmail.com> 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.
> > >
> > > Kuan-Wei Chiu (2):
> > >   min_heap: Optimize number of calls to min_heapify()
> > >   min_heap: Optimize number of comparisons in min_heapify()
> >
> > Thanks Kuan-Wei,
> >
> > The patch series looks good to me. Given the extra conditions should
> > there be some updates to:
> > https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/lib/test_min_heap.c
> > to ensure coverage?
> >
> Hi Ian,
>
> Thank you for your review.
>
> The current min_heap test is sufficient to cover all the code changes
> introduced by this patch series, even when only tested with a known
> set of values copied from the data.
>
> Additionally, I'm unsure if the commit message title prefix I used is
> correct. Perhaps I should use "lib:" instead of "min_heap:"?

Yes, "lib:" would be most consistent or "lib min_heap:". Could you
update this in a v2?

Thanks,
Ian