linux-kernel - Re: [PATCH] lib/sort: Optimize number of calls to comparison function

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] [day] [month] [year] [list]

Message-ID: <20231202211245.GA2632691@sivslab-System-Product-Name>
Date:   Sun, 3 Dec 2023 05:12:45 +0800
From:   Kuan-Wei Chiu <visitorckw@...il.com>
To:     akpm@...ux-foundation.org
Cc:     linux-kernel@...r.kernel.org
Subject: Re: [PATCH] lib/sort: Optimize number of calls to comparison function

On Sun, Dec 03, 2023 at 12:37:17AM +0800, Kuan-Wei Chiu wrote:
> The current implementation continues the loop when the comparison
> function returns a non-negative value, which includes the case when it
> returns 0. However, in scenarios where the comparison function returns
> 0, further comparisons are unnecessary. By making this adjustment, we
> can potentially reduce the number of comparisons by approximately 50%
> in extreme cases where all elements in the array are equal, and the
> array size is sufficiently large.
> 
> 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..1e98a62bb2f3 100644
> --- a/lib/sort.c
> +++ b/lib/sort.c
> @@ -267,7 +267,7 @@ void sort_r(void *base, size_t num, size_t size,
>  			b = c;
>  
>  		/* Now backtrack from "b" to the correct location for "a" */
> -		while (b != a && do_cmp(base + a, base + b, cmp_func, priv) >= 0)
> +		while (b != a && do_cmp(base + a, base + b, cmp_func, priv) > 0)
>  			b = parent(b, lsbit, size);
>  		c = b;			/* Where "a" belongs */
>  		while (b != a) {	/* Shift it into place */
> -- 
> 2.25.1
>

While the patch decreases the number of comparisons, it simultaneously
leads to an increase in the number of swaps. As a result, the overall
performance improvement may not be guaranteed.

Therefore, I believe it would be more prudent to drop this patch.
I apologize for any disruption caused on the mailing list.

Best regards,
Kuan-Wei Chiu