From cd0b94e650a880b2ab04922e476aa28007277d5c Mon Sep 17 00:00:00 2001 From: Jonathan Wakely Date: Wed, 12 Jun 2019 15:52:02 +0100 Subject: [PATCH] Replace std::to_string for integers with optimized version The std::to_chars functions from C++17 can be used to implement std::to_string with much better performance than calling snprintf. Only the __detail::__to_chars_len and __detail::__to_chars_10 functions are needed for to_string, because it always outputs base 10 representations. The return type of __detail::__to_chars_10 should not be declared before C++17, so the function body is extracted into a new function that can be reused by to_string and __detail::__to_chars_10. The existing tests for to_chars rely on to_string to check for correct answers. Now that they use the same code that doesn't actually ensure correctness, so add new tests for std::to_string that compare against printf output. * include/Makefile.am: Add new header. * include/Makefile.in: Regenerate. * include/bits/basic_string.h (to_string(int), to_string(unsigned)) (to_string(long), to_string(unsigned long), to_string(long long)) (to_string(unsigned long long)): Rewrite to use __to_chars_10_impl. * include/bits/charconv.h: New header. (__detail::__to_chars_len): Move here from . (__detail::__to_chars_10_impl): New function extracted from __detail::__to_chars_10. * include/std/charconv (__cpp_lib_to_chars): Add, but comment out. (__to_chars_unsigned_type): New class template that reuses __make_unsigned_selector_base::__select to pick a type. (__unsigned_least_t): Redefine as __to_chars_unsigned_type::type. (__detail::__to_chars_len): Move to new header. (__detail::__to_chars_10): Add inline specifier. Move code doing the output to __detail::__to_chars_10_impl and call that. * include/std/version (__cpp_lib_to_chars): Add, but comment out. * testsuite/21_strings/basic_string/numeric_conversions/char/ to_string.cc: Fix reference in comment. Remove unused variable. * testsuite/21_strings/basic_string/numeric_conversions/char/ to_string_int.cc: New test. From-SVN: r272186 --- libstdc++-v3/ChangeLog | 24 +++ libstdc++-v3/include/Makefile.am | 1 + libstdc++-v3/include/Makefile.in | 1 + libstdc++-v3/include/bits/basic_string.h | 64 +++++-- libstdc++-v3/include/bits/charconv.h | 106 +++++++++++ libstdc++-v3/include/std/charconv | 75 +++----- libstdc++-v3/include/std/version | 1 + .../numeric_conversions/char/to_string.cc | 4 +- .../numeric_conversions/char/to_string_int.cc | 164 ++++++++++++++++++ 9 files changed, 365 insertions(+), 75 deletions(-) create mode 100644 libstdc++-v3/include/bits/charconv.h create mode 100644 libstdc++-v3/testsuite/21_strings/basic_string/numeric_conversions/char/to_string_int.cc diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index c758643fe8e..6d5e4b9ec16 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,27 @@ +2019-06-12 Jonathan Wakely + + * include/Makefile.am: Add new header. + * include/Makefile.in: Regenerate. + * include/bits/basic_string.h (to_string(int), to_string(unsigned)) + (to_string(long), to_string(unsigned long), to_string(long long)) + (to_string(unsigned long long)): Rewrite to use __to_chars_10_impl. + * include/bits/charconv.h: New header. + (__detail::__to_chars_len): Move here from . + (__detail::__to_chars_10_impl): New function extracted from + __detail::__to_chars_10. + * include/std/charconv (__cpp_lib_to_chars): Add, but comment out. + (__to_chars_unsigned_type): New class template that reuses + __make_unsigned_selector_base::__select to pick a type. + (__unsigned_least_t): Redefine as __to_chars_unsigned_type::type. + (__detail::__to_chars_len): Move to new header. + (__detail::__to_chars_10): Add inline specifier. Move code doing the + output to __detail::__to_chars_10_impl and call that. + * include/std/version (__cpp_lib_to_chars): Add, but comment out. + * testsuite/21_strings/basic_string/numeric_conversions/char/ + to_string.cc: Fix reference in comment. Remove unused variable. + * testsuite/21_strings/basic_string/numeric_conversions/char/ + to_string_int.cc: New test. + 2019-06-09 Edward Smith-Rowland <3dw4rd@verizon.net> Fix ConstexprIterator requirements tests - No constexpr algorithms! diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am index 92975b1ddc1..742f2c38ad5 100644 --- a/libstdc++-v3/include/Makefile.am +++ b/libstdc++-v3/include/Makefile.am @@ -102,6 +102,7 @@ bits_headers = \ ${bits_srcdir}/boost_concept_check.h \ ${bits_srcdir}/c++0x_warning.h \ ${bits_srcdir}/char_traits.h \ + ${bits_srcdir}/charconv.h \ ${bits_srcdir}/codecvt.h \ ${bits_srcdir}/concept_check.h \ ${bits_srcdir}/cpp_type_traits.h \ diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in index 58c56f7a0f8..fd4dbf7ffb7 100644 --- a/libstdc++-v3/include/Makefile.in +++ b/libstdc++-v3/include/Makefile.in @@ -446,6 +446,7 @@ bits_headers = \ ${bits_srcdir}/boost_concept_check.h \ ${bits_srcdir}/c++0x_warning.h \ ${bits_srcdir}/char_traits.h \ + ${bits_srcdir}/charconv.h \ ${bits_srcdir}/codecvt.h \ ${bits_srcdir}/concept_check.h \ ${bits_srcdir}/cpp_type_traits.h \ diff --git a/libstdc++-v3/include/bits/basic_string.h b/libstdc++-v3/include/bits/basic_string.h index 897acaa8c02..f1bdc6c553f 100644 --- a/libstdc++-v3/include/bits/basic_string.h +++ b/libstdc++-v3/include/bits/basic_string.h @@ -6500,6 +6500,7 @@ _GLIBCXX_END_NAMESPACE_VERSION #if __cplusplus >= 201103L #include +#include namespace std _GLIBCXX_VISIBILITY(default) { @@ -6547,43 +6548,68 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 { return __gnu_cxx::__stoa(&std::strtold, "stold", __str.c_str(), __idx); } #endif // _GLIBCXX_USE_C99_STDLIB -#if _GLIBCXX_USE_C99_STDIO - // NB: (v)snprintf vs sprintf. + // DR 1261. Insufficent overloads for to_string / to_wstring - // DR 1261. inline string to_string(int __val) - { return __gnu_cxx::__to_xstring(&std::vsnprintf, 4 * sizeof(int), - "%d", __val); } + { + const bool __neg = __val < 0; + const unsigned __uval = __neg ? (unsigned)~__val + 1u : __val; + const auto __len = __detail::__to_chars_len(__uval); + string __str(__neg + __len, '-'); + __detail::__to_chars_10_impl(&__str[__neg], __len, __uval); + return __str; + } inline string to_string(unsigned __val) - { return __gnu_cxx::__to_xstring(&std::vsnprintf, - 4 * sizeof(unsigned), - "%u", __val); } + { + string __str(__detail::__to_chars_len(__val), '\0'); + __detail::__to_chars_10_impl(&__str[0], __str.size(), __val); + return __str; + } inline string to_string(long __val) - { return __gnu_cxx::__to_xstring(&std::vsnprintf, 4 * sizeof(long), - "%ld", __val); } + { + const bool __neg = __val < 0; + const unsigned long __uval = __neg ? (unsigned long)~__val + 1ul : __val; + const auto __len = __detail::__to_chars_len(__uval); + string __str(__neg + __len, '-'); + __detail::__to_chars_10_impl(&__str[__neg], __len, __uval); + return __str; + } inline string to_string(unsigned long __val) - { return __gnu_cxx::__to_xstring(&std::vsnprintf, - 4 * sizeof(unsigned long), - "%lu", __val); } + { + string __str(__detail::__to_chars_len(__val), '\0'); + __detail::__to_chars_10_impl(&__str[0], __str.size(), __val); + return __str; + } inline string to_string(long long __val) - { return __gnu_cxx::__to_xstring(&std::vsnprintf, - 4 * sizeof(long long), - "%lld", __val); } + { + const bool __neg = __val < 0; + const unsigned long long __uval + = __neg ? (unsigned long long)~__val + 1ull : __val; + const auto __len = __detail::__to_chars_len(__uval); + string __str(__neg + __len, '-'); + __detail::__to_chars_10_impl(&__str[__neg], __len, __uval); + return __str; + } inline string to_string(unsigned long long __val) - { return __gnu_cxx::__to_xstring(&std::vsnprintf, - 4 * sizeof(unsigned long long), - "%llu", __val); } + { + string __str(__detail::__to_chars_len(__val), '\0'); + __detail::__to_chars_10_impl(&__str[0], __str.size(), __val); + return __str; + } + +#if _GLIBCXX_USE_C99_STDIO + // NB: (v)snprintf vs sprintf. inline string to_string(float __val) diff --git a/libstdc++-v3/include/bits/charconv.h b/libstdc++-v3/include/bits/charconv.h new file mode 100644 index 00000000000..0911660fab6 --- /dev/null +++ b/libstdc++-v3/include/bits/charconv.h @@ -0,0 +1,106 @@ +// Numeric conversions (to_string, to_chars) -*- C++ -*- + +// Copyright (C) 2017-2019 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// . + +/** @file bits/charconv.h + * This is an internal header file, included by other library headers. + * Do not attempt to use it directly. @headername{charconv} + */ + +#ifndef _GLIBCXX_CHARCONV_H +#define _GLIBCXX_CHARCONV_H 1 + +#pragma GCC system_header + +#if __cplusplus >= 201103L + +#include + +namespace std _GLIBCXX_VISIBILITY(default) +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION +namespace __detail +{ + // Generic implementation for arbitrary bases. + template + _GLIBCXX14_CONSTEXPR unsigned + __to_chars_len(_Tp __value, int __base = 10) noexcept + { + static_assert(is_integral<_Tp>::value, "implementation bug"); + static_assert(is_unsigned<_Tp>::value, "implementation bug"); + + unsigned __n = 1; + const int __b2 = __base * __base; + const int __b3 = __b2 * __base; + const int __b4 = __b3 * __base; + for (;;) + { + if (__value < __base) return __n; + if (__value < __b2) return __n + 1; + if (__value < __b3) return __n + 2; + if (__value < __b4) return __n + 3; + __value /= (unsigned)__b4; + __n += 4; + } + } + + // Write an unsigned integer value to the range [first,first+len). + // The caller is required to provide a buffer of exactly the right size + // (which can be determined by the __to_chars_len function). + template + void + __to_chars_10_impl(char* __first, unsigned __len, _Tp __val) noexcept + { + static_assert(is_integral<_Tp>::value, "implementation bug"); + static_assert(is_unsigned<_Tp>::value, "implementation bug"); + + static constexpr char __digits[201] = + "0001020304050607080910111213141516171819" + "2021222324252627282930313233343536373839" + "4041424344454647484950515253545556575859" + "6061626364656667686970717273747576777879" + "8081828384858687888990919293949596979899"; + unsigned __pos = __len - 1; + while (__val >= 100) + { + auto const __num = (__val % 100) * 2; + __val /= 100; + __first[__pos] = __digits[__num + 1]; + __first[__pos - 1] = __digits[__num]; + __pos -= 2; + } + if (__val >= 10) + { + auto const __num = __val * 2; + __first[__pos] = __digits[__num + 1]; + __first[__pos - 1] = __digits[__num]; + } + else + __first[__pos] = '0' + __val; + } + +} // namespace __detail +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace std +#endif // C++11 +#endif // _GLIBCXX_CHARCONV_H diff --git a/libstdc++-v3/include/std/charconv b/libstdc++-v3/include/std/charconv index 9f01d4c0889..a777f60501d 100644 --- a/libstdc++-v3/include/std/charconv +++ b/libstdc++-v3/include/std/charconv @@ -36,8 +36,11 @@ #include #include #include +#include // for __to_chars_len, __to_chars_10_impl #include // for std::errc +// Define when floating point is supported: #define __cpp_lib_to_chars 201611L + namespace std _GLIBCXX_VISIBILITY(default) { _GLIBCXX_BEGIN_NAMESPACE_VERSION @@ -76,42 +79,30 @@ namespace __detail using __integer_to_chars_result_type = enable_if_t<__is_int_to_chars_type<_Tp>::value, to_chars_result>; + // Pick an unsigned type of suitable size. This is used to reduce the + // number of specializations of __to_chars_len, __to_chars etc. that + // get instantiated. For example, to_chars and to_chars + // and to_chars will all use the same code, and so will + // to_chars when sizeof(int) == sizeof(long). template - using __unsigned_least_t - = conditional_t<(sizeof(_Tp) <= sizeof(int)), unsigned int, - conditional_t<(sizeof(_Tp) <= sizeof(long)), unsigned long, - conditional_t<(sizeof(_Tp) <= sizeof(long long)), unsigned long long, -#if _GLIBCXX_USE_INT128 - conditional_t<(sizeof(_Tp) <= sizeof(__int128)), unsigned __int128, -#endif - void + struct __to_chars_unsigned_type : __make_unsigned_selector_base + { + using _UInts = _List + , unsigned __int128 #endif - >>>; + >; + using type = typename __select::__type; + }; + + template + using __unsigned_least_t = typename __to_chars_unsigned_type<_Tp>::type; // Generic implementation for arbitrary bases. + // Defined in . template constexpr unsigned - __to_chars_len(_Tp __value, int __base = 10) noexcept - { - static_assert(is_integral<_Tp>::value, "implementation bug"); - static_assert(is_unsigned<_Tp>::value, "implementation bug"); - - unsigned __n = 1; - const int __b2 = __base * __base; - const int __b3 = __b2 * __base; - const int __b4 = __b3 * __base; - for (;;) - { - if (__value < __base) return __n; - if (__value < __b2) return __n + 1; - if (__value < __b3) return __n + 2; - if (__value < __b4) return __n + 3; - __value /= (unsigned)__b4; - __n += 4; - } - } + __to_chars_len(_Tp __value, int __base /* = 10 */) noexcept; template constexpr unsigned @@ -242,7 +233,7 @@ namespace __detail } template - __integer_to_chars_result_type<_Tp> + inline __integer_to_chars_result_type<_Tp> __to_chars_10(char* __first, char* __last, _Tp __val) noexcept { static_assert(is_integral<_Tp>::value, "implementation bug"); @@ -259,29 +250,7 @@ namespace __detail return __res; } - static constexpr char __digits[201] = - "0001020304050607080910111213141516171819" - "2021222324252627282930313233343536373839" - "4041424344454647484950515253545556575859" - "6061626364656667686970717273747576777879" - "8081828384858687888990919293949596979899"; - unsigned __pos = __len - 1; - while (__val >= 100) - { - auto const __num = (__val % 100) * 2; - __val /= 100; - __first[__pos] = __digits[__num + 1]; - __first[__pos - 1] = __digits[__num]; - __pos -= 2; - } - if (__val >= 10) - { - auto const __num = __val * 2; - __first[__pos] = __digits[__num + 1]; - __first[__pos - 1] = __digits[__num]; - } - else - __first[__pos] = '0' + __val; + __detail::__to_chars_10_impl(__first, __len, __val); __res.ptr = __first + __len; __res.ec = {}; return __res; diff --git a/libstdc++-v3/include/std/version b/libstdc++-v3/include/std/version index 9da3854aad3..cef4f1f8e9c 100644 --- a/libstdc++-v3/include/std/version +++ b/libstdc++-v3/include/std/version @@ -139,6 +139,7 @@ #endif #define __cpp_lib_shared_ptr_weak_type 201606 #define __cpp_lib_string_view 201603 +// #define __cpp_lib_to_chars 201611L #define __cpp_lib_type_trait_variable_templates 201510L #define __cpp_lib_uncaught_exceptions 201411L #define __cpp_lib_unordered_map_insertion 201411 diff --git a/libstdc++-v3/testsuite/21_strings/basic_string/numeric_conversions/char/to_string.cc b/libstdc++-v3/testsuite/21_strings/basic_string/numeric_conversions/char/to_string.cc index 11cb7c8a451..a3dab3e54ac 100644 --- a/libstdc++-v3/testsuite/21_strings/basic_string/numeric_conversions/char/to_string.cc +++ b/libstdc++-v3/testsuite/21_strings/basic_string/numeric_conversions/char/to_string.cc @@ -20,7 +20,7 @@ // with this library; see the file COPYING3. If not see // . -// 21.4 Numeric Conversions [string.conversions] +// C++11 21.5 Numeric Conversions [string.conversions] #include #include @@ -28,7 +28,6 @@ void test01() { - bool test = true; using namespace std; long long ll1 = -2; @@ -59,5 +58,4 @@ test01() int main() { test01(); - return 0; } diff --git a/libstdc++-v3/testsuite/21_strings/basic_string/numeric_conversions/char/to_string_int.cc b/libstdc++-v3/testsuite/21_strings/basic_string/numeric_conversions/char/to_string_int.cc new file mode 100644 index 00000000000..8eb2a48bd30 --- /dev/null +++ b/libstdc++-v3/testsuite/21_strings/basic_string/numeric_conversions/char/to_string_int.cc @@ -0,0 +1,164 @@ +// { dg-options "-DSIMULATOR_TEST" { target simulator } } +// { dg-do run { target c++11 } } + +// Copyright (C) 2019 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// C++11 21.5 Numeric Conversions [string.conversions] + +#include +#include +#include +#include +#include + +namespace test +{ +static char buf[100]; + +// Canonical version of std::to_string(int) as specified in the standard. +static std::string to_string(int val) +{ + std::string str; + const int len = std::snprintf(buf, sizeof(buf), "%d", val); + VERIFY( len < (int)sizeof(buf) ); + return std::string(buf, len); +} + +static std::string to_string(unsigned int val) +{ + std::string str; + const int len = std::snprintf(buf, sizeof(buf), "%u", val); + VERIFY( len < (int)sizeof(buf) ); + return std::string(buf, len); +} + +static std::string to_string(long val) +{ + std::string str; + const int len = std::snprintf(buf, sizeof(buf), "%ld", val); + VERIFY( len < (int)sizeof(buf) ); + return std::string(buf, len); +} + +static std::string to_string(unsigned long val) +{ + std::string str; + const int len = std::snprintf(buf, sizeof(buf), "%lu", val); + VERIFY( len < (int)sizeof(buf) ); + return std::string(buf, len); +} + +static std::string to_string(long long val) +{ + std::string str; + const int len = std::snprintf(buf, sizeof(buf), "%lld", val); + VERIFY( len < (int)sizeof(buf) ); + return std::string(buf, len); +} + +static std::string to_string(unsigned long long val) +{ + std::string str; + const int len = std::snprintf(buf, sizeof(buf), "%llu", val); + VERIFY( len < (int)sizeof(buf) ); + return std::string(buf, len); +} + +} // namespace test + +const std::uint_least32_t values[] = { + 0x10, 0x30, 0x50, 0x80, 0xc0, + 0x100, 0x180, 0x1c0, 0x200, 0x400, 0x800, 0xc00, + 0x1000, 0x1800, 0x2000, 0x4000, 0x8000, 0xc000, + 0x10000, 0x10101, 0x80000, 0x80706, 0xc0000, 0xccccc, + 0x100000, 0x101010, 0x800000, 0x807060, 0xc0fefe, 0xc1d2e3f, + 0x1000000, 0x1001000, 0x1008000, 0x1010000, 0x1080000, 0x1100000, 0x1234567, + 0x10000000, 0x10101010, 0x12345678, 0x80000010, 0x87654321, 0xaaaaaaaa, + 0xf0000000, 0xf0101010, 0xf0f00000, 0xf0f0f0f0, 0xf0ff0ff0, 0xff0ff00f, + 0xffff0000, 0xffff00f0, 0xffff0ff0, 0xffffff00 +}; + +const std::size_t empty_string_capacity = std::string().capacity(); + +#include + +template + void check_value(T val) + { + const std::string s = std::to_string(val); + const std::string expected = test::to_string(val); + VERIFY( s == expected ); + VERIFY( s[s.size()] == '\0' ); // null-terminator not overwritten! + if (s.size() > empty_string_capacity) + VERIFY( s.capacity() == s.size() ); // GNU-specific guarantee + } + +#ifdef SIMULATOR_TEST +const int width = 3; +#else +const int width = 16; +#endif + +template + void check_values() + { +#ifdef SIMULATOR_TEST + check_value((T)-1); + check_value((T)0); + check_value((T)+1); +#endif + + for (auto v : values) + { + for (int i = -width; i < +width; ++i) + { + const T val = (T)v + i; + check_value(val); + } + + if (std::numeric_limits::digits > 32) + { + for (auto v2 : values) + { + for (int i = -width; i < +width; ++i) + { + typename std::make_unsigned::type hi = v2; + hi += i; + hi <<= 32; + const T val = T(hi) | v; + check_value(val); + } + } + } + } + } + +void test02() +{ + check_values(); + check_values(); + check_values(); + check_values(); + check_values(); + check_values(); +} + +int main() +{ + test02(); +} -- 2.30.2