[PATCH] libstdc++: Micro-optimize __from_chars_pow2_base

[PATCH] libstdc++: Micro-optimize __from_chars_pow2_base

[Patrick Palka]

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:

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?

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

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

[Jonathan Wakely]

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