[musl] [PATCH] Decreasing the number of divisions

[musl] [PATCH] Decreasing the number of divisions

[Viktor Reznov]

diff --git a/src/stdio/vfprintf.c b/src/stdio/vfprintf.c
index 497c5e19..0f9a1e6a 100644
--- a/src/stdio/vfprintf.c
+++ b/src/stdio/vfprintf.c
@@ -165,8 +165,10 @@ static char *fmt_o(uintmax_t x, char *s)
 static char *fmt_u(uintmax_t x, char *s)
 {
        unsigned long y;
+       if (x == 0) return s;
        for (   ; x>ULONG_MAX; x/=10) *--s = '0' + x%10;
-       for (y=x;           y; y/=10) *--s = '0' + y%10;
+       for (y=x;       y>=10; y/=10) *--s = '0' + y%10;
+       *--s = '0' + y;
        return s;
 }

Re: [musl] [PATCH] Decreasing the number of divisions

[Markus Wichmann]

Am Tue, Apr 16, 2024 at 04:29:05PM +0300 schrieb Viktor Reznov:
> diff --git a/src/stdio/vfprintf.c b/src/stdio/vfprintf.c
> index 497c5e19..0f9a1e6a 100644
> --- a/src/stdio/vfprintf.c
> +++ b/src/stdio/vfprintf.c
> @@ -165,8 +165,10 @@ static char *fmt_o(uintmax_t x, char *s)
>  static char *fmt_u(uintmax_t x, char *s)
>  {
>         unsigned long y;
> +       if (x == 0) return s;
>         for (   ; x>ULONG_MAX; x/=10) *--s = '0' + x%10;
> -       for (y=x;           y; y/=10) *--s = '0' + y%10;
> +       for (y=x;       y>=10; y/=10) *--s = '0' + y%10;
> +       *--s = '0' + y;
>         return s;
>  }

I played around with this change on godbolt: https://godbolt.org/z/9PoGK9zae

Seems to me like the version with OPTIMIZE=1 is longer and more
complicated.

OK, let's take a step back: What is the point of this patch? It makes
the code longer and less readable. It does not fix a logic bug. The only
reason I can see is that it makes the code "faster". In that case, I
would like to see a benchmark.

On x86-64, the loop condition on the first loop is always false, so the
unchanged function becomes a single loop. The changed function becomes a
selection statement, a loop, and an assignment. Don't see how that could
possibly be faster. But am willing to be convinced otherwise.

Ciao,
Markus

Re: [musl] [PATCH] Decreasing the number of divisions

[Rich Felker]

On Tue, Apr 16, 2024 at 04:29:05PM +0300, Viktor Reznov wrote:
> diff --git a/src/stdio/vfprintf.c b/src/stdio/vfprintf.c
> index 497c5e19..0f9a1e6a 100644
> --- a/src/stdio/vfprintf.c
> +++ b/src/stdio/vfprintf.c
> @@ -165,8 +165,10 @@ static char *fmt_o(uintmax_t x, char *s)
>  static char *fmt_u(uintmax_t x, char *s)
>  {
>         unsigned long y;
> +       if (x == 0) return s;
>         for (   ; x>ULONG_MAX; x/=10) *--s = '0' + x%10;
> -       for (y=x;           y; y/=10) *--s = '0' + y%10;
> +       for (y=x;       y>=10; y/=10) *--s = '0' + y%10;
> +       *--s = '0' + y;
>         return s;
>  }

Seems like a good change. Is there a reason you put the if at the top
rather than making the last line the following?

	if (y) *--s = '0' + y;

That would keep the overall flow the same as before and avoid a burden
to reason about if/why it's the same.

Rich

Re: [musl] [PATCH] Decreasing the number of divisions

[Rich Felker]

On Tue, Apr 16, 2024 at 07:34:32PM +0300, Viktor Reznov wrote:
> > Is there a reason you put the if at the top
> > rather than making the last line the following?
> 
> No.

Ok. Can I make that simplifying change and still attribute you as
commit author?

