std::string and std::ostringstream performances

[Guest]

Sounds like something Knuth would have noticed, but I can't find it in
TAoCP. Recognising its Knuthiness and the use of the golden ratio, it
looks like a Fibonacci thing:

+-+
|X|
+-+

+---+-+
|X X| |
+---+-+

+-----+
|X X X|
+-----+

+---------+-----+
|X X X X X| |
+---------+-----+

+---------------+
|X X X X X X X X|
+---------------+

+-------------------------+---------------+
|X X X X X X X X X X X X X |
+-------------------------+---------------+

+-----------------------------------------+
|X X X X X X X X X X X X X X X X X X X X X|
+-----------------------------------------+

This seems like a good idea if you can use a smart implementation of
realloc. I have never written any allocators so I do not know much about
it but it was my belief that most implementations of realloc simply
looked to see if there was enough extra space "in front" to satisfy the
request (so that no data have to be copied), but I suppose there might
be some implementations that looks "behind" also.

However would that work in a C++ collection where the elements have to
be copy-constructed and simple copying wont work. It was my belief that
the container must first allocate the new memory, copy-construct the old
elements, add the new, and first then can it get rid of the old
allocation. To support a scheme like above the container must assume
that the two allocations overlap but to my knowledge the C++ allocators
can not allocate overlapping memory areas.

Perhaps another use for the ~ 1.6 ratio is to avoid unnecessary wasted
space in the form of over allocation?

 

[Bala]

This seems like a good idea if you can use a smart implementation of
realloc. I have never written any allocators so I do not know much about
it but it was my belief that most implementations of realloc simply
looked to see if there was enough extra space "in front" to satisfy the
request (so that no data have to be copied), but I suppose there might
be some implementations that looks "behind" also.

However would that work in a C++ collection where the elements have to
be copy-constructed and simple copying wont work. It was my belief that
the container must first allocate the new memory, copy-construct the old
elements, add the new, and first then can it get rid of the old
allocation. To support a scheme like above the container must assume
that the two allocations overlap but to my knowledge the C++ allocators
can not allocate overlapping memory areas.

Perhaps another use for the ~ 1.6 ratio is to avoid unnecessary wasted
space in the form of over allocation?

Another observation i found when i was browsing through the
std::string class is that probably i should be using append instead of
a +=. I have a strong feeling there could be benefit of maybe append
using a reference whereas += creating a local variable and then using
it.
Any comments on this front?

 

[Guest]

Please do not quote signature.

Another observation i found when i was browsing through the
std::string class is that probably i should be using append instead of
a +=. I have a strong feeling there could be benefit of maybe append
using a reference whereas += creating a local variable and then using
it.
Any comments on this front?

It depends, for concatenating two strings they should be equal in
performance, but if you add string literals, C strings, or just a char
then append is probably faster.

 

[Bala]

Please do not quote signature.


It depends, for concatenating two strings they should be equal in
performance, but if you add string literals, C strings, or just a char
then append is probably faster.

Yeah, most of the data that i append are one of the following.
1. String literals
2. C style arrays.
3. Chars.

So i think, i should change the code to use append instead and then
again check the performance.

 

[Guest]

Please do not quote signature.


It depends, for concatenating two strings they should be equal in
performance, but if you add string literals, C strings, or just a char
then append is probably faster.

Actually, I think that on a good implementation there should be no
difference in performance between += and append(). To see whether you
can gain anything by using append() instead of += you have to measure.

 

[Bala]

Actually, I think that on a good implementation there should be no
difference in performance between += and append(). To see whether you
can gain anything by using append() instead of += you have to measure.

True.. Thats what im planning to do next. Because the documentation
doesnt specify much in terms of which performs better in which
scenarios. The best way to get an answer is as u said.. measure

 

[red floyd]

[redacted]

This seems like a good idea if you can use a smart implementation of

realloc. I have never written any allocators so I do not know much about
it but it was my belief that most implementations of realloc simply
looked to see if there was enough extra space "in front" to satisfy the
request (so that no data have to be copied), but I suppose there might
be some implementations that looks "behind" also.

Many years ago, I implemented a Fibonacci buddy system allocator, based
on an algorithm published in JACM in June 1975: "A simplified
recombination scheme for the Fibonacci buddy system".


Overhead was 2 bits + block size indicator per allocated block (wound up
being 1 byte total).

 

[Roland Pibinger]

OUCH! No wonder you are having performance issues! Your platform isn't
preallocating ANY extra space! This means every time you add a character it
has to reallocate memory. Very bad. Yes, in your case .reserve() should
help TREMENDOUSLY.

When you extensively use std::string you start programming against an
implementation, not an iterface.

That, in my opionion, is a very bad implementation of std::string.

Have you looked at the Microsoft/Dinkumware implementation?

 

[Jim Langston]

When you extensively use std::string you start programming against an
implementation, not an iterface.


Have you looked at the Microsoft/Dinkumware implementation?

I am using Microsoft Visual C++ .net 2005.

Mine is doing the 1.6 allocation. This is better than this one by far.