`InlineOrHeap` sequence

[MahdiBM]

We should have an InlineOrHeap sequence/collection that uses an InlineArray to some extent, and more than that it allocates on heap.

This will avoid allocating on heap when there are not enough values to justify so. This can be pretty useful in performance-sensitive code.

Something along the lines of:

enum InlineOrHeap<let count: Int, Element> {
    case inline(InlineArray<count, Element>)
    case heap(Array<Element>)
}

Usage:

let tinyValue: InlineOrHeap<8, Int> = ...

[lorentey]

We do need (and really really want) a Heap variant with inline storage, and also one that starts out with a fixed-capacity inline buffer and switches to heap allocation when it runs out of room. (I'm calling the latter SmallHeap.)

Unfortunately, InlineArray is not suitable for serving as a backing store for such constructs. Despite the name, that type is not really an inline version of Array. It is actually a fixed-size vector/tuple type: it requires its elements to be fully initialized at all times. (It has a constant count, not just a constant capacity.) This generally makes it a poor choice to serve as backing store for a resizable data structure like heap. What we actually need to make this happen is a proper inline array type, with a variable count, and partially initialized storage.

To get there, we need to get over two major obstacles:

• First, allowing partially-initialized inline storage requires fundamental changes in how the compiler expects Swift types to manage memory -- in effect, we need to allow Swift types to customize the way they get copied/moved, at least to a limited extent (i.e., we need something like custom copy/move constructors). We had some prototypes for this; it's mostly an engineering problem, with a side measure of carefully working out precisely how much customizability we actually need/can allow.
• The second problem is not technical. The LSG has made it clear they do not consider fixed-capacity inline storage an important direction for the near term (if at all). Accordingly, I have lost my motivation to push more things through in this area, at least for a little while -- my current focus is on creating standard heap-allocated noncopyable data structure variants, and shipping prototypes for the eventual standard noncopyable container protocols.

[MahdiBM]

@lorentey I did encounter the constant count problem before I even file this issue. I worked around it by having an InlineArray wrapper that stores Optional elements, and if an element is unavailable it'd just set the value to nil. I wonder what you think about that? Would it be acceptable, at least for now until we have the desired construct in stdlib or somewhere? We could, not expose it as public so we can change it down the line when we have the proper type.

my current focus is on creating standard heap-allocated noncopyable data structure variants, and shipping prototypes for the eventual standard noncopyable container protocols.

Those are also very welcome by me 🙂

[lorentey]

Yes, a buffer of optionals is the usual workaround. It works well in a pinch, but it has several drawbacks that make it undesirable for this specific library:

1. Memory overhead -- the stride of Optional<T> can be as much as 100% higher than T, unnecessarily wasting memory. Inline storage should be used sparingly, with as little waste as possible.
2. Runtime overhead -- wrapping/unwrapping optionals is really cheap in Swift, but the cost of doing it is not zero.
3. Lack of contiguous storage -- we're working on high-performance container protocols that prioritize piecewise contiguous storage by exposing direct access to it through the new Span types. A buffer of Optional<T> is generally not layout-compatible with a buffer of Ts; this means that InlineArray<Optional<T>> storage will not be efficiently accessible through the Span type.
4. Increased implementation size -- our current high-performance heap implementation assumes contiguous/uninitialized storage. We'd need to add a separate heap implementation specifically for buffers of optionals, keeping both versions around. This would increase the size of generated binaries and it would also increase maintenance costs (2x the code → 2x the bugs).

Of all these, I consider the third point the most important. I do strongly expect Swift's standalone heap abstractions to provide direct access to their storage as a single contiguous span of its elements. (In fact, in the fullness of time, I also hope to add a lightweight nonescapable heap abstraction that can be initialized around a single MutableSpan (or OutputSpan) instance.)

In case Swift never gains support for partially initialized inline storage, then we'll be forced to nevertheless swallow these issues -- but I don't think that is likely. (FWIW, we were a couple of weeks away from a working implementation. The technical challenges aren't that deep, although they do include reaching an agreement on precisely how much we want to let Swift types customize their copy/move implementation.)