hvec

In memory of Anna Harren, who coined the term turbofish - which you'll see a lot of if you use this crate.

The main purpose of this crate is the HarrenVec type - a Vec-like data structure that can store items of different types and sizes from each other.

Usage

use hvec::hvec;

// Make a list that can contain any type
let list = hvec![
    1_usize,
    2_usize,
    999_usize,
    "Wow, big number!".to_string(),
    3_usize,
];

// Make an iterator (unfortunately can't use `for` loops)
let mut iter = list.into_iter();

// Use `next` with the turbofish to step through elements of different types
let mut total = 0;
while let Some(number) = iter.next::<usize>() {
    if number > 100 {
        let comment = iter.next::<String>().unwrap();
        println!("{}", comment); // Wow, big number!
    }
    total += number;
}
assert_eq!(total, 1005);

Iteration benchmark

The sum_with_optionals benchmark in this repo measures the relative time taken to iterate over a collection of small pieces of data with larger pieces of data sparsely distributed within the same collection.

This is accomplished three ways:

1. Including the larger data in an Option (so every struct is large, but more cache-friendly)
2. Including the larger data in a Box (so it is stored on the heap and the structs being iterated over stay small)
3. Including both large and small structs within the same HVec (so there is no indirection and minimal storage overhead)

Data types

// 128 bytes
struct Extra {
    array: [f32; 32],
}

// 136 bytes (including the tag for the Option enum)
struct BigStruct {
    number: f32,
    extra: Option<Extra>,
}

// 12 bytes on the stack (plus 128 on the heap)
struct BoxStruct {
    number: f32,
    extra: Option<Box<Extra>>,
}

// 8 bytes, bool indicates whether an `Extra` will be packed next to it
struct BareStruct {
    number: f32,
    has_extra: bool,
}

The BigStruct and BoxStruct structures encode within the struct whether the Extra data is included, thus either inflating the size of the struct, or adding a layer of indirection to the heap.

The BareStruct just has a flag that indicates whether the Extra data will follow it in-band.

Timings

If you were to judge by these benchmarks: unless the larger data included in your collection is very rare, HVec can be a more time and space efficient way to store and iterate over it.