 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Joe
Guest
|
 Posted: Fri Jun 24, 2005 3:36 pm Post subject: Premature optimization or good sense? |
 |
|
Hi everyone,
Recently, I have seen several code snippets like the following:
while (some cond)
{
std::string a(anotherString);
<do something modifying a and doing something with it>
}
And I have been wondering about what happens in these cases. On the
one hand, the variable a is properly scoped and therefore can be
reasoned about quite nicely, but on the other hand, isn't the memory
use by 'a' reallocated each time through the loop? In other words,
wouldn't the following code snippet be more efficient?
std::string a;
while (some cond)
{
a.assign(anotherString);
<do something modifying a and doing something with it>
}
The idea here being that the memory is allocated for 'a' and reused
rather than having to deallocate and allocate another chunk of memory
for the string? Another possibility is that the compiler special cases
collections in loops so that the two are equivalent, but I am not so
sure that they (the compilers) are allowed to be that clever. What is
the consensus here? Is the second form more efficient? Is the scoping
benefits worth the price you pay regardless?
joe
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
 |
ThosRTanner
Guest
|
| Posted: Fri Jun 24, 2005 5:05 pm Post subject: Re: Premature optimization or good sense? |
|
|
Joe wrote:
| Quote: | Hi everyone,
Recently, I have seen several code snippets like the following:
while (some cond)
{
std::string a(anotherString);
do something modifying a and doing something with it
}
And I have been wondering about what happens in these cases. On the
one hand, the variable a is properly scoped and therefore can be
reasoned about quite nicely, but on the other hand, isn't the memory
use by 'a' reallocated each time through the loop? In other words,
wouldn't the following code snippet be more efficient?
std::string a;
while (some cond)
{
a.assign(anotherString);
do something modifying a and doing something with it
}
|
It rather depends on how string is implemented. It could be implemented
in such a way that assign works as
if (buff) free(buff)
buff = new (anotherString.length)
copy anotherString.data into buff
And construction of an empty string:
buff = none
And construction from a string:
buff = new (anotherString.length)
copy anotherString.data into buff
Your original code would be as follows:
while (cond) do
{
create new buff & copy
...
free(buff)
}
your new code would be as follows:
buff = none
while (cond) do
{
if buff then free(buff)
create new buff & copy
}
(eventually)
free(buff)
So your new more efficient code actually has an extra test every time
round the loop, so it will be slower.
| Quote: | The idea here being that the memory is allocated for 'a' and reused
rather than having to deallocate and allocate another chunk of memory
for the string? Another possibility is that the compiler special cases
collections in loops so that the two are equivalent, but I am not so
sure that they (the compilers) are allowed to be that clever. What is
the consensus here? Is the second form more efficient? Is the scoping
benefits worth the price you pay regardless?
|
I wouldn't do it unless you have evidence that you are wasting a lot of
time in there. There are all sorts of things the compiler is allowed to
do when optimising, and the chances are a really good one could hoist
the construction of an empty string out of the loop if it thought it
was worth while. (Actually, it could hoist the construction back inside
the loop if it spotted the string wasn't used outside the loop...)
Write the code clear and with minimal scopes. Do NOT optimise until you
have MEASURED the performance and determined it is wanting. Then you
may rearrange the code to optimise it, and don't be surprised if it
makes things worse unless you really understand the library. And don't
be surprised if a new version of the library ruins your optimisations.
Tom
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Victor Bazarov
Guest
|
| Posted: Sat Jun 25, 2005 1:22 am Post subject: Re: Premature optimization or good sense? |
|
|
Joe wrote:
| Quote: | Recently, I have seen several code snippets like the following:
while (some cond)
{
std::string a(anotherString);
do something modifying a and doing something with it
}
And I have been wondering about what happens in these cases. On the
one hand, the variable a is properly scoped and therefore can be
reasoned about quite nicely, but on the other hand, isn't the memory
use by 'a' reallocated each time through the loop?
|
Not necessarily. First, 'a' itself uses very little memory and second,
since it's automatic, the compiler can set aside the memory for it at
the beginning of the function scope.
| Quote: | In other words,
wouldn't the following code snippet be more efficient?
std::string a;
while (some cond)
{
a.assign(anotherString);
do something modifying a and doing something with it
}
The idea here being that the memory is allocated for 'a' and reused
rather than having to deallocate and allocate another chunk of memory
for the string?
|
Actually the chunk of memory for the object itself is negligible compared
to what may be needed to store the _contents_ of the string. Allocation
and freeing of the memory for the string contents is still happening when
you use 'assign', so the savings in this case are minimal (if any at all).
| Quote: | Another possibility is that the compiler special cases
collections in loops so that the two are equivalent, but I am not so
sure that they (the compilers) are allowed to be that clever. What is
the consensus here? Is the second form more efficient?
|
Theoretically, yes. Practically, no.
| Quote: | Is the scoping
benefits worth the price you pay regardless?
|
Yes, they are.
V
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Carlos Moreno
Guest
|
| Posted: Sat Jun 25, 2005 1:23 am Post subject: Re: Premature optimization or good sense? |
|
|
ThosRTanner wrote:
| Quote: | [...]
So your new more efficient code actually has an extra test every time
round the loop, so it will be slower.
|
*Beautiful* !!!!
The irony that often results from the obsession to make everything
(relevant or not) more efficient at the code level!!! *Love* it !!!!
(actually, I didn't follow too closely your analysis, and quite likely
is only valid for not-so-good string implementations or compilers; but
still, this sort of thing *does* happen, I'm sure more often than most
people believe)
Carlos
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Greg
Guest
|
| Posted: Sun Jun 26, 2005 2:07 pm Post subject: Re: Premature optimization or good sense? |
|
|
Joe wrote:
| Quote: | Hi everyone,
Recently, I have seen several code snippets like the following:
while (some cond)
{
std::string a(anotherString);
do something modifying a and doing something with it
}
And I have been wondering about what happens in these cases. On the
one hand, the variable a is properly scoped and therefore can be
reasoned about quite nicely, but on the other hand, isn't the memory
use by 'a' reallocated each time through the loop? In other words,
wouldn't the following code snippet be more efficient?
std::string a;
while (some cond)
{
a.assign(anotherString);
do something modifying a and doing something with it
}
|
The rule of thumb is to favor construction over assignment. Applying
that rule in this case would favor the first implementation over the
second.
Greg
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
kanze@gabi-soft.fr
Guest
|
| Posted: Mon Jun 27, 2005 11:31 am Post subject: Re: Premature optimization or good sense? |
|
|
Carlos Moreno wrote:
| Quote: | ThosRTanner wrote:
[...]
So your new more efficient code actually has an extra test
every time round the loop, so it will be slower.
*Beautiful* !!!!
The irony that often results from the obsession to make
everything (relevant or not) more efficient at the code
level!!! *Love* it !!!!
(actually, I didn't follow too closely your analysis, and
quite likely is only valid for not-so-good string
implementations or compilers; but still, this sort of thing
*does* happen, I'm sure more often than most people believe)
|
Actually, who cares about the analysis. I actually measured the
difference with g++ 3.something -- creating a new instance of
string was faster than reusing the old one. Of course, that's
with one particular implementation of std::string, in one
particular use. (I forget the exact details; I think I was
initializing the string with a return value from a function.)
In general, it's been my experience that people who think about
optimizations at this level write slower programs than those who
don't worry about it. I don't know why, but that's been my
experience. (Another thing from my experience: people who don't
worry about the performance issue tend to encapsulate better.
So when there is a performance problem, it can generally be
fixed with a local modification in the class concerned, rather
than by having to modify code everywhere.)
--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Joe
Guest
|
| Posted: Mon Jun 27, 2005 5:01 pm Post subject: Re: Premature optimization or good sense? |
|
|
It is as I suspected. One should code to the way that makes the most
sense and let the compiler do the optimizing. I haven't had
opportunity to actually benchmark this case, but I am surprised that it
is faster to nest the string than not. I can't imagine an
implementation that throws away the previous string on assignment, but
maybe I'm not too imaginative. lol
Thanks for your input.
joe
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
kanze@gabi-soft.fr
Guest
|
| Posted: Tue Jun 28, 2005 10:00 am Post subject: Re: Premature optimization or good sense? |
|
|
Joe wrote:
| Quote: | It is as I suspected. One should code to the way that makes
the most sense and let the compiler do the optimizing. I
haven't had opportunity to actually benchmark this case, but I
am surprised that it is faster to nest the string than not. I
can't imagine an implementation that throws away the previous
string on assignment, but maybe I'm not too imaginative.
|
Well, the G++ implementation uses reference counting and a
shared representation. And my tests constructed the new value
elsewhere, as a string, and in the end, constructed the new
string from a temporary. In that case, it's not surprising that
creating a new string is cheaper -- if you assign, you will
typically end up deleting the old representation, whereas the
constructor just sets the pointer and increments the reference
count.
If you assign/construct with a char const* each time, the
results might be different, but that doesn't sound like a very
realistic use to me.
If your implementation uses some form of the small string
optimization, and most of your strings a small, constructing a
new string each time will also probably be slightly faster.
As a general rule, in fact, assignment is more expensive than
construction, because it requires doing something with the
existing value, as well as creating the new value. The one
exception is if you are able to reuse parts of the old
representation in the new. This is rarely the case with a
sophisticated implementation.
--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
ThosRTanner
Guest
|
| Posted: Wed Jun 29, 2005 8:31 am Post subject: Re: Premature optimization or good sense? |
|
|
[email]kanze (AT) gabi-soft (DOT) fr[/email] wrote:
| Quote: | Actually, who cares about the analysis.
Well, not me. I was just pointing out that you really don't know. It is |
more important to choose good algorithms and use good coding practices
(minimise the scope of variables, that sort of thing), and then measure
the results.
| Quote: | I actually measured the
difference with g++ 3.something -- creating a new instance of
string was faster than reusing the old one. Of course, that's
with one particular implementation of std::string, in one
particular use. (I forget the exact details; I think I was
initializing the string with a return value from a function.)
I think there's some reason for believing initialisation to be faster |
than copying, but that might just be hot air, and / or dependant on the
class in question. It's certainly easier to follow.
| Quote: | In general, it's been my experience that people who think about
optimizations at this level write slower programs than those who
don't worry about it. I don't know why, but that's been my
experience. (Another thing from my experience: people who don't
worry about the performance issue tend to encapsulate better.
So when there is a performance problem, it can generally be
fixed with a local modification in the class concerned, rather
than by having to modify code everywhere.)
|
I can believe that latter bit. People who are chronically worried about
the expense of a function call (yes, they still exist) will indulge in
an astonishing amount of cut & paste and either pass 0 or at least 10
parameters to function calls. Trying to maintain the resulting mess is
an up-hill struggle.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Andrea Griffini
Guest
|
| Posted: Wed Jun 29, 2005 10:27 am Post subject: Re: Premature optimization or good sense? |
|
|
On 27 Jun 2005 13:01:55 -0400, "Joe" <jgreer (AT) nsisoftware (DOT) com> wrote:
| Quote: | I haven't had opportunity to actually benchmark this case, but I
am surprised that it is faster to nest the string than not.
|
I spent some time writing this inner loop
std::string s = "This is a beautiful string";
for (int i=0; i
{
std::string s2(s);
s2[10] = 'B';
result = s2;
}
and comparing it against the same with s2 being just assigned
with "assign" instead of being copy-constructed.
With VC++ 6 /Ox results were
4.95 sec with copy construction
3.50 sec with assign
With VC++ 2003 /Ox results were instead
3.64 sec with copy construction
0.78 sec with assign
With g++ 3.3.3 (cygwin special) -O2
202.531 with copy construction
202.829 with assign
As usual with C++, YMMV :-)
*IF* this is an hot spot in your code *AND* speed is important
*AND* you already think it's difficult to find a better
algorithm instead I'd say that some profiling of alternatives
(on the specific platform with real data) would be needed.
Depending on the compiler (and I would say also on the library
version, e.g. single/multi thread) difference can be important.
HTH
Andrea
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Christian Brock
Guest
|
| Posted: Wed Jun 29, 2005 7:06 pm Post subject: Re: Premature optimization or good sense? |
|
|
<kanze (AT) gabi-soft (DOT) fr> wrote:
news:1119864591.970684.204910 (AT) g14g2000cwa (DOT) googlegroups.com...
| Quote: | Carlos Moreno wrote:
ThosRTanner wrote:
[...]
So your new more efficient code actually has an extra test
every time round the loop, so it will be slower.
*Beautiful* !!!!
The irony that often results from the obsession to make
everything (relevant or not) more efficient at the code
level!!! *Love* it !!!!
(actually, I didn't follow too closely your analysis, and
quite likely is only valid for not-so-good string
implementations or compilers; but still, this sort of thing
*does* happen, I'm sure more often than most people believe)
Actually, who cares about the analysis. I actually measured the
difference with g++ 3.something -- creating a new instance of
string was faster than reusing the old one. Of course, that's
with one particular implementation of std::string, in one
particular use. (I forget the exact details; I think I was
initializing the string with a return value from a function.)
|
Hi everybody, I did some profiling myself and got different:
<CODE>
#include <string>
#include <ctime>
#include <iostream>
int main()
{
const std::clock_t start = std::clock();
// case A (code version 2)
// std::string a;
for(unsigned i=0; i<1000000; ++i)
{
// case B (code version 1)
std::string a;
a.assign(std::rand() % 512, 'x');
}
std::cout << std::clock() - start << 'n';
return 0;
}
My results are:
- g++ 3.4.4 (cygwin) (option -O3)
case A: ~1300
case B: ~4500
- VC7 (Release)
case A: ~150
case B: ~500
This tells me that the second code version (case A) is faster.
The advantage of A is that memory is only allocated if the string grows
above its capacity.
Even if it's "*Beautiful* !!!!" I does not have to be true!!!
-- Christian.Brock (please don't reply)
| Quote: |
In general, it's been my experience that people who think about
optimizations at this level write slower programs than those who
don't worry about it. I don't know why, but that's been my
experience. (Another thing from my experience: people who don't
worry about the performance issue tend to encapsulate better.
So when there is a performance problem, it can generally be
fixed with a local modification in the class concerned, rather
than by having to modify code everywhere.)
--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
|
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Carl Barron
Guest
|
| Posted: Thu Jun 30, 2005 9:42 am Post subject: Re: Premature optimization or good sense? |
|
|
In article <gdg3c1td61655vvjrjlgmluut0ibl8mpk7 (AT) 4ax (DOT) com>, Andrea
Griffini <agriff (AT) tin (DOT) it> wrote:
| Quote: |
Depending on the compiler (and I would say also on the library
version, e.g. single/multi thread) difference can be important.
|
My results [0S X 3,9 Metrowerks 9,4] the results of the random
sized less than 512 byte strings of 'x's its 4 to 1 in favor of
string::assign, with 10K strings its 2 to 1 in favor or string::assign,
Seems the gain is related to size of the string, but not in terms of
whether the compiler optimizes or not, Optimization is faster but
not by much.
Anyway on this machine,compiler combination string::assign is at least
as fast as construction in a loop. But all this is compiler/machine
dependent I'd suspect. [no altvec or similiar feature used] .
Premature optimization or not it seems to me that string::assign should
be at least as fast as construction. Its similar to the ++x vs x++
debate x++ is at best the same as ++x, often times slower.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
kanze@gabi-soft.fr
Guest
|
| Posted: Thu Jun 30, 2005 11:06 am Post subject: Re: Premature optimization or good sense? |
|
|
Christian Brock wrote:
| Quote: | kanze (AT) gabi-soft (DOT) fr> wrote:
news:1119864591.970684.204910 (AT) g14g2000cwa (DOT) googlegroups.com...
Carlos Moreno wrote:
ThosRTanner wrote:
[...]
So your new more efficient code actually has an extra test
every time round the loop, so it will be slower.
*Beautiful* !!!!
The irony that often results from the obsession to make
everything (relevant or not) more efficient at the code
level!!! *Love* it !!!!
(actually, I didn't follow too closely your analysis, and
quite likely is only valid for not-so-good string
implementations or compilers; but still, this sort of thing
*does* happen, I'm sure more often than most people
believe)
Actually, who cares about the analysis. I actually measured
the difference with g++ 3.something -- creating a new
instance of string was faster than reusing the old one. Of
course, that's with one particular implementation of
std::string, in one particular use. (I forget the exact
details; I think I was initializing the string with a return
value from a function.)
Hi everybody, I did some profiling myself and got different:
|
If you measure different things, your results are likely to be
different.
| Quote: | CODE
#include
#include
#include
int main()
{
const std::clock_t start = std::clock();
// case A (code version 2)
// std::string a;
for(unsigned i=0; i<1000000; ++i)
{
// case B (code version 1)
std::string a;
a.assign(std::rand() % 512, 'x');
}
std::cout << std::clock() - start << 'n';
return 0;
}
/ENDCODE
My results are:
- g++ 3.4.4 (cygwin) (option -O3)
case A: ~1300
case B: ~4500
- VC7 (Release)
case A: ~150
case B: ~500
This tells me that the second code version (case A) is faster.
The advantage of A is that memory is only allocated if the
string grows above its capacity.
|
Necessarily an advantage only if you are building the new string
immediately in place in the loop, from non-strings. My
benchmarks generated the new string in a separate function
(which would pratically always be the case in real code --
although in my benchmark, it actually returned a copy of an
existing string); my measurements showed that for one particular
implementation (g++ 3.4.3), copy constructing a string with the
results of a function is significantly faster than assigning it
to an existing string.
In sum, I tried to measure something vaguely similar to what
might be done in real code. Obviously, it's not exactly the
same, and your results for real code may be different as well.
| Quote: | Even if it's "*Beautiful* !!!!" I does not have to be true!!!
|
I'm not sure what this is supposed to mean. You can make no
initial assumptions about the performance, so why try. Write
things correctly, then profile.
--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
