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.
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)
}
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.
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
.
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
andSO_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. âŠď¸
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.
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:
And that was in a reply to me..
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.
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.
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.
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.