 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Allan Odgaard
Guest
|
 Posted: Fri Jan 16, 2004 1:17 pm Post subject: Const reference worse than a copy (passing by value)? |
 |
|
I noticed that in my implementation (gcc 3.3/Mac OS X) std::copy is
implemented as a chain of functions, each use traits and argument
overloading to specialize the implementation, similar to the following
(simplified to illustrate point -- does not compile!):
_OutIter copy (_Iter f, _Iter l, _OutIter out)
{
return help_copy(f, l, out, is_simple_iter<_Iter>::value);
}
_OutIter help_copy (_Iter f, _Iter l, _OutIter out, true_type)
{
return pod_copy(f, l, out, is_simple_iter<_OutIter>::value);
}
_OutIter help_copy (_Iter f, _Iter l, _OutIter out, false_type)
{
return class_copy(f, l, out, is_simple_iter<_OutIter>::value);
}
In the real implementation there are five functions in this chain --
what puzzled me was, that the iterator arguments are declared to be
by-value.
This means that the iterators will be copied five times (and I
checked, they are, even with full optimizations).
I only know of two reasons for why not to prefer const reference, one
being the penalty related to accessing the value (and not being able
to cache it w/o full alias analysis), and the other being that there
is no need for alias analysis with by-value, which may allow for more
aggressive optimization.
But I do not see this as relevant in the intermediate helper
functions, which just call another function, each passing its own
arguments verbatim to the next.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
 |
