Package implement persistent array using a variant of rope data structure.
Fundamentally, it can be viewed as a binary-tree of array-blocks, where
each leaf-node is a contiguous-block of type T items, while intermediate
nodes only hold references to the child nodes, left and right.
To be more precise, intermediate nodes in the tree are organised similar
to rope structure, as a tuple of (weight, left, right) where weight is
the sum of all items present in the leaf-nodes under the left-branch.
Stated goals:
- Vector parametrized over type T.
- Immutable / Persistent collection of Vector.
- CRUD operation, get(), set(), delete(), insert(), all are persistent.
- Convert from Vec to ppar::Vector.
- Convert from ppar::Vector to Vec.
- Thread safe operations.
- std::vec::Vec like mutable API.
- Iteration over collection, item-wise, chunk-wise, reverse.
- Deduplication.
- Membership.
- Joining collections, splitting into collections.
- Partial collection.
- Extending collection.
- Queue operations, like pop(), push().
- Functional ops, like filter, map, reduce.
- Sort and search operations.
- Trait implementations.
- Clone
- Eq, PartialEq, Ord, PartialOrd
- Extend
- From, FromIterator, IntoIterator
- Hash
- Index, IndexMut
- Write
- Parallel iteration with rayon.
- Arbitrary implementation from quickcheck.
Benchmark:
On a 2010 8GB core2-duo machine, thread safe:
)
)
)
)
)
)
On a 2010 8GB core2-duo machine, single threaded:
)
)
)
)
)
)
Via performance application,
ppar::Vector performance characterization
-----------------------------------------
append-load(1000000 items) : 8.918079ms
random-load(1000000 items) : 5.854µs
get(1000000 ops) : 124ns
set(1000000 ops) : 5.489µs
delete-insert(1000000 ops) : 10.313µs
overhead : "37.19%"
overhead after 90% delete : "33.30%"
Alternate libraries: