aph_disjoint_set 0.1.1

Disjoint set implementation with optimized memory usage and ability to detach elements.
Documentation
  • Coverage
  • 27.78%
    5 out of 18 items documented1 out of 1 items with examples
  • Size
  • Source code size: 140.34 kB This is the summed size of all the files inside the crates.io package for this release.
  • Documentation size: 1.71 MB This is the summed size of all files generated by rustdoc for all configured targets
  • Ø build duration
  • this release: 10s Average build duration of successful builds.
  • all releases: 10s Average build duration of successful builds in releases after 2024-10-23.
  • Links
  • Repository
  • crates.io
  • Dependencies
  • Versions
  • Owners
  • AngelicosPhosphoros

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:
  • 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]

Benchmarks code available by link.

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.