|Luke 0fca83aeb1||3 weeks ago|
|benches||6 months ago|
|misc||6 months ago|
|src||3 weeks ago|
|.drone.yml||6 months ago|
|.gitignore||6 months ago|
|.gitlab-ci.yml||6 months ago|
|.rustfmt.toml||6 months ago|
|CHANGELOG.md||3 weeks ago|
|Cargo.lock||3 weeks ago|
|Cargo.toml||3 weeks ago|
|LICENSE||6 months ago|
|README.md||3 weeks ago|
The purpose of “persist-o-vec” is to:
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
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.
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).
The space use is at least 24 extra bytes per entry. Rust will perform some optimization depending on what is stored.
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)
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.