Fastest way to zero a vector?

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

re: Fastest way to zero a vector?

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

re: Fastest way to zero a vector?

Joseph Turian wrote:[color=blue]
> 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".[/color]

How about

memset(&bob[i], 0, N*sizeof(bob[i]));

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

V

re: Fastest way to zero a vector?

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

re: Fastest way to zero a vector?

Victor Bazarov wrote:

[snip][color=blue]
>
>
> How about
>
> memset(&bob[i], 0, N*sizeof(bob[i]));[/color]

Considering bob is array of T(built-in type) of N elements, it certainly invokes
undefined behavior.
[color=blue]
>
> for built-in types (or any PODs for that matter)? You can't do it
> with non-PODs, however.
>
> V[/color]

Krishanu

re: Fastest way to zero a vector?

Victor Bazarov wrote:[color=blue]
> Joseph Turian wrote:[color=green]
> > 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".[/color]
>
> How about
>
> memset(&bob[i], 0, N*sizeof(bob[i]));
>
> for built-in types (or any PODs for that matter)? You can't do it
> with non-PODs, however.
>
> V[/color]

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

re: Fastest way to zero a vector?

Krishanu Debnath wrote:[color=blue]
> Victor Bazarov wrote:
>
> [snip]
>[color=green]
>>
>>
>> How about
>>
>> memset(&bob[i], 0, N*sizeof(bob[i]));[/color]
>
>
> Considering bob is array of T(built-in type) of N elements, it certainly
> invokes
> undefined behavior.[/color]

Right. I meant to use bob[0] not bob[i], 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

re: Fastest way to zero a vector?

Victor Bazarov wrote:[color=blue]
> Krishanu Debnath wrote:
>[color=green]
>> Victor Bazarov wrote:
>>
>> [snip]
>>[color=darkred]
>>>
>>>
>>> How about
>>>
>>> memset(&bob[i], 0, N*sizeof(bob[i]));[/color]
>>
>>
>>
>> Considering bob is array of T(built-in type) of N elements, it
>> certainly invokes
>> undefined behavior.[/color]
>
>
> Right. I meant to use bob[0] not bob[i], of course. Or did you mean[/color]

Why bob[0]? You want to reset whole array, right? So it should be
memset(bob, 0, N * sizeof(*bob));
[color=blue]
> something else? Please consider explaining your point of view instead
> of just stating it so I don't have to guess. Thanks.
>
> V[/color]

Krishanu

re: Fastest way to zero a vector?

Victor Bazarov wrote:
[color=blue]
> How about
>
> memset(&bob[i], 0, N*sizeof(bob[i]));
>
> for built-in types (or any PODs for that matter)? You can't do it
> with non-PODs, however.[/color]


Forgive my ignorance; What's a POD?

Joseph

re: Fastest way to zero a vector?

Krishanu Debnath wrote:[color=blue]
> Victor Bazarov wrote:
>[color=green]
>> Krishanu Debnath wrote:
>>[color=darkred]
>>> Victor Bazarov wrote:
>>>
>>> [snip]
>>>
>>>>
>>>>
>>>> How about
>>>>
>>>> memset(&bob[i], 0, N*sizeof(bob[i]));
>>>
>>>
>>>
>>>
>>> Considering bob is array of T(built-in type) of N elements, it
>>> certainly invokes
>>> undefined behavior.[/color]
>>
>>
>>
>> Right. I meant to use bob[0] not bob[i], of course. Or did you mean[/color]
>
>
> Why bob[0]? You want to reset whole array, right? So it should be
> memset(bob, 0, N * sizeof(*bob));[/color]

'&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

re: Fastest way to zero a vector?

Plain Old Datatype.

re: Fastest way to zero a vector?

Joseph Turian wrote:[color=blue]
> Forgive my ignorance; What's a POD?[/color]

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

Krishanu Debnath wrote:
[color=blue]
> Why bob[0]? You want to reset whole array, right? So it should be
> memset(bob, 0, N * sizeof(*bob));[/color]

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

Joseph

re: Fastest way to zero a vector?

Joseph Turian wrote:[color=blue]
> Victor Bazarov wrote:
>
>[color=green]
>>How about
>>
>> memset(&bob[i], 0, N*sizeof(bob[i]));
>>
>>for built-in types (or any PODs for that matter)? You can't do it
>>with non-PODs, however.[/color]
>
>
>
> Forgive my ignorance; What's a POD?[/color]

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

re: Fastest way to zero a vector?

Joseph Turian wrote:[color=blue]
> Joseph Turian wrote:
>[color=green]
>>Forgive my ignorance; What's a POD?[/color]
>
>
> Ah, got it.
> http://www.parashift.com/c++-faq-lit....html#faq-26.7
>
> Krishanu Debnath wrote:
>
>[color=green]
>>Why bob[0]? You want to reset whole array, right? So it should be
>>memset(bob, 0, N * sizeof(*bob));[/color]
>
>
> Wait, bob is vector<bool>, so you can't memset it.
> Is the suggestion that I use a raw array?[/color]

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

re: Fastest way to zero a vector?

