linux-kernel - [PATCH 1/2] lib/sort: Optimize heapsort for equal elements in sift-down path

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date: Sat, 13 Jan 2024 11:13:51 +0800
From: Kuan-Wei Chiu <visitorckw@...il.com>
To: akpm@...ux-foundation.org
Cc: lkml@....org,
	jserv@...s.ncku.edu.tw,
	linux-kernel@...r.kernel.org,
	Kuan-Wei Chiu <visitorckw@...il.com>
Subject: [PATCH 1/2] lib/sort: Optimize heapsort for equal elements in sift-down path

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.

Signed-off-by: Kuan-Wei Chiu <visitorckw@...il.com>
---
 lib/sort.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/lib/sort.c b/lib/sort.c
index b399bf10d675..fe4efd4a1410 100644
--- a/lib/sort.c
+++ b/lib/sort.c
@@ -262,7 +262,7 @@ void sort_r(void *base, size_t num, size_t 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;

-- 
2.25.1