Memory efficient way to store huge number of booleans in PHP

Question

I'm looking for an efficient way to store a huge number of booleans (up to 2.5*10e11) in PHP's memory. My first idea was to create an array of integers and store one boolean per bit in each integer:

// number of booleans to store
$n = 2.5 * pow(10, 11);

// bits per integer
$bitsPerInt = PHP_INT_SIZE * 8;

// init storage
$storage = array();
for ($i=0; $i<ceil($n/$bitsPerInt); $i++) {
    $storage[$i] = 0;
}

// bits in each integer can be accessed using PHP's bitwise operators

However, the overhead with this solution is still way too big: Storing 10^8 booleans (bits) in a 32-bit environment (PHP_INT_SIZE = 4 bytes) needs an array of 3125000 integers, consuming ~ 254 MB of memory, whereas the rare data of 10^8 booleans would only need ~ 12 MB.

So which is the best way to store a huge number of booleans in PHP (5)?

Answer 1

If you really must use an array of that many booleans you can use a string as a ByteArray and pack 8 booleans for each char in the string. This has very little memory overhead compared to the native PHP array but it is more difficult to use.
You can convert bytes to chars and back with the ord and chr functions.

Answer 2

Perhaps the SplStack or the SplFixedArray classes from the SPL fit your needs better.

Answer 3

If using one bit per value uses too much memory then you will need to rethink your design - everything in memory is just bits at the end of the day, and you can't squeeze more than one boolean value into a single bit (by definition).