tnballo / scapegoat Goto Github PK

Hello!

First and foremost, thank you for this very nice crate!

Do you think it would be feasible to add a with_capacity to the arena allocator, and ultimatly to the SgMap and SgSet implementation to pre-allocate nodes at run-time ?

This would be useful for cases where we know how much inserting will be done in the near future but don't want to pay the cost of frequent allocations (and/or re-allocations).

The current method for setting stack arena size via the SG_MAX_STACK_ELEMS environment variable has the advantage of keeping APIs compatible with BTreeMap/BTreeSet. For example, a new map can be declared in the usual way:

let map: SGMap<usize, usize> = SGMap::new();
assert_eq!(map.capacity(), 1024); // Assuming `SG_MAX_STACK_ELEMS == 1024` (default)

But this has the disadvantage of being a fixed, global setting. It'd be awesome if we could additionally support the array-style type declaration syntax used by crates like smallvec and tinyvec. This would allow unique stack arena sizes for each callsite, like so:

let default_map: SGMap<usize, usize> = SGMap::new();
assert_eq!(default_map.capacity(), 1024); // Assuming `SG_MAX_STACK_ELEMS == 1024` (default)

let little_map: SGMap<[(usize, usize); 256]> = SGMap::new();
assert_eq!(little_map.capacity(), 256);

let big_map: SGMap<[(usize, usize); 8192]> = SGMap::new();
assert_eq!(big_map.capacity(), 8192);

Making this change will require a little refactoring, the types in src/tree/types.rs would likely have to become associated with the SGTree struct instead of being global?

They live here.

Problem:

If multiple crates in the dependency tree use scapegoat and configure a mutually exclusive setting/feature, cargo's resolver will attempt to merge and may misbehave or fail.

Necessary fixes:

• Disallow compile-time configuration via environment variables:

  • Replace SG_MAX_STACK_ELEMS with SGMap::with_capacity(capacity: usize) constructor (see #9), set some default size for new constructor.
  • Remove SG_ALPHA_NUMERATOR/SG_ALPHA_DENOMINATOR. Only map.set_rebal_param(alpha_num: f32, alpha_denom: f32) to change from non-default alpha at runtime.

• high_assurance feature replaces fallible APIs, should only add try_* variants (see #8):

  • E.g. APIs available with feature disabled is a strict subset of APIs with feature enabled.

To mirror BTreeSet's range, and BTreeMap's range/range_mut.

To help navigate the codebase:

• src/tree/tree.rs is where the majority of logic is implemented, both sets and maps are public wrappers around this tree. Since v2.0, this module is internal-only (not part of crate's public API). So you're free to make any changes necessary to support the range APIs. Current iterator implementations live in src/tree/iter.rs.

• Return types like Range should be added to src/set_types.rs and src/map_types.rs.

Any performance optimizations that don't introduce unsafe are welcome!

To mirror BTreeMap's entry, first_entry, and last_entry.

The blog post "Writing a Linux-compatible kernel in Rust" by Seiya Nuta raises a good point about the need for "fallible versions of dynamically allocated containers".

• If no features are enabled, scapegoat should be as API-compatible with BTreeMap/BTreeSet as possible. That means supporting infallible traits like Extend, which could panic! in a #![no_std] environment if (self.len() + iter.len()) > self.capacity().

• The intent of the optional high_assurance feature, however, is to make this library suitable for critical systems - where crashing at runtime is unacceptable. We have the potential to remove all implicit panic!s by making any fallible operation return Result /Option to the caller. But this requires breaking changes, e.x. replacing the From trait with TryFrom.

Current state of fallible operations for the high_assurance feature

Let's use SGMap as an example, applies to SGSet as well. Note there are multiple versions of extend and from, but we only list one for brevity.

Desired state of fallible operations for the high_assurance feature

Replace smallvec dependency with tinyvec.

• Pro: all deps and this lib become #![forbid(unsafe_code)], e.g. 100% of the compiler's output is safe.

• Con: Breaking change, additional trait bound for map keys and set elements: from Ord to Ord + Default. Requires v2.X.

Cannot use feature flag to toggle between the two deps since trait aliases are not yet supported on stable?

This was discussed a bit in #18, but I have a need for an exceedingly fast, zero-runtime-allocation Sorted Map. We need to hand a few dozen GBs to the SGMap. That's not something we'd ever be able to put on the stack :)

If Scapegoat SGMap could possibly be parameterized to use TinyVec::SliceVec instead of ArrayVec, we'd have everything we need. Scapegoat could remain no-std and fully safe. We'd be doing the unsafe stuff (MMapping actually) to supply the slice to TinyVec::SliceVec

I think it would be simplest to have a feature flag slice-vec that swapped out the ArrayVec for a SliceVec, and introduced a from_slice or with_slice? associated function.

If this or something similar is amenable, I would be happy to submit a PR