2 releases
0.1.1 | Oct 10, 2023 |
---|---|
0.1.0 | Sep 15, 2023 |
#2430 in Algorithms
18KB
278 lines
Order Maintenance
This crate is still under development and may contain nasty bugs!
Totally-ordered priorities for the order maintenance problem.
Current implementation uses Dietz & Sleator (1987)'s tag-range relabeling approach.
Supports no_std
environments out of the box, though it requires alloc
to be
available.
Opportunities for Optimization
This crate is still in its infancy and remains to be thoroughly tested, benchmarked, or optimized.
Here are some premature ideas for potential optimization:
-
Use Bender et al. (2002)'s list-range relabeling approach instead of tag-range relabeling; list-range relabling favors bitwise operations over multiplication and division, so it should be faster.
-
Rather than setting
Arena::SIZE
to2^63
, just let it be2^64
, and let overflow happen naturally. This omits numerous modulus operations that are currently used. This is currently unimplemented out of caution (this crate was ported from an implementation with explicit modulus ops), but should be fine in theory. -
Experiment with using different underlying allocators, between
slotmap::{SlotMap, HopSlotMap,DenseSlotMap}
,slab::Slab
, plain oldVec
(shifting elements on insertion and deletion),{,A}Rc
, or even raw pointers. -
Re-adjust the use of
RefCell
s used internally, or even replace them withUnsafeCell
s, to reduce memory footprint and dynamic checks.
Dependencies
~280KB