tracking issue for smallvec enum prototype

[alejandro-vaz]

@alejandro-vaz have you tried enum SmallVec { Stack(...), Heap(Vec) } solution? I have a feeling we can achieve good optimizations with it. Moving all our api specialized for stack vec and when on Vec simply use alloc provided functions instead.

Originally posted by @fereidani in #590 (comment)

anyone is welcome to make their own prototype implementation as well

[alejandro-vaz]

my biggest concern with this one is that we're suddenly introducing a branch in order to get the length for example

many common operations go from one lookup to one branch and a lookup

[alejandro-vaz]

it'd be something like this

pub enum SmallVec<Type, const N: usize, Stored: Allocator> {
    Stack {
        length: usize,
        data: [MaybeUninit<Type>; N]
    },
    Heap(Vec<Type, Stored>)
}

[fereidani]

I would make stack first invariant, We would optimize for branchless stack access(unlikely/cold Vec), as most users expect SmallVec to stay mostly on stack(if not why not use Vec instead?)

[pedrodesu]

I'm a bit confused, how does this leave #601? Would we abandon RawSmallVec altogether? Or keep its implementation closely tied to our small vec implementation, and then SmallVec would just be the bridge between its implementation and the (unlikely/cold) regular Vec implementation? And if it's the latter, or more concretely, if we do intend to make use of std::Vec, how would we satisfy the alloc::alloc::Allocator constraint since it's unstable and we're using allocator2's at the moment? Please let me know if there's something I misunderstood.

[alejandro-vaz]

you didn't misunderstand anything, that's the concept and the issues are very real

RawSmallVec would disappear, and the allocator concern is deal-breaking now that I think about it

[alejandro-vaz]

I'll build the prototype tomorrow and report back

[pedrodesu]

Very well. I'll be waiting for the prototype. In the meantime, a small note: Regarding the allocator API, I'd recommend either directly using allocator_api2::vec::Vec or using conditional enum variants via cfg. Both seem to be decent answers for the allocator question; the former probably even more so than the latter, as it was created exactly for this type of situation.