Is an array of bools also "optimized", like a vector<bool> is? I want to make arrays of true or false, but I also dont want the problems that some with vector<bool> to show up in an array, such as slow access times
-
what exactly do you need? memory efficient storage? fast? sparse? growable? want to access it like it were an array, etcetc..Karoly Horvath– Karoly Horvath2011-07-10 22:58:14 +00:00Commented Jul 10, 2011 at 22:58
-
The good way of understanding it - is by sitting in front of your computer with a debuger.Ulterior– Ulterior2011-07-10 22:58:38 +00:00Commented Jul 10, 2011 at 22:58
-
i want to access individual values in a 2d array quicklycalccrypto– calccrypto2011-07-10 22:59:11 +00:00Commented Jul 10, 2011 at 22:59
-
"2d array"? What has this to do with your original question??Kerrek SB– Kerrek SB2011-07-10 23:00:57 +00:00Commented Jul 10, 2011 at 23:00
-
2I think we can say one thing for sure: At the basic design stage, do not worry about how an array of bools is laid out. It's not even guaranteed yet that bool access will be a bigger bottleneck than your big network coding bug ;-)Kerrek SB– Kerrek SB2011-07-10 23:08:49 +00:00Commented Jul 10, 2011 at 23:08
|
Show 3 more comments
3 Answers
bool[N] will occupy N times sizeof(bool) contiguous bytes in memory.
5 Comments
BugShotGG
This will use 1 byte per bool element right? I would also like to know how to make it use only a bit for each but i guess this is not easily implemented right?
Kerrek SB
@GeoPapas: Such an optimization has been implemented for you in
std::vector<bool>, written by professionals.BugShotGG
Thanks for your reply, I would like to implement a fast bool array for use in cuda. Would this std::vector<bool> implementation be suficient and fast? From what i ve heard this is only for minimal space management but not for optimal speed. Any suggestions? Thanks in advance!
BugShotGG
Hmm i found out that it says:
Simultaneous access to different elements is not guaranteed to be thread-safe (as storage bytes may be shared by multiple bits). Maybe that is not suitable for cuda.Kerrek SB
@GeoPapas: That's a complex question with lots of details and trade-offs.
std::vector<bool> doesn't guarantee any specific implementation, and in any case it'd be difficult to use with CUDA memory. Maybe Thrust has a packed bitset? But as you said, sharing can be a terrible, terrible performance problem.Optimized for speed is one bool per word so it doesn't need to do masking and read-modify-write operations. Optimized for space would be to pack 32 bools per word, so you have to be more specific about what "optimized" means.
3 Comments
calccrypto
optimized as in how
vector<bool> fails
Phil Miller
Experienced C++ people will recognize what you mean when you say 'optimized' in scare quotes, but it's much preferable to be explicit. As best I can tell, you are asking whether any aggregation of
bools gets packed, or just vector<bool>. You should say so directly, and not hint at it.
Karoly Horvath
upvoted it, seems perfectly fine to me. calccrypto, have you downvoted this?
I think the C++ default implementation is mainly for saving the space, while the access time may be affected.
if you need quicker access time, you may have implement it by yourself and sacrifice the space.
2 Comments
Jerry Coffin
Note, however, that in many cases the effect on access time is positive. The smaller representation lets more fit in a cache.
edA-qa mort-ora-y
Err, No, Kerrek SB's answer is correct. An array must occupy
N * sizeof(bool) memory which implies zero space optimization.