I think we already have
RandomAccessCollection) for the shared base -- we don't need something that's specific to inline buffers.
I'm not sure we want to implement multiple sizes. The stdlib has a tuple-based FixedArray implementation that used to use gyb to stamp out any size we needed; we've now cut it back to a 16-element tuple. (And we're only using it for String stuff, with UInt8/UInt16 Elements, so it's not pulling its weight at all.)
Small array is one of those types that are useful in practice and desirable to have but (1) we can't do a really good job of implementing it in the language we currently have (because we cannot flexibly stack-allocate n items) and (2) it is also somewhat prone to misuse (because instances have a remarkably large constant memory footprint, even if they spill over into a heap-allocated buffer; so ideally these would only be used in local variables, and never copied).
Not being able to do a really good implementation means that while we could (and probably should) add a small array to the Collections package, it will be on a lesser tier than most other data structure implementations there: we won't have the expectation that it'll be ready to go through Swift Evolution any time soon. (It would be a little like
UnsafeAtomics in the Atomics package, although with fewer deathly traps.)
Using tuples for the inline storage takes care of deinitialization, which is the most troublesome obstacle for implementing inline storage with an unconstrained element type. But there are also two lesser technical hurdles:
Representing the array with an enum value with smol and large cases will complicate in-place mutations, perhaps to the extent that we'd need to end up going with a purely struct-based approach -- which may waste some memory. (Giving up on
enums is a sadly a frequent theme in this kind of code.)
Tuple elements always need to be initialized, so the array will probably need to take a default value to fill unused slots in its inline storage. (The alternative is to use an Array of optionals, which would probably be a bad idea.)
_FixedArray16 works around this by only providing an initializer
where Element: FixedWidthInteger, which obviously won't work in a general-purpose array.
I wonder if the ideal implementation for
SmallArray would be a generic move-only type, using something like
alloca & a custom deinit, with the inline capacity coming from an integer-typed generic argument value. Getting to this ideal state would take a bit of time; these language features don't exist yet.
It is not entirely obvious to me that we can implement generic smol arrays in a way that would be measurably faster than a regular
Array. (Inline storage trades allocation costs for having to initialize the entire capacity, and if array values are copied around, they may trade one retain/release pair with n separate ones.) We'll need to carefully compare benchmark results and we need to be mentally prepared to discard the code if we cannot make it work.