boolean - What's the difference between Array{Bool} and BitArray in Julia and how are they related?

Question

I was writing a function for boolean 2d arrays:

function foo(A::Array{Bool,2})
   ...
end

Evaluating and testing it with

A = randbool(3,3)
foo(A)

returns

ERROR: 'foo' has no method matching foo(::BitArray{2})

Obviously, randbool() generates a BitArray, whereas I assumed randbool() would yield an Array{Bool}.

How are Array{Bool} and BitArray related? Why do they both exist?

Can I write foo() in such a way that it accept both input types using a single method (since I can't see a difference)?

Answer 1

An Array{Bool} stores each true/false value as a Bool, which is represented internally as a UInt8. So if your array has N elements, it will take N bytes to store it.

A BitArray stores each true/false value as a single bit, with (conceptually) 8 of them packed into a single UInt8. Consequently, it takes only N/8 bytes to store the array. A BitArray also has methods defined that handle all the required bit-twiddling operations for you.

Depending on the operation, BitArrays are sometimes slower than the corresponding Array{Bool}, and sometimes faster. But by and large the performance differences are quite small, so it makes sense to use BitArrays unless you have a specific reason not to. But overall they are fairly interchangeable.

Note that both are subtypes of AbstractArray{Bool}:

julia> BitArray <: AbstractArray{Bool}
true

julia> Array{Bool} <: AbstractArray{Bool}
true

This makes it easy to write generic methods that take either one.