Questions about vector's interface - C++ language, library and standards

C++Talk.NET
C++ language newsgroups

Archives

FAQ

Memberlist

Usergroups

Profile

Questions about vector's interface
Goto page 1, 2 Next

C++Talk.NET Forum Index -> C++ language, library and standards

View previous topic :: View next topic

Author

Message

Scott Meyers
Guest

Posted: Thu Dec 21, 2006 10:10 am Post subject: Questions about vector's interface

I recently noticed a couple of things about vector's interface I don't understand. 1. vector::at has no exception specification. Why not? 2. vector::resize has this signature: void resize(size_type, T = T()); Why is the second argument passed by value instead of by ref-to-const? The analogous constructor uses ref-to-const: explicit vector(size_type, const T& = T(), [...] ); Thanks for any clarification of these design decisions. Scott --- [ comp.std.c++ is moderated. To submit articles, try just posting with ] [ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ] [ --- Please see the FAQ before posting. --- ] [ FAQ: http://www.comeaucomputing.com/csc/faq.html ]

Pete Becker
Guest

Posted: Thu Dec 21, 2006 10:53 pm Post subject: Re: Questions about vector's interface

Scott Meyers wrote:

Quote:

I recently noticed a couple of things about vector's interface I don't
understand.

2. vector::resize has this signature:

void resize(size_type, T = T());

Why is the second argument passed by value instead of by
ref-to-const? The analogous constructor uses ref-to-const:

explicit vector(size_type, const T& = T(), [...] );

Thanks for any clarification of these design decisions.

vector<int> v;
// populate v;

v.resize(v[0]);

If resize takes its argument by reference, the reference to v[0] becomes
invalid during the resize. Passing the argument by values means that
resize is always dealing with a copy, so there's no validity problem.

--

-- Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." (www.petebecker.com/tr1book)

---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]

Howard Hinnant
Guest

Posted: Fri Dec 22, 2006 2:48 am Post subject: Re: Questions about vector's interface

In article <12okbusm53ndm31 (AT) corp (DOT) supernews.com>,
usenet (AT) aristeia (DOT) com (Scott Meyers) wrote:

Quote:

I recently noticed a couple of things about vector's interface I don't
understand.

1. vector::at has no exception specification. Why not?

Because the only thing that would add is code bloat. The purpose of an
exception specification is to create a run time check which checks for
exceptions which don't meet the spec, and call unexpected() when that
happens. There is no way for that to happen within at(). Compilers may
or may not be able to detect that, and optimize the check away.

In article <TrudnbTYYadRDhfYnZ2dnUVZ_ruknZ2d (AT) giganews (DOT) com>,
pete (AT) versatilecoding (DOT) com (Pete Becker) wrote:

Quote:

Scott Meyers wrote:
I recently noticed a couple of things about vector's interface I don't
understand.

2. vector::resize has this signature:

void resize(size_type, T = T());

Why is the second argument passed by value instead of by
ref-to-const? The analogous constructor uses ref-to-const:

explicit vector(size_type, const T& = T(), [...] );

Thanks for any clarification of these design decisions.

vector<int> v;
// populate v;

v.resize(v[0]);

If resize takes its argument by reference, the reference to v[0] becomes
invalid during the resize. Passing the argument by values means that
resize is always dealing with a copy, so there's no validity problem.

This was the reason, but it is in error. Taking t by value is a plain
and simple performance bug in the standard.

There are 3 cases to consider:

1. Size is shrinking.
2. Size is growing, but to less than or equal to capacity().
3. Size is growing beyond capacity().

In case 1, t is never referenced. So the fact that the call may
invalidate it is irrelevant.

In case 2, t can not be invalidated.

In case 3, t can be invalidated (as the old buffer is destroyed), but it
is trivial to delay deleting the old buffer until the new buffer is
fully populated, including the new copies of t. I would even imagine
this is how most implementations behave anyway.

For entertainment value, note that resize is specified in terms of:

if (sz > size())
insert(end(), sz-size(), c);
else if (sz < size())
erase(begin()+sz, end());
else
; // do nothing

