Mailing-List: contact stdcxx-dev-help@incubator.apache.org; run by ezmlm
Precedence: bulk
Reply-To: stdcxx-dev@incubator.apache.org
Received-SPF: pass (athena.apache.org: local policy)
Message-ID: <46B89132.3020503@roguewave.com>
Date: Tue, 07 Aug 2007 09:35:14 -0600
From: Martin Sebor <sebor@roguewave.com>
Organization: Rogue Wave Software
User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US;
 rv:1.8.1.2) Gecko/20070221 SeaMonkey/1.1.1
MIME-Version: 1.0
To: stdcxx-dev@incubator.apache.org
Subject: Re: [PATCH] for STDCXX-491 - string::push_back() slow
References: <7bdb2168beaef14c98f1901fd2de6438b0127d@epmsa009.minsk.epam.com>
  <46b69223.5040707@roguewave.com> <46a582a2.5080501@roguewave.com>
  <46a3d4bf.8010209@gmail.com> <46a639d5.7050305@roguewave.com>
 <6779DB5F1F2.0000073Bmbrown@inbox.com>
In-Reply-To: <6779DB5F1F2.0000073Bmbrown@inbox.com>
Content-Type: multipart/mixed;
 boundary="------------020302070005080301080508"

--------------020302070005080301080508
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

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: sebor@roguewave.com
>> 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:msebor@gmail.com] 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.
>>>>


--------------020302070005080301080508--