Re: std::string and std::ostringstream performances
"Bala" <R.Balaji.Iyer@gmail.com> wrote in message
news:1193955553.826123.196060@19g2000hsx.googlegroups.com...
On Nov 1, 5:37 pm, "Jim Langston" <tazmas...@rocketmail.com> wrote:
"Erik Wikstr?m" <Erik-wikst...@telia.com> wrote in message
news:durWi.12684$ZA.8173@newsb.telia.net...
On 2007-11-01 21:53, Jim Langston wrote:
"James Kanze" <james.ka...@gmail.com> wrote in message
news:1193911545.733761.171970@50g2000hsm.googlegroups.com...
On Oct 31, 10:55 pm, Erik Wikstr? <Erik-wikst...@telia.com> wrote:
[...]
I do not know, and I do not think the standard says anything
about it. But a good implementation will probably use a
resizing scheme similar to the one used for vectors, such as
(at least) doubling the capacity every time it resizes.
Doubling is actually not a very good strategy; multiplying by
say 1.5 is considerably better. (As a general rule, the
multiplier should be less that (1+sqrt(5))/2---about 1.6. 1.5
is close enough, and easy to calculate.) In memory tight
situations, of course, the multiplier should be even smaller.
The original STL implementation did use 2, and I suspect that
many implementations still do, even though we now know that it
isn't such a good idea.
=====
I deciced to test my implementation so I wrote this:
#include <iostream>
#include <string>
int main()
{
std::string Foo;
std::string::size_type LastCapacity = Foo.capacity();
std::cout << "Initial Capacity:" << LastCapacity << "\n";
for ( int i = 0; i < 100; ++i )
{
Foo += "x";
if ( Foo.capacity() != LastCapacity )
{
std::cout << "Size:" << Foo.size() << " " << "Capacity:" <<
Foo.capacity() << "\n";
LastCapacity = Foo.capacity();
}
}
}
The output for my system is:
Initial Capacity:15
Size:16 Capacity:31
Size:32 Capacity:47
Size:48 Capacity:70
Size:71 Capacity:105
So as we can see, on my system if I did not initially .reserve() and
added 1
character at a time then I would wind up with 4 extra memory
reallocations.
And for those too lazy to do the math themselves the numbers means that
the capacity is multiplied by 1.5 on each resize.
To James Kanze: I too would be interested in hearing about the source of
the "less than 1.6 multiplication" rule. I have tried to google for it
but I do not even know about where to start.
It was explained to me once. Consider a string with an initial capacity
of
100. There are 100 bytes of memory allocated. Then if you double it,
there
is a hole in the first 100 bytes, and the next 200 bytes are allocated.
Now
you double it again to 400. 100 is not enough so it can't use the hole,
so
it allocates 400 bytes,leaving a 300 byte hole. Double again, 800, 300 is
not enough, it allcoates 800, leaving a 700 byte hole. As we can see, it
can never reuse the memory from the previous allocations since they have
to
be continguous.
So that's where the 1.6 comes in. That with future allocations eventually
the system will be able to reuse previous memory allocated for the
string.- Hide quoted text -
- Show quoted text -
I wrote a similar test application on Solaris 10 Sparc with g++3.4.3.
It clearly shows, that the reserve thing is surely going to help my
performance.
Thanks a ton for your inputs. Will let you know once the test is
successful.
I started appending 2 characters a time in a loop of 10.
This is the output without reserve
Start With :0
Current Size:2 Current Capacity:2
Current Size:4 Current Capacity:4
Current Size:6 Current Capacity:6
Current Size:8 Current Capacity:8
Current Size:10 Current Capacity:10
Current Size:12 Current Capacity:12
Current Size:14 Current Capacity:14
Current Size:16 Current Capacity:16
Current Size:18 Current Capacity:18
Current Size:20 Current Capacity:20
This is the output with reserve of 20
Start With :20
Thanks,
Bala
======================
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.
That, in my opionion, is a very bad implementation of std::string.