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

[Kuan-Wei Chiu]

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@xxxxxxxxx>
> ---
>  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