min_heap: Min heap optimizations
Kuan-Wei Chiu
maintainercover 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.
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(-)
Signature · 1 line
2.25.1
Kuan-Wei Chiu
maintainerPATCH 1/2 min_heap: Optimize number of calls to min_heapify()
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.
--- include/linux/min_heap.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
include/linux/min_heap.h +1 -1
@@ -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
Kuan-Wei Chiu
maintainerPATCH 2/2 min_heap: Optimize number of comparisons in min_heapify()
In reply to Kuan-Wei ChiuThis 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.
--- include/linux/min_heap.h | 42 +++++++++++++++++++++------------------- 1 file changed, 22 insertions(+), 20 deletions(-)
include/linux/min_heap.h +22 -20
@@ -35,31 +35,33 @@ static __always_inlinevoid 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
Quoted 11 lines · 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 tomin_heapify()
min_heap: Optimize number of comparisons inmin_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
Quoted 7 lines
include/linux/min_heap.h | 44 +++++++++++++++++++++------------------- 1 file changed, 23 insertions(+), 21 deletions(-)--
2.25.1
Kuan-Wei Chiu
maintainerQuoted 13 lines · Ian Rogers
Quoted 11 lines · 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 tomin_heapify()
min_heap: Optimize number of comparisons inmin_heapify()
Quoted 7 lines
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
Quoted 24 lines · Kuan-Wei Chiu
Quoted 13 lines · Ian Rogers
Quoted 11 lines · 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 tomin_heapify()
min_heap: Optimize number of comparisons inmin_heapify()Quoted 7 lines
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,
Quoted 8 lines
Thank you for your review.
The current
min_heaptest 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