I first read about this at: Using Uninitialized Memory for Fun and Profit.

Clever.

It is particularly suitable for some compiler use-cases.

Unsurprisingly, there is an LLVM implementation, which has a nice summary of the data structure:

SparseSet - Fast set implementation for objects that can be identified by small unsigned keys.

SparseSet allocates memory proportional to the size of the key universe, so it is not recommended for building composite data structures. It is useful for algorithms that require a single set with fast operations.

Briggs and Torczon’s original paper 1 is an easy read. PDF is accessible on ACM.

I also found it in Rust standard library.

Over the years, I encountered a few cases where this could have been applied, but I kept forgetting how to search for it. :smile: Cardinality was often 64.

Maybe I will run some tests in Part 2.

  1. Briggs, Torczon, “An efficient representation for sparse sets”, ACM Letters on Programming Languages and Systems, Volume 2 Issue 1-4, March-Dec. 1993. ↩