Solving the mutating slice CoW problem

Development Standard Library
19

[Edit: I forgot to say,] Andy, thank you for your patient engagement.

That's not obvious to me, especially in the case of “ An 'inout' AnyObject argument may release one reference.” That would seem to imply that an inout argument would be retained one more time than it actually is.

The only salient properties of isUniquelyReferenced that prevent the compiler from removing necessary copies (preventing false positives) are that isUniquelyReferenced may release the reference addressed by isUniquelyReferenced's inout argument, and isUniquelyReferenced can never be fully inlined (the builtin also takes an inout reference).

Okay. That's a really weak foundation on which to build the system whose semantics we have today, but I can accept that it's coded that way.

The only semantic property an individual retain has today is that one must exist for each potential release, i.e. to provide an owned reference.

When you say ”An 'inout' AnyObject argument may release one reference” is that not a “potential release?” This language even more strongly implies one more retain for inout arguments than we actually observe.

As soon as we can determine a reference cannot be released within its lifetime, then the retain has no purpose. I think you want semantics on retains that have something to do with local variable scope.

I want the semantics that I claimed must already be implemented.

  1. An object's reference count will never be 1 unless there's only one variable (whose lifetime could not have ended already) referencing it.
  2. When an existing lvalue is passed inout , no needless retains are added.

This has nothing to do with localness or scope (which is about name lookup, right?) of variables, but does have to do with general variable lifetime. Also, we can add that the compiler can do whatever it wants with reference counts as long as they follow these rules when observed by blessed/builtin operations like isUniquelyReferenced; that doesn't change my story at all.

The only way I can think of attaching additional semantics to a retain is by introducing a "forced copy" feature. In my previous response, I explained that the compiler could provide such a feature without much difficultly, but that using the feature in ArraySlice.init might have a performance penalty.

I agree that such forcing sounds on the face of it like it would be costly, especially if you mean to do it unconditionally.

The burden of proof is on us when introducing an API to explain why it is correct in terms the compiler's model of language semantics.

Sure. I hope you don't imagine that I'm beyond suggesting that the compiler's model of language semantics might be wrong, though :wink:

If we can't write down enforceable rules for SIL that the implementation must follow, then none of us can predict how some combination of implementation choices will violate our expectations.

