More RAM efficient boolean array? Arduino environment

Question

I have some code I have in the Arduino environment that requires x (in increments of 8) boolean values that are manipulatable during run time for some shift register code. So currently I am using a boolean array like so:

 #define number_of_shiftRegisters 220 //num of 8 bit shift registers

 #define numOfRegisterPins number_of_shiftRegisters * 8 //number of booleans needed

 boolean registers[numOfRegisterPins]; //boolean array

But I was running out of RAM around 200 (1600 booleans) and didn't know why until I saw that, even though booleans are 1 bit, they are stored in 8 bits of data.

As I said before, the number of bools needed is always in an increment of 8, so I don't know if that could work to my advantage.

Is there a more memory efficient way to store 1000+ boolean values and still be able to reference them by index?

Or... At least more memory efficient that will not cost significantly more CPU time to set and iterate through?

I had thought about a char array, and then bit masking each char to access the individual bits. But I didn't know if there was an easier way, or if this would take up considerably more CPU time.

Answer 1

Yes, you could easily use masking to get around that issue..

Every byte (unsigned char) will contain 8 boolean values, to get the i-th you can just use values & (1 << i) in if tests, and it will work since if the correct bit is set, then result will be != to 0.

To set instead a bit just shift it and or to the value: values | (1 << i) (in case of unset you have to AND it with 0).

Another solution could be to use a packed struct:

struct Bools
{
  int b1 : 1;
  int b2 : 1;
  int b3 : 1;
  ... // up to b8
}

This should manage elements with direct access to the boolean value and allow you to define an union to manage them either as 8 single bit booleans value either as bytes.

Answer 2

You can have memory-efficient or you can have compute-efficient, but you can't have both at the same time.

Packing booleans into an array of unsigned char means that for any random read access, you have to:

1. Calculate the offset into the array where the bit lives
2. Retrieve that element
3. Calculate the offset into that byte where the bit you're interested in lives
4. Shift the byte that many times to position the bit in the least-significant position
5. Mask off all but the least-significant position
6. Test for zero/nonzero

Storing them in individual array elements cuts it down to:

1. Retrieve the element containing the boolean you're interested in
2. Test for zero/nonzero

Selecting one over the other depends on how your storage and performance needs balance each other, how you intend to use the data and what trade-offs you're willing to make. In your case, the directly-accessed approach costs an eight-fold increase in storage that runs you out of memory and causes a failure, so it's off the table. That leaves packed bits at a cost of some extra processing.

If you spend a lot of time iterating over all or part of the set, you can use the packed approach and cut back on some of the computation by retrieving bytes only when you need them and doing a single shift and mask each time you go after the next bit. Doing this immediately would be premature optmization, so just keep it in your back pocket until you discover that access is actually actually causing a bottleneck. Get your program to run the available memory first.

Also keep in mind that the microcontroller used in Arduino is not particularly sophisticated and doesn't have large registers, so packing into anything larger like unsigned int or unsigned long might end up being couterproductive.