Inspired by @gankro's comment in the thread about SSO on discuss.rust-lang.org.

This is a drop-in replacement for Vec that dynamically moves between stack and heap for smaller vectors. The threshold is currently governed by two hardcoded constants, the size of the on-stack array and the max number of bytes in the contained type, but perhaps in the future it could be configurable at compile-time or even calculated from a percentage of the running stack size. I didn't know enough about DST to implement a dynamically-sized array so the on-stack array is a constant size.

The file is huge mainly because I copied all the tests from vec.rs to make sure it was up to snuff. In fact, a lot of code was shamelessly copied from vec.rs and adapted to HybridVec, mostly with respect to heap storage management.

I had to comment out the assertions on capacity for smaller vectors because switching to stack storage broke them (HybridVec::new().capacity() != 0) and I didn't want to expose the ARRAY_SIZE constant for the tests submodule or copy it as a magic number for each occurrence.

Some methods, such as map_in_place, dedup and vec::as_vec, (and their associated tests) were omitted on purpose to limit complexity while others were omitted accidentally because Vec's API is massive and the tests didn't complain. Please let me know of any that should be there but aren't.

I made sure all tests passed before submitting this PR. I also ran benchmarks, though I'm not exactly sure if I'm interpreting them correctly because they seem to show regressions when the vector is on-stack: Pastebin

Of course, this could just be overhead. I expect some from the widespread use of dynamic dispatch required by this implementation strategy. A real comparison should compare HybridVec to Vec for vectors of the same size to emphasize any performance improvements/regressions. Additionally, some methods have a more naiive implementation than their Vec ancestors for simplicity's sake and should be benchmarked for performance regressions.

This is very much still a work-in-progress, though I feel it's mature enough already to be included as a working prototype so it can cut its teeth in the wild.

In addition to missing needed methods and benchmarks, I neglected to write doc-comments for most of the methods because the public API behaves, for the most part, equivalently to Vec's, with the exception of shrink_to_fit which has a new move_to_stack: bool parameter, which was needed to make into_boxed_slice() work correctly for smaller vectors.

The stack-vs-heap behavior happens transparently and is never exposed to the user except for this parameter.