stl <vector> clear and erase.

Hello,

The following resulted from a performance hotspot analysis in a larger
context.
Small vector <unsigned> variables are built up (typical size 6) and
they are cleared by v.clear(). This happens millions of times.

My free profiler "Very Sleepy", which has been of great use to me,
points me to the following, which is not my code and therefore
presumed to be STL-implementation. (VC++ 11, presumably Dinkum)

void clear()
0.16s { // erase all
0.08s erase(begin(), end());
0.00s }

Question: Why does it perform this erase as part of clear(), can I
keep it from doing so and how? I see no point in erasing for a vector
<unsigned>. As far as I remember what I have read, there should not
be any erasing in this case. The (logical) length of the vector
should be adjusted (constant complexity) and the old contents are left
as garbage. Could I be better off using old C arrays?

Any hint greatly appreciated, this is really a hotspot in my program.

Regards,
Peter


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Am 29.04.2012 22:09, schrieb Peter Liedermann:
> My free profiler "Very Sleepy", which has been of great use to me,
> points me to the following, which is not my code and therefore
> presumed to be STL-implementation. (VC++ 11, presumably Dinkum)
>
> void clear()
> 0.16s { // erase all
> 0.08s erase(begin(), end());
> 0.00s }
>
> Question: Why does it perform this erase as part of clear(), can I
> keep it from doing so and how? I see no point in erasing for a vector
> <unsigned>. As far as I remember what I have read, there should not
> be any erasing in this case. The (logical) length of the vector
> should be adjusted (constant complexity) and the old contents are left
> as garbage.

The implementation you are observing, is conforming, because the
standard describes above semantics. Nonetheless you are right: A good
quality-implementation can skip the iteration here and can simply adjust
the internal length representation via an O(1) step. I'm pretty sure
that gcc 4.8 does this, for example, if the value type of the vector has
a trivial destructor.

> Could I be better off using old C arrays?
>
> Any hint greatly appreciated, this is really a hotspot in my program.

This is really an quality-of-implementation issue, you should ask your
vendor for improvements, bringing the hot-spot situation as an example.

HTH & Greetings from Bremen,

Daniel Krügler


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

On Apr 29, 10:09 pm, "Peter Liedermann" <peter09...@hispeed.ch> wrote:
> Hello,
>
> The following resulted from a performance hotspot analysis in a larger
> context.
> Small vector <unsigned> variables are built up (typical size 6) and
> they are cleared by v.clear(). This happens millions of times.
>
> My free profiler "Very Sleepy", which has been of great use to me,
> points me to the following, which is not my code and therefore
> presumed to be STL-implementation. (VC++ 11, presumably Dinkum)
>
> void clear()
> 0.16s { // erase all
> 0.08s erase(begin(), end());
> 0.00s }

Are you compiling with optimizations enabled? Compiling without
optimizations gives almost useless results as far as profiling is
concerned, since the relative cost of things can change massively. In
this case, erase() will probably even change from O(n) to O(1).

Secondly, have you checked the output in assembler?

In gcc with full optimizations, the following function:

void test(std::vector<unsigned>& i)
{
i.erase(i.begin(), i.end());
}

gets rendered as:

_Z4testRSt6vectorIjSaIjEE:
..LFB638:
.cfi_startproc
movq (%rdi), %rax
movq %rax, 8(%rdi)
ret

If you're not getting something similar then your compiler is missing
a trick and you will ahve to work around that.

If the compiler is working as expected, then it makes the code very
hard to profile with optimizations. Once that function is used, it
will almost certainly be inlined and then possibly vanish completely.
Given how little the final output corresponds to the input (imagine
that function being inlined followed by loop optimization, register
allocation, a bit of reordering and some peep hole optimization)
profiling is very hard as there is probably not a single instruction
which corresponds in any meaningful way to the function you're trying
to profile.

Last time I used gprof it appeared to associate things somewhere
nearby where the vanished function should be. They could land in funny
places, giving very strange results with full optimizations. Your
profiler may be doing something similar.

-Ed


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

On Mon, 30 Apr 2012 14:24:29 +0200, Edward Rosten
<edward.rosten@gmail.com> wrote:

> On Apr 29, 10:09 pm, "Peter Liedermann" <peter09...@hispeed.ch> wrote:

First of all, thank you for taking the time to answer, I still have to
analyze this.

One very short question concerning your example:
>
> void test(std::vector<unsigned>& i)
> {
> i.erase(i.begin(), i.end());
> }
>

Does the "&" make any difference here and which? Is it maybe the cause
of my troubles that I presently do not have it?

Thanx
Peter


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

