[libcxx] speedup to_string for floating point numbers

[ivafanas]

Summary

Proposal to speedup to_string / to_wstring for floating points numbers by reducing sprintf calls and allocations using stack buffer.

Benchmark results:
http://quick-bench.com/vS-2RuYzsZrBNRbhsliN4o8M8B4

• to_string is improved in 1.3x times for small values (tested on zero)
• to_wstring is not changed for small values
• to_string is improved in 2.1x times for -DBL_MAX
• to_wstring is improved in 5.2x times for -DBL_MAX

Proposed implementation fallbacks to the previous one for some long double values and non-standard floats / doubles so conversion tests were added for numeric_limits<T>::max / min / lowest.

[mclow.lists]

I would like to hold this for a while; because in a few weeks, we should have an implementation of to_chars for floating point - which we may be able to use in to_string (like we did for the integral types).

[ivafanas]

In D64341#1574437, @mclow.lists wrote:

I would like to hold this for a while; because in a few weeks, we should have an implementation of to_chars for floating point - which we may be able to use in to_string (like we did for the integral types).

Hi Marshall,

I'm not sure there is a way to reuse to_chars for floating point numbers inside to_string function due to locale issues:

• to_string must produce the same output as sprintf with %f or %Lf format specifiers (N. 7, 8, 9 and note 3)
• sprintf is locale-dependent. I suppose there is a difference between comma and point character for locales. Maybe something more.
• to_chars must produce the same result as sprintf in the default ("C") locale (N. 2)

If there is a tricky way to get around problem with locale dependency it would be nice.

libcxx/src/string.cpp

