Skip to contentSkip to conversation

lib-sort-optimize-heapsort-for-equal-elements-in-sift-down-path.patch removed from -mm tree

merged mm-hotfixes-stable Andrew Morton 1 participant 1 message Feb 22, 2024

lore
Share & tools
lore

Andrew Morton

author tree notice Applied
#0 lore raw

The quilt patch titled
Subject: lib/sort: optimize heapsort for equal elements in sift-down path
has been removed from the -mm tree. Its filename was
lib-sort-optimize-heapsort-for-equal-elements-in-sift-down-path.patch

This patch was dropped because it was merged into the mm-hotfixes-stable branch of git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm

------------------------------------------------------
From: Kuan-Wei Chiu <[email protected]>
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.

---

 lib/sort.c |    2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
lib/sort.c renamed from lib/sort.c~lib-sort-optimize-heapsort-for-equal-elements-in-sift-down-path +1 -1
@@ -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 [email protected] are