On Sun, 29 Apr 2012 16:38:19 -0700 (PDT)
Daniel Krügler <daniel.kruegler@googlemail.com> wrote:
> Am 29.04.2012 22:09, schrieb Peter Liedermann:
> > My free profiler "Very Sleepy", which has been of great use to me,
> > points me to the following, which is not my code and therefore
> > presumed to be STL-implementation. (VC++ 11, presumably Dinkum)
> >
> > void clear()
> > 0.16s { // erase all
> > 0.08s erase(begin(), end());
> > 0.00s }
> >
> > Question: Why does it perform this erase as part of clear(), can I
> > keep it from doing so and how? I see no point in erasing for a
> > vector <unsigned>. As far as I remember what I have read, there
> > should not be any erasing in this case. The (logical) length of the
> > vector should be adjusted (constant complexity) and the old
> > contents are left as garbage.
>
> The implementation you are observing, is conforming, because the
> standard describes above semantics. Nonetheless you are right: A good
> quality-implementation can skip the iteration here and can simply
> adjust the internal length representation via an O(1) step. I'm
> pretty sure that gcc 4.8 does this, for example, if the value type of
> the vector has a trivial destructor.
>
> > Could I be better off using old C arrays?
> >
> > Any hint greatly appreciated, this is really a hotspot in my
> > program.
>
> This is really an quality-of-implementation issue, you should ask your
> vendor for improvements, bringing the hot-spot situation as an
> example.

Isn't this similar to the problem of constructing a vector of int of a
particular size, which in C++98 requires the constructor to be called
for each of the vector's elements (so initializing them to 0), whether
that is wanted or not? I imagine C++11 requires the same.

Rather than chasing compiler optimizations (or making non-standard use
of std::vector::reserve()), there are a number of cases where the answer
to the OP's question might indeed be (using his words) "Yes, you could
be better off using old C arrays", or in C++11 using std::array. I
don't think it is possible to know that just from the poster's original
description.

Chris



--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

On 30/04/2012 21:33, Chris Vine wrote:
> On Sun, 29 Apr 2012 16:38:19 -0700 (PDT)
> Daniel Krügler<daniel.kruegler@googlemail.com> wrote:
>> Am 29.04.2012 22:09, schrieb Peter Liedermann:
>>> My free profiler "Very Sleepy", which has been of great use to me,
>>> points me to the following, which is not my code and therefore
>>> presumed to be STL-implementation. (VC++ 11, presumably Dinkum)
>>>
>>> void clear()
>>> 0.16s { // erase all
>>> 0.08s erase(begin(), end());
>>> 0.00s }
>>>
>>> Question: Why does it perform this erase as part of clear(), can I
>>> keep it from doing so and how? I see no point in erasing for a
>>> vector<unsigned>. As far as I remember what I have read, there
>>> should not be any erasing in this case. The (logical) length of the
>>> vector should be adjusted (constant complexity) and the old
>>> contents are left as garbage.
>>
>> The implementation you are observing, is conforming, because the
>> standard describes above semantics. Nonetheless you are right: A good
>> quality-implementation can skip the iteration here and can simply
>> adjust the internal length representation via an O(1) step. I'm
>> pretty sure that gcc 4.8 does this, for example, if the value type of
>> the vector has a trivial destructor.
>>
>>> Could I be better off using old C arrays?
>>>
>>> Any hint greatly appreciated, this is really a hotspot in my
>>> program.
>>
>> This is really an quality-of-implementation issue, you should ask your
>> vendor for improvements, bringing the hot-spot situation as an
>> example.
>
> Isn't this similar to the problem of constructing a vector of int of a
> particular size, which in C++98 requires the constructor to be called
> for each of the vector's elements (so initializing them to 0), whether
> that is wanted or not? I imagine C++11 requires the same.

Sorry but one of us is confused. ints do not have ctors so there is no
such requirement. In general the Standard does not specify how things
should be done only what the resulting behaviour should be.


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

On 30/04/2012 21:11, Peter Liedermann wrote:
> On Mon, 30 Apr 2012 14:24:29 +0200, Edward Rosten
> <edward.rosten@gmail.com> wrote:
>
>> On Apr 29, 10:09 pm, "Peter Liedermann" <peter09...@hispeed.ch> wrote:
>
> First of all, thank you for taking the time to answer, I still have to
> analyze this.
>
> One very short question concerning your example:
>>
>> void test(std::vector<unsigned>& i)
>> {
>> i.erase(i.begin(), i.end());
>> }
>>
>
> Does the "&" make any difference here and which?

A rather large difference, the difference between operating on the
original and operating on a copy. Without the & the function has no
effects on the code calling test.


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

On 4/30/2012 1:11 PM, Peter Liedermann wrote:

