nanovec: Arrays and friends, packed in an integer or two.
Ever felt the need to store a few small integers, but a Vec (or even tinyvec) takes up more space than you'd like?
nanovec offers both fixed- and variable-length arrays of integers with limited range, all packed within one or two
machine words that you can effortlessly lug around.
This crate:
- is
no_std. - is inspired by tinyvec, including the name.
- has minimum dependencies.
Cheatsheet of types offered
[NanoArray] (trait) |
[NanoDeque] (adapter) |
[NanoStack] (adapter) |
|---|---|---|
[NanoArrayBit] (impl) |
[NanoDequeBit] (alias) |
[NanoStackBit] (alias) |
[NanoArrayRadix] (impl) |
[NanoDequeRadix] (alias) |
[NanoStackRadix] (alias) |
Packed Arrays
Two space-saving strategies are offered: bit-packing and radix-packing.
Both support the same set of operations defined as trait [NanoArray].
A wide unsigned integer (e.g. u64) can be treated as an array of narrower integers (e.g. 16 x 4-bit or 5 x 12-bit).
Given the packed integer type (n bits) and the bit-width of each element (k bits), the capacity can be determined as
floor(n / k). This is implemented as [NanoArrayBit].
Generalizing the bit-packing approach, a base-r integer can be treated as an array of integers in the range 0..r.
A good example is a decimal (base-10) number --- 12345678 can be treated as an array of [8, 7, 6, 5, 4, 3, 2, 1]
(least-significant digit first). This is implemented as [NanoArrayRadix].
Bit-packing is expected to perform better than radix-packing, as bit operations are cheaper than mul-div-mod.
Therefore, bit-packing is the preferred approach, unless you need to squeeze in more elements when the element
range is inconvenient for bit-packing (i.e. when r is only marginally larger than a power of two, but much smaller
than the next power of two).
Adapters
Building upon the fixed-length packed arrays, the following variable-length data structures are offered:
-
[
NanoDeque] implements a double-ended queue as [NanoArray] + length. This is the most versatile as it supports pushing/popping at both ends, and get/set at any index. The only drawback is the extra space and padding needed for storing the length. -
[
NanoStack] implements a zero-terminated stack backed by [NanoArray] alone, but its elements must be non-zero (think C-style strings with'\0'at the end). This supports pushing/popping at only one end, and get at any index.