And if you look at the spec for insert(pos, size, value):

void insert(iterator position, size_type n, const T& x);

(note the const T&), and their is no precondition that x not be a
reference into *this. Therefore implementations already have to watch
out for this issue within insert. insert (unlike resize) is capable of
invalidating the reference out from under itself when x is reference
into *this occurring at or beyond the point of insertion (not possible
when inserting at end()).

So the only purpose of passing T by value in resize() is to keep those
bored little electrons in your computer a little busier. For what its
worth, I took the CodeWarrior implementation outlaw on this issue a long
time ago (and documented that fact in the header synopsis of each
affected container). No complaints were ever lodged.

This issue is mentioned in one of the rvalue reference papers:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1858.html

(search for resize) Ironically enough, I considered the resize(size,T)
issue too controversial to actually suggest fixing it in this paper.
<sigh>

-Howard

---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]

Greg Herlihy
Guest

Posted: Fri Dec 22, 2006 11:37 pm Post subject: Re: Questions about vector's interface

Howard Hinnant wrote:

Quote:

pete (AT) versatilecoding (DOT) com (Pete Becker) wrote:
vector<int> v;
// populate v;

v.resize(v[0]);

If resize takes its argument by reference, the reference to v[0] becomes
invalid during the resize. Passing the argument by values means that
resize is always dealing with a copy, so there's no validity problem.

This was the reason, but it is in error. Taking t by value is a plain
and simple performance bug in the standard.

Why would we expect vector::resize() to be appreciably more efficient
if it accepted the initializer value from a const reference - instead
of from (as is currently specified) a value parameter? As far as I can
tell the requirements of the two most time-consuming operations that
resize() potentially has to perform (allocate memory and initialize
each newly allocated element) would be unaffected by such a change. And
although I don't know much about compiler technology, I would have
guessed that initializing newly-allocated objects with an rvalue has
the potential to be much more efficent (at least when the initializer
value is known at compile-time) than initializing the same same objects
with a value copied from an lvalue parameter - a value that can only be
ascertained at runtime.

Quote:

For entertainment value, note that resize is specified in terms of:

if (sz > size())
insert(end(), sz-size(), c);
else if (sz < size())
erase(begin()+sz, end());
else
; // do nothing

And if you look at the spec for insert(pos, size, value):

void insert(iterator position, size_type n, const T& x);

(note the const T&), and their is no precondition that x not be a
reference into *this. Therefore implementations already have to watch
out for this issue within insert. insert (unlike resize) is capable of
invalidating the reference out from under itself when x is reference
into *this occurring at or beyond the point of insertion (not possible
when inserting at end()).

I'm not sure I understand why only those iterators beyond the point of
insertion may be invalidated by an insert() operation. If the vector
needs to be resized in order to accomodate the objects being inserted
into the vector, then calling insert() must have the same potential
side effects as a call to resize(), namely, that the call may
invalidate all of the vector's iterators no matter their position in
the vector.

Greg

---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]

Guest

Posted: Sat Dec 23, 2006 3:52 am Post subject: Re: Questions about vector's interface

Greg Herlihy wrote:
..

Quote:

Section 23.2.4.3p1 says: "Notes: Causes reallocation if the new size is
greater than the old capacity. If no reallocation happens, all of the
iterators and references before the insertion point remain valid. ..."

This garantee is only useful when the user has made sure that capacity
is adequate to ensure that reallocation is not allowed. Of course, it's
perfectly feasible for the user to ensure that.

---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]

Scott Meyers
Guest

Posted: Sat Dec 23, 2006 5:53 am Post subject: Re: Questions about vector's interface

Howard Hinnant wrote:

Quote:

This is an interesting perspective on exception specifications (ESes)
that I have not heard before. It suggests that the role of an ES is not
to document to callers what the exception-related interface to the
function is, but instead to enforce that interface (which is presumably
documented elsewhere). Interestingly, this is consistent with the
notion that a function's type does not include its ES (except when it
does :-}).