Absolutely agreed! Let's write down rules that support both value semantics and optimization! That means representing things at a level closer to the user model, like “semantic ARC” has been promising to do. I think the retains you can't eliminate are those on mutable copies of a reference (except where the compiler can prove that those copies aren't accessed, of course). [EDIT] That is a little conservative, but it's approaching rightness. I need to think about this some more.

Nonetheless, your ObjectIdentifier example is interesting and educational:

Cool, let's discuss!

There are two answers to why the ObjectIdentifier example works in practice, depending how much of the code the compiler can see at one time (depending on inlining).

  1. Builtin.isUnique forces an in-memory copy of a reference by virtue of taking its address inout .

By “forces an in-memory copy” I presume you mean it is forced to exist, rather than occur. That is, if the reference was already in memory, I presume no copy is needed.

The same is true for any wrapper around Builtin.isUnique that takes the reference's address inout .

Sure. Didn't you just say that Builtin.isUnique is opaque to the compiler? It would seem that an opaque thing being passed the reference's address at all (e.g. not inout) should be enough to force the reference into memory.

In this example, when everything is inlined, the fact that you're casting to and from an opaque pointer simply does not matter. The compiler sees through it.

Sorry, I don't see any OpaquePointer in this example. Do you just mean, “a pointer?” When you say “casting” are you referring to the use of withMemoryRebound? FWIW, when I wrote that code I was not trying to hide anything from the compiler. The only tricky thing was to avoid passing references around by value, which could interfere with the observation of uniqueness, at least in unoptimized builds. Note also this code was written before the calling convention changed from owned to guaranteed.

Now, when Builtin.isUnique forces the lvalues x1 , and x2 into memory locations, it effectively forces a copy. Relating that to your situation, if both the Array and ArraySlice are mutated, then your "Solving the mutating slice CoW implementation" does work fine in practice and in theory.

In the two incorrect scenarios that I pointed out, sliceCopy is not mutated, and is not forced into a distinct memory location.

It's not exactly clear what you mean by “are mutated.” Mutating the slice mutates the logical value of the Array, and we're already in the context of a mutating method on the array, so in both those senses, they both are mutated. But perhaps you really mean “if the shallow bits of both the Array and ArraySlice are mutated…?“ That appears to be the implication of the last sentence, because your first example definitely mutates sliceCopy, semantically.

  1. Nested retains are not currently eliminated, even when they are blantantly redundant.

Huh, is that sometimes, or always? I was under the impression that at least some nested retain/release pairs were eliminated by optimization.

If we carefully control inlining so that everything except the non-mutating liveObjectIsUniquelyReferenced is inlined, then the ObjectIdentifier example becomes interesting.

In this case, x2 is no longer passed @inout to any opaque code. There's no reason for the implementation to generate a copy.

So why does the example still work today even with worst-case inlining? (I actually tried this.) The SIL optimizer is extraordinarily bad at removing redundant nested retains to the same object. All it takes is one escape or unknown use of the reference to prevent copy elimination. This inability to optimize seemingly obvious redundancy is a problem with the representation that will disappear in due time. So, when _liveObjectIsUniquelyReferenced is not inlined, there just isn't any fundamental reason that your ObjectIdentifier example works. And more importantly, I can't think of any SIL-level requirement that would preserve the current behavior short of "the compiler never removes nested copies of the same reference".

Ewww. I think you've convinced me that might be what would be required within the model of the compiler as you've described it. I still think a better model is possible.

  1. An object's reference count will never be 1 unless there's only one variable (whose lifetime could not have ended already) referencing it. That guarantees we preserve value semantics while still doing the Cow optimization.

SIL has no way to represent that formalism and doesn't need to because reference counts aren't directly observable. It is only the act of observing a variable's uniqueness, via Builtin.isUnique, that forces the variable's reference to be distinct from any other instances of the same reference. This makes it appear to the programmer "as-if" each variable has its own reference, but only for the purpose of uniqueness checking.

That's all that matters, for this rule's purpose. I don't care whether the reference count is 1 when I'm not observing it.

This model does not provide any way to count higher than one.

Sorry, I just don't see how that can be true. If it can't count higher than one, isUnique could always return true. If what you mean to say is that it provides no way to distinguish meaningfully between a count of 2 and a count of 3, then I can accept that. And, since my scheme treats 2 specially, I could see how that could be a problem. My thinking was that it was conservative, so the optimization might fail to kick in but soundness could not be violated… but I could be wrong about that.

As I explained, the only way to observe a reference count of 2 would be to (a) observe two independent variables at the same time

Would you kindly define “independent” and ”at the same time”?

(b) create a new language feature that forces variables to have distinct reference counts even when they aren't being observed.

Is that (a) and (b) or (a) or (b)?

Also, even if this uniqueness property were modeled the way you seem to think it is, I don't know how you get from "An object's reference count will never be 1..." to "An object's reference count will never be 2...".

Aye, there's the rub.

Let's make sure we don't confuse the statement "a reference count is greater than one" with "a reference count is exactly 2". That said, in this example, the array clearly has reference count==2 before it is copied:

let a = [1, 2, 3]
var b = a
b[0] = 99 // if there isn't a retain for b, this writes on a
assert(a != b)

s/the array/the buffer/ and we can agree. The array itself is copied in the 2nd line. And I don't know of anything you've said that prevents the buffer's reference count being >2 at that point.

And in this example, the array might have refcount==2 or 3 when it is copied. It's not determined by language semantics:

let a = [1, 2, 3] // 1
let b = a         // 2
var c = b         // 3
c[0] = 99         // 4
assert(a != c)    // 5
_ = b            // 6

I take your point (though I think you need to replace line 6 with an actual observation of b to really make it).

Yes, the reference count can be 2 on line 4, but we're not in an inout slice context so the borrowed bit wouldn't be set here and that's harmless to my scheme.

In this case, you would need both the ArrayBuffer and the SliceBuffer's address at the same time

Well, I don't know about “addresses”—this is high-level Swift after all :wink:—but we do have both the ArrayBuffer and the SliceBuffer passed inout at the same time at all points where it's important to detect that there are two references.

This is roughly how isDuallyReferenced would need to be written today, without any additional support (e.g. without some way to force copies).

Builtin.isDuallyReferenced(_ object1: inout AnyObject, _ object2: inout AnyObject) -> Bool {
  do {
    _precondition(object1 == object2)
  }
  return swift_isDuallyReference(Builtin.addressof(&object1),
                                 Builtin.addressof(&object2))
}

So, by saying the addresses need to be taken “at the same time” you mean they both need to be passed to a function that's opaque to the compiler and therefore might do two releases?

I just don't see how it would work for you. The address of the Array struct, which holds reference #1, is not available during ArraySlice._modify.

Well, this is all at the level of awful hackery at this point, but… the “borrowed” bit is what tells you that they have the same value.

The only way you can get in that situation is if the compiler is able to prove that the lifetime of either the array or the slice could have been ended (rule 1 above). I'm pretty certain it's actually impossible for the compiler to prove that if the slice is mutated or copied, because their values will both be observed.

Between the creation of the rhs slice and its last use, there is no way that array's storage can be released. Consequently, the compiler could remove the retain of the non-mutating ArraySlice rhs . I can elaborate on this more if we need to.

No, thanks. It's very clear to me why that's true under the existing model.

Hah, the reason this whole thing is needed in the first place is that ArraySlice does always retain its storage for mutation, so I'm pretty sure you will observe no change from that experiment!

ArraySlice does retain its storage when it is mutated. If the compiler does its job, then ArraySlice does not retain its storage when

  • the ArraySlice is not checked for uniqueness (not mutated)
  • the ArraySlice lifetime is limited to the Array's lifetime
  • the Array is not checked for uniqueness within the ArraySlice's lifetime

is that an “and” list or an “or” list?

(A fake uniqueness check on either the ArraySlice or on the array within the ArraySlice's lifetime would be a way to force the copy without any special Builtin, I was just afraid that the compiler would eliminate uniqueness check itself if it's not used)

We could always pass its result to some opaque builtin ;-)

