diff --git a/libcxx/benchmarks/to_chars-method-1.bench.cpp b/libcxx/benchmarks/to_chars-method-1.bench.cpp new file mode 100644 --- /dev/null +++ b/libcxx/benchmarks/to_chars-method-1.bench.cpp @@ -0,0 +1,10 @@ +//===----------------------------------------------------------------------===// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#define __METHOD 1 + +#include "to_chars.bench.cpp" diff --git a/libcxx/benchmarks/to_chars-method-2.bench.cpp b/libcxx/benchmarks/to_chars-method-2.bench.cpp new file mode 100644 --- /dev/null +++ b/libcxx/benchmarks/to_chars-method-2.bench.cpp @@ -0,0 +1,10 @@ +//===----------------------------------------------------------------------===// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#define __METHOD 2 + +#include "to_chars.bench.cpp" diff --git a/libcxx/benchmarks/to_chars-method-3.bench.cpp b/libcxx/benchmarks/to_chars-method-3.bench.cpp new file mode 100644 --- /dev/null +++ b/libcxx/benchmarks/to_chars-method-3.bench.cpp @@ -0,0 +1,10 @@ +//===----------------------------------------------------------------------===// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#define __METHOD 3 + +#include "to_chars.bench.cpp" diff --git a/libcxx/benchmarks/to_chars-method-4.bench.cpp b/libcxx/benchmarks/to_chars-method-4.bench.cpp new file mode 100644 --- /dev/null +++ b/libcxx/benchmarks/to_chars-method-4.bench.cpp @@ -0,0 +1,10 @@ +//===----------------------------------------------------------------------===// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#define __METHOD 4 + +#include "to_chars.bench.cpp" diff --git a/libcxx/benchmarks/to_chars-method-5.bench.cpp b/libcxx/benchmarks/to_chars-method-5.bench.cpp new file mode 100644 --- /dev/null +++ b/libcxx/benchmarks/to_chars-method-5.bench.cpp @@ -0,0 +1,10 @@ +//===----------------------------------------------------------------------===// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#define __METHOD 5 + +#include "to_chars.bench.cpp" diff --git a/libcxx/include/charconv b/libcxx/include/charconv --- a/libcxx/include/charconv +++ b/libcxx/include/charconv @@ -75,6 +75,7 @@ #include <__config> #include <__availability> +#include <__bits> #include <__errc> #include <__utility/to_underlying.h> #include // for log2f @@ -394,6 +395,288 @@ return __to_chars_integral(__first, __last, __x, __base, false_type()); } +// TODO Only one should remain {{{ +// Methods +// 1 - current [lit passes] +// 2 - __base -> _Base [lit passes] +// 3 - per base optimizations for width [lit passes] +// 4 - per base optimizations for width and output test > [lit passes] +// 5 - per base optimizations for width and output test >= [lit passes] + +#ifndef __METHOD +#define __METHOD 4 +#endif + +#if __METHOD == 2 +template +_LIBCPP_AVAILABILITY_TO_CHARS _LIBCPP_INLINE_VISIBILITY int +__to_chars_integral_width(_Tp __value) { + unsigned __base_2 = _Base * _Base; + unsigned __base_3 = __base_2 * _Base; + unsigned __base_4 = __base_2 * __base_2; + + int __r = 0; + while (true) { + if (__value < _Base) + return __r + 1; + if (__value < __base_2) + return __r + 2; + if (__value < __base_3) + return __r + 3; + if (__value < __base_4) + return __r + 4; + + __value /= __base_4; + __r += 4; + } + + _LIBCPP_UNREACHABLE(); +} + +template +_LIBCPP_AVAILABILITY_TO_CHARS _LIBCPP_INLINE_VISIBILITY to_chars_result +__to_chars_integral(char* __first, char* __last, _Tp __value) { + ptrdiff_t __cap = __last - __first; + int __n = __to_chars_integral_width<_Base>(__value); + if (__n > __cap) + return {__last, errc::value_too_large}; + + __last = __first + __n; + char* __p = __last; + do { + unsigned __c = __value % _Base; + __value /= _Base; + *--__p = "0123456789abcdefghijklmnopqrstuvwxyz"[__c]; + } while (__value != 0); + return {__last, errc(0)}; +} +#elif __METHOD >= 3 + +namespace __detail { + +template +struct _LIBCPP_HIDDEN __integral; + +template <> +struct _LIBCPP_HIDDEN __integral<2> { + enum : unsigned { _Base = 2 }; + + template + _LIBCPP_INLINE_VISIBILITY static constexpr int __width(_Tp __value) noexcept { + // If value == 0 still need one digit. If the value != this has no + // effect since the code scans for the most significat bit set. (Note + // that __libcpp_clz doesn't work for 0.) + return numeric_limits<_Tp>::digits - __libcpp_clz(__value | 1); + } + + template + _LIBCPP_INLINE_VISIBILITY static to_chars_result __to_chars(char* __first, char* __last, _Tp __value) { + ptrdiff_t __cap = __last - __first; + int __n = __width(__value); + if (__n > __cap) + return {__last, errc::value_too_large}; + + __last = __first + __n; + char* __p = __last; +#if __METHOD >= 4 + const unsigned __divisor = 16; +#if __METHOD == 5 + while (__value >= __divisor) +#else + while (__value > __divisor) +#endif + { + unsigned __c = __value % __divisor; + __value /= __divisor; + __p -= 4; + // 64 characters + const char* __lut = "0000" + "0001" + "0010" + "0011" + "0100" + "0101" + "0110" + "0111" + "1000" + "1001" + "1010" + "1011" + "1100" + "1101" + "1110" + "1111"; + _VSTD::memcpy(__p, &__lut[4 * __c], 4); + } +#if __METHOD == 5 + // if value == 0 at the start need to iterate once + if (__first != __last) +#endif +#endif + do { + unsigned __c = __value % _Base; + __value /= _Base; + *--__p = "01"[__c]; + } while (__value != 0); + return {__last, errc(0)}; + } +}; + +template <> +struct _LIBCPP_HIDDEN __integral<8> { + enum : unsigned { _Base = 8 }; + + template + _LIBCPP_INLINE_VISIBILITY static constexpr int __width(_Tp __value) noexcept { + // If value == 0 still need one digit. If the value != this has no + // effect since the code scans for the most significat bit set. (Note + // that __libcpp_clz doesn't work for 0.) + return ((numeric_limits<_Tp>::digits - __libcpp_clz(__value | 1)) + 2) / 3; + } + + template + _LIBCPP_INLINE_VISIBILITY static to_chars_result __to_chars(char* __first, char* __last, _Tp __value) { + ptrdiff_t __cap = __last - __first; + int __n = __width(__value); + if (__n > __cap) + return {__last, errc::value_too_large}; + + __last = __first + __n; + char* __p = __last; +#if __METHOD >= 4 + unsigned __divisor = 64; +#if __METHOD == 5 + while (__value >= __divisor) +#else + while (__value > __divisor) +#endif + { + unsigned __c = __value % __divisor; + __value /= __divisor; + __p -= 2; + // 128 characters + const char* __lut = "0001020304050607" + "1011121314151617" + "2021222324252627" + "3031323334353637" + "4041424344454647" + "5051525354555657" + "6061626364656667" + "7071727374757677"; + _VSTD::memcpy(__p, &__lut[2 * __c], 2); + } +#if __METHOD == 5 + // if value == 0 at the start need to iterate once + if (__first != __last) +#endif +#endif + do { + unsigned __c = __value % _Base; + __value /= _Base; + *--__p = "01234567"[__c]; + } while (__value != 0); + return {__last, errc(0)}; + } +}; + +template <> +struct _LIBCPP_HIDDEN __integral<16> { + enum : unsigned { _Base = 16 }; + + template + _LIBCPP_INLINE_VISIBILITY static constexpr int __width(_Tp __value) noexcept { + // If value == 0 still need one digit. If the value != this has no + // effect since the code scans for the most significat bit set. (Note + // that __libcpp_clz doesn't work for 0.) + return (numeric_limits<_Tp>::digits - __libcpp_clz(__value | 1) + 3) / 4; + } + + template + _LIBCPP_INLINE_VISIBILITY static to_chars_result __to_chars(char* __first, char* __last, _Tp __value) { + ptrdiff_t __cap = __last - __first; + int __n = __width(__value); + if (__n > __cap) + return {__last, errc::value_too_large}; + + __last = __first + __n; + char* __p = __last; +#if __METHOD >= 4 + unsigned __divisor = 256; +#if __METHOD == 5 + while (__value >= __divisor) +#else + while (__value > __divisor) +#endif + { + unsigned __c = __value % __divisor; + __value /= __divisor; + __p -= 2; + // 512 characters + const char* __lut = "000102030405060708090a0b0c0d0e0f" + "101112131415161718191a1b1c1d1e1f" + "202122232425262728292a2b2c2d2e2f" + "303132333435363738393a3b3c3d3e3f" + "404142434445464748494a4b4c4d4e4f" + "505152535455565758595a5b5c5d5e5f" + "606162636465666768696a6b6c6d6e6f" + "707172737475767778797a7b7c7d7e7f" + "808182838485868788898a8b8c8d8e8f" + "909192939495969798999a9b9c9d9e9f" + "a0a1a2a3a4a5a6a7a8a9aaabacadaeaf" + "b0b1b2b3b4b5b6b7b8b9babbbcbdbebf" + "c0c1c2c3c4c5c6c7c8c9cacbcccdcecf" + "d0d1d2d3d4d5d6d7d8d9dadbdcdddedf" + "e0e1e2e3e4e5e6e7e8e9eaebecedeeef" + "f0f1f2f3f4f5f6f7f8f9fafbfcfdfeff"; + _VSTD::memcpy(__p, &__lut[2 * __c], 2); + } + if (__first != __last) +#if __METHOD == 5 + // if value == 0 at the start need to iterate once + if (__first != __last) +#endif +#endif + do { + unsigned __c = __value % _Base; + __value /= _Base; + *--__p = "0123456789abcdef"[__c]; + } while (__value != 0); + return {__last, errc(0)}; + } +}; + +} // namespace __detail + +template = sizeof(unsigned)), int>::type = 0> +_LIBCPP_AVAILABILITY_TO_CHARS _LIBCPP_INLINE_VISIBILITY int +__to_chars_integral_width(_Tp __value) { + return __detail::__integral<_Base>::__width(__value); +} + +template ::type = 0> +_LIBCPP_AVAILABILITY_TO_CHARS _LIBCPP_INLINE_VISIBILITY int +__to_chars_integral_width(_Tp __value) { + return __to_chars_integral_width<_Base>(static_cast(__value)); +} + +template = sizeof(unsigned)), int>::type = 0> +_LIBCPP_AVAILABILITY_TO_CHARS _LIBCPP_INLINE_VISIBILITY to_chars_result +__to_chars_integral(char* __first, char* __last, _Tp __value) { + return __detail::__integral<_Base>::__to_chars(__first, __last, __value); +} + +template ::type = 0> +_LIBCPP_AVAILABILITY_TO_CHARS _LIBCPP_INLINE_VISIBILITY to_chars_result +__to_chars_integral(char* __first, char* __last, _Tp __value) { + return __to_chars_integral<_Base>(__first, __last, static_cast(__value)); +} +#endif +// }}} + template _LIBCPP_AVAILABILITY_TO_CHARS _LIBCPP_INLINE_VISIBILITY int __to_chars_integral_width(_Tp __value, unsigned __base) { _LIBCPP_ASSERT(__value >= 0, "The function requires a non-negative value."); @@ -426,9 +709,21 @@ __to_chars_integral(char* __first, char* __last, _Tp __value, int __base, false_type) { +#if __METHOD == 1 if (__base == 10) return __to_chars_itoa(__first, __last, __value, false_type()); - +#else + if (__base == 10) [[likely]] + return __to_chars_itoa(__first, __last, __value, false_type()); + switch (__base) { + case 2: + return __to_chars_integral<2>(__first, __last, __value); + case 8: + return __to_chars_integral<8>(__first, __last, __value); + case 16: + return __to_chars_integral<16>(__first, __last, __value); + } +#endif ptrdiff_t __cap = __last - __first; int __n = __to_chars_integral_width(__value, __base); if (__n > __cap)