John McCall abfe16574d [NFC] Add FixedBitSet ...

I wanted a bit vector that I could use as a compact sorted
set of enum values: an inline-allocated, fixed-size array
of bits supporting efficient and convenient set operations
and iteration.

The C++ standard library offers std::bitset, but the API
is far from ideal for this purpose.  It's positioned as
an abstract bit-vector rather than as a set.  To use it
as a set, you have to turn your values into indices, which
for enums means explicitly casting them all in the caller.
There's also no iteration operation, so to find the
elements of the set, you have to iterate over all possible
indices, test whether they're in the set, and (if so)
cast the current index back to the enum.  Not only is that
much more awkward than normal iteration, but it's also
substantially less efficient than what you can get by
counting trailing zeroes in a mask.

LLVM and Swift offer a number of other bit vectors, but
they're all dynamically allocated because they're meant
to track arbitrary sets.  That's not a non-starter for my
use case, which is in textual serialization and so rather
slow anyway, but it's also not very hard to whip together
the optimal data structure here.

I have committed the cardinal sin of C++ data structure
design and provided the operations as ordinary methods
instead of operators.

2022-02-16 12:52:47 -05:00

7.3 KiB

Raw Permalink Blame History

View Raw