aph_disjoint_set 0.1.0

Disjoint set implementation with optimized memory usage and ability to detach elements.
Documentation

Implementation of Disjoint Set structure, also known as Union-Find.

Documentation

Examples

Reasons to use this implementation:

  • It uses single memory allocation to store all tree and all ranks.
  • Unique feature: unions operations in parallel threads.
  • Unique feature: After initial union operations, it is possible to query roots in parallel.
  • Optimization from knowledge that all tags are valid indexes for underlying buffer. Other implementations use safe indexing with bounds checks which is not optimized away.
    • This crate is heavily tested using Miri so it must be safe to use.
  • Has 3 flavors suitable for your specific needs:
    • recommended default [DisjointSet] is suitable for cases when you know amount of nodes ahead of time,
    • [DisjointSetArrayU8]/[DisjointSetArrayU16]/[DisjointSetArrayU32]/[DisjointSetArrayU64], for cases when it is preferable to store all datastructure inline without extra heap allocation.
    • [DisjointSetDynamic] if exact number of nodes isn't known beforehand.
  • [DisjointSet] and [DisjointSetDynamic] use smaller node tag type to reduce memory usage. It is significant, for example, DisjointSet with u16::MAX nodes use 256 KByte memory, which fits to L2 caches pretty well, while u16::MAX+1 would use approximately 512 KBytes, which is much harder to fit. This optimization is opaque to user so there is no need to think about it.
  • Good documentation.
  • Good test coverage.

Benchmark results

I benchmarked againts most popular crates with union find implementation on crates.io: union-find and ena. Benchmarked on Core i5 6300HQ.

Labyrinth/aph-disjoint-set serial   time:   [230.91 µs 231.54 µs 232.21 µs]
Labyrinth/aph-disjoint-set parallel time:   [84.909 µs 85.978 µs 87.173 µs]
Labyrinth/Crate Union-Find          time:   [254.05 µs 254.21 µs 254.37 µs]
Labyrinth/Crate eno                 time:   [444.44 µs 444.77 µs 445.11 µs]
Islands/aph-disjoint-set serial     time:   [177.12 µs 183.31 µs 190.54 µs]
Islands/aph-disjoint-set parallel   time:   [132.87 µs 134.11 µs 135.66 µs]
Islands/Crate Union-Find            time:   [167.80 µs 172.37 µs 177.84 µs]
Islands/Crate eno                   time:   [399.41 µs 400.37 µs 401.52 µs]

Contributing

Crate is licensed by either Apache 2.0 or MIT license so by contributing to it you agree to license your code by both licenses.