more efficient boolean representation?

[shwestrick]

The type bool is a 32-bit type, which makes it inefficient for use in arrays of flags. Ideally, it would be an 8-bit type.

In our benchmarks, we have been working around this manually to reduce memory footprints; see for example primes which on input size n needs an array of n flags. Using Word8.word array achieves 4x smaller memory footprint in comparison to bool array. This is significantly faster--I've measured as much as 2-3x time improvement on this particular benchmark on high core counts.

I haven't looked closely yet at what changes to the compiler would be needed to achieve 8-bit booleans, but my guess is that it might be a little tricky. It would certainly impact the FFI (which, following MLton, specifies 32-bit bools; see ForeignFunctionInterfaceTypes).

Some preliminary digging:

• WordSize.bool is set to 32 here:

  mpl/mlton/atoms/word-size.fun

  Line 54 in a71659b

  val bool = fromBits (Bits.fromInt 32)

• This commit might be helpful: MLton/mlton@54bf609
• See also perhaps Investigate representation issues for enum-like types MLton/mlton#301