12 releases
0.3.1 | Jul 11, 2020 |
---|---|
0.3.0 | Jan 31, 2020 |
0.2.4 | Jan 29, 2020 |
0.1.7 | Jan 28, 2020 |
#979 in Data structures
23 downloads per month
Used in tiny_ecs
23KB
533 lines
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.