Are you speaking primarily for yourself in defining the role of an ES
this way, or would you say that you believe you reflect consensus on the
committee regarding the role of ESes as being more enforcement than
documentation? (I realize that you can't speak for the committee, hence
my question about whether you *believe* that this sentiment is probably
shared by most members of the committee. Still an unfair question, I
know, but I'm doing my best to ask whether you think this view of ESs is
"commonly accepted.")

Quote:

So the only purpose of passing T by value in resize() is to keep those
bored little electrons in your computer a little busier.

Nice analysis, thanks :-)

Scott

---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]

Howard Hinnant
Guest

Posted: Sun Dec 24, 2006 12:59 am Post subject: Re: Questions about vector's interface

In article <12omrng6bv9bm41 (AT) corp (DOT) supernews.com>,
usenet (AT) aristeia (DOT) com (Scott Meyers) wrote:

Quote:

Howard Hinnant wrote:
Because the only thing that would add is code bloat. The purpose of an
exception specification is to create a run time check which checks for
exceptions which don't meet the spec, and call unexpected() when that
happens.

This is an interesting perspective on exception specifications (ESes)
that I have not heard before. It suggests that the role of an ES is not
to document to callers what the exception-related interface to the
function is, but instead to enforce that interface (which is presumably
documented elsewhere). Interestingly, this is consistent with the
notion that a function's type does not include its ES (except when it
does :-}).

Are you speaking primarily for yourself in defining the role of an ES
this way

Yes, in that I'm representing only myself. However I'm attempting to
speak from the perspective of the compiler/language. An ES has an
effect, and that effect is to generate code to enforce a run time check
that the ES is respected, else unexpected() is called. That run time
check may or may not be optimized back out during a later phase of
compilation.

Yes, there is a documentation aspect to ES, in the same way that every
part of the language documents the programmer's intent (as opposed to
say machine language). E.g. the declaration of a function documents its
purpose, arguments and return types.

If you want the documentation aspect of ES, but not the associated run
time check, better to simply use a comment. If you want the run time
check, then ES is your tool. If you want a compile time check of the
exception specification, write a paper. Wink

The only compile time
checking I would personally be in favor of is a no-throw spec.

-Howard

---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]

Howard Hinnant
Guest

Posted: Sun Dec 24, 2006 11:45 pm Post subject: Re: Questions about vector's interface

In article <1166757304.037836.30250 (AT) 73g2000cwn (DOT) googlegroups.com>,
"Greg Herlihy" <greghe (AT) pacbell (DOT) net> wrote:

Quote:

This was the reason, but it is in error. Taking t by value is a plain
and simple performance bug in the standard.

Why would we expect vector::resize() to be appreciably more efficient
if it accepted the initializer value from a const reference - instead
of from (as is currently specified) a value parameter? As far as I can
tell the requirements of the two most time-consuming operations that
resize() potentially has to perform (allocate memory and initialize
each newly allocated element) would be unaffected by such a change. And
although I don't know much about compiler technology, I would have
guessed that initializing newly-allocated objects with an rvalue has
the potential to be much more efficent (at least when the initializer
value is known at compile-time) than initializing the same same objects
with a value copied from an lvalue parameter - a value that can only be
ascertained at runtime.

"Appreciable" is a subjective term. So I'll just count copies...

I wrote this little test harness to help, and tested it on gcc 4.0.1:

template <class T>
struct vec
{
void resize(unsigned, T t) {}
};

struct A
{
A() {}
A(const A&) {std::cout << "A(const A&)\n";}
};

Once inside resize, I believe we can expect the N copies of A, no matter
whether it is passed by value or by const&. So we're just counting
copies to get the parameter in. We want to do this for both lvalue and
rvalue arguments, and modeling both pass by value and pass by const T&.
For example, here's the code for passing an lvalue:

int main()
{
vec<A> v;
A a;
v.resize(0, a);
}

Here are my empirical results:

T const T&

lvalue 1 0
rvalue 0 0

As a sanity check, I ran the same test on CodeWarrior, and got the same
results.

It appears to me that const T& (in general) is the more efficient
approach. As T can have an arbitrarily expensive copy constructor, and
the number of T's copied into the vector internally can be arbitrarily
small (including 0), then (imho) it is prudent to pass by const T& for
the case of resize. A copy saved is a copy earned. ;-)

