[PATCH] Add header implementation of std::to_string for integers (PR libstdc++/71108)

[Adrian Wielgosik <adrian dot wielgosik at gmail dot com>]

Currently std::to_string takes a fairly long trip to vs(n/w)printf. The patch
implements int-to-string formatting in header, to improve function performance.

Results of a benchmark on my PC:
to_string(integer) takes 85-107ns per call (depending on result string size),
out of which ~75ns is spent in vsnprintf. The new implementation removes the
overhead, reducing time per call to 12-29ns.

Tested on x64.

As a side note, this is my first patch for libstdc++/GCC, so please try to
forgive any silly mistakes. Regarding requesting copyright assignment, do I
have to contact assign@gnu.org separately, or is mentioning it here enough?


2017-05-27  Adrian Wielgosik  <adrian.wielgosik@gmail.com>

    PR libstdc++/71108
    * libstdc++-v3/include/ext/string_conversions.h:
    (__int_to_string, __format_uint): New.
    * libstdc++-v3/include/bits/basic_string.h: Use the new function.


 libstdc++-v3/include/bits/basic_string.h      | 44
++++++++++++--------------------------------
 libstdc++-v3/include/ext/string_conversions.h | 38
++++++++++++++++++++++++++++++++++++++
 2 files changed, 50 insertions(+), 32 deletions(-)


diff --git a/libstdc++-v3/include/bits/basic_string.h
b/libstdc++-v3/include/bits/basic_string.h
index b6693c440c01..7732b246a962 100644
--- a/libstdc++-v3/include/bits/basic_string.h
+++ b/libstdc++-v3/include/bits/basic_string.h
@@ -6210,37 +6210,27 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
   // DR 1261.
   inline string
   to_string(int __val)
-  { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, 4 * sizeof(int),
-   "%d", __val); }
+  { return __gnu_cxx::__int_to_string<string>(__val); }

   inline string
   to_string(unsigned __val)
-  { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
-   4 * sizeof(unsigned),
-   "%u", __val); }
+  { return __gnu_cxx::__int_to_string<string>(__val); }

   inline string
   to_string(long __val)
-  { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, 4 * sizeof(long),
-   "%ld", __val); }
+  { return __gnu_cxx::__int_to_string<string>(__val); }

   inline string
   to_string(unsigned long __val)
-  { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
-   4 * sizeof(unsigned long),
-   "%lu", __val); }
+  { return __gnu_cxx::__int_to_string<string>(__val); }

   inline string
   to_string(long long __val)
-  { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
-   4 * sizeof(long long),
-   "%lld", __val); }
+  { return __gnu_cxx::__int_to_string<string>(__val); }

   inline string
   to_string(unsigned long long __val)
-  { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
-   4 * sizeof(unsigned long long),
-   "%llu", __val); }
+  { return __gnu_cxx::__int_to_string<string>(__val); }

   inline string
   to_string(float __val)
@@ -6313,37 +6303,27 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
   // DR 1261.
   inline wstring
   to_wstring(int __val)
-  { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, 4 * sizeof(int),
-    L"%d", __val); }
+  { return __gnu_cxx::__int_to_string<wstring>(__val); }

   inline wstring
   to_wstring(unsigned __val)
-  { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
-    4 * sizeof(unsigned),
-    L"%u", __val); }
+  { return __gnu_cxx::__int_to_string<wstring>(__val); }

   inline wstring
   to_wstring(long __val)
-  { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, 4 * sizeof(long),
-    L"%ld", __val); }
+  { return __gnu_cxx::__int_to_string<wstring>(__val); }

   inline wstring
   to_wstring(unsigned long __val)
-  { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
-    4 * sizeof(unsigned long),
-    L"%lu", __val); }
+  { return __gnu_cxx::__int_to_string<wstring>(__val); }

   inline wstring
   to_wstring(long long __val)
-  { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
-    4 * sizeof(long long),
-    L"%lld", __val); }
+  { return __gnu_cxx::__int_to_string<wstring>(__val); }

   inline wstring
   to_wstring(unsigned long long __val)
-  { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
-    4 * sizeof(unsigned long long),
-    L"%llu", __val); }
+  { return __gnu_cxx::__int_to_string<wstring>(__val); }

   inline wstring
   to_wstring(float __val)
diff --git a/libstdc++-v3/include/ext/string_conversions.h
b/libstdc++-v3/include/ext/string_conversions.h
index 89cba61857d4..617a626a7955 100644
--- a/libstdc++-v3/include/ext/string_conversions.h
+++ b/libstdc++-v3/include/ext/string_conversions.h
@@ -93,6 +93,44 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       return __ret;
     }

+  template<typename _CharT, typename _T>
+    _CharT*
+    __format_uint(_CharT *__end, _T __value)
+    {
+      do
+      {
+        *--__end = '0' + __value % 10;
+        __value /= 10;
+      } while(__value);
+
+      return __end;
+    }
+
+  template<typename _String, typename _T>
+    _String
+    __int_to_string(_T __value)
+    {
+      using _UT = typename std::make_unsigned<_T>::type;
+      using _CharT = typename _String::value_type;
+      constexpr std::size_t __n = 4 * sizeof(_T);
+
+      _UT __absolute;
+      bool __negative = __value < 0;
+      if (__negative)
+        __absolute = -static_cast<_UT>(__value);
+      else
+        __absolute = static_cast<_UT>(__value);
+
+      _CharT __s[__n];
+      _CharT* __end = __s + __n;
+      _CharT* __start = __format_uint(__end, __absolute);
+
+      if (__negative)
+        *--__start = '-';
+
+      return _String(__start, __end);
+    }
+
   // Helper for the to_string / to_wstring functions.
   template<typename _String, typename _CharT = typename _String::value_type>
     _String