{"id":439,"date":"2025-03-25T18:29:00","date_gmt":"2025-03-25T18:29:00","guid":{"rendered":"https:\/\/permutationcity.co.uk\/bp\/?p=439"},"modified":"2025-03-27T17:40:30","modified_gmt":"2025-03-27T17:40:30","slug":"bits-and-bools","status":"publish","type":"post","link":"https:\/\/permutationcity.co.uk\/bp\/2025\/03\/25\/bits-and-bools\/","title":{"rendered":"Bits and bools"},"content":{"rendered":"\n

One of my friends was wondering about the performance difference between large representations of bools,\nsay bytes, and packed representations of bools, individual bits.\nAccessing a byte is easier, requiring fewer instructions, but is going to fill up your processor’s cache.\nAccessing a bit is harder, requiring more instructions, but you can fit more in.\nIf you’re going down a\nData-oriented Design<\/a>\nroute which should you choose?\nI’ve looked at bit manipulation before when talking about the\njourney, destination and story<\/a>\nof code’s development.\nI thought this would be an easy investigation.<\/p>\n\n\n\n

Accessing bits<\/h2>\n\n\n\n

If we want to compress bools into a smaller space that probably means a collection of unsigned integers.\nTaking an index for which bool we want that has to be used to determine which integer and then which bit.\nThere are options to consider:\nwhat unsigned integer to use,\nwhat collection to use.\nI can use some templates in my testing although a final implementation might pick specific types.<\/p>\n\n\n\n

template <typename Collection>\nclass BitCollection\n{\npublic:\n    using Value = Collection::value_type;\n\n    BitCollection(Collection& values) :\n        m_Values(values) {\n    };\n\n    bool GetBit(size_t index) const {\n        auto offsets = IndexToOffsets(index);\n        auto& value = m_Values[offsets.Value];\n        auto mask = GetBitMask<Value>(offsets.Bit);\n        return value & mask;\n    }\n\n    void SetBit(size_t index, bool bit) {\n        auto offsets = IndexToOffsets(index);\n        auto& value = m_Values[offsets.Value];\n        auto mask = GetBitMask<Value>(offsets.Bit);\n        if (bit) {\n            value |= mask;\n        }\n        else {\n            value &= ~mask;\n        }\n    }\n\nprivate:\n    Collection& m_Values;\n\n    struct Offsets {\n        size_t Value;\n        uint8_t Bit;\n    };\n\n    static Offsets IndexToOffsets(size_t index) {\n        auto bitCount = GetBitCount<Value>();\n        return { index \/ bitCount, static_cast<uint8_t>(index % bitCount) };\n    }\n};<\/pre><\/div>\n\n\n\n
There are three basic operations here: checking, setting and clearing a bool.\nThey all have the same setup so we are doing the same thing a lot.<\/p>\n\n\n\n
How fast?<\/h2>\n\n\n\n
Let’s start by considering\nwhich underlying integer<\/a>\nto use.\nThey’re all of a similar speed but it does make a difference.\nuint64_t<\/code> and particularly uint32_t<\/code> are better.\nQuick Bench shows the assembly as well.\nTo me it looks like the 32-bit code is a bit more compact.\nMaybe the instruction set or the optimiser is better suited for that.<\/p>\n\n\n\n
Now we can look at how the different algorithms do.\nI’m going to compare my code to\nstd::array<\/code><\/a> and\nstd::vector<\/code><\/a>\nusing bool<\/code> but also\nstd::bitset<\/code><\/a>\nwhich has a compact representation.\nWhich algorithm<\/a>\nis best?<\/p>\n\n\n\n