Quote:

Yes, sorry, my language got sloppy. In the case of insert(pos, n, t),
there are 3 cases to consider:

1. n == 0, there is no possibility for invalidation of t.
2. size() + n <= capacity().
3. size() + n > capacity().

In the case of 2, if t references an element within the same vector
prior to position "pos", then t will not be invalidated. If it
references an element at or beyond "pos", then it will be invalidated.
Since t is pass by const&, a properly implemented vector::insert must
take this into account. Some implementations will make an internal copy
"just in case". My preferred implementation technique is to simply
detect this situation, and chase the moved element with a pointer. This
simple "check & chase" is potentially far more efficient than a copy.
Note that if "pos" == end(), (as it would if being called from
resize()), then there is no possibility for this mode of invalidation.

In the case of 3, we have the identical situation that I spoke about for
resize when size() + n > capacity(). t could be invalidated as the old
buffer is destroyed. But it is both easy and typical to completely
construct the new buffer, including all new elements, before destroying
the old buffer, thus avoiding an untimely invalidation. Indeed, with
insert it is required because of the pass by const T&.

Therefore if resize() is simply implemented in terms of insert, then you
could pass T by const T&, and invalidation would not be possible
(because insert isn't permitted to allow it).

-Howard

---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]

Lance Diduck
Guest

Posted: Mon Dec 25, 2006 6:37 pm Post subject: Re: Questions about vector's interface

Howard Hinnant wrote:

Quote:

The only compile time
checking I would personally be in favor of is a no-throw spec.
Speaking from the perspective of an applications designer, ESes create

way more problems than they solve.
First:
A common idiom for an app writer is placing catch blocks like so:
//in a library header
namespace SomeLibrary{
struct Err1;
void use()throw(Err1);
}
//user writes
try{
SomeLibrary::use();
}catch(SomeLibrary::Err1 const&){/*...*/}
}catch(std::exception const&){/*...*/}
}catch(...){/*...*/}
So an exception specification anywhere in SomeLibrary is useless -- the
user is already very likely to build the "firewall" where it belongs,
which is after the function exits, not before.

Second:
Many newcomers to C++ approach it from Java. Java ES has a somewhat
different semantic than C++, and at least in Java you can get compiler
support to make sure the ES is correct. Getting them to unlearn this
semantic, and then tell them they have to play with global handlers
and/or do full coverage regression tests (Oh yeah that is going to
happen) to make sure that you got the exception return paths perfect on
pain of death....

Third:
Every non-trivial library is going to inherit their exceptions from
std::exception. So we typically have this case
namespace SomeLibrary{
struct Err1:std::logic_error{
Err1(std::string const&_a):std::logic_error(_a){}
}
void use()
throw (Err1)//Thinking in Java
{
std::vector <int> j(20);//Init somehow
// buried deep in bowels of the library
// using Configuraton 15, j is resized to 5
if(j.at(19)==1)//Oops!!! we didn't convert to an Err1
throw Err1("Too bad");
}
}//namespace

You can just imagine what the user of SomeLibrary thinks now--
everytime he calls the library in a particular configuration, his app
just crashes. Either a) we tell the user that he should have
set_unexpected() to make the library work, or b) we maintain complete
coverage regression tests hoping that we catch these errors, which add
significantly to the cost of the library.
And for what? The user is already catching std::exception just by habit
anyway. He would have just reported a bug rather than now preparing
litigation.
The natural progression is of course
namespace SomeLibrary{
void use()thow(Err1,std::exception)
//documents nothing a user isn't already doing, but at least works!!
}
and then the ES comes out altogether like a bad appendix.

So whether there is a documentation effect, a performance hit, some
code bloat or what not, C++ ES has the notable effect of making a
program less fault-tolerant and more error-prone. Which is exactly the
opposite effect that you intended. Perhaps there is a little value in
throw() as a optimizing hint to the compiler, however in practice
virtually all functions that use nothrow are inlined anyway.

---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]

Stephen Howe
Guest

