Persist-O-Vec

The purpose of "persist-o-vec" is to:

• prevent reallocation
• remove items without shifting right to left
• re-use freed slots, pop, push, and remove, fast
• iterate over used slots only

As such, you must allocate what you need before use up to the maximum determined by the chosen indexer feature. In future there will be an option to increase the capacity if required.

It functions a little like stable-vec which will be a lot faster in some cases (push), but it will not reuse freed slots in the vec.

WIP! I will add stuff to this as I work on it.

Notes: A feature to enable reallocation will be added in future. Currently the purpose of this crate is to prevent reallocation and thus invalidation of pointers. This crate is something of an experiment at this time.

Iterators will not always be in order

Default functionality is FIFO

Why

I was in a situation where I required an Vec<Option<T> - a fairly common use of Vec really. But I also needed the Vec to never move (reallocate) so that pointers would not become invalidated, and I also wanted to iterate over the Vec fast.

The iteration problem stems from Vec normally being very fast, but because it is a contiguous block of memory. Once you introduce Option<T> to it, you need to check each slot and will be iterating over the full length of the Vec that may have a lot of blank spots.

Persist-O-Vec tries to alleviate this somewhat. Iters are now fast and only iterate over actually allocated slots, and enforces allocating the space you require upfront so that locations will not move.

In future I will add a feature to enable reallocation if the given space is not enough when attempting to push an item.

Use of unsafe

There are 10 uses of unsafe in the code within 7 functions - these are used to dereference pointers which are guaranteed safe, fast. The uses are heavily vetted and tested by unit tests, benchmarks, and use in external code (and later, fuzzing).

Space usage

The space use is at least 24 extra bytes per entry. Rust will perform some optimization depending on what is stored.

Benches

running 10 tests
test pst_init_with_capacity        ... bench:      17,221 ns/iter (+/- 1,012)
test pst_iter                      ... bench:      19,105 ns/iter (+/- 798)
test pst_iter_mut                  ... bench:      19,220 ns/iter (+/- 1,281)
test pst_populate_to_capacity      ... bench:      65,173 ns/iter (+/- 2,484)
test pst_populate_to_capacity_fast ... bench:      42,507 ns/iter (+/- 2,122)
test pst_remove_and_push           ... bench:          51 ns/iter (+/- 7)
test vec_iter                      ... bench:       4,476 ns/iter (+/- 253)
test vec_iter_mut                  ... bench:       6,159 ns/iter (+/- 1,500)
test vec_populate_to_capacity      ... bench:      18,886 ns/iter (+/- 1,143)
test vec_remove_and_push           ... bench:      22,673 ns/iter (+/- 1,244)

The pst_populate_to_capacity_fast looks like Persist::with_capacity_filled_by(LIMIT, || Velocity(1.0));

Reminder: Benchmarking little things like this is relatively difficult as the compiler is often able to optimise things to a reduced amount or even away entirely. The benchmarks above should be taken lightly although they did help with some optimizations.

In real use, for example backing an ECS in a game engine Persist-O-Vec performs extremely well. For example when it is used to back tiny_ecs:

     Running target/release/deps/pos_vel_legion-2f3c5c5d2ec6ce5d

running 2 tests
test bench_build  ... bench:     526,150 ns/iter (+/- 42,578)
test bench_update ... bench:       1,898 ns/iter (+/- 98)

test result: ok. 0 passed; 0 failed; 0 ignored; 2 measured; 0 filtered out

     Running target/release/deps/pos_vel_specs-bbdfcc04780f88ac

running 2 tests
test bench_build  ... bench:     316,030 ns/iter (+/- 25,096)
test bench_update ... bench:       3,315 ns/iter (+/- 142)

test result: ok. 0 passed; 0 failed; 0 ignored; 2 measured; 0 filtered out

     Running target/release/deps/pos_vel_tiny_ecs-26c6953c8fca73ca

running 2 tests
test bench_build  ... bench:     386,614 ns/iter (+/- 22,060)
test bench_update ... bench:       2,040 ns/iter (+/- 229)

It appears to be able to keep up with the ECS engines which are highly specialised to ECS.