libstdc++: Optimize integer std::from_chars
This applies the following optimizations to the integer std::from_chars
implementation:
1. Use a lookup table for converting an alphanumeric digit to its
base-36 value instead of using a range test (for 0-9) and switch
(for a-z and A-Z). The table is constructed using a C++14
constexpr function which doesn't assume a particular character
encoding or __CHAR_BIT__ value. This new conversion function
__from_chars_alnum_to_val is templated on whether we care
only about the decimal digits, in which case we can perform the
conversion with a single subtraction since the digit characters
are guaranteed to be contiguous (unlike the letters).
2. Generalize __from_chars_binary to handle all power-of-two bases.
This function (now named __from_chars_pow2_base) is also templated
on whether we care only about the decimal digits for the benefit of
faster digit conversion for base 2, 4 and 8.
3. In __from_chars_digit, use
static_cast<unsigned char>(__c - '0') < __base
instead of
'0' <= __c && __c <= ('0' + (__base - 1)).
as the digit recognition test (exhaustively verified that the two
tests are equivalent).
4. In __from_chars_alnum, use a nested loop to consume the rest of the
digits in the overflow case (mirroring __from_chars_digit) so that
the main loop doesn't have to maintain the overflow flag __valid.
At this point, __from_chars_digit is nearly identical to
__from_chars_alnum, so this patch merges the two functions by removing
the former and templatizing the latter according to whether we care only
about the decimal digits. Finally,
5. In __from_chars_alnum, maintain a lower bound on the number of
unused bits in the result and use it to omit the overflow check
when it's safe to do so.
In passing, this patch replaces the non-portable function ascii_to_hexit
used by __floating_from_chars_hex with the new conversion function.
Some runtime measurements for a simple 15-line benchmark that roundtrips
printing/parsing 200 million integers via std::to/from_chars (average of
5 runs):
Base Before After (seconds, lower is better)
2 9.37 9.37
3 15.79 12.13
8 4.15 3.67
10 4.90 3.86
11 6.84 5.03
16 4.14 2.93
32 3.85 2.39
36 5.22 3.26
libstdc++-v3/ChangeLog:
* include/std/charconv (__from_chars_alnum_to_val_table): Define.
(__from_chars_alnum_to_val): Define.
(__from_chars_binary): Rename to ...
(__from_chars_pow2_base): ... this. Generalize to handle any
power-of-two base using __from_chars_alnum_to_val.
(__from_chars_digit): Optimize digit recognition to a single
test instead of two tests. Use [[__unlikely___]] attribute.
(__from_chars_alpha_to_num): Remove.
(__from_chars_alnum): Use __from_chars_alnum_to_val. Use a
nested loop for the overflow case. Maintain a lower bound
on the number of available bits in the result and use it to
omit the overflow check.
(from_chars): Adjust appropriately.
* src/c++17/floating_from_chars.cc (ascii_to_hexit): Remove.
(__floating_from_chars_hex): Use __from_chars_alnum_to_val
to recognize a hex digit instead.