linux-kernel - [PATCH 3/4] lib/sort: Optimize heapsort for handling final 2 or 3 elements

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: Tue, 28 May 2024 04:30:10 +0800
From: Kuan-Wei Chiu <visitorckw@...il.com>
To: akpm@...ux-foundation.org
Cc: jserv@...s.ncku.edu.tw,
	linux-kernel@...r.kernel.org,
	Kuan-Wei Chiu <visitorckw@...il.com>
Subject: [PATCH 3/4] lib/sort: Optimize heapsort for handling final 2 or 3 elements

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.

Signed-off-by: Kuan-Wei Chiu <visitorckw@...il.com>
---
 lib/sort.c | 10 ++++++----
 1 file changed, 6 insertions(+), 4 deletions(-)

diff --git a/lib/sort.c b/lib/sort.c
index b918ae15302d..048b7a6ef967 100644
--- a/lib/sort.c
+++ b/lib/sort.c
@@ -250,10 +250,7 @@ void sort_r(void *base, size_t num, size_t 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_t 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);

-- 
2.34.1