Fast way to check list of 0 or 1 values?

**matsp** · 08-04-2008

But vector<bool> is a "special" specialization, and it stores each value in a single bit, which makes the math to get the value back out again a whole lot more complex because of the bit-logical operaitons need to find individual value. I can certainly see how that would make a 3-fold slowdown - it takes roughly three times more instructions, most of which depend on the previous instruction [so no place for the processor to make use of it's superscalar nature].

--
Mats

**Elysia** · 08-04-2008

Try adding...
#define _SECURE_SCL 0
...BEFORE including the vector header and re-do the tests.

**cpjust** · 08-04-2008

Originally Posted by MarkZWEERS

Well, 'vector<int>' is not bad at all! This is just the price for the generic programming part. What does surprise me, however, is that the 'vector<bool>' is so much slower than the 'int' specialisation.
I think this is due to the abscence of what cpjust is suggesting: the member function "reserve(..)". The boolean specialisation should be faster than the int specialisation, as matsp says....

In general, if speed is an enourmous constraint on your design, your application is extremely critical etc etc, use an array. If not, use a container from the library. Simply because you don't have to care anymore about what's behind and because it's so much more generic...

Originally Posted by matsp

But vector<bool> is a "special" specialization, and it stores each value in a single bit, which makes the math to get the value back out again a whole lot more complex because of the bit-logical operaitons need to find individual value. I can certainly see how that would make a 3-fold slowdown - it takes roughly three times more instructions, most of which depend on the previous instruction [so no place for the processor to make use of it's superscalar nature].

--
Mats

Yes, vector<bool> sucks because of a "feature" they added to the standard as an example of using proxy objects... Unfortunately their experiment remained in the standard.
If you really want a vector<bool> then I'd suggest using a deque<bool> or a basic_string<bool> which do actually store bools rather than packed bits...
But if you're just storing 0 or 1 numeric values vector<char> is fine.

**DrSnuggles** · 08-05-2008

Hey, thanks for all the input. I'm now using a vector<char>. I don't have the exact same test situation as last time and the code now also invloves zeroing out all values before each intersection. The timing for Array and vector<char> is pretty much the same, around 0.062 sec for 1000 intersections on 60000 tris (also using an octree(which sets values in the list)). Could be that using vector.assign(num,0) is faster for zeroing out all than using a for loop to reset the Array.

I'm only setting the size of the vector once outside of the intersection code so using reserve() did not contribute a lot.

Using #define _SECURE_SCL 0 did not produce any difference in my case.

Cheers

**Elysia** · 08-05-2008

Can you try both
#define _HAS_ITERATOR_DEBUGGING 0
#define _SECURE_SCL 0
before including vector, then?
They give me a significant speed boost (~20&#37

.

**anon** · 08-05-2008

Has DrSnuggles even mentioned that he is using VC++?

**tabstop** · 08-05-2008

Originally Posted by anon

Has DrSnuggles even mentioned that he is using VC++?

Originally Posted by DrSnuggles

Visual Studio 2008 pro

I'm guessing the answer is "yes".

Thread: Fast way to check list of 0 or 1 values?

Thread Tools

Search Thread

Display

Similar Threads

Sorting linked list please help with CODE

Need help sorting a linked list. Beginner

Please Help - Problem with Compilers

Linked List