How to build N bits variables in C++?

Question

I am dealing with very large list of booleans in C++, around 2^N items of N booleans each. Because memory is critical in such situation, i.e. an exponential growth, I would like to build a N-bits long variable to store each element.

For small N, for example 24, I am just using unsigned long int. It takes 64MB ((2^24)*32/8/1024/1024). But I need to go up to 36. The only option with build-in variable is unsigned long long int, but it takes 512GB ((2^36)*64/8/1024/1024/1024), which is a bit too much. With a 36-bits variable, it would work for me because the size drops to 288GB ((2^36)*36/8/1024/1024/1024), which fits on a node of my supercomputer.

I tried std::bitset, but std::bitset< N > creates a element of at least 8B. So a list of std::bitset< 1 > is much greater than a list of unsigned long int. It is because the std::bitset just change the representation, not the container.

I also tried boost::dynamic_bitset<> from Boost, but the result is even worst (at least 32B!), for the same reason.

I know an option is to write all elements as one chain of booleans, 2473901162496 (2^36*36), then to store then in 38654705664 (2473901162496/64) unsigned long long int, which gives 288GB (38654705664*64/8/1024/1024/1024). Then to access an element is just a game of finding in which elements the 36 bits are stored (can be either one or two). But it is a lot of rewriting of the existing code (3000 lines) because mapping becomes impossible and because adding and deleting items during the execution in some functions will be surely complicated, confusing, challenging, and the result will be most likely not efficient.

How to build a N-bits variable in C++?

Radian

How about ::std::vector<bool>? It is a good choice if you need to store large amount of bits. – Ilario

How about just using a std::array<uint8_t> or std::vector<uint8_t> of size number_of_bits_needed/sizeof(uint8_t) ? – Kovacs

Rather than a sequence of unsigned long long, why not a single dynamic_bitset? Then finding element X becomes as simple as going N*X bits in. That simplifies the logic around using it (and you can abstract on top of that) while still being minimal space. The main thing missing is insertion/deletion that isn't at the back. – Mendiola

I think it's reasonable to require quite a bit of rewriting if the fundamental data structures your architecture is based upon are changed. This is why it's usually best to figure out the important data structures first, before writing any code ;-) – Jello

@VTT A std::vector<bool> takes 40o, so it is not helping (and not recommended in any case). – Inspirit

What do you mean by "takes 40o"? – Ilario

@JesperJuhl Using a container of uint8_t or unsigned long long int is formally the same thing, however, uint8_t have more change that 36 bits are scatered between elements of the container. – Inspirit

@Mendiola Yes, a dynamic_bitset can help indeed, if size_type can be an unsigned long long int, which does not seems to be the case with my preliminary tests. – Inspirit

You cannot have a variable which has fractional sizeof. The best you can do is to round up to sizeof(char). So, for the 36-bit example, on a 8-bit char machine, you can have a type which has storage for 40-bits (5 bytes). On x86 architectures, it won't be that slow, as unaligned access is supported. So you can convert from/to 5-byte variable into unsigned long long pretty fast. – Insult

@VTT I made a typo, it is 40B. I meant that the container itself is 40B. – Inspirit

Use of vector<bool> implies that you will store all 2^N bits in a single container. If you need to reference a pack of N items you can just use a range in vector. – Ilario

@Insult This is great ! It tried quickly, I can indeed make 5B variables. It can fit in memory because it will take only 320GB, and the changes are very little effort (unsigned long long int to the name of my struct of 5 unsinged char and a function to convert from one to another). – Inspirit

38654705664*64/8/1024/1024/1024 gives 288GB, not MB – Assimilate

bitset2 provides an alternative to std::bitset. You can specify the underlying type to be uint8_t. Then sizeof( bitset2<36,uint8_t> )= 5 while sizeof( bitset2<36> )= 8. The latter on a 64-bit machine. – Desalinate