> One very short question concerning your example:
>>
>> void test(std::vector<unsigned>& i)
>> {
>> i.erase(i.begin(), i.end());
>> }
>>
>
> Does the "&" make any difference here and which? Is it maybe the cause
> of my troubles that I presently do not have it?
>

Yes. if you do not have the &, you are erasing a *COPY* of the vector,
and the original vector is unmodified.


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Am 30.04.2012 22:33, schrieb Chris Vine:
> On Sun, 29 Apr 2012 16:38:19 -0700 (PDT)
> Daniel Krügler<daniel.kruegler@googlemail.com> wrote:
>> Am 29.04.2012 22:09, schrieb Peter Liedermann:
[..]
>>> Could I be better off using old C arrays?
>>>
>>> Any hint greatly appreciated, this is really a hotspot in my
>>> program.
>>
>> This is really an quality-of-implementation issue, you should ask your
>> vendor for improvements, bringing the hot-spot situation as an
>> example.
>
> Isn't this similar to the problem of constructing a vector of int of a
> particular size, which in C++98 requires the constructor to be called
> for each of the vector's elements (so initializing them to 0), whether
> that is wanted or not? I imagine C++11 requires the same.

This is a very different thing. In contrast to the pseudo-destructor the
value-initializing constructor is *not* a no-op. Any compiler can decide
to omit the pseudo-destructor evaluation, because this action is not
observable, therefore I consider your comparison as inappropriate.

> Rather than chasing compiler optimizations (or making non-standard use
> of std::vector::reserve()), there are a number of cases where the answer
> to the OP's question might indeed be (using his words) "Yes, you could
> be better off using old C arrays", or in C++11 using std::array. I
> don't think it is possible to know that just from the poster's original
> description.

If you are satisfied with static initial size, std::array is your
friend. I find it rather amusing to see a comparison of std::array with
std::vector in this context, because the latter one would be the right
choice if unknown dynamic size (changes) might occur, so is usually
orthogonal to the former (An exception are very large array sizes that
would "explode the stack").

I have not much sympathy with general recommendations of the form "Use
C-array instead of std::vector":

First, as described before, the comparison is usually invalid, you
should decide in the beginning, if a fixed-size container is appropriate
and could be reasonably put on the stack (or what ever place in your
program). If you go back to std::array or a C array, your initial design
was badly evaluated [or the requirements have changed - sigh ;-) ]

Second, instead of fighting against specified behaviour of the
value-initializing constructor I suggest to use the most appropriate
function in the given use-case. This can be the constructor that
value-initializes n items at some times. In other situations it can be
the constructor accepting a range or the usage of reserve plus
individual element additions or other combinations. Sorry, if this
sounds like nick-picking, but I have heard these arguments often enough
and they are often based on misconceptions.

I certainly agree that there are some rare situations where std::vector
fits badly in: Most typically this is the need to adapt to a C-API of
the form

int fill_array(T* data, size_t n);

where fill_array takes the role of a "constructor-like" initializer
function for the elements referenced by data. If you really can
demonstrate that the resized vector (which is required in this case) is
a bottleneck in your program, you should reconsider the choice of your
container, presumably a thin RAII wrapper for a (presumably
non-resizable) continuous storage plus its size. Such types come and go
and I have (yet) not seen one that looked like a reusable component
(Hopefully this comment inspires someone to proof me wrong ;-))

HTH & Greetings from Bremen,

Daniel Krügler


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

On Mon, 30 Apr 2012 15:45:27 -0700 (PDT)
Daniel Krügler <daniel.kruegler@googlemail.com> wrote:
[snip]
> > Isn't this similar to the problem of constructing a vector of int
> > of a particular size, which in C++98 requires the constructor to
> > be called for each of the vector's elements (so initializing them
> > to 0), whether that is wanted or not? I imagine C++11 requires
> > the same.
>
> This is a very different thing. In contrast to the pseudo-destructor
> the value-initializing constructor is *not* a no-op. Any compiler
> can decide to omit the pseudo-destructor evaluation, because this
> action is not observable, therefore I consider your comparison as
> inappropriate.

In theory, a compiler could deduce that the initial 0 value for a
statically sized vector of int is never read in the program, and so
elide the initialization, in the same way that it could elide the
obviously no-op pseudo-destructor. I agree that that would be harder
for the compiler to deduce reliably though.

> If you are satisfied with static initial size, std::array is your
> friend. I find it rather amusing to see a comparison of std::array
> with std::vector in this context, because the latter one would be
> the right choice if unknown dynamic size (changes) might occur, so
> is usually orthogonal to the former (An exception are very large
> array sizes that would "explode the stack").

I agree that using C arrays for dynamically sized arrays is asking for
trouble. That is why I said "I don't think it is possible to know
that just from the poster's original description", and referred to the
use of std::array for the case of static sizing where C++11 is in use.