> On Tue, Apr 16, 2024 at 5:38 PM Rich Felker <dalias@libc.org> wrote:
> >
> > On Tue, Apr 16, 2024 at 04:29:05PM +0300, Viktor Reznov wrote:
> > > diff --git a/src/stdio/vfprintf.c b/src/stdio/vfprintf.c
> > > index 497c5e19..0f9a1e6a 100644
> > > --- a/src/stdio/vfprintf.c
> > > +++ b/src/stdio/vfprintf.c
> > > @@ -165,8 +165,10 @@ static char *fmt_o(uintmax_t x, char *s)
> > >  static char *fmt_u(uintmax_t x, char *s)
> > >  {
> > >         unsigned long y;
> > > +       if (x == 0) return s;
> > >         for (   ; x>ULONG_MAX; x/=10) *--s = '0' + x%10;
> > > -       for (y=x;           y; y/=10) *--s = '0' + y%10;
> > > +       for (y=x;       y>=10; y/=10) *--s = '0' + y%10;
> > > +       *--s = '0' + y;
> > >         return s;
> > >  }
> >
> > Seems like a good change. Is there a reason you put the if at the top
> > rather than making the last line the following?
> >
> >         if (y) *--s = '0' + y;
> >
> > That would keep the overall flow the same as before and avoid a burden
> > to reason about if/why it's the same.
> >
> > Rich

[musl] Re: [PATCH] Decreasing the number of divisions

[Rich Felker]

Can you clarify what's up with your email address? It appears to be a
sentence about another person, and I have no idea what the backstory
on that is, but I'm hesitant to accept it into the immutable commit
history in the author field.

On Tue, Apr 16, 2024 at 08:05:38PM +0300, Viktor Reznov wrote:
> Yes.
> 
> On Tuesday, April 16, 2024, Rich Felker <dalias@libc.org> wrote:
> 
> > On Tue, Apr 16, 2024 at 07:34:32PM +0300, Viktor Reznov wrote:
> > > > Is there a reason you put the if at the top
> > > > rather than making the last line the following?
> > >
> > > No.
> >
> > Ok. Can I make that simplifying change and still attribute you as
> > commit author?
> >
> > > On Tue, Apr 16, 2024 at 5:38 PM Rich Felker <dalias@libc.org> wrote:
> > > >
> > > > On Tue, Apr 16, 2024 at 04:29:05PM +0300, Viktor Reznov wrote:
> > > > > diff --git a/src/stdio/vfprintf.c b/src/stdio/vfprintf.c
> > > > > index 497c5e19..0f9a1e6a 100644
> > > > > --- a/src/stdio/vfprintf.c
> > > > > +++ b/src/stdio/vfprintf.c
> > > > > @@ -165,8 +165,10 @@ static char *fmt_o(uintmax_t x, char *s)
> > > > >  static char *fmt_u(uintmax_t x, char *s)
> > > > >  {
> > > > >         unsigned long y;
> > > > > +       if (x == 0) return s;
> > > > >         for (   ; x>ULONG_MAX; x/=10) *--s = '0' + x%10;
> > > > > -       for (y=x;           y; y/=10) *--s = '0' + y%10;
> > > > > +       for (y=x;       y>=10; y/=10) *--s = '0' + y%10;
> > > > > +       *--s = '0' + y;
> > > > >         return s;
> > > > >  }
> > > >
> > > > Seems like a good change. Is there a reason you put the if at the top
> > > > rather than making the last line the following?
> > > >
> > > >         if (y) *--s = '0' + y;
> > > >
> > > > That would keep the overall flow the same as before and avoid a burden
> > > > to reason about if/why it's the same.
> > > >
> > > > Rich
> >

Re: [musl] [PATCH] Decreasing the number of divisions

[NRK]

> I played around with this change on godbolt: https://godbolt.org/z/9PoGK9zae

You're looking at clang -O3, if you use gcc -Os (usual for musl
users/distros) you'll notice that gcc actually ends up emitting a div
instruction, which are known to be slow.

But I don't think trying to optimize around gcc's bad codegen is the
right move. It's better to just not use -Os with gcc. Which musl already
does since commit b90841e25832.

- NRK

Re: [musl] [PATCH] Decreasing the number of divisions

[Markus Wichmann]

Am Wed, Apr 17, 2024 at 01:25:18AM +0000 schrieb NRK:
> > I played around with this change on godbolt: https://godbolt.org/z/9PoGK9zae
>
> You're looking at clang -O3, if you use gcc -Os (usual for musl
> users/distros) you'll notice that gcc actually ends up emitting a div
> instruction, which are known to be slow.
>
> But I don't think trying to optimize around gcc's bad codegen is the
> right move. It's better to just not use -Os with gcc. Which musl already
> does since commit b90841e25832.
>
> - NRK

Well, yeah, if you use -Os and expect fast code, you are doing it wrong.
-Os explicitly asks for small code rather than fast. It is appropriate
for code that ends up having to fit in a ROM or a bootsector or
something, but otherwise I can't really see the point.

I remember once reading the insane claim that -Os code ends up being
faster than -O3 because the code fits in cache, but much as the OP in
this thread, there was no benchmark to actually show this. I call it
insane because -O3 is telling GCC explicitly to output the fastest code
possible, and in my experience it generally does.

Ciao,
Markus