Make Boolean Array Great Again | Swift | iOS

Bool is a simple type, that represents logical true or false. So this type can be represented using only one bit. However, every object must have an address. Bools are objects. The smallest addressable value is a char (1 byte). So bools will be one byte large and only 1 of 8 bits is used.

Generally, it’s not a big deal, but working with a huge boolean array, we can end up with many unused memory. Given that Swift is making strides towards optimization and giving more control to developers, the implementation of the boolean array can be improved. For example, we can store a boolean in 1 bit internally, like a C++ vector does.

Concept

In the array we will store raw bytes. 1 byte = 8 bits, so in 1 byte we can store 8 booleans. To address individual boolean, we need to calculate byte position and index in the byte. Indexes start from the lowest bit.

concept

Implementation

For our array we need to store a pointer to elements, allocated memory size and capacity of the array. At the initialization, we allocate the amount of memory needed to store the given capacity. Don’t forget to deallocate it in deinit.

final class BoolArray {
    let storage: UnsafeMutablePointer<UInt8> // pointer to booleans
    let capacity: Int 
    let chunks: Int // allocated memory size in bytes

    private static let base: Int = 8

    init(capacity: Int) {
        guard capacity > 0 else {
            fatalError("Capacity must be greater than zero")
        }

        self.capacity = capacity
        self.chunks = Int((Double(capacity) / Double(Self.base)).rounded(.up))
        self.storage = .allocate(capacity: chunks)
        self.storage.initialize(repeating: 0, count: chunks)
    }

    deinit {
        storage.deallocate()
    }
}

⚠️ We discuss fixed-size array for simplicity. And I also use class instead of struct for deinit. For better implementation you should use struct with internal class storage to support COW semantic.

The main part is in the subscript. At first, we need to calculate chunk position and bit index. After that, we should apply bit mask to update individual bit without changing the others.

extension BoolArray {

    subscript(index: Int) -> Bool {
        get {
            guard index >= 0, index < capacity else {
                fatalError("Index out of bounds")
            }

            let (chunk, index) = getPosition(index)
            return storage[chunk] & (1 << index) > 0
        }
        set {
            guard index >= 0, index < capacity else {
                fatalError("Index out of bounds")
            }

            let (chunk, index) = getPosition(index)

            if newValue {
                storage[chunk] |= (1 << index)
            } else {
                storage[chunk] &= ~(1 << index)
            }
        }
    }

    private func getPosition(_ arrayIndex: Int) -> (chunk: Int, index: Int) {
        return (arrayIndex / Self.base, arrayIndex % Self.base)
    }
}

To get a boolean, we should apply bit mask with all zeros except the index. And check if the result is greater than zero. To set a positive boolean, we should apply bitwise OR with all zero except the index. To set a negative boolean, we should apply bitwise AND with all ones except the index.

Summary

Using this technique, we can reduce the amount of used memory by 8 times. Array will use 32 bytes to store 32 booleans while BoolArray will use only 4 bytes.