Chris


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Daniel Krügler wrote:

> If you are satisfied with static initial size, std::array is your
> friend. I find it rather amusing to see a comparison of std::array
> with std::vector in this context, because the latter one would be
> the right choice if unknown dynamic size (changes) might occur, so
> is usually orthogonal to the former

My advice would be to distrust any feeling of satisfaction when using
a container with a size that is fixed at compile time. In my
experience, such a thing almost always flags some questionable
assumption that will come back to hunt you later.

- Wil


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

On Tue, 01 May 2012 00:42:11 +0200, red floyd
<no.spam.here@its.invalid> wrote:

> On 4/30/2012 1:11 PM, Peter Liedermann wrote:
>
>> One very short question concerning your example:
>>>
>>> void test(std::vector<unsigned>& i)
>>> {
>>> i.erase(i.begin(), i.end());
>>> }
>>>
>>
>> Does the "&" make any difference here and which? Is it maybe the
>> cause of my troubles that I presently do not have it?
>>
>
> Yes. if you do not have the &, you are erasing a *COPY* of the
> vector, and the original vector is unmodified.

Oh yes, sorry for the stupid question. I was thinking of something
completely different, vector<unsigned *> i versus vector<unsigned> i

Maybe i should use the screen magnifier


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

{ Article reformatted -mod }

On Tue, 01 May 2012 10:34:23 +0200, Wil Evers <bouncer@dev.null> wrote:

> Daniel Kr=FCgler wrote:
>
>> If you are satisfied with static initial size, std::array is your
>> friend. I find it rather amusing to see a comparison of std::array
>> with std::vector in this context, because the latter one would be
>> the right choice if unknown dynamic size (changes) might occur, so
>> is usually orthogonal to the former
>
> My advice would be to distrust any feeling of satisfaction when
> using a container with a size that is fixed at compile time. In my
> experience, such a thing almost always flags some questionable
> assumption that will come back to hunt you later.
>

This is generally good advice, especially to those who feel that they
do not need it

In my case, however, the size of the structure does not vary with
input, but only with certain functional extensions of the code. A
fixed size structure could constitute a trap anyway, but there is a
specific location in the code to place a sufficient comment. At the
moment, I do not want to use anything which requires C++ 11 for
reasons of portability.

Regards,
Peter


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Am 01.05.2012 06:38, schrieb Chris Vine:
> On Mon, 30 Apr 2012 15:45:27 -0700 (PDT)
> Daniel Krügler<daniel.kruegler@googlemail.com> wrote:
> [snip]
>>> Isn't this similar to the problem of constructing a vector of int
>>> of a particular size, which in C++98 requires the constructor to
>>> be called for each of the vector's elements (so initializing them
>>> to 0), whether that is wanted or not? I imagine C++11 requires
>>> the same.
>>
>> This is a very different thing. In contrast to the
>> pseudo-destructor the value-initializing constructor is *not* a
>> no-op. Any compiler can decide to omit the pseudo-destructor
>> evaluation, because this action is not observable, therefore I
>> consider your comparison as inappropriate.

In the last sentence I misleadingly referred to "any *compiler* can
decide to omit [..]", but actually I was thinking of an optimized
library implementation, so this should better say "Any library
implementation can decide to omit [..]".

> In theory, a compiler could deduce that the initial 0 value for a
> statically sized vector of int is never read in the program, and so
> elide the initialization, in the same way that it could elide the
> obviously no-op pseudo-destructor. I agree that that would be
> harder for the compiler to deduce reliably though.

In theory, yes, but I haven't seen this happening in real life. It
would require a much more kind of non-local code analysis, while the
above mentioned pseudo-destructor elimination can easily be done by
means of portable library code. The usual technique is to evaluate
some trait, like is_trivially_destructible (or corresponding compiler
intrinsics that did already exist in C++03) and to make a compile-time
code branch here. There is no much magic involved and therefore this
technique is very popular.

HTH & Greetings from Bremen,

Daniel Krügler




--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

On Tue, 01 May 2012 00:41:37 +0200, Francis Glassborow
<francis.glassborow@btinternet.com> wrote:

> On 30/04/2012 21:33, Chris Vine wrote:
> (...) In general the Standard does not specify how things
> should be done only what the resulting behaviour should be.
>

This takes me back to my original question. I have no access to the
standard, but as far as I know, it does specify the complexity of
operations, and for anyVector.clear() it says O(1) plus whatever
destruction is needed. In the case of vector <unsigned> anyVector
destruction is a no-op (this does not seem to be disputed here). This
would then preclude, in my opinion, iterating over the vector for the
purpose of clear()-ing it, and that would not just be an efficiency
issue of clever implementation.

Regards
Peter


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]