Not at all sure what you're getting at here. As I mentioned to Michael, you don't need Unmanaged to make this scheme work sufficiently for the non-parallel-mutation case. An ugly demonstration is here, but it uses only safe constructs.

I'm ruling out the possiblity of implementing manual reference counting on ArraySlice in case that isn't already obvious.

My goodness, man; I hope so! My code simply swaps the sub-slice's bounds into self and yields that, to avoid taking another reference.

It would be sufficient to add an opaque builtin and SIL instruction that simply takes AnyObject and produces a new one without the compiler knowing that they are in fact the same reference.

I think I understand why you were suggesting that now.

The complexity of doing that probably needs to be weighed against some sort of copy-on-escape support, which would have both the performance and semantic properties that we want.

I haven't tried to design copy-on-escape, so I just don't know how difficult it will be.

If this thread turns out to be another in a long line of examples where I implement something so badly that it disgusts real maintainers into doing it right, I promise I won't be insulted. Just sayin'.

I'd always love to do better.

3 Likes
20

I am very much a spectator, and to be honest I am surprised that recursively mutating a slice doesn’t already avoid copying the buffer.

My (now obviously incorrect) mental model goes something like this:

var a = Array(...)

// For this code, the compiler either retains the buffer,
// or statically proves that `a` is never used again:
var b = a[...]
b.sort()

// For this code, the compiler never retains the buffer.
// If the buffer is not uniquely referenced, then it makes
// a new buffer for `a` and operates directly on that:
a[...].sort()

Within the sort() call, my mental model is similar. Recursive calls to self[...].sort() also do not retain the buffer. If the buffer is uniquely referenced, they operate on it directly. Otherwise, they make a new buffer for self, which somehow is promulgated all the way up to make a new buffer for a. (Maybe the slice actually holds a reference-to-the-reference held by a?)

In this model, no matter how deep the recursion goes, none of the slice-and-immediately-mutate lines will ever bump the retain count. They always operate on the same buffer as a, either by verifying it is uniquely referenced, or if not then by making a new buffer for a first.

• • •

This thread has made it quite clear that my understanding is not accurate. My best guess (which is probably also wrong) as to why it doesn’t work like this, has to do with ensuring simultaneous overlapping slice-mutations are well-behaved.

That could be fixed up with an “Already being mutated” flag similar to Dave’s. That way while in the middle of an a[...].sort() call, recursive calls to self[...].sort() would work, but trying to mutate a directly (or through a new slice) would hit that flag. Unlike Dave’s plan though, this would work in conjunction with isUniquelyReferenced rather than isDuallyReferenced.

• • •

I’m sure there are good reasons why it wasn’t implemented like this, but that’s basically how I thought it worked.

21

After reading the proposal, I am very against it.

The reason why is that this is advocating for a solution that bakes into the ABI magic bits to create semantics due to missing language features. Before ABI was fixed, I was ok with this sort of thing (since we could remove these sorts of things before ABI is finalized as we did with the pinning bit). Now I am very against embedding anything like this into the ABI UNLESS, the proposer can prove that there aren't additional language features that would make this unnecessary.

For instance, Dave, what if we were in a world where we had move only types, struct destructors, and inout locals? Would that change the solution here? Or if one had a magic wand for language features that would not conflict with the current language, what would you need to do this?

2 Likes
22

Well, I couldn't blame you for being against it on the basis that it isn't quite right, which I think @Andrew_Trick has convinced me of (even if there's a lot of what he's said I'm still waiting for clarification on). Correctness might be salvageable, or not.

I do, however, object to framing this in terms of a requirement to prove something that seems obviously unprovable. There are an infinite number of imaginable language features that hypothetically solve this problem… especially when you're going to allow for “magic wands!” The problem here is that nobody knows how make such wands to produce the result we need, much less build the wands themselves. It would be much fairer for me to demand that you prove that that the proposed ABI changes are in fact “due to missing language features” by providing a single example specification and implementation that solves the problem without ABI changes.

I think there is a more productive way to look at it:

If a human like you or I can look at a piece of code and figure out what the compiler/library should be doing with reference counts, copies, and mutation, there should be a way to encode that understanding in language semantics and features with clearly specified meaning.

I agree with that, and that it would make for a better solution, which is why I'm excited to pursue this part of the conversation:

Ideally, this process would lead to an answer without ABI changes, though I think it's conceivable we'd to arrive at the end of the process having demonstrated that implementing the rules we came up with requires such changes. At that point I think it would be reasonable to demand a disproof by counterexample from anyone objecting to the ABI change.

P.S. I also don't know what you mean by “inout locals” and have only a vague idea of what you mean by “struct destructors” (which—at least as I understand them—don't change the picture one whit).

3 Likes
23