@ClaasBontus Nice, it is very a convenient library! – Inspirit

Answer 1

How about a struct with 5 chars (and perhaps some fancy operator overloading as needed to keep it compatible to the existing code)? A struct with a long and a char probably won't work because of padding / alignment...

Basically your own mini BitSet optimized for size:

struct Bitset40 {
   unsigned char data[5];
   bool getBit(int index) {
     return (data[index / 8] & (1 << (index % 8))) != 0;
   }
   bool setBit(int index, bool newVal) {
     if (newVal) {
        data[index / 8] |= (1 << (index % 8));
     } else {
        data[index / 8] &= ~(1 << (index % 8));
     }
   }
};

Edit: As geza has also pointed out int he comments, the "trick" here is to get as close as possible to the minimum number of bytes needed (without wasting memory by triggering alignment losses, padding or pointer indirection, see http://www.catb.org/esr/structure-packing/).

Edit 2: If you feel adventurous, you could also try a bit field (and please let us know how much space it actually consumes):

struct Bitset36 {
  unsigned long long data:36;
}

Supine

Great! This is what I was writing after seeing geza's comment. Unfortunately, sizeof(Bitset36) is 8B. – Inspirit

The last edit really isn't worth including as it indicates a lack of understanding of native bitfields and no testing. Native bitsets only allow you to pack multiple contiguous fields into the sizeof their shared type; they can't reduce that sizeof. – Ban

@Ban To my understanding, all storage and memory properties of bit fields are implementation-defined. So testing locally wouldn't necessary help and I don't think the spec prohibits reducing to 40 bit here, which might still simplify the use case. Not sure what exactly you are referring to by the "sizeof their shared type", as the sizes of the types of multiple contiguous fields may differ – Supine

@StefanHaustein I'm curious to know where you've seen a 40-bit type lately. Anyway, two bitfield members having different underlying type can't possibly be packed into the same underlying storage, afaik, and that was my point. – Ban

Answer 2

I'm not an expert, but this is what I would "try". Find the bytes for the smallest type your compiler supports (should be char). You can check with sizeof and you should get 1. That means 1 byte, so 8 bits.

So if you wanted a 24 bit type...you would need 3 chars. For 36 you would need 5 char array and you would have 4 bits of wasted padding on the end. This could easily be accounted for.

i.e.

char typeSize[3] = {0}; // should hold 24 bits

Now make a bit mask to access each position of typeSize.

const unsigned char one = 0b0000'0001;
const unsigned char two = 0b0000'0010;
const unsigned char three = 0b0000'0100;
const unsigned char four = 0b0000'1000;
const unsigned char five = 0b0001'0000;
const unsigned char six = 0b0010'0000;
const unsigned char seven = 0b0100'0000;
const unsigned char eight = 0b1000'0000;

Now you can use the bit-wise or to set the values to 1 where needed..

typeSize[1] |= four; 
*typeSize[0] |= (four | five); 

To turn off bits use the & operator..

typeSize[0] &= ~four; 
typeSize[2] &= ~(four| five); 

You can read the position of each bit with the & operator.

typeSize[0] & four

Bear in mind, I don't have a compiler handy to try this out so hopefully this is a useful approach to your problem.

Good luck ;-)

Glasses

Your reply also answers my question, but I cannot "accept" two answers. – Inspirit

If anyone checks sizeof(char) and doesn't get 1, they have a completely broken compiler, since that equality is a fundamental principle of the language. – Ban

Answer 3

You can use array of unsigned long int and store and retrieve needed bit chains with bitwise operations. This approach excludes space overhead.

Simplified example for unsigned byte array B[] and 12-bit variables V (represented as ushort):

Set V[0]:  
B[0] = V & 0xFF; //low byte 
B[1] = B[1] & 0xF0;  // clear low nibble
B[1] = B[1] | (V >> 8);  //fill low nibble of the second byte with the highest nibble of V

Economizer