[Accepted with modifications] SE-0453: InlineArray (formerly: Vector, a fixed-size array)

Oof, well there goes that idea. Maybe we do just need to add unsafe unions.

If you have a single enum for the entire collection then you’d only need one extra byte, but you’d probably want that anyway for bookkeeping where newly appended elements should go.

1 Like

For a buffer where any field could be uninitialized? Yes, but a fixed capacity array only has uninitialized elements in the storage slots at count..<capacity. So you don't need any tracking other than the current element count.

Right, and that’s what an enum like this would do:

enum Elements {
    case zero
    case one(T)
    case two(T, T)
    case three(T, T, T)
}
1 Like

I'd like to cut short the discussion of implementing types with user-defined copy/relocation semantics. This is an interesting topic, but it doesn't need to happen in this thread. Suffice it to say here that it is not currently supported except via C++ import.

8 Likes

As an LSG member rather than a moderator: we did consider whether InlineArray ought to be reserved for a future fixed-capacity array. Our thoughts were basically:

  • We agreed that fixed-capacity data structures were important in systems programming[1].
  • We did not accept the idea that a fixed-capacity array was more array-like than a fixed-size array. They are both kinds of arrays, despite the operation sets being different.
  • We noted that, while fixed-capacity data structures do have insertion operands, they are typically different insertion operations from those on growable data structures. Running out of space in a fixed-capacity ring buffer is typically a recoverable condition, not a precondition violation.
  • We felt that these data structures probably ought to have a name emphasizing that, such as CappedArray.

  1. They're often not inline, however, or even statically fixed in size. For example, in a network stack, the TCP send and receive buffers do not dynamically grow as more data is received, but they are not typically allocated inline as part of the socket data structure, and they can be resized with the SO_SNDBUF and SO_RCVBUF socket options. There is a key difference here between "allocations are bad" and "behind-the-scenes allocations are dangerous". In systems programming, separate allocation on the heap is often fine as long as you do it under controlled conditions and with proper handling for failure. ↩︎

20 Likes

But embedded code will often be written in a low-level language like C, which will have... Fixed length arrays, where you would keep track yourself of how much you are using, exactly like this proposal. Am I missing something?

The difference is that C and C++ let you have partially- or fully-uninitialized local and/or member variables:

struct SampleBuffer {
    unsigned int count;
    float samples[32];
    inline SampleBuffer() : count(0) { }
};

SampleBuffer *buf = new SampleBuffer{};
// at this point, buf->samples is entirely uninitialized
buf->packetCount = 1;
buf->samples[0] = 0.;
// now buf->samples is only partially uninitialized

In Swift, you can allocate typed uninitialized memory, but when you initialize it the entire value must be initialized:

struct SampleBuffer {
    var count: UInt
    var samples: InlineArray<32, Float>
}

let buf = UnsafeMutablePointer<SampleBuffer>.allocate(capacity: 1)
buf.initialize(from: SampleBuffer(count: 1, samples: [0.]))
// error: all 32 elements of samples must be initialized

The only way to partially initialize samples in this example would be to introduce an extra layer of indirection by turning it into an UnsafeMutableBufferPointer<Float>.

There's also withUnsafeTemporaryAllocation(of: capacity:_:), which will at least place the allocation on the stack.

We can already do that with init(unsafeUninitializedCapacity:, initializingWith:) on many of the existing built-in collection types, so I don't see why InlineArray couldn't easily be given a similar initializer.

That only works because those types store their elements out of line.

I've avoided the original naming discussion, but would agree with @rauhul and others here that Inline- prefix is confusing.

I was team "don't call it an Array" because Array to me (when using Swift) implies forgiveness about not knowing the size you want to work with at compile time.

Which honestly is more inline with how @rauhul wants to use InlineArray

That said I found @John_McCall 's explanation that the language group doesn't have that same allocation behavior hangup around the name Array interesting and maybe makes for a simpler-to-use language if all homogeneous buckets are some sort of Array? Okay?

Since it seems like we're going to end up with this type in the Array family, I kind of think Inline is maybe better than FixedSize because it brings to the front that there is a compilation difference rather than just the number of currently valid elements issue.

I think it will also be interesting to see how a Capped array is implemented in the future, if it uses its Inline cousin as the backing data, and if that all gets C interop...

TL;DR: If it's going to be in the Array family, Inline is maybe the best we can do to bring to front the compilation difference, not just the count difference?

Really looking to having this very important type available to Bwhahahah with.

1 Like

Sorry to bump the point (Karl brought up above) up again, but I don't see this was discussed or mentioned in the alternatives considered and IMHO this is far more important than the name discussion..

Aren't we making a huge mistake now by having the bottom type "fixed capacity, count == capacity" instead of "fixed capacity, count <= capacity"? Do we want the future type that's based on InlineArray (say, InlineCappedArray) the type that introduces the notion of count (that goes within 0 ..< capacity) to always copy all capacity elements of the base InlineArray type?

// future stdlib:
struct InlineCappedArray<N: Int, T> {
    private(set) var count: Int
    private var underlyingArray = InlineArray<N, T>
    ...
}

// usage example:
var samples = InlineCappedArray<4096, Int>(count: 0)
for i in 0 ..< 10 { samples.append(i) } // only 10 samples are here
var samplesCopy = samples // 1. O(10) or O(4096) ?!
....
samplesCopy = samples     // 2. O(10) or O(4096) ?!

Or will it be somehow possible to redefine the init and copy operations of InlineCappedArray (like in C++) to initialise / copy only "count" elements?

If the currently proposed answer to either (1) and (2) above is O(4096) – I would seriously consider returning to the drawing board.. At the very least this is worth mentioning in the alternative considered section.


Edit: unfortunately it doesn't look O(10) is possible in current Swift for either (1) or (2) above... that would require a serious investment of introducing a customisable copy constructor / assignment operator. Well, C++ needs to be better than Swift in some regards, so here is one..

This was discussed briefly in the review—it is not the plan of record that one of these types is the ‘primitive’ which the other is implemented in terms of:

3 Likes

And that was in a reply to me.. :man_facepalming:
This does seem twice the effort which is why I can't remember that (if I were to implement something like this I'd make one implemented in terms of another).

Keeping in mind that the fixed-capacity variant is still a hypothetical future direction, it’s been covered up-thread why InlineArray not a suitable primitive to implement in terms of even leaving the performance aside: `InlineArray requires that all its members always be fully initialized.

In the other direction, implementing InlineArray in terms of a fixed-capacity but variable size primitive would involve storing an extra count member that’s unneeded because the count always matches the generic parameter.

4 Likes

And even if we didn’t care about that overhead, it would make it impossible to use as the type of imported C arrays, which is still the long-term plan.

5 Likes

It’s twice the effort, but that effort is small, and implementing either in terms of the other would come with significant tradeoffs, if it were even possible.

4 Likes

If we were really interested in having a common implementation for caped and fixed-size, it could take the form of two generic parameters for count: the minimum and the maximum count:

InlineCappedArray<N, Element>  ->  InlineMinMaxArray<0, N, Element>
InlineArray<N, Element>        ->  InlineMinMaxArray<N, N, Element>

InlineMinMaxArray would have a count property with storage equal to the number of bits necessary to store max - min; so when max and min are equal there is no storage for count, making it equivalent to InlineArray.

This is just a theoretical exercise to see what the shape of a common type for both would look like. To me it doesn't seem like an InlineMinMaxArray type would be very useful in itself. Having two distinct types seems easier to deal with.

2 Likes