Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.35 as permitted sender) client-ip=23.128.96.35;
Date:   Sun, 3 Dec 2023 05:12:45 +0800
From:   Kuan-Wei Chiu <visitorckw@gmail.com>
To:     akpm@linux-foundation.org
Cc:     linux-kernel@vger.kernel.org
Subject: Re: [PATCH] lib/sort: Optimize number of calls to comparison function
Message-ID: <20231202211245.GA2632691@sivslab-System-Product-Name>
References: <20231202163717.687578-1-visitorckw@gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20231202163717.687578-1-visitorckw@gmail.com>
Precedence: bulk

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@gmail.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