The patch titled
Subject: lib/sort: optimize heapsort for equal elements in sift-down path
has been added to the -mm mm-nonmm-unstable branch. Its filename is
lib-sort-optimize-heapsort-for-equal-elements-in-sift-down-path.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-equal-elements-in-sift-down-path.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 equal elements in sift-down path
Date: Sat, 13 Jan 2024 11:13:51 +0800
Patch series "lib/sort: Optimize the number of swaps and comparisons".
This patch series aims to optimize the heapsort algorithm, specifically
targeting a reduction in the number of swaps and comparisons required.
This patch (of 2):
Currently, when searching for the sift-down path and encountering equal
elements, the algorithm chooses the left child. However, considering that
the height of the right subtree may be one less than that of the left
subtree, selecting the right child in such cases can potentially reduce
the number of comparisons and swaps.
For instance, when sorting an array of 10,000 identical elements, the
current implementation requires 247,209 comparisons. With this patch, the
number of comparisons can be reduced to 227,241.
Link: https://lkml.kernel.org/r/20240113031352.2395118-1-visitorckw@xxxxxxxxx
Link: https://lkml.kernel.org/r/20240113031352.2395118-2-visitorckw@xxxxxxxxx
Signed-off-by: Kuan-Wei Chiu <visitorckw@xxxxxxxxx>
Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
---
lib/sort.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
--- a/lib/sort.c~lib-sort-optimize-heapsort-for-equal-elements-in-sift-down-path
+++ a/lib/sort.c
@@ -262,7 +262,7 @@ void sort_r(void *base, size_t num, size
* average, 3/4 worst-case.)
*/
for (b = a; c = 2*b + size, (d = c + size) < n;)
- b = do_cmp(base + c, base + d, cmp_func, priv) >= 0 ? c : d;
+ b = do_cmp(base + c, base + d, cmp_func, priv) > 0 ? c : d;
if (d == n) /* Special case last leaf with no sibling */
b = c;
_
Patches currently in -mm which might be from visitorckw@xxxxxxxxx are
lib-min_heap-optimize-number-of-calls-to-min_heapify.patch
lib-min_heap-optimize-number-of-comparisons-in-min_heapify.patch
lib-sort-optimize-heapsort-for-equal-elements-in-sift-down-path.patch
lib-sort-optimize-heapsort-with-double-pop-variation.patch
