Skip to content

Index Mask

An IndexMask (source) is a sequence of unique and sorted indices. It's commonly used when a subset of elements in an array have to be processed. This is sometimes called existential processing and is often better than having e.g. a bool for every element that has to be checked in every inner loop to determine if it has to be processed.

Semantically, an IndexMask is very similar to a simple Vector<int64_t> with unique and sorted indices. However, due to the implementation details of IndexMask, it is significantly more efficient than the Vector.

An IndexMask does not own the memory it references. Typically the referenced data is either statically allocated or is owned by an IndexMaskMemory.

/* Owner of some dynamically allocated memory in one or more index masks. */
IndexMaskMemory memory;

/* Construct index mask for indices. */
const IndexMask mask = IndexMask::from_indices<int>({10, 12, 13, 14, ...}, memory);

/* Construct index mask from a boolean array. */
const IndexMask mask = IndexMask::from_bools(IndexRange(100), bool_span, memory);

/* Construct an index mask from a predicate. */
/* In this case, the index mask will contain every third index. */
/* The passed in grain size controls the level of parallelism. */
const IndexMask mask = IndexMask::from_predicate(
    IndexRange(1000), GrainSize(512), memory,
    [](const int64_t i) { return i % 3 == 0; });

/* Iterate over all indices in an index mask. */
mask.foreach_index([&](const int64_t i) { /* ... */ });

/* Work is parallelized when a grain size is passed in. */
mask.foreach_index(GrainSize(512), [&](const int64_t i) { /* ... */ });