Re: [PATCH] Halving the number of recursive calls

[Carlos O'Donell <carlos@redhat.com>]

On 5/12/24 10:40 PM, Viktor Reznov wrote:
> From b4813bd1d7f48014e24f8a8749da49f7749c4f37 Mon Sep 17 00:00:00 2001
> From: Reznov <yann.collet.is.not.a.perfectionist@gmail.com>
> Date: Mon, 13 May 2024 05:27:05 +0300
> Subject: [PATCH] Halving the number of recursive calls

Thank you for contributing to glibc! :-)

Please note that this patch fails to pass pre-commit CI:
https://patchwork.sourceware.org/project/glibc/patch/CAKs8_O+FRyB3kpzxQZPVrQGwVzRzwViK17kVpWzQAEzQtHi9VQ@mail.gmail.com/
- Patch fails to apply due to line wrapping.

Please have a look at the contribution checklist here:
https://sourceware.org/glibc/wiki/Contribution%20checklist

In particular:

- You can use `git send-email` to send the message to the list to avoid wrapping
  issues with mail clients.

- You must choose one of the processes for copyright for your patch, either
  disclaim, assign, or developer certificate of origin.


Lastly, How did you test the performance gains?

Does this change show up visibly in a microbenchmark or workload?


> ---
>  stdlib/qsort.c | 9 ++++-----
>  1 file changed, 4 insertions(+), 5 deletions(-)
> 
> diff --git a/stdlib/qsort.c b/stdlib/qsort.c
> index be47aebbe0..30ba492869 100644
> --- a/stdlib/qsort.c
> +++ b/stdlib/qsort.c
> @@ -198,16 +198,15 @@ msort_with_tmp (const struct msort_param *p,
> void *b, size_t n)
>    char *b1, *b2;
>    size_t n1, n2;
> 
> -  if (n <= 1)
> -    return;
> -
>    n1 = n / 2;
>    n2 = n - n1;
>    b1 = b;
>    b2 = (char *) b + (n1 * p->s);
> 
> -  msort_with_tmp (p, b1, n1);
> -  msort_with_tmp (p, b2, n2);
> +  if (n1 > 1)
> +    msort_with_tmp (p, b1, n1);
> +  if (n2 > 1)
> +    msort_with_tmp (p, b2, n2);
> 
>    char *tmp = p->t;
>    const size_t s = p->s;

-- 
Cheers,
Carlos.