Now that we understand the problem better, I'd like to work toward creating a PR that actually has a chance of being accepted. Having thought it through a bit, I think I see how to generalize this so it works for any Slice type, and I'm soliciting collaborators. Please DM me if you're interested in pursuing this.
Thanks, All!
Can you elaborate on what you are thinking of before you put up a PR. Specifically around how this generalizes?
I'm nowhere close to putting up a PR, so plenty of time for that.
But the generalization is fairly simple, depending on the implementation strategy. If we're adding value witness table entries as Andy suggested, it's easy to create “slice-borrow” operations that are synthesized for every type from those of its stored properties. But that might generate a lot more code than we really need. The simpler thing is to just need to add the special slicing operations as requirements on Collection with default implementations (ideally synthesized based on stored properties, but worst-case, we can just use conservative default implementations). Then the generic slicing subscript will use these operations.
Any idea on what that would (generally) look like? This generalizes doesn't-throw/throws/rethrows for any kind of out-of-band effect, right?
I think so. Full disclosure: I haven't given how to realize it in Swift a moment's thought, and I've never used or even studied first class effects in another language. I just know how the idea has been described to me, and can imagine the implications.
This recent blog post provides some arguments against "effect tracking" (@Pure and @Impure function declaration annotations) in the context of languages like Scala, Java, and PureScript. I found it to be an interesting read, perhaps some points are relevant for Swift.
Check out sections Effect Tracking?, Effect-Tracked Java™, and Worthless Effect Tracking. The last section questions the usefulness and productivity of purity annotations:
Thanks for the pointer, Dan. FWIW I started reading the article, and finding the central argument deeply unconvincing, skimmed the rest of it, finding lots more to be unconvinced of. At the point (and in the thread) where we're actually ready to discuss an effect system seriously, I hope you'll bring the article up again. If it turns out I'm wrong about the article it would be sad to waste further energy on the idea.
On some thread I read here, someone mentioned Microsoft doing programming languages researching this. I didn't find that post when I last mentioned the existence of said post.
I tried looking for the paper. So far, I found a different paper on implementing the original ideas in C. I'm only kind-of sure this paper is connected to the one I sort-of remember, but it does talk about async & await. More web-searching (on "microsoft language with first class effects") has found another paper, which lead to a preceding paper, which may have been the one I'm trying to remember. Maybe check the three (other) threads here that reference "koka."
FWIW, async in a few languages that already support it and throws in Swift is essentially "effect-tracking", albeit very specialised and ad-hoc, as it supports only two effects: errors and asyncronous computations. A proper effect system would allow to generalize this to many other use cases. See also Eff for an example of "untracked" effects. I'm not in favor of "untracked" effects (it would work as if Swift functions could throw, but didn't require throws and try annotations on them), but that Eff demo page is great for demonstrating multiple use cases for effect systems, such as IO, non-determinism, threads etc.
I've just had time to read this whole thread (I wanted to propose a mutable .ascii view for String, but just like slices, we can't mutate the storage in-place if it's via a wrapper view).
With all the deep technical talk, I'd like to bring it back to the original point of this discussion:
Basically we want to make use of mutating methods on the collection without our wrapper introducing a new reference. This is all a kind of sugar, and we can achieve the same thing by making a mutating method on the collection directly, albeit with some extra parameters that we'd like to express in a different way (using the Slice view).
The other way to write this would be as a function taking an inout parameter:
extension MyCollection {
mutating func sort_inplace(range: Range<Index>) { /* ... */ }
}
// is equivalent to:
func sort_inplace(collection self: inout MyCollection, range: Range<Index>) { /* ... */ }
But inout variables are problematic because you can't store them in a wrapper type. Therefore, the best answer I've heard so far is @gribozavr's idea to introduce inout stored properties, which might sound kind of weird but is actually quite simple. It is the ability to wrap an inout reference in a nominal type together with other data which we can write APIs on, that's all. It's just sugar; it doesn't fundamentally change anything about inout.
The next thing we need is modify-only properties and subscripts. Just like regular properties and subscripts, but they get preferred if the access is going to need to write back. Since it is a _modify, it will be called mutating, ensure its buffer is unique like a regular modify, but yield a wrapper type storing &self as inout rather than yielding an element.
With this, implementing a non-owning slice type which is used for in-place mutations would seem to be quite simple:
struct MutatingSlice<C: Collection> {
var base: inout C
var range: Range<C.Index>
mutating func sort() { /* can modify base in-place */ }
}
extension MyCollection {
subscript(bounds: Range<Index>) -> MutableSlice<Self> {
modify { yield MutableSlice(base: &self, bounds: bounds) }
}
}
(And similarly for mutating wrapper-views - also, note that this type doesn't need to work on the level of buffers directly).
Am I missing something here? It seems to work out in my head, I don't think anything in this thread contradicts it, it has a consistent model that fits well in to the language and doesn't require any dynamic borrow-bits IIUC.
I think the main complexity comes from the desire to retrofit borrowing on to our existing Slice<T>. And it's true - having a second MutatingSlice type isn't super-amazing, but you will almost never encounter it directly because you'd just use the modify-only subscript.
myArray[0..<5].count // Calls subscript(bounds:).get, returns Slice<T>
myArray[0..<5] = anotherArray[0..<5] // Calls subscript(bounds:).set, involving Slice<T>
myArray[0..<5].sort() // Calls subscript(bounds:)._modify and uses MutatingSlice in-between.
I've been playing around with this:
extension Collection {
public subscript(inplace_slice bounds: Range<Index>) -> Slice<Self> {
get { fatalError() }
_modify {
var slice = Slice(base: self, bounds: bounds)
yield &slice
}
}
}
I made a little benchmark, and it seems to give substantial wins at -O. Maybe it is really allowing in-place modification:
Sorting the first 5K integers in an Array of 10K in-place (average over 1000 iterations):
randomArrays[i][inplace_slice: 0..<5000].sort()
Test Results (Sort):
Iterations: 1000Regular subscript: 0.5345829725265503 ms
modify generic Slice: 0.3313169479370117 ms
modify native SubSeq: 0.5445460081100464 ms
So that's a 38% reduction in time, using a generic Slice<T> over an ArraySlice.
Appending an element to the slice from 0..<5000 (I always found it weird to express appending to a slice):
randomArrays[i][inplace_slice: 0..<5000].append(42)
Test Results (Append):
Iterations: 1000Regular subscript: 0.015619993209838867 ms
modify generic Slice: 0.009127020835876465 ms
modify native SubSeq: 0.01331794261932373 ms
A 41% reduction.
Benchmark code. The data is randomised but the pattern is consistent and too big to be a fluke.
EDIT: Also, removeAll:
randomArrays[i][inplace_slice: 0..<5000].removeAll()
Test Results (RemoveAll):
Iterations: 1000Regular subscript: 0.006350994110107422 ms
modify generic Slice: 1.5974044799804688e-05 ms
modify native SubSeq: 0.006295919418334961 ms
99% reduction. Either I'm messing up somewhere obvious or we can do in-place slice mutations today.
Definitely report it as a performance bug that the generic slice works faster than ArraySlice. Honestly I don't know why they kept ArraySlice around. That said, your test doesn't really examine the interesting case here, which is the invocation of a recursive divide-and-conquer algorithm that uses your inplace_slice subscript to “divide” vs. one that uses the built-in subscript. For example, you could write your own QuickSort algorithm. Also, to verify that you're actually doing the mutations in-place, you should build your test with -g and then in LLDB set a breakpoint on malloc just before your algorithm is entered. It's also possible you can do this by converting &slice[slice.startIndex] to an unsafe pointer and inspecting it, but it's better to be dead sure. Lastly, some people in this thread insist that the result is useless unless it also works at -Onone. I don't happen to agree, but it's something else you should verify.