Fastest way to zero a vector?

[Joseph Turian]

Okay.

I have a vector<bool> of fixed size N. Let's call it bob.
I'm zero'ing bob quite a bit, i.e.:
bob = vector<bool>(N, false);

Naturally, this is quite slow, because of all the object creation.

Can I do any better than the following:
bob.clear(); bob.resize(N, false);
?

I don't mind changing the container type or the entry type (e.g.
bool->char), so if you have any suggestions in that vein then fire
away.

I'm trying to get this to be really fast, so I'll entertain any
so-called "extreme solution".


Joseph

 

[Joseph Turian]

Oh.

The other thing I should point out is that N is really small:
N=3

(Depending upon the command-line, it may be less than 3, but not
greater.)

Joseph

 

[Victor Bazarov]

Okay.

I have a vector<bool> of fixed size N. Let's call it bob.
I'm zero'ing bob quite a bit, i.e.:
bob = vector<bool>(N, false);

Naturally, this is quite slow, because of all the object creation.

Can I do any better than the following:
bob.clear(); bob.resize(N, false);
?

I don't mind changing the container type or the entry type (e.g.
bool->char), so if you have any suggestions in that vein then fire
away.

I'm trying to get this to be really fast, so I'll entertain any
so-called "extreme solution".

How about

memset(&bob, 0, N*sizeof(bob));

for built-in types (or any PODs for that matter)? You can't do it
with non-PODs, however.

V

 

[John Dibling]

In the interest of entertaining any solution, I believe that this the
fastest possible way to 0-init an aggregate of PODs:

bool bob[123] = {0};

Of course if you already have allocated the array, you can't do this.

Take care,
John Dibling

 

[Geo]

Okay.

I have a vector<bool> of fixed size N. Let's call it bob.
I'm zero'ing bob quite a bit, i.e.:
bob = vector<bool>(N, false);

Naturally, this is quite slow, because of all the object creation.

Can I do any better than the following:
bob.clear(); bob.resize(N, false);
?

I don't mind changing the container type or the entry type (e.g.
bool->char), so if you have any suggestions in that vein then fire
away.

I'm trying to get this to be really fast, so I'll entertain any
so-called "extreme solution".

How about

memset(&bob, 0, N*sizeof(bob));

for built-in types (or any PODs for that matter)? You can't do it
with non-PODs, however.

V

But remember vector<bool> is a hideous mutant, an abberation, a
grotesque freak and this may not do what you hoped for.

 

[Krishanu Debnath]

Victor Bazarov wrote:

[snip]

How about

memset(&bob, 0, N*sizeof(bob));

Considering bob is array of T(built-in type) of N elements, it certainly invokes
undefined behavior.

for built-in types (or any PODs for that matter)? You can't do it
with non-PODs, however.

V

Krishanu

 

[Victor Bazarov]

Victor Bazarov wrote:

[snip]

How about

memset(&bob, 0, N*sizeof(bob));

Considering bob is array of T(built-in type) of N elements, it certainly
invokes
undefined behavior.

Right. I meant to use bob[0] not bob, of course. Or did you mean
something else? Please consider explaining your point of view instead
of just stating it so I don't have to guess. Thanks.

V

 

[Krishanu Debnath]

Victor Bazarov wrote:

[snip]

How about

memset(&bob, 0, N*sizeof(bob));

Considering bob is array of T(built-in type) of N elements, it
certainly invokes
undefined behavior.

Right. I meant to use bob[0] not bob, of course. Or did you mean

Why bob[0]? You want to reset whole array, right? So it should be
memset(bob, 0, N * sizeof(*bob));

something else? Please consider explaining your point of view instead
of just stating it so I don't have to guess. Thanks.

V

Krishanu

 

[Joseph Turian]

How about

memset(&bob, 0, N*sizeof(bob));

for built-in types (or any PODs for that matter)? You can't do it
with non-PODs, however.

Forgive my ignorance; What's a POD?

Joseph

 

[Victor Bazarov]

Victor Bazarov wrote:

[snip]



How about

memset(&bob, 0, N*sizeof(bob));




Considering bob is array of T(built-in type) of N elements, it
certainly invokes
undefined behavior.

Right. I meant to use bob[0] not bob, of course. Or did you mean

Why bob[0]? You want to reset whole array, right? So it should be
memset(bob, 0, N * sizeof(*bob));

