Source   Edit  

This module provides a memory optimized seq[uint] for a user-given range of numbers (by default its own initial length). E.g., if the range is 0..7, it uses just 3 bits per number (plus rounding error). Other pithy descriptions are "the array version of bit fields" | "the matrix version of bit vectors".

In the best case, this allows packing numbers 8x (e.g., 8/1) more densely than a "next biggest CPU int rounded" approach (like 8,16,32,64). The public API uses uint, usually a 64-bit unsigned integer.

To store n indices from 0..n-1 takes n*ceil(lg(n)) bits. E.g., circa 2020 L3 CPU caches have become large enough to support any permutation of 0..2^24-1 since (242*24/8 = 48 MiB).

Using the widest type for backing store and limiting the design to hold only numbers up to said wide type ensures <= 2 consecutive backing items are ever needed to access a given number.

While dynamically growing a SeqUint works, changing element size doesn't. So, callers must t=initSeqUint(s.len, 1 shl (s.bits+1)) & copy as needed.