Add with_capacity

[GrandChaman]

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).

[tnballo]

Hey, glad you like it! Good question, setting capacity at runtime would be a convenient feature. The answer is a little complicated, so bear with me on a long-ish explanation

This library is #![no_std] compatible, it’s geared toward embedded systems that don’t have heap memory (but works on any system). So the line let mut set: SgSet<i32, 1000> = SgSet::new(); actually pre-allocates space for 1,000 i32s (and internal metadata) on the stack, at compile-time. The "arena" in this crate is an abstraction over [T; N], via tinyvec.

• Good news: the current pre-allocation strategy is cheap - there’s no runtime call to a heap memory allocator and there’s no cost for move/re-allocation. That should support most cases where you know how much inserting will be done in the near future.

• Bad news: without the presence of heap/dynamic memory, creating or resizing the arena at runtime is tricky. And the parameter to with_capacity(capacity: usize) is only known at runtime.

The only crate I’m aware of (there may be others) that supports runtime capacity while still being #![no_std] is fixed_slice_vec. The trick it uses, instead of supporting fn with_capacity(capacity: usize), is supporting unsafe fn from_bytes(bytes: &'a mut [u8]). You provide a mutable byte slice of whatever size you have at runtime, and the crate uses it as it’s version of an arena.

• So it’s kind of like runtime pre-allocation, but less ergonomic than the usual with_capacity.
• Internally, that requires the unsafe transmutation function align_to_mut. And a driving goal of this library is to avoid unsafe entirely!

All that said, runtime capacity could be a valuable feature. Not so much for performance/preallocation, but definitely for flexibility. Thank you for the suggestion!

I’ll keep this issue open, pending on the state of safe transmutation in Rust: there seems to be working group established in RFC 2835.

[GrandChaman]

Hello!

Thank you for the long-ish answer, it's really appreciated.

I get that this library is geared toward embedded system. Although I think it might have applications elsewhere.

Because you use tinyvec as a dependency, I was wondering if it would be possible to add a feature flag that uses a TinyVec rather than an ArrayVec (the complexity could be hidden behind a type alias in the code).

This would still mean this library is #![no_std] but would also benefits to others like myself, looking to use this very fancy crate in more "dynamic contexts" :)

Edit: Although that might be another issue altogether.

[tnballo]

Ah, gotcha. A alloc feature flag that uses TinyVec to support to support heap use would be awesome. I'd love to make this crate viable for more users!

The blocker is I don't know how to support the current fallible APIs (like try_insert) once the heap is involved. We can't remove them because cargo's resolver requires features to be additive. But TinyVec (and Rust collections in general, see RFC 2116) don't have a way to report when the system's heap capacity is full (meaning, perhaps, a call to libc's malloc function returns null pointer, somewhere internally). Ideally this library could return a HeapCapacityExceeded error for such cases.

So it is indeed another issue altogether. But open to any suggestions!

[tnballo]

Thinking back to your idea about type-aliasing: what about aliasing tinyvec::ArrayVec to fallible_collections::vec::FallibleVec behind a feature flag?

• Provides value to ecosystem b/c the fallible_collections crate doesn't yet have a stable ordered map/set implementation (as of the time of this writing, v0.4.4).

• Additional dependency is behind a feature flag (alloc? std?) so current embedded users of this crate don't experience any supply chain impact.

• I think (not certain, needs test) this would maintain API semantics without modifying much code outside of src/tree/arena.rs. That means the alias could be local to a module?

• I'm just now seeing the fallible_collections crate, so not certain it'll work for this usecase, just brainstorming.

If this sounds good, or there's a preferable alternative, would you like to take ownership of an implementation/PR?

[GrandChaman]

Hi!

Wow there is loads to say!

The blocker is I don't know how to support the current fallible APIs [...]

To support those, we could indeed use the fallible_collections::vec::FallibleVec trait.
That woulnd't require any aliasing on tinyvec::ArrayVec IMO.

The tinyvec::TinyVec enum is either Inline which uses a tinyvec::ArrayVec or Heap which uses a Vec<T>.
The tinyvec::ArrayVec already has support for try_insert().

Because the trait
(FallibleVec) is implemented on all Vec<T>, we would get the try_insert() implementation also for the Heap variant.

