[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 thatisUniquelyReferenced
may release the reference addressed byisUniquelyReferenced's
inout
argument, andisUniquelyReferenced
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.
- An object's reference count will never be 1 unless there's only one variable (whose lifetime could not have ended already) referencing it.
- 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
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).
Builtin.isUnique
forces an in-memory copy of a reference by virtue of taking its addressinout
.
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 addressinout
.
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 lvaluesx1
, andx2
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.
- 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.
- 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
—but we do have both the
ArrayBuffer
and theSliceBuffer
passedinout
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 ArraySlicerhs
. 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.