@dabrahams Sorry if I was unclear, but I wasn't suggesting infinite possibilities. In fact, I suggested a few possible techniques explicitly: move only types, struct destructors (provided by move only types), and the ability to create a binding that in a sense is like an inout argument but over a region of code instead of over a function.

24

But Michael, it's irrelevant what you were suggesting. Meeting your demand to “prove that there aren't additional language features that would make this unnecessary” means proving something about an infinite set of unknown possible language features. And please don't say I'm just taking you too literally; solving this problem is going to require precise communication. If that's not your actual condition for accepting burning something into the ABI, what is it, exactly?

Even just limited to your suggested features, I think the condition is pretty unreasonable—how does one prove that a given tool couldn't be used to solve some problem? But I'll try anyway…

  • The problem under discussion is how to make the use of existing APIs (roughly, subscripts and swapAt), more efficient. These APIs have to work in existing code on types that don't use any new features, so the only way new features could be used to solve these problems is inside the implementation of the APIs concerned.
  • Move-only types don't allow new semantics to be implemented, they just allow us to enforce certain semantics with the type system. It's easy to see by doing a mental code transformation: just make the hypothetical move-only type copyable, take the code that would be in its destructor and instead call it explicitly in the right places. Similarly, struct destructors don't add an ability to create new semantics, they just allow certain things to be done implicitly rather than explicitly. But we don't care how explicit the standard library's implementation needs to be in order to solve this problem.
  • I still don't know enough about your "inout locals" idea to be sure, but in the only reasonable implementation of such a feature that I can imagine, they don't add any new semantics either: any “region of code” in which you could create an inout local could instead have been coded as a call to a helper function with a regular inout argument.

Most of all, I don't think any of these features get at what I see as the fundamental issue:

When an array has been inout-sliced:

  1. we want to allow the slice buffer to be mutated in-place without copying, but
  2. can't allow the buffer to be freed if the slice is assigned or resized.

Today, 1. requires uniqueness and 2. requires non-uniqueness at the point of mutation, which at least proves to me that uniqueness is insufficient information to use as the sole criterion for making decisions about whether a mutation can be done in-place. That's why my solution adds a bit.

I actually think I know how to solve the problem without relying on the ability to observe refcounts > 2, which I think is at the core of @Andrew_Trick's objection. But it still needs a bit to store the information that an array buffer is being inout-sliced. ¹ As of today I don't see a way around adding dynamic information, because the ultimate mutation being applied to the slice may not be visible to the compiler so the extra information can't reach the site of the mutation statically. That's about as close as I can come to a proof that ABI changes are needed, so maybe I did it after all. Q.E.D.?

¹ I suspect it will be hard to demonstrate because ARC isn't making all the optimizations I think Andy told me it should (“if it's doing its job”) but I'll try to code it. [Update] yeah, it's as I suspected: the compiler eagerly issues a retain for the slice, and no optimizations we have today seem to be able to move that retain even as far as the yield.

4 Likes
25

I'd just like to push back a tiny bit on making this specific to slicing Array, as I'd love to be able to do similar transformations on slices of things like matrices that may involve strides and being non-contiguous.

1 Like
26

Oh, absolutely. That's the gist of my fourth consideration:

  • This technique takes a bit too much hackery today to be broadly implementable by users, and AFAIK it can't be implemented just once by the library. I would love to find a more general solution.

The point of demonstrating it on arrays is to prove that it can be done in a way that's practically useful, not to limit it. Ideally, if we solve the problems, the solutions can be packaged into easily-reused library components.

27

As it stands though, I don't see a path for that with this technique even if we make it more user-facing, since it is based around knowledge of the buffer.

To me, the ultimate success criteria to consider this problem solvable is "does it compose"? That is, if I build a new MutableCollection type based on top of Array (or ultimately a generic Collection), could that new collection automatically acquire non-CoWing slices?

For comparison, this is how the (as yet only pitched, though implemented) design of modify works. If you implement your MutableCollection in terms of another Collection, using it as storage, and use modify instead of set for your subscript (a fairly straightforward user ask), then your custom type gains the same capability as Array wrt avoiding CoW with element mutation when backed by a collection that supports it.

As it stands, this won't be the case for non-CoW slicing. By default Slice takes a full copy of the parent, which will copy the inner array. We would need a design for Slice that accommodated this new technique, generically, on top of any other arbitrary Collection. I don't think this can be done by library changes + new runtime functions alone. I think it needs additional compiler features (as modify did), though what I still don't know.

Once we have a path here there are still possibly-insurmountable challenges:

  • this probably can't be done in an ABI stable way, so may be completely closed off to us
  • we also would need to be confident that this didn't require such additional complexity in the optimizer that it had negative knock on effects, and also would need to be robust i.e. can't fall off a cliff if, say, called from unspecialized/non-inlinable code.

I would dearly love this problem to be solved – but I think we have to be clear-eyed about the chances. At some point if we cannot solve it, we need to pivot to accepting the approach of passing around ranges explicitly and start adopting this approach widely. While this would be less elegant, and add some unfortunate foot guns (that maybe we could flag to users with static analysis), it may be better to go down that road clearly and sooner rather than continuing to hope in vain indefinitely. I'm not sure at what point we draw that line tho.