Posted: Thu Dec 28, 2006 6:12 am Post subject: Re: Questions about vector's interface

Quote:

Ironically enough, I considered the resize(size,T)
issue too controversial to actually suggest fixing it in this paper.

But is it considered at all?
It seems terrible that for C++0x - performance bugs are left in the
standard.
There should be no unneccesary copy constructors & corresponding destructors
invoked.

Stephen Howe

---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]

Howard Hinnant
Guest

Posted: Thu Dec 28, 2006 10:10 am Post subject: Re: Questions about vector's interface

In article <coidnZrP95hpew_YRVnytwA (AT) pipex (DOT) net>,
sjhoweATdialDOTpipexDOTcom (AT) giganews (DOT) com ("Stephen Howe") wrote:

Quote:

Ironically enough, I considered the resize(size,T)
issue too controversial to actually suggest fixing it in this paper.

But is it considered at all?
It seems terrible that for C++0x - performance bugs are left in the
standard.
There should be no unneccesary copy constructors & corresponding destructors
invoked.

Write a paper. Make a defect report. Do something that the committee
can not ignore (we can ignore posts to comp.std.c++ unless they are a DR
or request to submit a paper). If somebody has already submitted a DR
or paper on the subject, do not assume that it is taken care of.
Duplicates count; they are not wasted effort at all. Just because I
know it is a defect, don't assume I have the political power to get it
changed. *You* (collectively speaking) have the power to get it
changed. Send me a DR I can't ignore. :-)

To submit a defect report:

Post to comp.std.c++ with the words "Defect Report:" in the subject
line. Defect reports need not be lengthy. But they are more effective
if they clearly propose wording changes to the latest current working
draft (currently N2135). A brief motivating statement is helpful as
well. If you know you are submitting a duplicate, it might be helpful
to include motivation which other dr's have not yet stated. Otherwise
just re-asserting the motivation is also helpful.

Your vote counts.

-Howard

---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]

Pete Becker
Guest

Posted: Thu Dec 28, 2006 10:10 am Post subject: Re: Questions about vector's interface

Stephen Howe wrote:

Quote:

Have you seen an application in which this copy was shown to be a
bottleneck?

--

-- Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." (www.petebecker.com/tr1book)

---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]

Gennaro Prota
Guest

Posted: Fri Jan 05, 2007 4:56 pm Post subject: Re: Questions about vector's interface

I first posted this on December 22, 2006. But I'm quite obstinate, so
here's my belated reply :-)

On Thu, 21 Dec 2006 20:48:51 GMT, Howard Hinnant wrote:

Quote:

That's a typo for v.resize( s, v[ 0 ] ), isn't it?

Quote:

Taking t by value is a plain
and simple performance bug in the standard.

There are 3 cases to consider:

1. Size is shrinking.
2. Size is growing, but to less than or equal to capacity().
3. Size is growing beyond capacity().

In case 1, t is never referenced. So the fact that the call may
invalidate it is irrelevant.

In case 2, t can not be invalidated.

In case 3, t can be invalidated (as the old buffer is destroyed), but it
is trivial to delay deleting the old buffer until the new buffer is
fully populated, including the new copies of t.

In addition to what you point out, the choice is quite against the
don't pay for what you don't use principle: if one wants to pass a
value from v itself then why not writing

T t( v[ i ] );
v.resize( v, t );

Or am I missing something?

___
X-Replace-Address
\|||/ Gennaro Prota - For hire
(o o) https://sourceforge.net/projects/breeze/
--ooO-(_)-Ooo----- (to mail: name _ surname / yaho ! com)

---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]

Howard Hinnant
Guest

Posted: Sat Jan 06, 2007 11:11 pm Post subject: Re: Questions about vector's interface

In article <trhsp2975sgt991bgk6rlilh6oeajvoqmk (AT) 4ax (DOT) com>,
Gennaro Prota <gennaro_prota (AT) yahoo (DOT) com> wrote:

Quote:

vector<int> v;
// populate v;

v.resize(v[0]);

That's a typo for v.resize( s, v[ 0 ] ), isn't it?

Yes.

