The patch titled
Subject: lib/sort: optimize heapsort for handling final 2 or 3 elements
has been added to the -mm mm-nonmm-unstable branch. Its filename is
lib-sort-optimize-heapsort-for-handling-final-2-or-3-elements.patch
This patch will shortly appear at
https://git.kernel.org/pub/scm/linux/kernel/git/akpm/25-new.git/tree/patches/lib-sort-optimize-heapsort-for-handling-final-2-or-3-elements.patch
This patch will later appear in the mm-nonmm-unstable branch at
git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
Before you just go and hit "reply", please:
a) Consider who else should be cc'ed
b) Prefer to cc a suitable mailing list as well
c) Ideally: find the original patch on the mailing list and do a
reply-to-all to that, adding suitable additional cc's
*** Remember to use Documentation/process/submit-checklist.rst when testing your code ***
The -mm tree is included into linux-next via the mm-everything
branch at git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
and is updated there every 2-3 working days
------------------------------------------------------
From: Kuan-Wei Chiu <visitorckw@xxxxxxxxx>
Subject: lib/sort: optimize heapsort for handling final 2 or 3 elements
Date: Tue, 28 May 2024 04:30:10 +0800
After building the heap, the code continuously pops two elements from the
heap until only 2 or 3 elements remain, at which point it switches back to
a regular heapsort with one element popped at a time. However, to handle
the final 2 or 3 elements, an additional else-if statement in the while
loop was introduced, potentially increasing branch misses. Moreover, when
there are only 2 or 3 elements left, continuing with regular heapify
operations is unnecessary as these cases are simple enough to be handled
with a single comparison and 1 or 2 swaps outside the while loop.
Eliminating the additional else-if statement and directly managing cases
involving 2 or 3 elements outside the loop reduces unnecessary conditional
branches resulting from the numerous loops and conditionals in heapify.
This optimization maintains consistent numbers of comparisons and swaps
for arrays with even lengths while reducing swaps and comparisons for
arrays with odd lengths from 2.5 swaps and 1 comparison to 1.5 swaps and 1
comparison.
Link: https://lkml.kernel.org/r/20240527203011.1644280-4-visitorckw@xxxxxxxxx
Signed-off-by: Kuan-Wei Chiu <visitorckw@xxxxxxxxx>
Cc: Ching-Chun (Jim) Huang <jserv@xxxxxxxxxxxxxxxx>
Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
---
lib/sort.c | 10 ++++++----
1 file changed, 6 insertions(+), 4 deletions(-)
--- a/lib/sort.c~lib-sort-optimize-heapsort-for-handling-final-2-or-3-elements
+++ a/lib/sort.c
@@ -250,10 +250,7 @@ void sort_r(void *base, size_t num, size
a = size << shift;
n -= size;
do_swap(base + a, base + n, size, swap_func, priv);
- } else if (n > size) { /* Sorting: Extract root */
- n -= size;
- do_swap(base, base + n, size, swap_func, priv);
- } else { /* Sort complete */
+ } else { /* Sort complete */
break;
}
@@ -283,6 +280,11 @@ void sort_r(void *base, size_t num, size
do_swap(base + b, base + c, size, swap_func, priv);
}
}
+
+ n -= size;
+ do_swap(base, base + n, size, swap_func, priv);
+ if (n == size * 2 && do_cmp(base, base + size, cmp_func, priv) > 0)
+ do_swap(base, base + size, size, swap_func, priv);
}
EXPORT_SYMBOL(sort_r);
_
Patches currently in -mm which might be from visitorckw@xxxxxxxxx are
perf-core-fix-several-typos.patch
bcache-fix-typo.patch
bcachefs-fix-typo.patch
lib-min_heap-add-type-safe-interface.patch
lib-min_heap-add-min_heap_init.patch
lib-min_heap-add-min_heap_peek.patch
lib-min_heap-add-min_heap_full.patch
lib-min_heap-add-args-for-min_heap_callbacks.patch
lib-min_heap-add-min_heap_sift_up.patch
lib-min_heap-add-min_heap_del.patch
lib-min_heap-update-min_heap_push-and-min_heap_pop-to-return-bool-values.patch
lib-min_heap-rename-min_heapify-to-min_heap_sift_down.patch
lib-min_heap-update-min_heap_push-to-use-min_heap_sift_up.patch
lib-test_min_heap-add-test-for-heap_del.patch
bcache-remove-heap-related-macros-and-switch-to-generic-min_heap.patch
bcachefs-remove-heap-related-macros-and-switch-to-generic-min_heap.patch
lib-sort-remove-unused-pr_fmt-macro.patch
lib-sort-fix-outdated-comment-regarding-glibc-qsort.patch
lib-sort-optimize-heapsort-for-handling-final-2-or-3-elements.patch
lib-test_sort-add-a-testcase-to-ensure-code-coverage.patch