Although, that would mean setting the MSRV would be at least 1.57.0 to support the newly added try_reserve() in the Vec<T> implementation.

Thinking back to your idea about type-aliasing: what about aliasing tinyvec::ArrayVec to fallible_collections::vec::FallibleVec behind a feature flag?

My idea was to have an alias like:

// Bear with me for the not very original naming ;)
#[cfg(not(feature = "heap_collections"))]
type ScapegoatVec<A> = tinyvec::ArrayVec<A>;

#[cfg(feature = "heap_collections")]
type ScapegoatVec<A> = tinyvec::TinyVec<A>;

Additional dependency is behind a feature flag (alloc? std?)

I would maybe create a new heap_collections feature for that use case. I feel like alloc or std could have more fine grained features added to them later on.
In that case, the heap_collections feature would probably require alloc, std, and the fallible_collections crate.

[...] would you like to take ownership of an implementation/PR?

I would, but I'm afraid it might not be right this instant as I'm quite occupied. If you want to go ahead on an implementation that'd be great, otherwise I'll come back to that later on.

[tnballo]

Derp, FallibleVec is indeed a trait and not a type. You're right - no aliasing necessary. I understand your original idea now.

You may already know this but worth explicitly pointing out: ArrayVec's try_insert doesn't consider current heap capacity (just fixed stack space, much like we do currently), but the FallibleVec trait's try_insert does (which we need for heap support). And, like you said, it'll become available on the Vec within the Heap variant of the enum.

Luckily, since use of FallibleVec/try_reserve() would be feature-gated, it won't increase crate MSRV. Just like we use the tinyvec crate's rustc_1_55 feature for const generics here, even though the crate itself has a 1.34 MSRV.

Thanks for working through all this with me and taking the time for a detailed response. I think I understand both the requirements and a path to implementation now. Should have time to work on it later this week, so will assign to myself and keep you posted on progress! 👍

[tnballo]

So unfortunate update: after starting implementation and running into unanticipated roadblocks I think it's better to not add heap support due to fallibility complications. Even though it'd open up more dynamic usescases. 😢

A good example of the problem is the internal function get_subtree_size (which may be called after the user calls insert):

fn get_subtree_size<U: SmallUnsigned + Default>(&self, idx: usize) -> usize {
        let mut subtree_worklist = array_vec![[U; N] => U::checked_from(idx)];
        let mut subtree_size = 0;

        while let Some(idx) = subtree_worklist.pop() {
            let node = &self.arena[idx.usize()];
            subtree_size += 1;

            if let Some(left_idx) = node.left_idx() {
                subtree_worklist.push(U::checked_from(left_idx));
            }

            if let Some(right_idx) = node.right_idx() {
                subtree_worklist.push(U::checked_from(right_idx));
            }
        }

        subtree_size
    }

Ignore the U generic, that just abstracts a u16 here. The problem is subtree_worklist. Currently we can assume subtree_worklist.push will always succeed. That's true because the arena can't store more than N items - same as subtree_worklist's length. The only "allocation" this function does is temporarily storing N unsigned integers on the stack. That stack usage is fixed, it'd decided at compile-time.

Now if we support the heap, N is no longer a constant, it could be some arbitrarily large number (len of TinyVec::Heap(Vec<A::Item>)). So push might fail at any given loop iteration, since subtree_worklist is growing dynamically after each push. Thus we need to use fallible_collectsion's try_push to maintain the current fallibility semantics of this library's public API.

Going down that path would mean changing a lot of internal signatures to return Result, and probably using a lot of cfg to keep things working without fallible_collections for the current embedded use case (default build, no features enabled). It's possible, but adds more complexity than I'd like to maintain.

As an alternative solution, tried "pulling up" buffers like subtree_worklist into the struct &self refers to. The idea being only a single, central location in the code handles fallible actions (using try_with_capacity or similar) and all other functions borrow "scratch" buffers by reference as needed. But that created a worse problem - functions passing arguments/results via implicit struct state.

So, based on this experimentation, opting to close this issue for now. It'd be too major of a change, and the standard library currently covers dynamic usecases. But always happy to discuss further or eventually circle back, learning as I go!