stold(const wstring& str, size_t* idx)
     return as_float<long double>( "stold", str, idx );
 }
 
 // to_string
 
 namespace
 {
 
-// as_string
+// f_to_string
+
+template<typename T>
+struct value_traits;
+
+template<>
+struct value_traits<float>
+{
+    static constexpr size_t stack_buffer_size = 47;
+};
+
+template<>
+struct value_traits<double>
+{
+    static constexpr size_t stack_buffer_size = 317;
+};
+
+template<>
+struct value_traits<long double>
+{
+    // For performance reasons value 4941 would be a better choice for 16-bit
+    // long double but in this way to_wstring(long double) would require 16Kb
+    // of stack memory. Use the same value as for doubles as tradeoff between
+    // performance and stack memory usage.
+    static constexpr size_t stack_buffer_size = 317;
+};
 
-template<typename S, typename P, typename V >
+template<typename S, typename P, typename V>
 inline
 S
-as_string(P sprintf_like, S s, const typename S::value_type* fmt, V a)
+f_to_string(P sprintf_like, const typename S::value_type* fmt, V a)
 {
     typedef typename S::size_type size_type;
+
+    S s;
+
+    // Try fast algorithm with stack buffer. Return result on success or resize
+    // result to advice on characters count on fail.
+    constexpr size_t buf_size = value_traits<V>::stack_buffer_size + 1;
+    typename S::value_type buf[buf_size];
+    int status = sprintf_like(buf, buf_size, fmt, a);
+    if (status >= 0)
+    {
+        size_type used = static_cast<size_type>(status);
+        if (used <= buf_size)
+        {
+            s.assign(buf, buf + used);
+            return s;
+        }
+        s.resize(used);
+    }
+    else
+    {
+        s.resize(2 * buf_size + 1);
+    }
+
+    // Fallback to iterative version with growing capacity.
     size_type available = s.size();
     while (true)
     {
         int status = sprintf_like(&s[0], available + 1, fmt, a);
         if ( status >= 0 )
         {
             size_type used = static_cast<size_type>(status);
             if ( used <= available )
             {
                 s.resize( used );
                 break;
             }
             available = used; // Assume this is advice of how much space we need.
         }
         else
             available = available * 2 + 1;
         s.resize(available);
     }
     return s;
 }
 
-template <class S>
-struct initial_string;
-
-template <>
-struct initial_string<string>
-{
-    string
-    operator()() const
-    {
-        string s;
-        s.resize(s.capacity());
-        return s;
-    }
-};
-
-template <>
-struct initial_string<wstring>
-{
-    wstring
-    operator()() const
-    {
-        wstring s(20, wchar_t());
-        s.resize(s.capacity());
-        return s;
-    }
-};
-
 typedef int (*wide_printf)(wchar_t* __restrict, size_t, const wchar_t*__restrict, ...);
 
 inline
 wide_printf
 get_swprintf()
 {
 #ifndef _LIBCPP_MSVCRT
     return swprintf;

 wstring to_wstring(int val)                { return i_to_string<wstring>(val); }
 wstring to_wstring(long val)               { return i_to_string<wstring>(val); }
 wstring to_wstring(long long val)          { return i_to_string<wstring>(val); }
 wstring to_wstring(unsigned val)           { return i_to_string<wstring>(val); }
 wstring to_wstring(unsigned long val)      { return i_to_string<wstring>(val); }
 wstring to_wstring(unsigned long long val) { return i_to_string<wstring>(val); }
 
 
-string  to_string (float val)       { return as_string(snprintf,       initial_string< string>()(),   "%f", val); }
-string  to_string (double val)      { return as_string(snprintf,       initial_string< string>()(),   "%f", val); }
-string  to_string (long double val) { return as_string(snprintf,       initial_string< string>()(),  "%Lf", val); }
-
-wstring to_wstring(float val)       { return as_string(get_swprintf(), initial_string<wstring>()(),  L"%f", val); }
-wstring to_wstring(double val)      { return as_string(get_swprintf(), initial_string<wstring>()(),  L"%f", val); }
-wstring to_wstring(long double val) { return as_string(get_swprintf(), initial_string<wstring>()(), L"%Lf", val); }
+string  to_string (float val)       { return f_to_string< string>(snprintf,       "%f", val); }
+string  to_string (double val)      { return f_to_string< string>(snprintf,       "%f", val); }
+string  to_string (long double val) { return f_to_string< string>(snprintf,       "%Lf", val); }
+
+wstring to_wstring(float val)       { return f_to_string<wstring>(get_swprintf(), L"%f", val); }
+wstring to_wstring(double val)      { return f_to_string<wstring>(get_swprintf(), L"%f", val); }
+wstring to_wstring(long double val) { return f_to_string<wstring>(get_swprintf(), L"%Lf", val); }
 
 _LIBCPP_END_NAMESPACE_STD

libcxx/test/std/strings/string.conversions/to_string.pass.cpp

 // string to_string(unsigned long long val);
 // string to_string(float val);
 // string to_string(double val);
 // string to_string(long double val);
 
 #include <limits>
 #include <string>
 #include <cassert>
+#include <cmath>
 #include <sstream>
 
 #include "test_macros.h"
 
 template <class T>
 void
 test_signed()
 {
test_float()
         assert(s == "12345.000000");
     }
     {
         std::string s = std::to_string(T(-12345));
         assert(s.size() == 13);
         assert(s[s.size()] == 0);
         assert(s == "-12345.000000");
     }
+
+    // to_string is required to be result of printf-like function with %f /
+    // %Lf format specifier. %f and %Lf format specifiers convert floating
+    // point number to string representation with minimum number of digits
+    // after decimal point character equal to 6.
+    const auto check_by_deconversion = [](const T value){
+        const std::string s = std::to_string(value);
+        const T restored_value = static_cast<T>(std::stold(s));
+        assert(std::fabs(value - restored_value) < T(1e-6));
+    };
+    check_by_deconversion(std::numeric_limits<T>::max());
+    check_by_deconversion(std::numeric_limits<T>::min());
+    check_by_deconversion(std::numeric_limits<T>::lowest());
 }
 
 int main(int, char**)
 {
     test_signed<int>();
     test_signed<long>();
     test_signed<long long>();
     test_unsigned<unsigned>();
     test_unsigned<unsigned long>();
     test_unsigned<unsigned long long>();
     test_float<float>();
     test_float<double>();
     test_float<long double>();
 
   return 0;
 }

libcxx/test/std/strings/string.conversions/to_wstring.pass.cpp

 // wstring to_wstring(unsigned long long val);
 // wstring to_wstring(float val);
 // wstring to_wstring(double val);
 // wstring to_wstring(long double val);
 
 #include <limits>
 #include <string>
 #include <cassert>
+#include <cmath>
 #include <sstream>
 
 #include "test_macros.h"
 
 template <class T>
 void
 test_signed()
 {
test_float()
         assert(s == L"12345.000000");
     }
     {
         std::wstring s = std::to_wstring(T(-12345));
         assert(s.size() == 13);
         assert(s[s.size()] == 0);
         assert(s == L"-12345.000000");
     }
+
+    // to_wstring is required to be result of printf-like function with %f /
+    // %Lf format specifier. %f and %Lf format specifiers convert floating
+    // point number to string representation with minimum number of digits
+    // after decimal point character equal to 6.
+    const auto check_by_deconversion = [](const T value){
+        const std::wstring s = std::to_wstring(value);
+        const T restored_value = static_cast<T>(std::stold(s));
+        assert(std::fabs(value - restored_value) < T(1e-6));
+    };
+    check_by_deconversion(std::numeric_limits<T>::max());
+    check_by_deconversion(std::numeric_limits<T>::min());
+    check_by_deconversion(std::numeric_limits<T>::lowest());
 }
 
 int main(int, char**)
 {
     test_signed<int>();
     test_signed<long>();
     test_signed<long long>();
     test_unsigned<unsigned>();
     test_unsigned<unsigned long>();
     test_unsigned<unsigned long long>();
     test_float<float>();
     test_float<double>();
     test_float<long double>();
 
   return 0;
 }