Dhruv
Guest
|
| Posted: Sat Jan 17, 2004 3:22 am Post subject: Re: Const reference worse than a copy (passing by value)? |
|
|
On Fri, 16 Jan 2004 08:17:29 -0500, Allan Odgaard wrote:
[...]
| Quote: | In the real implementation there are five functions in this chain --
what puzzled me was, that the iterator arguments are declared to be
by-value.
This means that the iterators will be copied five times (and I
checked, they are, even with full optimizations).
I only know of two reasons for why not to prefer const reference, one
being the penalty related to accessing the value (and not being able
to cache it w/o full alias analysis), and the other being that there
is no need for alias analysis with by-value, which may allow for more
aggressive optimization.
|
Basically, in loopy functions such as copy, find, for_each, the value of
an iterator is queried and the iterator is incremented/decremented very
frequently. So, if you pass the iterator by reference, the cache locality
may get disturbed badly. Also, const reference can not be used because
then, the iterators' dereferenced value may not be passed to functors that
take non-const references. (Usually, the operator*() for the iterators is
not a const member) Also, pass by reference may not be used because
then, the code such as this will become invalid:
find (v.begin(), v.end(), Some_Value);
Also, generally iterators for vector/list are small, and fit into a
hardware register, so with optimizations, and if the compiler is ready to
change the function calling convention partially, or for inlines, it may
optimize away the passing altogether. However, for map/multimap/deque the
iterators are quite large. Do sizeof on the iterator to find out the size
of the iterators on your implementation. After all, iterators are
implementation defined entities.
| Quote: | But I do not see this as relevant in the intermediate helper
functions, which just call another function, each passing its own
arguments verbatim to the next.
|
I haven't quite followed you here. Please could you elaborate.
Regards,
-Dhruv.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Geno Rice
Guest
|
| Posted: Sat Jan 17, 2004 11:02 am Post subject: Re: Const reference worse than a copy (passing by value)? |
|
|
Allan Odgaard wrote:
| Quote: | I noticed that in my implementation (gcc 3.3/Mac OS X) std::copy is
implemented as a chain of functions, each use traits and argument
overloading to specialize the implementation, similar to the following
(simplified to illustrate point -- does not compile!):
_OutIter copy (_Iter f, _Iter l, _OutIter out)
{
return help_copy(f, l, out, is_simple_iter<_Iter>::value);
}
_OutIter help_copy (_Iter f, _Iter l, _OutIter out, true_type)
{
return pod_copy(f, l, out, is_simple_iter<_OutIter>::value);
}
_OutIter help_copy (_Iter f, _Iter l, _OutIter out, false_type)
{
return class_copy(f, l, out, is_simple_iter<_OutIter>::value);
}
In the real implementation there are five functions in this chain --
what puzzled me was, that the iterator arguments are declared to be
by-value.
This means that the iterators will be copied five times (and I
checked, they are, even with full optimizations).
I only know of two reasons for why not to prefer const reference, one
being the penalty related to accessing the value (and not being able
to cache it w/o full alias analysis), and the other being that there
is no need for alias analysis with by-value, which may allow for more
aggressive optimization.
But I do not see this as relevant in the intermediate helper
functions, which just call another function, each passing its own
arguments verbatim to the next.
|
Perhaps they don't bother to pass references because passing
an iterator, which, after all, is just a pointer, is the same (at
the assembly code level) as passing a reference, which itself is just a pointer.
What surprises me is that the implementation uses 5 nested function
calls. Doesn't that screw up code cache locality, branch prediction, etc?
Are you sure these don't get turned into inlines, and then get
optimized away?
Geno Rice
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Ivan Vecerina
Guest
|
| Posted: Sat Jan 17, 2004 11:08 am Post subject: Re: Const reference worse than a copy (passing by value)? |
|
|
"Allan Odgaard" <Duff (AT) DIKU (DOT) DK> wrote
| Quote: | I noticed that in my implementation (gcc 3.3/Mac OS X) std::copy is
implemented as a chain of functions, each use traits and argument
overloading to specialize the implementation, similar to the following
(simplified to illustrate point -- does not compile!):
....
This means that the iterators will be copied five times (and I
checked, they are, even with full optimizations).
I would hope that, once the helper-functions are inlined (as they should), |
the intermediate iterator copies are optimized out...
| Quote: | I only know of two reasons for why not to prefer const reference, one
being the penalty related to accessing the value (and not being able
to cache it w/o full alias analysis), and the other being that there
is no need for alias analysis with by-value, which may allow for more
aggressive optimization.
I see other reasons: |
- readability (author didn't bother, wanted to rely on the compiler)
- the standard does define std::copy and other algorithms as taking
their iterator arguments by value. Using a const-reference instead
could create portability issues (e.g. if using function pointers).
And of course, by-const-ref is pointless if the function wants to
modify its (local) arguments.
| Quote: | But I do not see this as relevant in the intermediate helper
functions, which just call another function, each passing its own
arguments verbatim to the next.
I would guess that intermediate functions that are not visible to |
the user could use const-references. But this might be unnecessarily
complicated.
I would rather expect that a decent compiler would optimize out, as
allowed by the standard, the unnecessary parameter copies in all
inlined functions.
Regards,
Ivan
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- e-mail contact form
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Allan Odgaard
Guest
|
| Posted: Sat Jan 17, 2004 11:09 am Post subject: Re: Const reference worse than a copy (passing by value)? |
|
|
"Dhruv" <dhruvbird (AT) gmx (DOT) net> wrote
| Quote: | Basically, in loopy functions such as copy, find, for_each, the value of
an iterator is queried and the iterator is incremented/decremented very
frequently. So, if you pass the iterator by reference, the cache locality
may get disturbed badly.
|
I doubt locality of reference plays any role here -- the iterator is
most likely to be found on the calling functions stack-frame. I do not
see a reason why moving it 32 bytes or so should make a difference in
performance (with an associative cache).
However, this is not related to my letter, as I was not talking about
mutating values passed by non-const reference.
| Quote: | Also, const reference can not be used because
then, the iterators' dereferenced value may not be passed to functors that
take non-const references. (Usually, the operator*() for the iterators is
not a const member)
|
Yes, assuming the calling function wants to mutate the value (w/o
making a copy), then it cannot take it by const-reference, but I do
not think this was implied in my letter -- also, the end iterator is
rarely used for anything other than as an argument to
iterator::operator!=, which anyway take it as const reference, so why
not always pass this as const reference to the "algorithm"?
| Quote: | Also, pass by reference may not be used because
then, the code such as this will become invalid:
find (v.begin(), v.end(), Some_Value);
|
That would only be invalid if you assume that find wants to call
non-const member functions on the iterators. It may make a copy of the
first iterator or take that by-value and still take the end iterator
by const reference.
| Quote: | Also, generally iterators for vector/list are small, and fit into a
hardware register, so with optimizations, and if the compiler is ready to
change the function calling convention partially, or for inlines, it may
optimize away the passing altogether.
|
But why should we rely on all these factors (which often do not hold),
when we can explicitly avoid the extra copy by using const reference?
i.e. I was interested in the downside of const reference, and I listed
two myself, which I did not see apply to the case I was speaking about
(std::copy), and would be interested if there are other hidden "costs"
of const reference.
btw: iterators are often not just a memory copy, it will need to
invoke the copy-constructor (and destructor when done).
| Quote: | But I do not see this as relevant in the intermediate helper
functions, which just call another function, each passing its own
arguments verbatim to the next.
I haven't quite followed you here. Please could you elaborate.
|
I am afraid this applies to my entire letter ;)
As explained in the beginning of my previous letter, std::copy (for
gcc) is in essence implemented like this:
OutIter copy (Iter f, Iter l, OutIter o)
{ return copy_1(f, l, o, xyz); }
OutIter copy_1 (Iter f, Iter l, OutIter o, magic)
{ return copy_2(f, l, o, xyz); }
OutIter copy_2 (Iter f, Iter l, OutIter o, magic)
{ return copy_3(f, l, o, xyz); }
OutIter copy_3 (Iter f, Iter l, OutIter o, magic)
{ return copy_4(f, l, o, xyz); }
OutIter copy_4 (Iter f, Iter l, OutIter o, magic)
{ /* do actual copy */ }
Here 'xyz' and 'magic' are standins for some traits stuff which
resolve various properties of the iterators passed in, to specialize
the copy (and thus make it more effective).
So calling std::copy will go through a chain of five functions, before
it arrives at the proper one, and for each step in this chain, it will
invoke the copy constructor for the iterators, since these are passed
by-value.
As I see it, there is no reason to not make the arguments a const
reference in all but the last function, and in the last function the
end iterator could still be by const reference, sinec it is probably
only used as rhs argument to operator!=.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
John Potter
Guest
|
| Posted: Sun Jan 18, 2004 1:24 am Post subject: Re: Const reference worse than a copy (passing by value)? |
|
|
On 16 Jan 2004 08:17:29 -0500, [email]Duff (AT) DIKU (DOT) DK[/email] (Allan Odgaard) wrote:
| Quote: | I noticed that in my implementation (gcc 3.3/Mac OS X) std::copy is
implemented as a chain of functions, each use traits and argument
overloading to specialize the implementation,
In the real implementation there are five functions in this chain --
what puzzled me was, that the iterator arguments are declared to be
by-value.
This means that the iterators will be copied five times (and I
checked, they are, even with full optimizations).
|
I don't know what you are using. I tried -S and got five calls, but
-O -S inlined the whole mess and called memmove directly.
Maybe you should post your code.
John
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Allan Odgaard
Guest
|
| Posted: Sun Jan 18, 2004 11:20 am Post subject: Re: Const reference worse than a copy (passing by value)? |
|
|
Geno Rice <geno (AT) monmouth (DOT) com> wrote
| Quote: | This means that the iterators will be copied five times (and I
checked, they are, even with full optimizations).
Perhaps they don't bother to pass references because passing
an iterator, which, after all, is just a pointer, is the same (at
the assembly code level) as passing a reference, which itself is just a pointer.
|
For std::vector and std::string, the normal iterator *could* be a
pointer, but it generally isn't.
| Quote: | What surprises me is that the implementation uses 5 nested function
calls. Doesn't that screw up code cache locality, branch prediction, etc?
Are you sure these don't get turned into inlines, and then get
optimized away?
|
They most likely will be inline, but the iterators are still being
copied. As stated, I did test this!
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Allan Odgaard
Guest
|
| Posted: Sun Jan 18, 2004 11:25 am Post subject: Re: Const reference worse than a copy (passing by value)? |
|
|
John Potter <jpotter (AT) falcon (DOT) lhup.edu> wrote
| Quote: | This means that the iterators will be copied five times (and I
checked, they are, even with full optimizations).
I don't know what you are using. I tried -S and got five calls, but
-O -S inlined the whole mess and called memmove directly.
|
Probably the optimizer is better at removing redundant temporaries
when they are POD. I was using non-POD iterators.
| Quote: | Maybe you should post your code.
|
The code is dependent on other things, but here's a minimal slip of
code to illustrate it:
struct count_iterator : public std::iterator<std::input_iterator_tag,
int, size_t, int*, int&>
{
typedef count_iterator self;
static int copy_count;
int value;
count_iterator (int i) : value(i)
{ }
count_iterator (self const& rhs) : value(rhs.value)
{ ++copy_count; }
self& operator= (self const& rhs)
{ ++copy_count; value = rhs.value; return *this; }
int& operator* ()
{ return value; }
self& operator++ ()
{ ++value; return *this; }
bool operator== (self const& rhs) const
{ return value == rhs.value; }
bool operator!= (self const& rhs) const
{ return value != rhs.value; }
};
Doing:
std::vector<int> v;
std::copy<count_iterator>(5, 15, back_inserter(v));
printf("%dn", count_iterator::copy_count);
Will output 8, i.e. 4 copies pr. iterator. This is *with*
optimizations.
--
Private Mails To: Allan At Top-House Dot DK
http://www.top-house.dk/~aae0030/
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
John Potter
Guest
|
| Posted: Mon Jan 19, 2004 12:28 am Post subject: Re: Const reference worse than a copy (passing by value)? |
|
|
On 18 Jan 2004 06:25:37 -0500, [email]Duff (AT) DIKU (DOT) DK[/email] (Allan Odgaard) wrote:
| Quote: | John Potter <jpotter (AT) falcon (DOT) lhup.edu> wrote
|
| Quote: | This means that the iterators will be copied five times (and I
checked, they are, even with full optimizations).
I don't know what you are using. I tried -S and got five calls, but
-O -S inlined the whole mess and called memmove directly.
Probably the optimizer is better at removing redundant temporaries
when they are POD. I was using non-POD iterators.
Maybe you should post your code.
The code is dependent on other things, but here's a minimal slip of
code to illustrate it:
|
Yes. It illustrates that you need to trust your compiler.
| Quote: | std::vector<int> v;
std::copy<count_iterator>(5, 15, back_inserter(v));
printf("%dn", count_iterator::copy_count);
Will output 8, i.e. 4 copies pr. iterator. This is *with*
optimizations.
|
Yep. Now look at the assembler code. That 8 is observable
behavior. It optimized out all of the calls to the copy
ctor and just added 8 to the static int. Beautiful use of
the as-if rule. Because each function call introduces a
new variable, there are no temporaries to remove using the
special rules in 12.8/15. However, it is allowed to not
make the calls and copies if it can fool you into thinking
that it did.
A good magician whose slight of code is faster than printf.
Remove the instrumentation and save the compiler the time
needed to fool you.
John
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Allan Odgaard
Guest
|
| Posted: Mon Jan 19, 2004 5:26 pm Post subject: Re: Const reference worse than a copy (passing by value)? |
|
|
John Potter <jpotter (AT) falcon (DOT) lhup.edu> wrote
| Quote: | The code is dependent on other things, but here's a minimal slip of
code to illustrate it [...]
Yes. It illustrates that you need to trust your compiler.
|
I would think that it illustrates that the compiler will not optimize
away the copying of iterators. It will inline the copy-constructor and
then fold the four repeated increments into a single add, and thus my
example may have been bad at illustrating that there is a price
connected with copying the iterators, but it is done, nonetheless,
hence my original question about why not to prefer const reference
over passing by value (even though the compiler will often be able
optimize the code so that the copy is virtually free -- but there are
exceptions, which there AFAIK is not with const reference).
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Tom
Guest
|
| Posted: Tue Jan 20, 2004 11:09 am Post subject: Re: Const reference worse than a copy (passing by value)? |
|
|
[email]Duff (AT) DIKU (DOT) DK[/email] (Allan Odgaard) wrote:
| Quote: | Geno Rice <geno (AT) monmouth (DOT) com> wrote:
This means that the iterators will be copied five times (and I
checked, they are, even with full optimizations).
Perhaps they don't bother to pass references because passing
an iterator, which, after all, is just a pointer, is the same (at
the assembly code level) as passing a reference, which itself is just a
pointer.
For std::vector and std::string, the normal iterator *could* be a
pointer, but it generally isn't.
|
Although an iterator for std::vector and std::string may or may not be
an ordinary pointer, for a non-debug implementation, size_of such
iterators should be the same as an ordinary pointer, which I think is
what Geno Rice meant. In other words, copying is no more expensive
than passing by reference for such iterators.
Best regards,
Tom
[ 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: Wed Jan 21, 2004 3:48 pm Post subject: Re: Const reference worse than a copy (passing by value)? |
|
|
[email]Thomas8675309 (AT) yahoo (DOT) com[/email] (Tom) wrote in message
news:<7b68d58f.0401190748.57963b03 (AT) posting (DOT) google.com>...
| Quote: | Duff (AT) DIKU (DOT) DK (Allan Odgaard) wrote:
Geno Rice <geno (AT) monmouth (DOT) com> wrote:
This means that the iterators will be copied five times (and
I checked, they are, even with full optimizations).
Perhaps they don't bother to pass references because passing an
iterator, which, after all, is just a pointer, is the same (at
the assembly code level) as passing a reference, which itself is
just a pointer.
For std::vector and std::string, the normal iterator *could* be a
pointer, but it generally isn't.
Although an iterator for std::vector and std::string may or may not be
an ordinary pointer, for a non-debug implementation, size_of such
iterators should be the same as an ordinary pointer, which I think is
what Geno Rice meant. In other words, copying is no more expensive
than passing by reference for such iterators.
|
This depends very much on the compiler. With the compilers I use, a
pointer or an int is passed in a register, whereas, regardless of the
size, a class is passed as a temporary in memory.
More important than performance, however, is perhaps the semantics. In
many cases, the algorthme modifies one or more of the iterators passed
in the algorithm. And the semantics of all of the algorithms is that
the iterator in the calling function is NOT modified. So there must be
a copy somewhere.
Also, one of the key elements of the two iterator idiom is that you do
copy iterators. You search a first element, save the iterator, then
search a second, to define a sub-interval, for example. The entire STL
is based on the premise that iterators, items in collections and
functional objects are copiable at a reasonable price. (What reasonable
means, of course, depends on the application.)
--
James Kanze GABI Software mailto:kanze (AT) gabi-soft (DOT) fr
Conseils en informatique orientée objet/ http://www.gabi-soft.fr
Beratung in objektorientierter Datenverarbeitung
11 rue de Rambouillet, 78460 Chevreuse, France, +33 (0)1 30 23 45 16
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Tom
Guest
|
| Posted: Thu Jan 22, 2004 9:00 am Post subject: Re: Const reference worse than a copy (passing by value)? |
|
|
[email]kanze (AT) gabi-soft (DOT) fr[/email] wrote:
| Quote: | Although an iterator for std::vector and std::string may or may not be
an ordinary pointer, for a non-debug implementation, size_of such
iterators should be the same as an ordinary pointer, which I think is
what Geno Rice meant. In other words, copying is no more expensive
than passing by reference for such iterators.
This depends very much on the compiler. With the compilers I use, a
pointer or an int is passed in a register, whereas, regardless of the
size, a class is passed as a temporary in memory.
|
You are certainly correct that I should have acknowledged that this is
an implementation detail. Still, I'm curious. Which compilers do you
use? If I understand you correctly, on your compilers, passing struct
{ int* p; } by value is more expensive than passing a simple int* by
value. That suggests that the Stepanov abstraction penalty must be
significant, so that for time-critical operations, there is a
disincentive to using the STL. If you have a few spare moments, I
would be interested in the results of running Stepanov's benchmark
tests on your compiler. (If you don't have a copy of the Stepanov
tests, you can find a version on Scott Ladd's website at
http://www.coyotegulch.com/reviews/intel_comp/icc_gcc_benchmarks.tar.gz
)
For comparison purposes, gcc 3.3.1's Stepanov abstraction penalty is
less than 10% with full optimizations, and you probably know of other
compilers that do even better.
| Quote: | More important than performance, however, is perhaps the semantics. In
many cases, the algorthme modifies one or more of the iterators passed
in the algorithm. And the semantics of all of the algorithms is that
the iterator in the calling function is NOT modified. So there must be
a copy somewhere.
|
Agreed.
| Quote: | The entire STL
is based on the premise that iterators, items in collections and
functional objects are copiable at a reasonable price. (What reasonable
means, of course, depends on the application.)
|
Agreed.
Best regards,
Tom
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Samuel Krempp
Guest
|
| Posted: Thu Jan 22, 2004 9:03 am Post subject: Re: Const reference worse than a copy (passing by value)? |
|
|
le Monday 19 January 2004 18:26, [email]Duff (AT) DIKU (DOT) DK[/email] écrivit :
| Quote: | John Potter <jpotter (AT) falcon (DOT) lhup.edu> wrote in message
news:<62al00dcskv8vqjqbsu9ga0fe72sk6fa7h (AT) 4ax (DOT) com>...
The code is dependent on other things, but here's a minimal slip of
code to illustrate it [...]
Yes. It illustrates that you need to trust your compiler.
I would think that it illustrates that the compiler will not optimize
away the copying of iterators. It will inline the copy-constructor and
then fold the four repeated increments into a single add, and thus my
|
I suggest using iterators with adequately big vector members, and using only
time of execution as hint of whether the compiler was able to avoid the
copying overhead.
If it does not, it demonstrates the point.
(and if it does avoid the overhead, I'm impressed  )
--
Samuel.Krempp
cout << "@" << "crans." << (is_spam ? "trucs.en.trop." : "" )
<< "ens-cachan.fr" << endl;
[ 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: Fri Jan 23, 2004 9:01 pm Post subject: Re: Const reference worse than a copy (passing by value)? |
|
|
[email]Thomas8675309 (AT) yahoo (DOT) com[/email] (Tom) wrote in message
news:<7b68d58f.0401211545.12961805 (AT) posting (DOT) google.com>...
| Quote: | kanze (AT) gabi-soft (DOT) fr wrote:
Although an iterator for std::vector and std::string may or may
not be an ordinary pointer, for a non-debug implementation,
size_of such iterators should be the same as an ordinary pointer,
which I think is what Geno Rice meant. In other words, copying
is no more expensive than passing by reference for such
iterators.
This depends very much on the compiler. With the compilers I use,
a pointer or an int is passed in a register, whereas, regardless of
the size, a class is passed as a temporary in memory.
You are certainly correct that I should have acknowledged that this is
an implementation detail. Still, I'm curious. Which compilers do you
use? If I understand you correctly, on your compilers, passing struct
{ int* p; } by value is more expensive than passing a simple int* by
value.
|
I tried the following code:
class S
{
int* p ;
public:
S() : p( 0 ) {}
S( int* pp ) : p( pp ) {}
int& operator*() const { return *p; }
S& operator++() { ++ p ; return *this ; }
} ;
typedef int* P ;
S
func_sss( S s )
{
++ s ;
return s ;
}
P
func_ppp( P p )
{
++ p ;
return p ;
}
I tried it with Sun CC (version 5.1, -O4), g++ (version 3.3.1, -O3,
under Solaris Sparc) and VC++ 6.0 (-Ox, under Windows NT). In all three
cases, the class is copied into a temporary in memory, and returned via
another temporary in memory. As a simple idea, the generated code with
g++ was:
func_sss:
ld [%o0], %g1
ld [%sp+64], %o0
add %g1, 4, %g1
jmp %o7+12
st %g1, [%o0]
func_ppp:
retl
add %o0, 4, %o0
Sun CC was very similar. The difference is less striking on the Intel
platform, because even pure pointers are passed on the stack, but still:
func_sss:
mov eax, dword ptr 12[esp-4]
lea ecx, dword ptr [eax+4]
mov eax, dword ptr 8[esp-4]
mov dword ptr [eax], ecx
ret 0
func_ppp:
mov eax, dword ptr 8[esp-4]
add eax, 4
ret 0
Differences at the call site were similar -- Sun CC and g++ never even
allocated memory for P, whereas they did for S.
| Quote: | That suggests that the Stepanov abstraction penalty must be
significant, so that for time-critical operations, there is a
disincentive to using the STL. If you have a few spare moments, I
would be interested in the results of running Stepanov's benchmark
tests on your compiler. (If you don't have a copy of the Stepanov
tests, you can find a version on Scott Ladd's website at
http://www.coyotegulch.com/reviews/intel_comp/icc_gcc_benchmarks.tar.gz
) For comparison purposes, gcc 3.3.1's Stepanov abstraction penalty is
less than 10% with full optimizations, and you probably know of other
compilers that do even better.
|
I gave it a try. I'm not sure what the output means. It displayed an
abstraction penalty of 3.1 with Sun CC, and 1.23 with g++. Is this
percent, or does it mean that the abstract version takes 3.1/1.23 times
more time?
At any rate, I'm not sure that the benchmark signifies much. There is
only one module -- when I compiled my test with g++ or Sun CC, I had to
put the calls in a separate module for either of the compilers to ever
call them. Both Unix compilers inline functions defined in the same
module, whether they are declared inline or not, and once inlined, both
of the functions are optimized to a simple incrementation (which is then
further optimized according to the surrounding context).
You might want to try the following benchmark:
s.hh:
-----
class S
{
int* p ;
public:
S() : p( 0 ) {}
S( int* pp ) : p( pp ) {}
int& operator*() const { return *p; }
S& operator++() { ++ p ; return *this ; }
} ;
typedef int* P ;
extern S incr( S ) ;
extern P incr( P ) ;
x.cc:
-----
#include "s.hh"
S
incr( S s )
{
++ s ;
return s ;
}
P
incr( P p )
{
++ p ;
return p ;
}
bench.cc:
---------
#include "gb/CommandLine.hh"
#include "gb/NumericOption.hh"
#include "gb/ProgramStatus.hh"
#include "gb/BenchHarness.hh"
#include <ostream>
#include <iostream>
#include "s.hh"
template< typename Ptr >
class Test : public GB_BenchHarness
{
public:
virtual void operator()() ;
private:
int myData[ 10 ] ;
} ;
template< typename Ptr >
void
Test< Ptr >::operator()()
{
Ptr p( myData ) ;
*incr( p ) = 1 ;
}
int
main( int argc, char** argv )
{
GB_BoundNumericOption
count( 'c', 1000000 ) ;
GB_CommandLine::instance().parse( argc, argv ) ;
GB_BenchHarness::setLoopCount( count ) ;
Test< P >().run(
std::cout,
GB_BenchHarness::iterationTime,
"Pointer" ) ;
Test< S >().run(
std::cout,
GB_BenchHarness::iterationTime,
"Class" ) ;
return GB_ProgramStatus::instance().returnCode() ;
}
-------
(The necessary includes and libraries are available at my site,
www.gabi-soft.fr. I think they are pretty portable, but I've only
actually built them for Sun CC and g++, under Solaris, and g++ under
Linux.)
I find a difference of a factor more than 10 with Sun CC, and around 7
with g++.
--
James Kanze GABI Software mailto:kanze (AT) gabi-soft (DOT) fr
Conseils en informatique orientée objet/ http://www.gabi-soft.fr
Beratung in objektorientierter Datenverarbeitung
11 rue de Rambouillet, 78460 Chevreuse, France, +33 (0)1 30 23 45 16
[ 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
