StackCollections v0.2: Fixed-size bit vectors and bit sets

Package Announcements
1

I present StackCollections v0.2, in which I have completely rewritten the package from v0.1.

StackCollections.jl provides small, immutable isbits collections. Currently, it provides:

  • USet{U <: Unsigned} <: AbstractSet{UInt32}, an isbits bit set similar to Base.BitSet, but stored in a single U. Basically a normal integer-as-bitset with an AbstractSet interface.
  • UVec{U <: Unsigned} <: AbstractVector{Bool}, an isbits bit vector similar to Base.BitVector, but stored in a single U

Why use StackCollections.jl?

The types in StackCollections.jl are mostly useful as performance optimized implementations the Base equivalent of USet and UVec (which is BitSet or BitVector, respectively). If performance is not a concern, you can use the Base types and the StackCollections type don’t provide much extra.

However, if you do need extra performance, then the USet and UVec types are generally faster. They are small isbits types and so typically not heap allocated, and are stored inline in arrays. A USet{UInt8} is stored in a single byte. Most operations on the types are register-only ops and do not touch memory.

Right, but why use a package and not just write bit sets myself?

Integers as bit sets / bit vectors is a common trick and most programmers have implemented them many times. So why would you want to reach for a package for this basic functionality when you can implement it yourself easily?

  • I already dealt with annoying edge cases: Did you think about how floats should be handled, such as 1.0? What about 1e100 which is not convertible to Integer? What about -0.0 which is zero, but not isequal to 0? What about missing? Or 1+0im? Logical indexing when it conflicts with masking? Etc etc.
  • Lots of non-obvious methods are already implemented. A small bit vector implementation is easy, but there is a ton of methods you could add specializations for. You probably won’t need specialized vararg symdiff or specialized three-argument reverse - but it’s nice it’s there.
  • StackCollections.jl is microoptimized. I did my best to avoid branches, outlined errors, and pulled all the bit tricks I (and Claude) could think of.
  • The implementation is already well tested - so you don’t have to write tests for your ad hoc implementation.

History

StackCollections.jl was one of my first published Julia packages from 2019. When I wrote it I was a much worse programmer than I am now, hence the subpar v0.1 release and unfortunate package name - it probably should have been called BitsCollections.
Since making StackCollections.jl, I have used bit sets and bit vectors a few times, where I have ad hoc implemented them, always thinking that I should just use StackCollections.jl, but that I couldn’t be bothered to clean up the package.

2

USet looks very much like SmallBitSet from SmallCollections.jl. UVec{U} seems to be somewhat similar to PackedVector{U,1,Bool} from the same package. The difference is that the length of a PackedVector is stored separately. I think it’s a good idea to store the length in the bit mask, see this post.

(Disclaimer: I’m the author of SmallCollections.jl. StackCollections.jl is older; I was not aware of it.)