3D Array of Bool

This is a discussion on 3D Array of Bool within the C++ Programming forums, part of the General Programming Boards category; I program with the g++ compiler on a linux workstation. I am testing a very simple program that has only ...

  1. #1
    Registered User
    Join Date
    Jun 2007
    Posts
    30

    3D Array of Bool

    I program with the g++ compiler on a linux workstation. I am testing a very simple program that has only a 1000x1000x1000 array of boolean variables. I thought each boolean variable occupied only one bit. So the program would require appromixately 10^9 bits ~= 119 megabytes of RAM. However, the system monitor tells me that the program requires about 976 megabytes of RAM.

    Why?

    Thanks.

  2. #2
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    a bool is a byte in size, generally.

  3. #3
    Registered User
    Join Date
    Jun 2007
    Posts
    30
    O..that explains why. But why would it use 1 byte if 1 bit can already represent 0 or 1. Anyway, is there any data type that uses only 1 bit? For what I am doing, even a 1000x1000x1000 array would not be enough.

    Thanks.

  4. #4
    Registered User Queatrix's Avatar
    Join Date
    Apr 2005
    Posts
    1,342
    >> But why would it use 1 byte if 1 bit can already represent 0 or 1.
    Because bool doesn't just hold true or false, it also hold integers.

    >> For what I am doing, even a 1000x1000x1000 array would not be enough.
    If you're worried about room, make a matrix of chars instead, and alter each bit (0x80 for starters) to hold your "bool" value; so that way one char holds 8 "varibles".

  5. #5
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    Quote Originally Posted by cybernike View Post
    O..that explains why. But why would it use 1 byte if 1 bit can already represent 0 or 1. Anyway, is there any data type that uses only 1 bit? For what I am doing, even a 1000x1000x1000 array would not be enough.

    Thanks.
    The way memory is structured it would probably be wasteful and time consuming traversing the whole of memory by bits.

  6. #6
    Registered User
    Join Date
    Jun 2007
    Posts
    30
    >>If you're worried about room, make a matrix of chars instead, and alter each >>bit (0x80 for starters) to hold your "bool" value; so that way one char holds 8>> "varibles".

    Would you please elaborate more? or give me a reference? It seems to be a good solution for my problem.

    Thanks.

  7. #7
    Registered User
    Join Date
    Dec 2005
    Location
    Canada
    Posts
    267
    is there any data type that uses only 1 bit?
    bitsets

    [edit]
    >>Would you please elaborate more? or give me a reference? It seems to be a good solution for my problem.

    a char can hold 8bits worth of data. you can use each bit as a seperate variable, for example:
    if you want to store the values true in the first bit of a char...
    Code:
    char a;
    a |= true*2^0; //the zero is like the array index (if you were using an array)
    a |= true*2^1; //stores true in the second bit
    // and so on...
    //i think this is how a bit goes from true to false
    if (a & 2^0) //checks if the first bit is true
        a ^= true*2^0; //if so, xor it with true to change it to false
    the 2^x in bold means 2 to the power of x, not xor. i think having it written this way makes the (pseudo)code slightly clearer
    Last edited by h_howee; 06-26-2007 at 08:51 PM.

    OS: Windows 7, XUbuntu 11.10, Arch Linux
    IDE: CodeBlocks
    Compiler: GCC

  8. #8
    semi-colon generator ChaosEngine's Avatar
    Join Date
    Sep 2005
    Location
    Chch, NZ
    Posts
    597
    Quote Originally Posted by Queatrix View Post
    >> But why would it use 1 byte if 1 bit can already represent 0 or 1.
    Because bool doesn't just hold true or false, it also hold integers.
    what the hell are you talking about?
    "I saw a sign that said 'Drink Canada Dry', so I started"
    -- Brendan Behan

    Free Compiler: Visual C++ 2005 Express
    If you program in C++, you need Boost. You should also know how to use the Standard Library (STL). Want to make games? After reading this, I don't like WxWidgets anymore. Want to add some scripting to your App?

  9. #9
    Registered User
    Join Date
    Jun 2007
    Posts
    30
    Quote Originally Posted by h_howee View Post
    bitsets

    [edit]
    >>Would you please elaborate more? or give me a reference? It seems to be a good solution for my problem.

    a char can hold 8bits worth of data. you can use each bit as a seperate variable, for example:
    if you want to store the values true in the first bit of a char...
    Code:
    char a;
    a |= true*2^0; //the zero is like the array index (if you were using an array)
    a |= true*2^1; //stores true in the second bit
    // and so on...
    //i think this is how a bit goes from true to false
    if (a & 2^0) //checks if the first bit is true
        a ^= true*2^0; //if so, xor it with true to change it to false
    the 2^x in bold means 2 to the power of x, not xor. i think having it written this way makes the (pseudo)code slightly clearer
    Thanks, the syntax is probably too cumbersome for my problem. You once mentioned bitsets and I played with it. However, both bitset<1> and bitset<8> use 4 bytes after I checked with the function sizeof( ). Why?

  10. #10
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,337
    > both bitset<1> and bitset<8> use 4 bytes after I checked with the function sizeof( ). Why?
    They're still going to use the smallest amount of allocatable storage, no matter how few bits you choose.
    Try something like say 1000 or 2000, then you should see the benefit if it really is using just bits internally.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  11. #11
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    I'm surprised that no one mentioned vector<bool>, which unlike bitset<> can be used if the size is determined at runtime. It has issues, but is worth knowing about, since even if it's removed from a future version of the standard, the functionality will probably be duplicated somehow.

    http://www.informit.com/guides/conte...seqNum=98&rl=1

  12. #12
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,262
    Yeah guys, why no vector<bool> mentions?
    Or in this case:
    Code:
    vector< vector< vector<bool> > >
    Yes I know that the explicit specialisation is a hack that doesn't work exactly the same as every other data type, but for most purposes it works fine.
    I'm sure boost has something better though.

    I presume this is for voxel data? Have you considered compressing it? (beyond using 1-bit per voxel of course)
    I mean you could probably use something like RLE to compress it in such a way that you can still quickly determine the status of an individual voxel. Reducing the memory usage by even say a factor of four would probably still provide a speed increase after decompression, as memory would probably be your bottleneck. Of course it depends on how often you write to it. If it is read in and then not changed, doing this should be sweet as!
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  13. #13
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    I'd say if he wants to test each bit then he should use a vector of bitsets. That way each element can be however wide he would like and he can easily access, test, and set each bit.

  14. #14
    Registered User
    Join Date
    Jan 2007
    Posts
    330
    Why do you need 10^9 bools anyway?

  15. #15
    Registered User
    Join Date
    Jun 2007
    Posts
    30
    Quote Originally Posted by iMalc View Post
    Yeah guys, why no vector<bool> mentions?
    Or in this case:
    Code:
    vector< vector< vector<bool> > >
    Yes I know that the explicit specialisation is a hack that doesn't work exactly the same as every other data type, but for most purposes it works fine.
    I'm sure boost has something better though.

    I presume this is for voxel data? Have you considered compressing it? (beyond using 1-bit per voxel of course)
    I mean you could probably use something like RLE to compress it in such a way that you can still quickly determine the status of an individual voxel. Reducing the memory usage by even say a factor of four would probably still provide a speed increase after decompression, as memory would probably be your bottleneck. Of course it depends on how often you write to it. If it is read in and then not changed, doing this should be sweet as!
    You are right that it is for voxel data (I had to look up what voxel means). I am writing a Monte Carlo program that describes brownian motions.
    I will definitely look into RLE, if it could reduce memory usage and still provide a speed increase. However, I always thought a compression would usually slow things down? not true? Also, I need to constantly change the true/false values in the array, since the particles move.
    Last edited by cybernike; 06-27-2007 at 09:03 AM.

Page 1 of 3 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 16
    Last Post: 05-29-2009, 07:25 PM
  2. Code review
    By Elysia in forum C++ Programming
    Replies: 71
    Last Post: 05-13-2008, 09:42 PM
  3. DirectInput help
    By Muphin in forum Game Programming
    Replies: 2
    Last Post: 09-10-2005, 11:52 AM
  4. How do I play an MP3?
    By Hunter2 in forum Windows Programming
    Replies: 28
    Last Post: 05-20-2002, 08:49 PM
  5. 3d array
    By Pamela in forum C++ Programming
    Replies: 1
    Last Post: 10-24-2001, 03:59 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21