Fast way to check list of 0 or 1 values?

What is the fastest way to look up a list for 0 or 1 values?

I used an Array which was very fast like:

Code:

---

int boolList[5000];

---

and each entry would either have a value of 0 or 1.

I would then check this like:

Code:

---

if (boolList[i])

---

...but that needs to be initialized to a set number of entries. I would like to be able to have the same speed but also be able to set number of entries at runtime. A linked list would be a lot slower right? The predefined lists I tested with was but I'm not sure how much bulk they had. Ideas?

If you want an array whose size is determined at runtime, then the most obvious choice is vector.

Quote:

---

Originally Posted by anon

If you want an array whose size is determined at runtime, then the most obvious choice is vector.

---

Nevermind.:)

Vector reference.

Ok I tried with vector now but it is about 30% slower than with an Array in my test case.

Could it be worth having a pointer to an Array and deleting and recreating the Array at runtime instead? Can you even do that?

vector<bool> , although this is a special specialisation of vector

Quote:

---

Originally Posted by DrSnuggles

Ok I tried with vector now but it is about 30% slower than with an Array in my test case.

Could it be worth having a pointer to an Array and deleting and recreating the Array at runtime instead? Can you even do that?

---

That is exactly what the vector does.

Would you mind posting some code that you are worrying about?

Consider a bitset.

Ok, I tried a few things and timed them, here are the results. Not very high values overall but they were consistent anyways.

Array: 0.078 sec
vector<int>: 0.094 sec
bitset: 0.156 sec
vector<bool>: 0.172 sec
Tab<int> : 0.203 sec

Array is still the fastest by quite a lot. Need to find a way to use something similar.

What compiler are you using?

Those times don't mean anything without code. Array does not seem a lot faster than a vector in those timings, and you said you won't be able to use an array anyway.

Quote:

---

Originally Posted by Elysia

What compiler are you using?

---

Visual Studio 2008 pro

Quote:

---

Originally Posted by anon

Those times don't mean anything without code. Array does not seem a lot faster than a vector in those timings, and you said you won't be able to use an array anyway.

---

What I'm doing is actually intersecting a 3d object(60000 tris) 1000 times. For each triangle I check if the value in the list is 0 or 1. Quite a lot of code involved but this is the difference in time if I use the different types to get and set the 0 or 1 values. Nothing else is different so those are real differences. Did a test now with 10000 intersections and for Array the time was 0.703 and vector<int> 0.938. That is quite a lot more intersections I could squeeze in for the time difference between those...something like 3300 more if I use Array.

I probably won't be able to use an Array no which is too bad. If I can't find another way the vector<int> will have to do.

Try using a vector<char> to make it 4 or 8 times smaller than vector<int>. Making the vector smaller could allow more of it to stay in the CPU cache.
Also, try calling vector::reserve() to reserve a large size first before you start using your vector. If you can reduce the number of reallocations the vector does, it could speed things up.

Can I just point out that there's no way that you can get faster than an array - other solutions will be SIMILAR speed, but likely never quite as fast.

If you just need to know at runtime how large your array should be, you could use dynamic memory allocation, but that [at least sometimes] adds an extra memory read to fetch the pointer to the memory block that contains your array.

Edit: As suggested, using a byte-size entry (char or bool) would increase performance of walking through the array due to less cache pollution.

--
Mats

Quote:

---

Array: 0.078 sec
vector<int>: 0.094 sec
bitset: 0.156 sec
vector<bool>: 0.172 sec
Tab<int> : 0.203 sec

---

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...

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

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

Quote:

---

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...

---

Quote:

---

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.

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

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;).

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

Quote:

---

Originally Posted by anon

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

---

Quote:

---

Originally Posted by DrSnuggles

Visual Studio 2008 pro

---

I'm guessing the answer is "yes".