Re: [PATCH] for STDCXX-491 - string::push_back() slow

[Martin Sebor]

Arrgh! The attachment got stripped again. I'm going to go ahead
and request that they not strip images as Justin suggests in his
comment on https://issues.apache.org/jira/browse/INFRA-1194.

Martin

Martin Sebor wrote:

Mark Brown wrote:

Neat graph! What software did you use to create it?

gnuplot: http://www.gnuplot.info/

I'm also curious about the precipitous drop in the performance of both stdcxx and stlport around 32 elements. Do you have an explanation for it?

I was going to say that string in stdcxx reaches its initial
capacity at 32 characters and needs to be reallocated, but
now that I've checked the source code I see that the value
of _RWSTD_MINIMUM_STRING_CAPACITY is 128, so that can't be
it. I don't see the same pattern in the graph on Solaris
(attached) where there is a dip around 128 as expected so
I wonder if it's a function of the allocator in glibc.

Martin

-- Mark

-----Original Message-----
From: [EMAIL PROTECTED]
Sent: Sun, 05 Aug 2007 21:28:30 -0600
To: stdcxx-dev@incubator.apache.org
Subject: Re: [PATCH] for STDCXX-491 - string::push_back() slow

Looks like ezmlm stripped the grap attached to my previous post so
I attached it to the issue instead:

http://issues.apache.org/jira/secure/attachment/12363211/push_back.png

Martin

Martin Sebor wrote:

FWIW, I've benchmarked the latest push_back() against stdcxx 4.1.3
and a number of other implementations, including STLport 5.1.3. We
are faster than any other implementation except STLport, and close
to STLport in the general case. STLport has an advantage for short
strings (less than 16 characters), most likely because of the short
string optimization.

Martin

Martin Sebor wrote:

Farid Zaripov wrote:

-----Original Message-----
From: Martin Sebor [mailto:[EMAIL PROTECTED] On Behalf Of Martin
Sebor
Sent: Tuesday, July 24, 2007 7:40 AM
To: stdcxx-dev@incubator.apache.org
Subject: Re: [PATCH] for STDCXX-491 - string::push_back() slow

mark.g.brown wrote:

Hi all,

The attached simple patch speeds up push_back() nearly six times
relative to stdcxx 4.1.3 and makes it more than twice faster that
gcc's.

Let me test your patch for regressions and if it passes I'll commit
it tomorrow.

  I see the difference between the old push_back() behavior and after
this patch.
The append (size_type (1), __c); also appends terminating NULL
character
(string.cc, line 472). Below is the corrections to the patch:

Ah, yes, good catch!

On the subject of the terminating NUL, I wonder it would simplify
(and speed up) the implementation if we appended the terminating
NUL in c_str() instead in every modifying member function. We'd
still need to allocate enough memory for it because c_str() isn't
allowed to invalidate iterators, pointers, and references into
the object but we might be able to save ourselves a few CPU
cycles if we set data()[size()] to charT() only in c_str().

Hmmm, something to think about...

Martin

 template <class _CharT, class _Traits , class _Allocator>  inline
void basic_string<_CharT, _Traits, _Allocator>::
+push_back (value_type __c)
+{
+    const size_type __size = size () + 1;
+
+    if (   capacity () < __size
+        || size_type (1) < size_type (_C_pref ()->_C_get_ref ()))
+        append (1, __c);
+    else {
+        traits_type::assign (_C_data [size ()], __c);

                // append the terminating NUL character

traits_type::assign (_C_data [__size], value_type ());

+        _C_pref ()->_C_size._C_size = __size;
+    }
+}

Farid.