Quote:

I don't recommend making a copy to avoid self referencing in this case.
The container can, and should handle it for you. The container already
handles it for you for insert, so there's no reason it can't handle it
for you for resize as well (which is a simpler case than insert).

-Howard

---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]

Greg Herlihy
Guest

Posted: Fri Jan 12, 2007 5:33 pm Post subject: Re: Questions about vector's interface

"Stephen Howe" wrote:

Quote:

The question in this case is very simple: whether an implementation of
vector::resize() declared like this:

vector::resize(size_type sz, const T& c = T());

would be at least as fast as - if not faster - than vector's current
resize() method:

vector::resize(size_type sz, T c = T());

for all eligible types, T, and on all machine architectures for which a
C++ compiler exists.

If the answer to this question is "yes" then a performance defect (of
some magnitude) would exist with the current declaration of
vector::resize(). But given the wide variety of potential types for T
and architectures to consider, even knowing the effect of such a change
for certain would be a challenge. After all, it is not enough to find
some vector resizing operations which benefit from the change, it is
necessary to show somehow that resizing a vector would never be slower.
Because if resizing a vector would be slower in some cases - that is -
if the answer turns out to be "no" - then there is no performance bug
(or at least this change is not its fix). Instead, there is a tradeoff.
And making tradeoffs is a design decision, not a defect to be fixed.

So is it conceivable that changing an argument passed by-value to one
passed by-reference would actually making resizing a vector slower?
Let's consider a C++ program compiled for a machine achitecture in
which arguments in function calls are passed in registers (such as the
PowerPC). Now imagine resizing a vector containing elements small
enough to fit within a register (such as a vector<int> or vector<const
char *>). In this scenario, passing an argument by-reference to
resize() is less efficient - since the value must now be copied out of
its register into a memory location while a pointer to that location is
passed in its place. In other words, the "work" that the C program
appears to be performing does not always correspond to the work that
the compiled binary performs - in fact, in this case, it is the
opposite. At the C++ language level: passing by value appears to
require a copy operation - at the machine level: no copy is made. At
the C level: passing the argument by reference does not make a copy, at
the machine level: the argument is copied from a register into a memory
location.

So the essential premise - that machine level optimizations can be
achieved from changes being made at the source code level - is
mistaken. The only sure optimizations that can be implemented at the
source code level are those that eliminate logical operations - not
those that make changes but leave the amount of "work" performed the
same. There is no work saved at the language level, the parameter is
still passed to resize() in both cases, so no "optimization" at the
language level has been made with this change, so no performance
improvement in the compiled program is assured.

Moreover, while the benefit of this change is to eliminate one copy
operation per resize operation, its cost is to make inserting each
object into the vector take longer (by replacing a register-to-memory
location copy with a copy between two memory locations). So the bargain
seems to be: in exchange for making one set of resizing operations
faster by a constant amount of time, it is necessary to slow down
another set of resize operations by a variable amount, an amount of
time proportional to the however long resizing currently takes. So
resizing a vector by a large amount may either be a little bit faster -
or a lot slower - than it was before. Even if the former cases
outnumber the latter, it is still an unattractive deal, since no matter
how much a program stands to gain with this change, it only takes a few
operations to nullify those gains.

One could argue that a compiler's optimizer is likely to minimize the
cost of this change, maybe even completely get rid of it. But this is
the same, optimizing compiler deemed unable to make the optimization
for which this change was necessary in the first place. And it seems
more likely that an optimizer would be able to eliminate the copy of
resize()'s value parameter on its own (especially if resize() is
inlined) than it would be able to undo the effects of pushing a value
out of a register. But one thing is certain, these types of issues
cannot be optimized at the language level - the application
environments affected by these types of changes are too diverse for
these kinds of decisions to be made here. Instead the Standard should
grant the necessary latitude to implementions in order to make the
desired optimizations on a case-by-case basis, and then leave it up to
them to do just that.

Greg

---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]

Display posts from previous:

	C++Talk.NET Forum Index -> C++ language, library and standards	All times are GMT Goto page 1, 2 Next
Page 1 of 2

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