[PATCH] Optimize to_chars

[Antony Polukhin]

пт, 30 авг. 2019 г. в 19:01, Jonathan Wakely <jwakely@redhat.com>:
<...>
> Have you tried comparing the improved code to libc++'s implementation?
> I believe they use precomputed arrays of digits, but they use larger
> arrays that allow 4 bytes to be written at once, which is considerably
> faster (and those precomputed arrays libe in libc++.so not in the
> header). Would we be better off keeping the precomputed arrays and
> expanding them to do 4-byte writes?

This would not do good for bases 2, 8 and 16. For power of two bases
there is no costly `mod` or `div` instructions, only bit operations.
By increasing the digits table size the cache misses become more
likely.

For base 10... A few decades ago it was definitely a good idea to have
a big array of digits. Nowadays compilers know how to replace `__val /
10` and `__val % 10` with much cheaper multiplications and bit magic.
This is not as cheap as bit operations for power of two bases, but
some cache misses could nullify the advantage.

I need to experiment with base 10. There are ways to compress the
digits table, but it requires benchmarking. Because of that this patch
does not touch the __detail::__to_chars_10.

>
> Since we don't have a patch to do that, I think I'll commit yours. We
> can always go back to precomputed arrays later if somebody does that
> work.
>
> My only comments are on the changelog:
>
> >Changelog:
> >    * include/std/charconv (__detail::__to_chars_8,
> >    __detail::__to_chars_16): Replace array of precomputed digits
>
> When the list of changed functions is split across lines it should be
> like this:
>
>     * include/std/charconv (__detail::__to_chars_8)
>     (__detail::__to_chars_16): Replace array of precomputed digits
>
> i.e close the parentheses before the line break, and reopen on the
> next line.
>
> >    with arithmetic operations to avoid CPU cache misses. Remove
> >    zero termination from array of digits to allow symbol merge with
> >    generic implementation of __detail::__to_chars. Replace final
> >    offsets with constants. Use __detail::__to_chars_len_2 instead
> >    of a generic __detail::__to_chars_len.
> >    * include/std/charconv (__detail::__to_chars): Remove
>
> Don't repeat the asterisk and filename for later changes in the same
> file, i.e.
>
>     (__detail::__to_chars): Remove zero termination from array of digits.
>     (__detail::__to_chars_2): Leading digit is always '1'.
>
> There's no changelog entry for the changes to __to_chars_len_8 and
> __to_chars_len_16.
>
> Also, please don't include the ChangeLog diff in the patch, because it
> just makes it hard to apply the patch (the ChangeLog part will almost
> always fail to apply because somebody else will have modified the
> ChangeLog file since you created the patch, and so that hunk won't
> apply. The ChangeLog text should be sent as a separate (plain text)
> attachment, or just in the email body (as you did above).

Thanks! I'll take it into account next time.

-- 
Best regards,
Antony Polukhin