removeLast() mutates the collection and returns the removed element. But removeLast(_:) mutates the collection and doesn’t return the removed elements; if you want them, you need to ask for suffix(n) beforehand.
Why? I’ve been using Swift since day one, and I always get this wrong — suggesting that, at the very least, on the principle of Least Surprise, removeLast(_:) should return a value.
I don't speak for the standard library team, but my guess would be that returning a single element is fairly cheap (at least in terms of constant time/space), whereas returning an arbitrary number of elements would require the API to either
Neither of these is great for performance: choice 1 is a potential bottleneck if you keep the suffix around longer than you need to, and choice 2 is wasted if you don't need the elements afterwards, so it's better for users to explicitly request them if they need them instead of making everyone pay that cost.
Ben talked a bit about some of the performance issues this gets into and better API that avoid them in his talk at ServerSide this year. (https://www.youtube.com/watch?v=jz3hCRSPrdo, from around 6:00 to around 20:00).
(TL;DR it’s better to nudge people to process the elements in-place before removing them when possible, rather than always copying them into new storage).
Hmm. I’m currently saying
let slice = array.suffix(n)
array.removeLast(n)
slice.forEach { /.../ }
If the inefficiency in that code is the slice storage, then I could write instead
array.suffix(n).forEach { /.../ }
array.removeLast(n)
But to return to my original question: if, as you say, the language should nudge me to write my code that way, then maybe I should ask why removeLast(_:) doesn’t take an Optional closure that takes a slice, just like the video’s suggested code…
In other words, how about if Swift would give me a way to “return” the removed items, even if that way is not to give removeLast(_:) itself a slice return type? Because, as things stand, everyone is naturally doing what I do in my first code, which you’re telling me is inefficient which is why Swift doesn’t already do it.
I agree that it’s curious.
I’d wager that the idea of removeLast(_:) building an array that is a @discardableResult (like removeLast() does) just seemed to introduce too much overhead if there is a good chance that the caller is likely to discard the returned array, anyway.
But there is a popLast(), that doesn’t have a @discardableResult, perhaps begging the question why there is not a popLast(_:).
Could this be done efficiently without a closure? Like so:
extension Array {
@discardableResult mutating func removeAndReturnLast(_ n: Int) -> ArraySlice<Element> {
let elements = suffix(n)
defer { removeLast(n) }
return elements
}
}
The efficiency hit in question is having to copy the array storage to do the remove (because the slice is holding on to the original array storage too). At that point, you might as well do the copy for the removed elements instead (heuristic that it’s more common to remove less than half the array).
You mean COW is triggered? But I am not writing yet when removeLast is called, it could just lower the item count (of the removed head). Later on I could even modify the first k - n elements – and that won't be possibly affecting the slice that lies afterwards. Only if I append some new elements to the removed head – that's where COW would fire, I mean ideally. Ditto for changing the elements in the slice – modifying those won't possibly affect elements in the removed head, hence COW could be avoided.
Remove is a write (unlike popLast). The buffer needs to know how many elements to destroy if it’s deallocated, and that’s done with a single counter—the array’s length, stored in the buffer object.
Because nobody thought of this at the time the API was implemented.
At this point, I would say "sounds like a good proposal" except things have moved on a little since. We now have non escapable types. So a better option than the closure would be to return a non-escapable Span-like type that allows you to consume its elements, de-initializing the memory. This could be done from either end, and when done, the type would consume any remaining elements. Array could return this type spanning the popped elements of its buffer, and consider them de-initialized at that point, so long as its tied to the lifetime of the array, blocking any mutations to the array until the span goes out of scope.
This is similar to the role of the Drain type in Rust. I believe that type is specific to vec, but the type I'm describing could be a general-purpose type and usable by other types as well (UniqueArray, Deque etc). It's kind of the opposite of OutputSpan so might be called InputSpan (though that is a little confusing, because it's used as an output of the pop-n function... DrainingSpan may be another naming option).
What exactly does that mean?
let removed = array.removeLastAndReturn(10) // returns a span
array.append(1) // mutate, will that not work?
removed.forEach {
...
or mutate array here
}
// removed goes out of scope
Right, you would not be able to do this. The compiler would tell you that this was overlapping access. You can see this with Span too:
var array = [1, 2, 3, 4, 5]
let span = array.span
array.append(6)
// error: Overlapping accesses to 'array', but modification requires exclusive access
That span is like the UnsafeBufferPointer you get from calling withUnsafeBufferPointer. It has the same kind of low-level performance characteristics. But unlike with the with block, it does not need to be scoped by a closure. Instead the compiler tracks that it came from the array, and won't let you mutate the array while it is alive. If you did, the memory that span is pointing to could become invalid. That isn't allowed - and the compiler guarantees it can't happen.
The idea is to do something very similar – but with a different kind of type to Span, one that "drains" elements from initialized memory. As you pop them, they'd be "consumed" – that is, moved out of that memory and the memory de-initialized. This is what happens when you pop an element from an array: the element is given to you and the memory in the array's buffer is de-initialized. The idea is to let this happen with multiple elements but without needing to allocate any separate storage. But the sacrifice there is that you mustn't touch the array while you are holding onto those drained elements, because they're still really in the array's buffer, so array mustn't write new elements into that buffer (as would happen with append).
I see, good to know.
Is the following hypothetical slice-based approach not good and why not? (pseudocode):
// not current swift
var tail = array.removeLast(10)
// no COW yet. `array` count is reduced by 10,
// the array "capacity" is also set to 10.
// the elements' buffer is shared between `tail` and array
// the `tail` capacity is the original `array` capacity
// less the number of elements in `array`
array[0] = 42 // no COW yet as the tail elements are not affected
array.remove(at: 0) // no COW needed yet still, the count of array is reduced
// and is lower than it's capacity.
array.append(1) // no COW needed yet still, the count of array is
// increased and now matches its capacity.
tail[0] = 42 // no COW needed here, `array` elements are not affected
array.append(1) // OK, now COW is needed as otherwise the newly added
// element will overflow into the area used by `tail`
Just to clarify, my question is more about the inconsistencies in the current repertoire, which I find surprising and confusing every time I use one of the methods in question; after all these years I still always have to consult the docs. (I’ll use the word “array” throughout, but you know I really mean something more like BidirectionalCollection.)
dropLast() returns a new array, leaves the old array untouched.dropLast(_:) returns a new array, leaves the old array untouched.popLast() returns the removed element, if any, mutates the old array.popLast(_:) doesn't exist.removeLast() returns the removed element, mutates the old array.removeLast(_:) doesn't return anything, mutates the old array.In the absence of a syntactic clue (like Ruby exclamation mark) or a grammatical clue (e.g. -ing), we have to remember which of these three pairs is mutating and which is not. If we can remember that, we can conclude that the mutating ones return the removed material, except that removeLast(_:) doesn't: the removed material, unlike any of the others, is dropped on the floor. It is destructive (unlike, oddly, the ones named drop which do not actually drop anything on the floor).
Thus, if we overlook the lack of popLast(_:), removeLast(_:) is very much the odd one out. I'm suggesting that this is so surprising that it deserves attention.
(And in addition to the surprise, the lack of a returned value encourages the user to capture the about-to-be-removed material beforehand (e.g. suffix(_:)), which I have just learned has a possibly unwanted side effect.)
No, this is just incorrect. Conceptually, you can think of ArraySlice as being
struct ArraySlice<T> {
var base: Array<T>
var start: Int
var count: Int
}
and so just as the following immediately has to copy:
var a = [1, 2, 3]
let b = a
a.removeLast(2)
print(b)
so does this:
var a = [1, 2, 3]
let b = a.suffix(2)
a.removeLast(2)
print(b)
Any design where this is not the case would have to keep track of whether every individual element in the buffer was still referenced by some slice, which…well, I don’t think it can be done with reference counting and still have copies and slicing be O(1).
So this design can't fly you think?
class ArrayBuffer {
// var refCount: Int
var totalCapacity: Int
// here goes either inline storage or out of line allocated storage
}
struct Array {
var arrayBufferRef: ArrayBuffer
var count: Int
var capacity: Int
}
struct ArraySlice {
var arrayBufferRef: ArrayBuffer
var offset: Int
var count: Int
var capacity: Int
}
Forget for a second the inefficiencies due to increasing value sizes, which could possibly be mitigated by switching to 32 bit indices or sacrificing capacity field in the slice, etc. on the positive side having larger array values could allow the "short array" optimisation like it's done with strings.
Note: the above structs (and the corresponding implementation) won't micromanage the byte ranges... for example if you have an array, with two slices at the end, one after another:
<Array> <Slice1> <Slice2>
and then slice1 is getting deallocated 'array1` will still not know it can now grow to fill the available space. Only when the underlying Array's Buffer RC gets to 1 array will be able to expand to the buffer's full capacity.
When all the values sharing a buffer are released, how does the buffer know what elements need to be destroyed and which don’t? Keeping in mind that having Array and ArraySlice be Copyable is a requirement, so they can’t have custom deinit logic.
(Sorry to keep sidetracking, Matt.)
Somewhat tricky indeed.
I think it could be possible to distinguish reference counts due to having array copies from those due to having slices by having an extra tracker object (only one per buffer). Effectively it will allow having two separate reference counts, one will track only slices and another slices and array copies. Conceptual code:
final class ArraySliceTracker {} // empty implementation, we only need RC from here
final class ArrayBuffer {
var sliceTracker = ArraySliceTracker()
var totalCapacity: Int = 100
// a number of array copies
private var copyCount: Int {
CFGetRetainCount(self) - sliceCount - 1
}
// a number of slices
private var sliceCount: Int {
CFGetRetainCount(sliceTracker) - 1
}
var isKnownHavingCopies: Bool { copyCount > 0 }
var isKnownHavingSlices: Bool { sliceCount > 0 }
deinit {
// deinit logic
}
}
struct Array {
var buffer: ArrayBuffer
var count: Int
var capacity: Int
}
struct ArraySlice {
private let buffer: ArrayBuffer
private let sliceTracker: ArraySliceTracker
var offset: Int
var count: Int
var capacity: Int
init(buffer: ArrayBuffer, offset: Int, count: Int, capacity: Int) {
self.buffer = buffer
self.sliceTracker = buffer.sliceTracker
self.offset = offset
self.count = count
self.capacity = capacity
}
}
But those checks have to be quite shallow, right? So sometimes they will have to be done at runtime?
This compiles and works (without runtime failures) on godbolt (tried with "-strict-concurrency=complete"):
// corrected example:
class C {
var array = [1, 2, 3, 4, 5]
func bar() {
array.append(6)
}
func foo(_ execute: () -> Void) {
let span = array.span
execute()
//array.append(6)
print(span[1])
print(array)
}
func foo() {
foo(bar)
}
}
C().foo()
No, these are all static guarantees. It would kill performance to perform these checks at runtime.