[Pre-RFC] Two new structures for two different types of memory

Taken from the RFC:

This RFC proposes the creation of two types of primitive "growable" structures that manages different types of memories and can be seen as an alternative for alloc::vec::Vec<T> , the built-in structure that manages heap-allocated memory.

  1. A vector for stack-based allocations.
  2. Hydric approach between heap and stack memory.

This proposal is a bit controversial and my instinct says it won't go too far, that is why I didn't put a lot of content. Well, tell me what you guys think about it -> https://github.com/c410-f3r/rfcs/pull/1

This seems like a solution in need of a problem.

You haven't really explained why the status quo needs to be changed (yes, there's fragmentation, but fragmentation isn't that big of a problem), or why one implementation should be preferred over the others.

4 Likes

All of the custom vecs deref to &[T], so there's very little need to unify them.

I like that there are many to choose from, so I can choose trade-offs. For example, I don't always need the on-stack vec to be able to grow beyond stack space, so I can pick a slightly more optimized stack-only version instead of a hybrid one.

Even if you make the best implementation that obsoletes them all, there's no need to put it in libstd unless you need tightly integrated compiler support to make it good. But if you need such compiler support, why not make RFC for that only, so that all crates can benefit?

3 Likes

Yes, there isn't a "problem" but it would be nice to have these types of primitive vectors in std for convenience. Remember that each one deals with different types of memory and they serve as building blocks for higher structures.

In regards to preferred implementations, here goes a list of the mentioned crates and their current status:

StackVec<T, const N: usize> (Stack-based allocation)

  • arrayvec::ArrayVec: Uses declarative macros and an Array trait for implementations but lacks support for arbitrary sizes.
  • tinyvec::ArrayVec: Supports both arbitrary and fixed sizes, requires T: Default for security reasons and isn't very suitable for general usage.
  • StaticVec: Uses constant generic for arrays with arbitrary size.
  • heapless::Vec: With the support of typenum, can also support arbitrary sizes

DynVec<T, const N: usize> (Stack-based and Heap-based allocations)

  • SmallVec: Supports both arbitrary and fixed sizes for arrays.
  • tinyvec::TinyVec: Taking aside the additional T: Default, it is roughly the same as SmallVec.

As seen, there isn't an outstanding implementation that is much better than the others because all of them roughly share the same purpose and functionality. Noteworthy is the usage of constant generics that makes it possible to create an efficient and unified approach for arbitrary array sizes.

Nevertheless, your comments raised important statements that I will transpose into the RFC. Thanks!

Vec implements get(idx: usize) -> Option<&...> to avoid the indirect call of vec.deref()/as_ref()/as_slice().get(some_idx) to simply do vec.get(some_idx). The same reasoning was applied to StackVec and DynVec block implementations.

As commented, all available implementations roughly do the same thing with tinyvec being the most outsider because of the T: Default bound restriction.

Hum... It was about unstable features that can't be used on stable compiler versions, most notably, specialization and union. With a built-in structure, it will be possible to use these and other types of unstable operations internally to generate more efficient code or circumvent unforeseen restrictions like the recent imp<T, const N: usize> Default for [T; N] and [T; 0].

Thanks for your comments