Sign in to follow this  
Storyyeller

maximum size of a bitset?

Recommended Posts

Storyyeller    215
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?

Share this post


Link to post
Share on other sites
Storyyeller    215
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;
}

Share this post


Link to post
Share on other sites
Drew_Benton    1861
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:

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

Share this post


Link to post
Share on other sites
Storyyeller    215
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]

Share this post


Link to post
Share on other sites
frob    44974
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.

Share this post


Link to post
Share on other sites
Zahlman    1682
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?

Share this post


Link to post
Share on other sites
Storyyeller    215
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.

Share this post


Link to post
Share on other sites
Storyyeller    215
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

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


Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this