2 Likes
28

Technically it's based on being able to observe a bit associated with the buffer instance. That could be in a side table or it could be folded into the refcount header, which still has not been baked into the ABI. That's where the old "pinned" bit was; it could be brought back.

Yes, that's the ideal place to end up, for sure, and is part of what I meant by finding “something more general.” Array is a first step, and a platform for understanding the problem, a journey I think we've only just started. We certainly can't get to the ideal composable answer without completing that journey.

That's…one way to put it I guess, but it blurs some distinctions, IMO making the situation sound much more hopeless than it actually is. Being more precise and filling in some details:

  • Slice contains a copy of the thing it was sliced out of, which (AFAICT according to Andrew because the compiler isn't “doing its job”) means the slice claims a second reference to the buffer, which means that the first time the slice is mutated, the buffer will be copied.

I'm not at all certain that doesn't fall out of solving the problem for the underlying collection, with no API changes to Slice. That scenario is certainly consistent with how I currently understand the problem (which might still be wrong of course).

I don't think this can be done by library changes + new runtime functions alone. I think it needs additional compiler features (as modify did), though what I still don't know.

  • this probably can't be done in an ABI stable way, so may be completely closed off to us

I don't know why you think these things; IMO it's just much too early to judge what's going to be needed, because we still don't have a solid understanding of the problem. One step at a time.

  • we also would need to be confident that this didn't require such additional complexity in the optimizer that it had negative knock on effects, and also would need to be robust i.e. can't fall off a cliff if, say, called from unspecialized/non-inlinable code.

There's a lot of room for debate about how much performance degradation is acceptable in the presence of such optimization barriers. There are plenty of places today where going from -Onone to -O or non-inlinable to inlinable makes the difference in whether a CoW occurs. That isn't a good reason to penalize code that could be optimized.

I would dearly love this problem to be solved – but I think we have to be clear-eyed about the chances. At some point if we cannot solve it, we need to pivot to accepting the approach of passing around ranges explicitly and start adopting this approach widely. While this would be less elegant, and add some unfortunate foot guns (that maybe we could flag to users with static analysis), it may be better to go down that road clearly and sooner rather than continuing to hope in vain indefinitely.

I agree!

I'm not sure at what point we draw that line tho.

Me neither, but IMO that point is not now, when we are only just getting a bead on the nature of the problem. Unless there's been a massive effort to solve it that I don't know about in the past four months, we've barely tried to work on it at all, as a group.

1 Like
29

This is not a debatable sliding scale. It needs to be a feature that is guaranteed even at -Onone, via language mechanics and mandatory optimization passes, for it to be considered solved and act as a basis for how to design collection APIs in the standard library and beyond. It is not something that can just be an optimization possibility in -O that may or may not happen (even if it happens "most of the time"), or something that only works on non-resilient types with fully inlinable implementations.

Again, how modify works should be the guide here. Elements are yielded at +0, and this is guaranteed by the language and happens even in -Onone.

That's not to say we can't experiment, and even land improvements incrementally as a nice-to-have property of certain types (though we need to be careful to explain that it doesn't generalize, similar in nature to indices being a performance trap when moving to generic code). But there's a clear line at which point we can use it to design APIs, and that point is that there is a clear guaranteed model for when divide-and-conquer slice mutation will not trigger CoW, ever, if you follow a simple pattern when writing a collection, including building on top of other collections generically.

(Additionally, since the "win" of implementing it only for specific types is so much lower than solving the problem in full, the bar for avoiding complexity in the optimizer is higher, and the lengths to which we might go to work around the ABI problems diminish)

30

Isn't it a little presumptuous to unilaterally declare anything non-debatable? Regardless, I obviously disagree. There is a huge potential community of users for Swift that do not care at all about resilience or non-inlinable implementations, and if we fail to serve them well, Swift will not grow significantly beyond Apple platforms. Speaking for my project, which falls squarely into the domain of HPC, there are many places we'd be willing to accept some performance cliffs in -Onone if it allows us to ship a cleaner, more elegant API that performs optimally at -O. In our case, we're competing with Python for code cleanliness, so the bar is extremely high. Another way to look at it: if we had to worry about all of the potential performance cliffs that exist in Swift today, my project would have to give up on Swift, because we'd never be able to deliver sufficiently high-level abstractions.

Whether the standard library has to start exposing inelegant APIs is a separate issue, but given that all the important parts of the standard library are actually non-resilient, it's not at all obvious to me, especially since the extent of ARC optimizations performed at -Onone is completely fungible.

So, while I agree that an ideal solution has all the properties you cite, it's very debatable how far we need to get to produce substantial value.

2 Likes
31

Going back to the question about missing language features.

Could the issue be that we want Slice to sometimes represent a separate independent value, and sometimes a mutable borrow that passes writes through?

@Michael_Gottesman mentioned local inout variables. What about stored inout properties? I think a stored inout property could capture the notion of a mutable borrow of the original collection. Therefore, we could implement a slice that passes mutations through to the original collection and is capable of being fully reassigned as:

enum MutableSlice<Base: Collection> {
  case Original(base: inout Base)
  case Replaced(base: Base)
}

I don't yet have a good idea of how to connect it to existing subscript that returns a Slice, which definitely represents a separate value today. We could add another subscript (distinguished by an argument label) to Collection that returned this MutableSlice.

Of course, in order for an instance of this MutableSlice to be safely used, we should enforce the exclusivity rule. IDK if it would be possible without significantly increasing the complexity of the planned ownership model.

3 Likes
32

I'm against the implementation in the runtime because it adds much complexity. I can remember how much a relief it was when we eventually could remove pinning. It would be really unfortunate if we would re-add something like that.

I like @gribozavr's idea. I'm not sure why "fully reassign" is actually needed (the compiler could prevent it). It would be awesome if a slice could be represented very cleanly as

struct MutableSlice<Base: Collection> {
  let base: inout Base
  let start: Base.Index
  let end: Base.Index
}

But I didn't think that through and maybe I'm missing something.

1 Like
33

To be able to mutate the base via the slice like this, you need to handle two things: the wipeout of the slice, and the possible escape of the slice. In both cases, I think it's a question of detecting it has happened and incrementing the reference counts in the base at that point to protect the it (in the case of wipeout: not leading to releasing the base when it should continue to exist; and in the case of escape, preserving the value semantics of the base). If you do that, I don't think you need to worry about preventing reassignment to the slice (which I don't think is possible – it's pretty baked into swift that you can always do that).

35

Hi Dmitri!

While that's true, I don't think it captures the reasons for our problem. I think what you just described is a characteristic of anything that can be written through a property or subscript. For example, here's a String property doing that:

struct X { var s = "abcde" }
var x: X

// `String` acts as independent value
var t = x.s
t.removeLast() // doesn't affect x

// `String` acts as “mutable borrow” that passes writes through.
x.s.removeLast()

Making it performant with CoW

When the target of the write is implemented with CoW, getting good performance depends on the property/subscript access not prematurely claiming an additional reference. When the target is already stored in memory somewhere, the compiler happens to oblige us by not claiming that reference, provided the accessor is either:

  • yielding the target's address from a _modify, or
  • is the accessor synthesized by the compiler for regular stored properties

The issue for slicing…

…is two^H^Hhreefold: [EDITED]

  1. When you slice an array, the Slice instance isn't already in memory anywhere, so it has to be constructed on the stack. At least today, that construction eagerly claims an additional reference to the buffer.

  2. If we could avoid claiming a reference for the yielded slice, when a slice is reshaped:

     a[3...7].removeLast()

    there is code that will deallocate elements belonging to the array if it finds the slice to be uniquely-referenced. I'm not sure how much of that code is compiled into clients already, but that could be a problem if the only test is uniqueness.

  3. If you could avoid claiming a reference for the yielded slice, you'd still need to prevent the array buffer from being deallocated in situations like this

     extension ArraySlice { 
   mutating func reassign() { self = ArraySlice() } 
 }
 a[3...7].reassign()
36

Years ago, before we ever got pinning as it was eventually formulated, @Joe_Groff and I designed a similar system that solved the problems of this thread, but that design wasn't adopted. I suggest to you that while it may have been a relief to you to see the bit gone, the bit (or something equivalent) was always needed to produce the semantics we want.

If you want to solve the problem without an extra bit you need to deal with all three parts of the issue for slicing. Solving the first part (the extra reference) would mean a way for the slicing subscript to initialize and destroy that inout Base without retaining it. However, I don't know how anyone can solve the other two parts of the problem, especially the third part, if there's only a single reference.

But I didn't think that through and maybe I'm missing something.

I mean, you're not missing anything in saying “it would be awesome.” The problem is making that feature do what's needed. As far as I can tell, I've proven that you can't solve the problem using only uniqueness tests and no additional bits.

37

Yes, the idea is this is a new representation that would take a "borrowed" copy of the Base. That borrow would mean a +0 copy (solving your issue #1), and would need to be scoped to reserve exclusive access of the Base. It would somehow need to detect the borrowed reference dropping to zero and not free it, but instead just return it (solving issue #3). For #2 – after the yield the Base needs code to examine the slice and reconcile, much like that code you linked to does. Generalizing the fast path, where it detects nothing needs doing because it was mutated in place, is hard though for a generic Slice implementation.

38

That's not what the code I linked to is doing. As a byproduct of detecting uniqueness in the slice it is releasing references to array elements outside the slice's bounds.

Anyhow, this still doesn't explain how the proposal can work. You need to be able to store a copy of this slice somewhere in the escaping case, and that copy needs to be +1, and needs to release its reference when destroyed. I'm not sure what inout is actually supposed to mean in this context, but if it means “don't retain another reference,” that's not intrinsic to the base property of all instances; it's intrinsic to the context (slicing subscript) where this one instance was created¹ — the slice that escapes does need to retain another reference, and in every other way needs to act like something that doesn't have inout on its base.

As I've been saying, when this thing crosses a visibility boundary in the compiler, you need some way to know how to handle it when it's being mutated. Imagine f is a mutating method, opaque to the compiler.

var a = [ ... ]
a[3...7].f()      // 1
var b = a[3...7]
a = []
b.f()             // 2

In both cases 1 and 2, f should observe that the buffer is uniquely referenced. If f happens to reassign self, in case 1 it must not release the buffer but in case 2 it must release the buffer. Something needs to communicate the need for that different behavior into the body of f. The information is not present in the type system, so it has to be communicated dynamically.

The only other possibility is that f (dynamically) communicates the potential release back up to the call site, where it's known whether we're in an inout slicing context.

Either way, there's dynamic information needed.

¹ That's why Erik's proposed notation doesn't make sense to me.

2 Likes
39

Here is the explanation I promised. This post only relates to the soundness of the implementation in GitHub - dabrahams/DivideAndConquer: Demonstrates a fix for the mutating divide-and-conquer COW problem, which I'll refer to below as "DivideAndConquer". Responding in-line point-by-point won't converge in a useful place. Instead I wanted to deal with this specific aspect coherently in one place. This post has no bearing on other important issues, notably:

  • a path to generalizing the design to other collections

  • guaranteeing non-copying behavior at -Onone

  • incurring Array implementation complexity--the initial
    implementation costs are insiginificant relative to the long-term
    costs

Let's keep those issues in separate posts.

Fix for Divide-And-Conquer

+++ b/Sources/DivideAndConquer/ContiguousArray.swift

   public subscript(bounds: Range<Int>) -> ArraySlice<Element> {
     get {
       _checkIndex(bounds.lowerBound)
       _checkIndex(bounds.upperBound)
       return ArraySlice(_buffer: _buffer[bounds])
     }
     _modify {
       _checkIndex(bounds.lowerBound)
       _checkIndex(bounds.upperBound)

       let wasUnique = _buffer.isUniquelyReferenced()
       var rhs = ArraySlice(_buffer: _buffer[bounds])
+      // Any runtime function that the compiler can't make any
+      // assumptions about and that takes the address of 'rhs' will
+      // work here.
+      strongRefCount(&rhs)

Test Case Requiring Fix

@inline(never)
func testEscapeWithTripleReference(array: inout ContiguousArray<Int>) -> ArraySlice<Int> {
1:  return copyAndMutate(slice: &array[0..<4])
}

@inline(__always)
func copyAndMutate(slice: inout ArraySlice<Int>) -> ArraySlice<Int> {
  // Why was `slice` passed inout? Maybe it used to be
  // `slice[0..<1].reverse()` which is inlined to nothing.
2:  var sliceCopy = slice
3:  sliceCopy[0..<2].reverse()
4:  return sliceCopy
}

var array = DivideAndConquer.ContiguousArray(0..<5)
let slice = testEscapeWithTripleReference(array: &array)
assert(array[0] != slice[0])

Explanation of the Bug

I was not actually able to break the above test, even after much massaging. However, I believe SIL rules allow the case to break, and I think ARC optimization based on OSSA form after inlining would be sufficient.

Here is the sequence of operations, where 'owner' always refers to the CoW storage object:

  1. ContiguousArray.subscript(bounds:)_modify

a. wasUnique = array.isUnique() = true
b. 'array.owner.isBorrowed' = true
c. retain 'slice.owner'

  1. Copy ArraySlice

d. retain 'sliceCopy.owner'

  1. ArraySlice.subscript(bounds:)_modify

e. isDuallyReferenced() = false (refcount==3)
f. borrowedOwner = nil
g. .reverse() copies storage
h. borrowedOwner == nil

  1. return 'sliceCopy'

i. retain 'returnedSlice.owner'
j. release 'sliceCopy.owner'

Optimization: remove the retain/release of 'sliceCopy' based on proving all of these conditions:

  • 'sliceCopy' is never checked for uniqueness (or mutated in any way)
  • 'array' outlives 'sliceCopy'
  • 'array.owner' is immutable during the lifetime of 'sliceCopy'

Now we have:

a. wasUnique = array.isUnique() = true
b. 'array.owner.isBorrowed' = true
c. retain 'slice.owner'
d. reuse 'sliceCopy.owner'
e. isDuallyReferenced() = true (refcount==2)
f. release 'borrowedOwner' (refcount==1)
g. .reverse() performs in-place mutation
h. retain 'borrowedOwner' (refcount==2)
i. retain 'returnedSlice.owner' (refcount==3)
j. ignore 'sliceCopy.owner'

This clobbers the original array.

Explanation of the Bug Fix

ContiguousArray.subscript(bounds:)_modify now takes the address of the mutable ArraySlice that it yields. This guarantees that it's 'owner' reference is opaque to the compiler. I used a call to strongRefCount(&rhs), but let's generalize this concept to _blackHole(inout AnyObject). We need two guarantees:

  • The compiler assumes that '_blackHole' may release its inout argument.

  • The compiler assumes that '_blackHole' cannot be eliminated.

The compiler can now never eliminate this operation:

c. retain 'slice.owner'

..because the retained reference may immediately be released by '_blackHole'. Even after the call to '_blackHole', it cannot share the representation of 'array.owner' and 'slice.owner', because it has no way to prove that they are the same value.

Consequences of the Bug Fix

For ArraySlice rvalues:

  • Implementation: Array.subscript(bounds:).get with no corresponding writeback

  • Returned ArraySlice may or may not be retained.

  • ArraySlice storage is copied on mutation (after copying to an lvalue).

  • Unaffected by the Divide-And-Conquer.

For ArraySlice lvalues today

  • Implementation: Array.subscript(bounds:).get + Array.subscript(bounds:).set:

  • Returned ArraySlice is retained and its storage is copied whenever
    it is mutated (after optimization)

  • Returned ArraySlice may not be retained if it is not mutated
    e.g. array[0..<1].reverse() never mutates the slice

For ArraySlice lvalues with (fixed) DivideAndConquer

  • Implementation: Array.subscript(bounds:)._modify

  • Returned ArraySlice is retained whenever it is mutated (after optimization)

  • Storage is never copied unless the slice is copied.

  • Returned ArraySlice may be retained if it is not mutated
    e.g. array[0..<1].reverse() requires a retain and can't be fully eliminated.

DivideAndConquer trades-off an extra retain in a corner case (divide-and-conquer base case) for eliminating a copy of the storage in the common case (ignoring the other overhead of borrowed status checks).

Explanation of Compile-Time Reference Counting

Axiom 1: At a single program point, any two instances of the same value (identical values) can share a representation.

Theorem 1: for any reference-counted type, checking uniqueness requires apparent mutability of the reference. Otherwise, its reference may share its representation with other instances of the same value.

Commentary: The source of confusion around this stems from the variable scopes that appear evident at the source level. But the presence of those scopes do not subvert the rules above.

While it is true that these two forms may have different semantics in some resepects:

Form 1:

let x = foo()
bar(x)
_ = x

Form 2:
bar(foo())

Those semantics have no impact on whether the implementation can share the representations of foo's returned value, the value in variable x, and bar's argument. Simply put, a single reference will suffice. This is fundamental to the compiler's model of the language.

Axiom 2: A reference passed as an argument (whether owned or inout) may be released no more than once without at least one retain for every additional release.

ARC can be reduced to a counting problem where each operation has a net effect on its operand's reference count.

var obj: AnyObject

retain(obj):  +1
release(obj): -1
apply(obj):   -1..<infinite (possible owned convention)
apply(&obj):  -1..<infinite (reassignment is a release)

The only constraint on the compile-time implementation is proving that an object's reference count does not reach zero before its last use. It's the same exercise required for manual reference counting.

Theorem 2: The only fully general way to check refcount==2 is by simultaneously mutating two distinct references to the same object. For example:

Builtin.isDuallyReferenced(_ object1: inout AnyObject, _ object2: inout AnyObject) -> Bool {
  do {
    _precondition(object1 == object2)
  }
  return swift_isDuallyReference(Builtin.addressof(&object1),
                                 Builtin.addressod(&object2))
}

You may be thinking "can't the compiler have special magic operations".

Yes, the compiler can have all the magic it wants, but that does not change any of these facts. Those magic operations exist within APIs, and those APIs must adhere to the calling conventions of the language. The only way out of the rules I've put forth above would be a language level calling convention that provides for a single reference argument to be net released more than once (without corresponding retains). I'm comfortable stating that we will never have such a convention.

Axiom 3: for any CoW type, mutability implies uniquenes.

Theorem 3: From Theorem 1 and Axiom 3. For any CoW type, mutability and uniqueness are mutually implied. These conditions can be used interchangeably. (I find this useful to simply the discussion).

Let's apply these rules to DivideAndConquer.

The ArraySlice does not have access to the Array when checking isDuallyReferenced(). With access to only one reference, isDuallyReferenced() does not prove anything on its own.

To rely on isDuallyReferenced(), we must guarantee that ArraySlice "owns" a distinct reference to storage. That can be guaranteed if any of these statements are shown true:

  • the ArraySlice is checked for uniqueness (i.e. mutated)--and this
    check cannot be removed.

  • the ArraySlice lifetime is surpasses the Array's lifetime

  • the Array is checked for uniqueness within the ArraySlice's
    lifetime--and this check cannot be removed.

We do know that the Array will be accessed again after ArraySlice's lifetime. That does not help.

We do not otherwise have any control over Array. Therefore, the only option is forcing ArraySlice to be apprently mutated regardless of how much information the compiler has. Note that this is exactly equivalent to forcing the ArraySlice's owner reference to be copied, which is exactly equivalent to forcing a retain. A Builtin.forceRetain(inout AnyObject) would have the same effect.

Conclusion

DivideAndConquer is a working implementation of in-place ArraySlice mutation, given a fairly nonintrusive fix.

isDuallyReferenced(inout AnyObject), as written, should not be exposed as a user-level API.

4 Likes