'&bob[0]' and 'bob' yield the same address for an array of T. However,
if 'bob' is NOT an array and instead is a _vector_ (std::vector<T>) like
the OP asked, then 'memset(bob..' is NOT going to work.

V

 

[Victor Bazarov]

Victor Bazarov wrote:

How about

memset(&bob, 0, N*sizeof(bob));

for built-in types (or any PODs for that matter)? You can't do it
with non-PODs, however.

Forgive my ignorance; What's a POD?

It's a TLA. And it's in the FAQ. Please read the FAQ before posting.

 

[John Dibling]

Plain Old Datatype.

 

[Chris Theis]

Victor Bazarov wrote:

[snip]



How about

memset(&bob, 0, N*sizeof(bob));



Considering bob is array of T(built-in type) of N elements, it certainly
invokes
undefined behavior.

Right. I meant to use bob[0] not bob, of course. Or did you mean

Why bob[0]? You want to reset whole array, right? [SNIP]

Yes, that's what Victor wants and actually does with his code (using [0]
instead of ).

Cheers
Chris

 

[Joseph Turian]

Forgive my ignorance; What's a POD?

Ah, got it.
http://www.parashift.com/c++-faq-lite/intrinsic-types.html#faq-26.7

Why bob[0]? You want to reset whole array, right? So it should be
memset(bob, 0, N * sizeof(*bob));

Wait, bob is vector<bool>, so you can't memset it.
Is the suggestion that I use a raw array?

Joseph

 

[Chris Theis]

How about

memset(&bob, 0, N*sizeof(bob));

for built-in types (or any PODs for that matter)? You can't do it
with non-PODs, however.

Forgive my ignorance; What's a POD?

A POD is the abbreviation of Plain Old Data. This means that it has an
equivalent in C, for example the "built-in" types like int, double, etc.
Check out the FAQ at
http://www.parashift.com/c++-faq-lite/intrinsic-types.html#faq-26.7

Cheers
Chris

 

[Victor Bazarov]

Forgive my ignorance; What's a POD?

Ah, got it.
http://www.parashift.com/c++-faq-lite/intrinsic-types.html#faq-26.7

Krishanu Debnath wrote:

Why bob[0]? You want to reset whole array, right? So it should be
memset(bob, 0, N * sizeof(*bob));

Wait, bob is vector<bool>, so you can't memset it.
Is the suggestion that I use a raw array?

No. Use whatever means 'vector<bool>' offers, like 'clear' or 'swap'
or assignment. Try

vector<bool> bob;
...
bob.assign(bob.size(), false);

or

bob = vector<bool>(bob.size());

or

vector<bool>(bob.size()).swap(bob);

V

 

[Joseph Turian]

bob = vector<bool>(bob.size());

Object creation is slow, this is the version I started with.

vector<bool>(bob.size()).swap(bob);

I can't see this being any faster than the above, especially since it
forces the memory to be freed, but I'll try it.

bob.assign(bob.size(), false);

I didn't even know that this function existed. It's not in the STL
docs:
http://www.sgi.com/tech/stl/Vector.html
Is it standard? (Just curious)


At this point, my guess is that---unless vector<bool> bit packing is
somehow really fast (is it?)---the speediest thing is the following:

Allocate a large array and memset it to zero.
Write a class that uses three bytes of the array at a time.
Whenever the class.zero() method is called, add three to the class
member variable that holds the pointer. If the array is exhausted,
memset it and reset the pointer to the beginning.


Joseph

 

[Victor Bazarov]

Victor Bazarov wrote:
[..]

bob.assign(bob.size(), false);

I didn't even know that this function existed. It's not in the STL
docs:
http://www.sgi.com/tech/stl/Vector.html

You should use up-to-date documentation. Like a copy of the Standard,
for example, or the docs for your compiler (hopefully, recent).

Is it standard? (Just curious)

Yes. Whether it's faster, remains to be seen.

BTW, I usually try to avoid recommending non-standard code here.
Just so that you know...

[...]

V

 

[Joseph Turian]

BTW, I usually try to avoid recommending non-standard code here.
Just so that you know...

Don't worry, your secret's safe with me

Thank you for recommendations

Joseph

 

[Ron Natalie]

How about

memset(&bob, 0, N*sizeof(bob));

for built-in types (or any PODs for that matter)? You can't do it
with non-PODs, however.

You better not do it with vector<bool> either!