[PATCH] Replace std::to_string for integers with optimized version

[PATCH] Replace std::to_string for integers with optimized version

[Jonathan Wakely]

[-- Attachment #1: Type: text/plain, Size: 1945 bytes --]

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 <bits/charconv.h> 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 <charconv>.
	(__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<T>::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.

Tested x86_64-linux, committed to trunk.


[-- Attachment #2: patch.txt --]
[-- Type: text/plain, Size: 19983 bytes --]

commit 00f08bc3d9bdc3c5bc75334dfa780918e7c7ee25
Author: redi <redi@138bc75d-0d04-0410-961f-82ee72b054a4>
Date:   Wed Jun 12 14:52:02 2019 +0000

    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 <bits/charconv.h> 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 <charconv>.
            (__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<T>::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.
    
    git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@272186 138bc75d-0d04-0410-961f-82ee72b054a4

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/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 <ext/string_conversions.h>
+#include <bits/charconv.h>
 
 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<string>(&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<string>(&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<string>(&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<string>(&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<string>(&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<string>(&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
+// <http://www.gnu.org/licenses/>.
+
+/** @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 <type_traits>
+
+namespace std _GLIBCXX_VISIBILITY(default)
+{
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+namespace __detail
+{
+  // Generic implementation for arbitrary bases.
+  template<typename _Tp>
+    _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<typename _Tp>
+    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 <type_traits>
 #include <limits>
 #include <cctype>
+#include <bits/charconv.h> // for __to_chars_len, __to_chars_10_impl
 #include <bits/error_constants.h> // 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<char> and to_chars<short>
+  // and to_chars<unsigned> will all use the same code, and so will
+  // to_chars<long> when sizeof(int) == sizeof(long).
   template<typename _Tp>
-    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,
+    struct __to_chars_unsigned_type : __make_unsigned_selector_base
+    {
+      using _UInts = _List<unsigned int, unsigned long, unsigned long long
 #if _GLIBCXX_USE_INT128
-	conditional_t<(sizeof(_Tp) <= sizeof(__int128)), unsigned __int128,
+	, unsigned __int128
 #endif
-	void
-#if _GLIBCXX_USE_INT128
-	>
-#endif
-	>>>;
+	>;
+      using type = typename __select<sizeof(_Tp), _UInts>::__type;
+    };
+
+  template<typename _Tp>
+    using __unsigned_least_t = typename __to_chars_unsigned_type<_Tp>::type;
 
   // Generic implementation for arbitrary bases.
+  // Defined in <bits/charconv.h>.
   template<typename _Tp>
     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<typename _Tp>
     constexpr unsigned
@@ -242,7 +233,7 @@ namespace __detail
     }
 
   template<typename _Tp>
-    __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
 // <http://www.gnu.org/licenses/>.
 
-// 21.4 Numeric Conversions [string.conversions]
+// C++11 21.5 Numeric Conversions [string.conversions]
 
 #include <string>
 #include <testsuite_hooks.h>
@@ -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
+// <http://www.gnu.org/licenses/>.
+
+// C++11 21.5 Numeric Conversions [string.conversions]
+
+#include <string>
+#include <limits>
+#include <cstdint>
+#include <cstdio>
+#include <testsuite_hooks.h>
+
+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 <set>
+
+template<typename T>
+  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<typename T>
+  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<T>::digits > 32)
+      {
+	for (auto v2 : values)
+	{
+	  for (int i = -width; i < +width; ++i)
+	  {
+	    typename std::make_unsigned<T>::type hi = v2;
+	    hi += i;
+	    hi <<= 32;
+	    const T val = T(hi) | v;
+	    check_value(val);
+	  }
+	}
+      }
+    }
+  }
+
+void test02()
+{
+  check_values<int>();
+  check_values<unsigned int>();
+  check_values<long>();
+  check_values<unsigned long>();
+  check_values<long long>();
+  check_values<unsigned long long>();
+}
+
+int main()
+{
+  test02();
+}

Re: [PATCH] Replace std::to_string for integers with optimized version

[Christophe Lyon]

Hi,


On Wed, 12 Jun 2019 at 16:54, Jonathan Wakely <jwakely@redhat.com> wrote:
>
> 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 <bits/charconv.h> 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 <charconv>.
>         (__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<T>::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.
>
> Tested x86_64-linux, committed to trunk.
>

The new test to_string_int.cc fails on arm-none-eabi:
PASS: 21_strings/basic_string/numeric_conversions/char/to_string_int.cc
(test for excess errors)
spawn /aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-arm-none-eabi/gcc3/utils/bin/qemu-wrapper.sh
./to_string_int.exe
/libstdc++-v3/testsuite/21_strings/basic_string/numeric_conversions/char/to_string_int.cc:105:
void check_value(T) [with T = long long int]: Assertion 's ==
expected' failed.
FAIL: 21_strings/basic_string/numeric_conversions/char/to_string_int.cc
execution test

Christophe

Re: [PATCH] Replace std::to_string for integers with optimized version

[Jonathan Wakely]

[-- Attachment #1: Type: text/plain, Size: 3836 bytes --]

On 13/06/19 22:41 +0200, Christophe Lyon wrote:
>Hi,
>
>
>On Wed, 12 Jun 2019 at 16:54, Jonathan Wakely <jwakely@redhat.com> wrote:
>>
>> 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 <bits/charconv.h> 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 <charconv>.
>>         (__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<T>::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.
>>
>> Tested x86_64-linux, committed to trunk.
>>
>
>The new test to_string_int.cc fails on arm-none-eabi:
>PASS: 21_strings/basic_string/numeric_conversions/char/to_string_int.cc
>(test for excess errors)
>spawn /aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-arm-none-eabi/gcc3/utils/bin/qemu-wrapper.sh
>./to_string_int.exe
>/libstdc++-v3/testsuite/21_strings/basic_string/numeric_conversions/char/to_string_int.cc:105:
>void check_value(T) [with T = long long int]: Assertion 's ==
>expected' failed.
>FAIL: 21_strings/basic_string/numeric_conversions/char/to_string_int.cc
>execution test

Does the target support "%lld" in printf?

Does the .sum file show UNSUPPORTED for the existing
21_strings/basic_string/numeric_conversions/char/to_string.cc test?

Does the attached patch make the test show what fails?

I suspect the problem is that the test relies on snprintf to check the
answers are correct, even though the actual library code doesn't need
snprintf any longer. Previously the std::to_string functions were all
guarded by _GLIBCXX_USE_C99_STDIO and so I'm guessing were not
supported for arm-none-eabi. Now the overloads for integral types
should work without any C library support, and so the new test is
enabled unconditionally. But the test itself still uses the C library.

Maybe I should have a simple test that doesn't use snprintf and just
checks some hardcoded values produce the expected results, and a more
involved test that compares the results to snprintf but uses 
{ dg-require-string-conversions "" } like the existing test.




[-- Attachment #2: patch.txt --]
[-- Type: text/x-patch, Size: 994 bytes --]

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
index 8eb2a48bd30..911e6812b39 100644
--- 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
@@ -95,13 +95,15 @@ const std::uint_least32_t values[] = {
 
 const std::size_t empty_string_capacity = std::string().capacity();
 
-#include <set>
+#include <iostream>
 
 template<typename T>
   void check_value(T val)
   {
     const std::string s = std::to_string(val);
     const std::string expected = test::to_string(val);
+    if (s != expected)
+      std::cerr << "GOT: " << s << " BUT EXPECTED: " << expected << '\n';
     VERIFY( s == expected );
     VERIFY( s[s.size()] == '\0' ); // null-terminator not overwritten!
     if (s.size() > empty_string_capacity)

Re: [PATCH] Replace std::to_string for integers with optimized version

[Christophe Lyon]

On Mon, 17 Jun 2019 at 15:21, Jonathan Wakely <jwakely@redhat.com> wrote:
>
> On 13/06/19 22:41 +0200, Christophe Lyon wrote:
> >Hi,
> >
> >
> >On Wed, 12 Jun 2019 at 16:54, Jonathan Wakely <jwakely@redhat.com> wrote:
> >>
> >> 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 <bits/charconv.h> 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 <charconv>.
> >>         (__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<T>::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.
> >>
> >> Tested x86_64-linux, committed to trunk.
> >>
> >
> >The new test to_string_int.cc fails on arm-none-eabi:
> >PASS: 21_strings/basic_string/numeric_conversions/char/to_string_int.cc
> >(test for excess errors)
> >spawn /aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-arm-none-eabi/gcc3/utils/bin/qemu-wrapper.sh
> >./to_string_int.exe
> >/libstdc++-v3/testsuite/21_strings/basic_string/numeric_conversions/char/to_string_int.cc:105:
> >void check_value(T) [with T = long long int]: Assertion 's ==
> >expected' failed.
> >FAIL: 21_strings/basic_string/numeric_conversions/char/to_string_int.cc
> >execution test
>
> Does the target support "%lld" in printf?
>
> Does the .sum file show UNSUPPORTED for the existing
> 21_strings/basic_string/numeric_conversions/char/to_string.cc test?
>
No, it PASSes.

> Does the attached patch make the test show what fails?
I didn't try because I realized that it might be a problem with how I
configure newlib in my validation system.

After I added the same flags I use when I build&test manually,
to_string_int.cc now passes.

I added:
        --enable-newlib-io-pos-args \
        --enable-newlib-io-c99-formats \
        --enable-newlib-io-long-long \
        --enable-newlib-io-long-double \
to newlib's configure flags.

However, this makes several other libstdc++ tests fail on aarch64:
    22_locale/money_get/get/char/5.cc execution test
    22_locale/money_get/get/wchar_t/5.cc execution test
    22_locale/num_get/get/char/39168.cc execution test
    22_locale/num_get/get/char/4.cc execution test
    22_locale/num_get/get/wchar_t/39168.cc execution test
    22_locale/num_get/get/wchar_t/4.cc execution test
    26_numerics/complex/inserters_extractors/char/1.cc execution test
    26_numerics/complex/inserters_extractors/wchar_t/1.cc execution test
    27_io/basic_istream/extractors_arithmetic/char/01.cc execution test
    27_io/basic_istream/extractors_arithmetic/char/12.cc execution test
    27_io/basic_istream/extractors_arithmetic/wchar_t/01.cc execution test
    27_io/basic_istream/extractors_arithmetic/wchar_t/12.cc execution test

but I guess that should be a separate bug report....

I'll add those flags to my automated tests.

Thanks,

Christophe

> I suspect the problem is that the test relies on snprintf to check the
> answers are correct, even though the actual library code doesn't need
> snprintf any longer. Previously the std::to_string functions were all
> guarded by _GLIBCXX_USE_C99_STDIO and so I'm guessing were not
> supported for arm-none-eabi. Now the overloads for integral types
> should work without any C library support, and so the new test is
> enabled unconditionally. But the test itself still uses the C library.
>
> Maybe I should have a simple test that doesn't use snprintf and just
> checks some hardcoded values produce the expected results, and a more
> involved test that compares the results to snprintf but uses
> { dg-require-string-conversions "" } like the existing test.
>
>
>

Re: [PATCH] Replace std::to_string for integers with optimized version

[Jonathan Wakely]

On 18/06/19 13:58 +0200, Christophe Lyon wrote:
>On Mon, 17 Jun 2019 at 15:21, Jonathan Wakely <jwakely@redhat.com> wrote:
>>
>> On 13/06/19 22:41 +0200, Christophe Lyon wrote:
>> >Hi,
>> >
>> >
>> >On Wed, 12 Jun 2019 at 16:54, Jonathan Wakely <jwakely@redhat.com> wrote:
>> >>
>> >> 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 <bits/charconv.h> 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 <charconv>.
>> >>         (__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<T>::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.
>> >>
>> >> Tested x86_64-linux, committed to trunk.
>> >>
>> >
>> >The new test to_string_int.cc fails on arm-none-eabi:
>> >PASS: 21_strings/basic_string/numeric_conversions/char/to_string_int.cc
>> >(test for excess errors)
>> >spawn /aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-arm-none-eabi/gcc3/utils/bin/qemu-wrapper.sh
>> >./to_string_int.exe
>> >/libstdc++-v3/testsuite/21_strings/basic_string/numeric_conversions/char/to_string_int.cc:105:
>> >void check_value(T) [with T = long long int]: Assertion 's ==
>> >expected' failed.
>> >FAIL: 21_strings/basic_string/numeric_conversions/char/to_string_int.cc
>> >execution test
>>
>> Does the target support "%lld" in printf?
>>
>> Does the .sum file show UNSUPPORTED for the existing
>> 21_strings/basic_string/numeric_conversions/char/to_string.cc test?
>>
>No, it PASSes.
>
>> Does the attached patch make the test show what fails?
>I didn't try because I realized that it might be a problem with how I
>configure newlib in my validation system.
>
>After I added the same flags I use when I build&test manually,
>to_string_int.cc now passes.
>
>I added:
>        --enable-newlib-io-pos-args \
>        --enable-newlib-io-c99-formats \
>        --enable-newlib-io-long-long \
>        --enable-newlib-io-long-double \
>to newlib's configure flags.

I assume it's io-c99-formats that makes "%lld" work.

>However, this makes several other libstdc++ tests fail on aarch64:
>    22_locale/money_get/get/char/5.cc execution test
>    22_locale/money_get/get/wchar_t/5.cc execution test
>    22_locale/num_get/get/char/39168.cc execution test
>    22_locale/num_get/get/char/4.cc execution test
>    22_locale/num_get/get/wchar_t/39168.cc execution test
>    22_locale/num_get/get/wchar_t/4.cc execution test
>    26_numerics/complex/inserters_extractors/char/1.cc execution test
>    26_numerics/complex/inserters_extractors/wchar_t/1.cc execution test
>    27_io/basic_istream/extractors_arithmetic/char/01.cc execution test
>    27_io/basic_istream/extractors_arithmetic/char/12.cc execution test
>    27_io/basic_istream/extractors_arithmetic/wchar_t/01.cc execution test
>    27_io/basic_istream/extractors_arithmetic/wchar_t/12.cc execution test
>
>but I guess that should be a separate bug report....
>
>I'll add those flags to my automated tests.

Thanks.