maximum size of a bitset?
Author
When I create a bitset of size 24^5, everything is fine, but when I try to create one of size 25^5, it crashes. I highly doubt it is due to memory constraints, since that's barely a megabyte.
What is going on?
Author
Sorry, I'm using C++
class SpaceArray{ static const uint RES = 24; std::bitset<RES * RES * RES * RES * RES> deadly; std::bitset<RES * RES * RES * RES * RES> sure;}
The problem you are seeing isn't related to the bitset class as much as just how much memory you are trying to allocate on the stack when you don't create a SpaceArray object on the heap.
Basic example:
If you are using Visual Studio, you can increase the size of the stack by going to Project -> Properties -> Configuration Properties -> Linker -> System -> Stack Reserve Size and make it something much larger, for example like 8000000. (additional reading)
Once you do that, you can uncomment the first line of the example program above and it no longer crashes. Alternatively, when you have such large objects, you can allocate on the heap or from a pool instead.
Basic example:
#include <bitset>class SpaceArray{ static const int RES = 24; std::bitset<RES * RES * RES * RES * RES> deadly; std::bitset<RES * RES * RES * RES * RES> sure;};int main(int argc, char * argv[]){ //SpaceArray onStack; // crashes printf("sizeof(SpaceArray) - %i\n", sizeof(SpaceArray)); SpaceArray * onHeap = new SpaceArray; // won't crash, unless new fails delete onHeap; return 0;}If you are using Visual Studio, you can increase the size of the stack by going to Project -> Properties -> Configuration Properties -> Linker -> System -> Stack Reserve Size and make it something much larger, for example like 8000000. (additional reading)
Once you do that, you can uncomment the first line of the example program above and it no longer crashes. Alternatively, when you have such large objects, you can allocate on the heap or from a pool instead.
Author
Ok I changed it to a heap allocation and it works now. Thanks!
Edit: I have another question
Does std::bitset have any support for binary file i/o?
[Edited by - Storyyeller on May 1, 2010 1:12:57 PM]
Edit: I have another question
Does std::bitset have any support for binary file i/o?
[Edited by - Storyyeller on May 1, 2010 1:12:57 PM]
Quote:Original post by Storyyeller
Does std::bitset have any support for binary file i/o?
No.
The language is very careful to give each class only a single responsibility.
File IO is handled in the fstream family of classes.
Bitsets have a function to attempt to extract the bits as a single unsigned long, and also have a function to extract it as a string, with '1' or '0' for each bit. They also have corresponding constructors.
In order to serialize a bitset, it would need to fit within an unsigned long or you would need to process the extracted string.
Trying to use a bitset for this is the wrong approach.
The std::bitset class is not really designed for more than a machine word. Trying to read or write anything larger than an unsigned long at a time is not directly supported. Many implementations have nonstandard 64-bit extensions, but that's about it. Any larger value will need to be interpreted as strings, which are 8x the size.
The bitset class is designed for, and generally works best on, small numbers of bits. Most implementations give specializations for 8, 16, 32, and 64 bit containers. Anything more and the class becomes unwieldy.
If you want to store 25^5 bits, or nearly 10 million bits, you will want to go with your own bit-manipulation functions, with your own class designed to work on such large data sets.
Author
How would anything I write be more efficient the the authors of the standard libraries?
In general, because of being specifically designed for your particular problem (which the standard library writers can't anticipate).
In particular, maybe it couldn't be. It also depends on who is doing the writing. ;)
If you are not using C++0x, you might try std::vector<bool>, which in the 98 standard is a specialization of the vector template that is space-optimized (the bits are packed together). (Many people thought this was a mistake because it means that elements of the vector don't have their own memory addresses.)
But let me first ask: Why do you need this data structure? What is it for?
In particular, maybe it couldn't be. It also depends on who is doing the writing. ;)
If you are not using C++0x, you might try std::vector<bool>, which in the 98 standard is a specialization of the vector template that is space-optimized (the bits are packed together). (Many people thought this was a mistake because it means that elements of the vector don't have their own memory addresses.)
But let me first ask: Why do you need this data structure? What is it for?
Author
The problem is that I have a 2d space game where each player controls a satellite that orbits around the moon and shoot at each other. Everything follows simple Newtonian gravity of the moon, and warps around when going off the edge of the screen. On each tick, they can shoot, accelerate, and or rotate to either side.
My problem is the ai. Sometimes, when attempting to dodge a bullet, my ai will accidentally get on a collision path with the moon.
My idea was to divide up the phase space into a 5d grid, and then precompute a big lookup table of whether each space is probably safe, or probably deadly. It's not perfect, but I figured it would likely make the ai much less likely to crash.
Anyway thats what I'm using the bitsets for. Two bits- one to mark if a spot is deadly, and one to mark if a spot has been processed yet.
My problem is the ai. Sometimes, when attempting to dodge a bullet, my ai will accidentally get on a collision path with the moon.
My idea was to divide up the phase space into a 5d grid, and then precompute a big lookup table of whether each space is probably safe, or probably deadly. It's not perfect, but I figured it would likely make the ai much less likely to crash.
Anyway thats what I'm using the bitsets for. Two bits- one to mark if a spot is deadly, and one to mark if a spot has been processed yet.
Author
Just out of curiosity, I decided to try writing my own class. It was around 2.6% slower then the bitset when tested at SIZE=16. Either I did something wrong, or std::bitset really is better. (Or both most likely)
Here's what I tried
Here's what I tried
template <unsigned int SIZE>class DualBitArray3{ typedef unsigned int uint; static const uint BITSETSIZE = SIZE * SIZE * SIZE * SIZE * SIZE; static const uint NUMBITS = BITSETSIZE * 2; static const uint INTSIZE = sizeof(uint); static const uint NUMINTS = (NUMBITS + INTSIZE - 1) / INTSIZE; boost::array<uint, NUMINTS> data; bool ischanged; void SetBit(uint b, bool val) { uint i = b / INTSIZE; uint bit = b % INTSIZE; if (val) { data.at(i) |= (1 << bit); } else { data.at(i) &= ~(1<<bit); } } bool GetBit(uint b) const { uint i = b / INTSIZE; uint bit = b % INTSIZE; return data.at(i) & (1<<bit); } public: DualBitArray3() : ischanged(false) { Reset(); } void Reset() { for(uint i = 0; i<data.size(); ++i) { data.at(i) = 0; } } bool Valid(uint i) const {return i<BITSETSIZE;} bool IsDeadly(uint i) const {return GetBit(i*2);} bool IsFixed(uint i) const {return GetBit(i*2+1);} void SetDeadly(uint i, bool val) {SetBit(i*2, val);} void SetFixed(uint i, bool val){ischanged = true; SetBit(i*2+1, val);} bool Changed() {return QueryAndReset(ischanged);}};This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement