Optimization for std::to_string()

Message ID c9b263c6182555a3241c48f368e477e5@autistici.org
State New
Headers show
Series
  • Optimization for std::to_string()
Related show

Commit Message

niXman July 20, 2018, 9:44 a.m.
Hi,



Patch in attachments.

Tested on x86_64-linux-gnu.


-- 
Regards, niXman
___________________________________________________
C++ for Bitcoins: github.com/niXman

Comments

Jonathan Wakely July 20, 2018, 10:05 a.m. | #1
On 20/07/18 12:44 +0300, niXman wrote:
>

>Hi,

>

>

>

>Patch in attachments.


Thanks. How did you verify it's an optimization?

The to_string functions always pass at least __n=16 to __to_xstring,
which is larger than the SSO buffer in std::__cxx11::string, and so
forces a memory allocation.

The current code uses alloca and if the result fits in the SSO buffer
there is no allocation. e.g. to_string(999999) doesn't allocate from
the heap at all for the new std::__cxx11::string.

For the old COW string this doesn't make much difference, because we
always allocate. Your patch will mean we return a string with excess
capacity, rather than one of exactly capacity()==length(). That isn't
a problem.


>Tested on x86_64-linux-gnu.

>

>

>-- 

>Regards, niXman

>___________________________________________________

>C++ for Bitcoins: github.com/niXman


>Index: libstdc++-v3/include/ext/string_conversions.h

>===================================================================

>--- libstdc++-v3/include/ext/string_conversions.h	(revision 262879)

>+++ libstdc++-v3/include/ext/string_conversions.h	(working copy)

>@@ -100,19 +100,18 @@

> 				 __builtin_va_list), std::size_t __n,

> 		 const _CharT* __fmt, ...)

>     {

>-      // XXX Eventually the result should be constructed in-place in

>-      // the __cxx11 string, likely with the help of internal hooks.

>-      _CharT* __s = static_cast<_CharT*>(__builtin_alloca(sizeof(_CharT)

>-							  * __n));

>+      _String __str(__n, 0);

> 

>       __builtin_va_list __args;

>       __builtin_va_start(__args, __fmt);

> 

>-      const int __len = __convf(__s, __n, __fmt, __args);

>+      const std::size_t __len = __convf(&__str[0], __n, __fmt, __args);

> 

>       __builtin_va_end(__args);

> 

>-      return _String(__s, __s + __len);

>+      __str.resize(__len);

>+

>+      return __str;

>     }

> 

> _GLIBCXX_END_NAMESPACE_VERSION
niXman July 20, 2018, 10:51 a.m. | #2
Jonathan Wakely 2018-07-20 13:05:
> On 20/07/18 12:44 +0300, niXman wrote:


> Thanks. How did you verify it's an optimization?

Optimization is that there is no superfluous copying into string.

> The to_string functions always pass at least __n=16 to __to_xstring,

> which is larger than the SSO buffer in std::__cxx11::string, and so

> forces a memory allocation.

I didn't think about this...


-- 
Regards, niXman
___________________________________________________
C++ for Bitcoins: github.com/niXman
Jonathan Wakely July 20, 2018, 1:49 p.m. | #3
On 20/07/18 13:51 +0300, niXman wrote:
>Jonathan Wakely 2018-07-20 13:05:

>>On 20/07/18 12:44 +0300, niXman wrote:

>

>>Thanks. How did you verify it's an optimization?

>Optimization is that there is no superfluous copying into string.

>

>>The to_string functions always pass at least __n=16 to __to_xstring,

>>which is larger than the SSO buffer in std::__cxx11::string, and so

>>forces a memory allocation.

>I didn't think about this...


Avoiding an unconditional dynamic allocation is the main advantage of
using alloca.

Patch

Index: libstdc++-v3/include/ext/string_conversions.h
===================================================================
--- libstdc++-v3/include/ext/string_conversions.h	(revision 262879)
+++ libstdc++-v3/include/ext/string_conversions.h	(working copy)
@@ -100,19 +100,18 @@ 
 				 __builtin_va_list), std::size_t __n,
 		 const _CharT* __fmt, ...)
     {
-      // XXX Eventually the result should be constructed in-place in
-      // the __cxx11 string, likely with the help of internal hooks.
-      _CharT* __s = static_cast<_CharT*>(__builtin_alloca(sizeof(_CharT)
-							  * __n));
+      _String __str(__n, 0);
 
       __builtin_va_list __args;
       __builtin_va_start(__args, __fmt);
 
-      const int __len = __convf(__s, __n, __fmt, __args);
+      const std::size_t __len = __convf(&__str[0], __n, __fmt, __args);
 
       __builtin_va_end(__args);
 
-      return _String(__s, __s + __len);
+      __str.resize(__len);
+
+      return __str;
     }
 
 _GLIBCXX_END_NAMESPACE_VERSION