Re: [PATCH] libstdc++: Micro-optimize __from_chars_pow2_base

[Jonathan Wakely <jwakely.gcc@gmail.com>]

On Mon, 18 Apr 2022, 15:39 Patrick Palka via Libstdc++, <
libstdc++@gcc.gnu.org> wrote:

> At the first iteration of __from_chars_pow2_base's main loop, we need
> to remember the value of the leading significant digit for sake of the
> overflow check at the end of the function (for bases other than 2).
>
> This patch manually unrolls this first iteration so as to not encumber
> the entire loop with logic that only the first iteration needs.  This
> seems to significantly improve performance:
>

Great, I was going to suggest looking into that change.



> Base  Before  After (seconds, lower is better)
>    2    9.36   9.37
>    8    3.66   2.93
>   16    2.93   1.91
>   32    2.39   2.24
>
> Tested on x86_64-pc-linux-gnu, does this look OK for trunk?
>

OK, thanks!



> libstdc++-v3/ChangeLog:
>
>         * include/std/charconv (__from_chars_pow2_base): Manually
>         unroll the first iteration of the main loop and simplify
>         accordingly.
> ---
>  libstdc++-v3/include/std/charconv | 30 +++++++++++++++++++++---------
>  1 file changed, 21 insertions(+), 9 deletions(-)
>
> diff --git a/libstdc++-v3/include/std/charconv
> b/libstdc++-v3/include/std/charconv
> index dda4ec87779..cd7f52e2195 100644
> --- a/libstdc++-v3/include/std/charconv
> +++ b/libstdc++-v3/include/std/charconv
> @@ -469,25 +469,37 @@ namespace __detail
>        while (__i < __len && __first[__i] == '0')
>         ++__i;
>        const ptrdiff_t __leading_zeroes = __i;
> +      if (__i >= __len) [[__unlikely__]]
> +       {
> +         __first += __i;
> +         return true;
> +       }
> +
> +      // Remember the leading significant digit value if necessary.
> +      unsigned char __leading_c;
> +      if (__base != 2)
> +       {
> +         __leading_c = __from_chars_alnum_to_val<_DecOnly>(__first[__i]);
> +         // __glibcxx_assert(__leading_c != 0);
> +         if (__leading_c >= __base) [[__unlikely__]]
> +           {
> +             __first += __i;
> +             return true;
> +           }
> +         __val = __leading_c;
> +         ++__i;
> +       }
>
> -      unsigned char __leading_c = 0;
>        for (; __i < __len; ++__i)
>         {
>           const unsigned char __c =
> __from_chars_alnum_to_val<_DecOnly>(__first[__i]);
>           if (__c >= __base)
>             break;
>           __val = (__val << __log2_base) | __c;
> -
> -         if (__i == __leading_zeroes)
> -           {
> -             // At the first iteration, remember the leading significant
> digit.
> -             // __glibcxx_assert(__leading_c == 0 && __c != 0);
> -             __leading_c = __c;
> -           }
>         }
>        __first += __i;
>        auto __significant_bits = (__i - __leading_zeroes) * __log2_base;
> -      if (__base != 2 && __leading_c != 0)
> +      if (__base != 2)
>         // Compensate for a leading significant digit that didn't use all
>         // of its available bits.
>         __significant_bits -= __log2_base - __bit_width(__leading_c);
> --
> 2.36.0.rc2.10.g1ac7422e39
>
>