[PATCH] Halving the number of recursive calls

[PATCH] Halving the number of recursive calls

[Viktor Reznov]

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

---
 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;
-- 
2.34.1

Re: [PATCH] Halving the number of recursive calls

[Carlos O'Donell]

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.

Re: [PATCH] Halving the number of recursive calls

[Viktor Reznov]

On Mon, May 13, 2024 at 5:14 PM Carlos O'Donell <carlos@redhat.com> wrote:
> Lastly, How did you test the performance gains?
> Does this change show up visibly in a microbenchmark or workload?

Even if a compiler is capable of doing "partial inlining", it is
better to do this inlining manually.

Re: [PATCH] Halving the number of recursive calls

[Xi Ruoyao]

On Tue, 2024-05-14 at 08:27 +0300, Viktor Reznov wrote:
> On Mon, May 13, 2024 at 5:14 PM Carlos O'Donell <carlos@redhat.com>
> wrote:
> > Lastly, How did you test the performance gains?
> > Does this change show up visibly in a microbenchmark or workload?
> 
> Even if a compiler is capable of doing "partial inlining", it is
> better to do this inlining manually.

No, in Glibc if we are pretty sure the compiler will optimize it, we
don't optimize it manually.

It's not really "better" unless a not-so-old GCC or Clang fails to
optimize it, *and* the optimization really makes it faster for
microbenchmark or workload.

-- 
Xi Ruoyao <xry111@xry111.site>
School of Aerospace Science and Technology, Xidian University

Re: [PATCH] Halving the number of recursive calls

[Adhemerval Zanella Netto]

On 14/05/24 08:08, Xi Ruoyao wrote:
> On Tue, 2024-05-14 at 08:27 +0300, Viktor Reznov wrote:
>> On Mon, May 13, 2024 at 5:14 PM Carlos O'Donell <carlos@redhat.com>
>> wrote:
>>> Lastly, How did you test the performance gains?
>>> Does this change show up visibly in a microbenchmark or workload?
>>
>> Even if a compiler is capable of doing "partial inlining", it is
>> better to do this inlining manually.
> 
> No, in Glibc if we are pretty sure the compiler will optimize it, we
> don't optimize it manually.
> 
> It's not really "better" unless a not-so-old GCC or Clang fails to
> optimize it, *and* the optimization really makes it faster for
> microbenchmark or workload.
> 

Kuan-Wei sent a similar optimization some time ago [1], which I 
complete forgot to install.  My plan is to re-run some tests and
apply, so how this patch compare to Kuan's change?

[1] https://sourceware.org/pipermail/libc-alpha/2024-March/155648.html