"Krishanu Debnath" <krishanu@cal.interrasystems.com> wrote in message
news:429dd334$0$18648$14726298@news.sunsite.dk...[color=blue]
> Victor Bazarov wrote:[color=green]
>> Krishanu Debnath wrote:
>>[color=darkred]
>>> Victor Bazarov wrote:
>>>
>>> [snip]
>>>
>>>>
>>>>
>>>> How about
>>>>
>>>> memset(&bob[i], 0, N*sizeof(bob[i]));
>>>
>>>
>>>
>>> Considering bob is array of T(built-in type) of N elements, it certainly
>>> invokes
>>> undefined behavior.[/color]
>>
>>
>> Right. I meant to use bob[0] not bob[i], of course. Or did you mean[/color]
>
> Why bob[0]? You want to reset whole array, right? [SNIP][/color]

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

Cheers
Chris

re: Fastest way to zero a vector?

"Joseph Turian" <turian@gmail.com> wrote in message
news:1117640328.341065.223860@g43g2000cwa.googlegr oups.com...[color=blue]
>
>
> Victor Bazarov wrote:
>[color=green]
>> How about
>>
>> memset(&bob[i], 0, N*sizeof(bob[i]));
>>
>> for built-in types (or any PODs for that matter)? You can't do it
>> with non-PODs, however.[/color]
>
>
> Forgive my ignorance; What's a POD?
>[/color]

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-lit....html#faq-26.7

Cheers
Chris

re: Fastest way to zero a vector?

Victor Bazarov wrote:[color=blue]
> bob = vector<bool>(bob.size());[/color]
Object creation is slow, this is the version I started with.
[color=blue]
> vector<bool>(bob.size()).swap(bob);[/color]
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.
[color=blue]
> bob.assign(bob.size(), false);[/color]
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

re: Fastest way to zero a vector?

Joseph Turian wrote:[color=blue]
> Victor Bazarov wrote:
> [..][color=green]
>> bob.assign(bob.size(), false);[/color]
>
> I didn't even know that this function existed. It's not in the STL
> docs:
> http://www.sgi.com/tech/stl/Vector.html[/color]

You should use up-to-date documentation. Like a copy of the Standard,
for example, or the docs for your compiler (hopefully, recent).
[color=blue]
> Is it standard? (Just curious)[/color]

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...
[color=blue]
> [...][/color]

V

re: Fastest way to zero a vector?

Victor Bazarov wrote:
[color=blue]
> BTW, I usually try to avoid recommending non-standard code here.
> Just so that you know...[/color]

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

Thank you for recommendations

Joseph

re: Fastest way to zero a vector?

Victor Bazarov wrote:[color=blue]
> Joseph Turian wrote:
>[color=green]
>> 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);
>>[/color][/color]
[color=blue]
>
> How about
>
> memset(&bob[i], 0, N*sizeof(bob[i]));
>
> for built-in types (or any PODs for that matter)? You can't do it
> with non-PODs, however.[/color]

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

re: Fastest way to zero a vector?

Victor Bazarov wrote:[color=blue]
> Joseph Turian wrote:
>[color=green]
>> Victor Bazarov wrote:
>>
>>[color=darkred]
>>> How about
>>>
>>> memset(&bob[i], 0, N*sizeof(bob[i]));
>>>
>>> for built-in types (or any PODs for that matter)? You can't do it
>>> with non-PODs, however.[/color]
>>
>>
>>
>>
>> Forgive my ignorance; What's a POD?[/color]
>
>
> It's a TLA. And it's in the FAQ. Please read the FAQ before posting.[/color]

What's a TLA? (I checked the FAQ too)

re: Fastest way to zero a vector?

Mark P wrote:[color=blue]
> Victor Bazarov wrote:[color=green]
>>
>> It's a TLA. And it's in the FAQ. Please read the FAQ before posting.[/color]
>
>
> What's a TLA? (I checked the FAQ too)[/color]

Er, nevermind. Figured it out... :)

re: Fastest way to zero a vector?

Joseph Turian wrote:[color=blue]
> 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.[/color]

Since N<=3 how about storing within a larger POD type? e.g.

// implementation
typedef int FullBob;
typedef bool BoolBob[4];
// spare entries not used (could store N if required)

inline void ZeroBob(BoolBob& bob)
{
reinterpret_cast<FullBob&>(bob) = 0;
}

// compile time size validation
template<bool test> inline bool CheckBob()
{
return true;
}

template<> inline bool CheckBob<false>()
{
// no return value
}

int main()
{
CheckBob<sizeof(BoolBob)==sizeof(FullBob)>();

// example usage
BoolBob bob;
ZeroBob(bob);
bob[0] = true;
}

Having bob aligned in memory (e.g. choose FullBob type to be 32 bit on 32
bit architechure) may provide a benefit provided the extra memory usage (if
many bob's exist) isn't an issue.

There are plenty of alternative implemention methods of the above idea (e.g.
unions, custom class). A union might provide more reliable memory alignment.
[color=blue]
> I'm trying to get this to be really fast, so I'll entertain any
> so-called "extreme solution".[/color]


To really guage performance you'll need to time various implementations as
they would typically be used. If this really is a bottleneck in a slowly
performing application then I'd suggest that a redesign at a higher level
would be more beneficial.

Regards,
cadull

re: Fastest way to zero a vector?

Mark P <not@my.real.email>:
[color=blue]
> What's a TLA? (I checked the FAQ too)[/color]

You can ask google with "define: tla"

Maett

re: Fastest way to zero a vector?

Maett wrote:[color=blue]
> Mark P <not@my.real.email>:
>[color=green]
>> What's a TLA? (I checked the FAQ too)[/color]
>
>
> You can ask google with "define: tla"
>
> Maett[/color]

Neat. I had tried google before eventually figuring it out on my own,
but didn't know about the define: command and received unhelpful results.