We investigate several dense bit-wise implementations of Boolean arrays in the context of the functional data-parallel array programming language SAC. A particular problem arises in compiler or directive based parallelisation as the scheduling of loops over Boolean arrays is unaware of the restricted addressability of densely stored Boolean arrays. We discuss our proposed solution and report on experiments analysing the impact of the runtime representation of Boolean arrays both on sequential performance as well as on scalability using up to 32 cores of a large ccNUMA multi-core system.