-
Notifications
You must be signed in to change notification settings - Fork 40
Decoupling from spec object graph for nulling out [[Target]] #105
Comments
That said, if we can agree on a stronger and more deterministic spec, that still allows the optimizations that engines already do and cannot be talked out of, then great. As with concurrency memory models, implementations will only be willing to pay a minor performance cost at most to forego optimizations that would make a mess of the spec. But the spec cannot demand any more than that or the spec becomes an empty fiction. We need to find a creative compromise of the cleanest most predicable spec that implementors will actually be willing to implement. When I wrote the text above, apparently in 2011, the specific optimization I knew I needed to allow is dead variable elimination. I believe that is still the case. |
Agree that we should push for as strong and deterministic a spec as we can so long as people are willing to implement. Do I take that to mean a preference for continuing to use spec object graph reachability as a proxy for garbage-collectability in the spec? |
I would be surprised if people were willing to implement that, for example, because of the desire to eliminate dead variables. What is the minimal additional wiggle room needed for the dead variable elimination that implementations want the freedom to do? Other than dead variable elimination, are there any other implementation optimizations which would become observable violations of a simple reachability spec? |
Ah, I see. I had created this dichotomy of spec graph reachability vs implementation observability in my head -- of course the naive spec graph reachability is too restrictive, as you point out. But the larger point is the spectrum has more points on it. We might be able to stick with reachability with the right clever concessions. |
I have come around and I am convinced that reachability definitely doesn't work for the optimization reasons and more. I am quite daunted at the prospect of defining a notion of observability, however. Let me outline a particular scenario I'm worried about. Suppose we define observability as heycam recommended by quantification over all possible future executions of the script. Also suppose spec keeps some object o in an internal list [[ForSpecMachineryOnly]] for its own spec machinery such that that list is always unreachable and unobservable from script. At time t, because script can never dereference o, it is collected and a finalizer is observably run. Should the spec, at time t+1, be able to then get o out of [[ForSpecMachineryOnly]] and do something with it that doesn't affect execution, like asserting that it has certain properties? This feels odd to me and I am not sure how to think about it yet. Edit: I realize asserting that it has certain properties might trigger proxy traps. Let's say instead that it has certain internal fields. |
We are the ones writing the spec. We shouldn't do that. If we do, we should consider the object to be reachable. To do otherwise would be an extraordinary act of hair splitting that would only be justified by an extraordinary reason. |
I was thinking about things like dead variable elimination and closure edge cases when this first occurred to me, but perhaps even more worrying is the world of library and embedder specifications, which would suddenly have to think about a whole new level of meaning to their text, as @domenic raised in #18 . Between these, I am skeptical that anyone will (or should) actually implement the current precise language. |
The wording in #105 (comment) looks pretty great to me, except I don't understand how "be dereferenced" should be defined. |
I'm not so sure. This also ties in to Dan's how "be dereferenced" should be defined. Let's consider a real example, FunctionDeclarationInstantiation steps 26 and 28.f.i.4. Step 26 initializes parameters, and 28.f.i.4 copies the initial parameter value to a same-named For the following snippet of code: function g(unused) {
var unused;
// do stuff but doesn't use unused
}
function f() {
var o = {};
gRef = new WeakRef(o);
// reasonable to empty gRef here
g(o);
} Seems reasonable to me to inline If so, going back to FunctionDeclarationInstantiation, the question I'm grappling with is: if In the context of Dan's question of how "dereferenced" should be defined, ISTM it has to be tied to some notion of observability, which is daunting. Does that make sense? Edit: typos Edit 2: This particular example doesn't work because newly created |
Regarding #105 (comment), I had an enlightening conversation with Jim Blandy and Jason Orendorff from the SpiderMonkey team. A clean way to address my concern is simply to keep the spec assumption that all objects live forever. From a spec's POV, This assumption will end up being viral for all specs that interact with JS. I think it's reasonable, and that HTML at the very least seems like it'd be fine with this. Here's a write up from Jim: https://gist.github.com/jimblandy/0014dc11233d2d40df922af850b0489a |
Considering all objects to be immortal still allows us to classify each object as "collected" or "retained". Only irrelevant objects can be classified as collected. Only weakrefs to "collected" objects can be nulled. How does "relevant" relate to the language I quote at #105 (comment) :
I would say that if the the operational semantics of the remaining execution includes such a possibility, then the object is "relevant". Otherwise it is "irrelevant". Of course, we cannot tell where the boundary is precisely. But any object "known to be irrelevant" can be reclassified as "collected". |
Agree.
That's the art of it, yeah. In my example from #105 (comment), do you think that counts as the operational semantics dereferencing |
We need to separate two senses of "dereference" that I had not thought to distinguish.
I think the second notion of |
closed by mistake |
I think it's really good to talk all this through. I just wanted to ask, when does this need to be decided by? Is it OK to iterate I'm these details during Stage 3? |
That is an important process question for which I do not know the answer. Perhaps the best precedent would be the design and debugging of memory model for SABs. That said, I hope this does not need to be precisely settled in detail before stage 3. I hope agreement on the general approach to take should be enough. But maybe not. |
I agree the exact language should not be a stage 3 blocker, but consensus on the spirit of the language should be gotten from the implementers before stage 3. |
@erights I'm trying to understand #105 (comment) . What do you think we could write as specification text to capture this? How does it differ from the "observability" direction discussed above in, well, observability? Do we agree, in this thread, that references from specification data structures don't necessarily keep things alive for the purposes of WeakRefs and FinalizationGroups? If so, maybe that would be enough to nail down the "spirit" for Stage 3 and respond to #31. I can't tell, though, whether @erights would agree with this. |
Before I answer, I realize I should first ask: What do either of you (@syg or @littledan) mean by "observability"? What I am looking for is a criteria that would set a lower bound, i.e., that would let us reason to a conclusion that a particular object at a particular time in specified (as opposed to implemented) execution sequence cannot be observably collected, i.e., that observing a weakref to that object at that time cannot report that the object is collected. In the previous examples, can we conclude that function g1(unused) {
// do stuff but doesn't use unused
}
function f1() {
const o = {};
const gRef = new WeakRef(o);
// reasonable to empty gRef here
g1(o);
} but function g2(used) {
// a clever enough compiler might have been able to optimize this out:
used.foo;
}
function f2() {
const o = {};
const gRef = new WeakRef(o);
// UNREASONABLE to empty gRef here
g2(o);
} ? (Code above revised to avoid distracting "var"s.) |
I don't have a formal definition to answer with. When I used the word "observable", I was thinking about something which would change the "result" of the program, or how it interacts with the rest of the world. But, in particular, I was thinking about omitting WeakRef and FinalizationGroup operations from the definition--those are allowed to change, and that's the point. It's just that, if nothing except for those operations changes in their semantics, it'd be fine to collect the object. I guess your example program is a little incomplete, since the WeakRef constructor includes KeepDuringJob. But if a turn has passed, I'd say, if the compiler can prove that there will be no side effect, then yes, it's OK if the WeakRef becomes empty. |
Oops. Yes, I should have inserted a turn boundary: function g1(unused) {
// do stuff but doesn't use unused
}
async function f1() {
const o = {};
const gRef = new WeakRef(o);
await 1;
// reasonable to empty gRef here
g1(o);
} vs function g2(used) {
// a clever enough compiler might have been able to optimize this out:
used.foo;
}
async function f2() {
const o = {};
const gRef = new WeakRef(o);
await 1;
// UNREASONABLE to empty gRef here
g2(o);
}
So here's the trickiness. Depending on the contents of the object If your notion of observability still allows collection immediately after the |
Yes, of course in that case, it should not be collected in that case. I was assuming that the compiler could trace that it was |
I don't have a particular notion of observability in mind, but was suggesting an alternative framework instead of "dereferenced". If we proceed with a "good" dereference and a "bad" dereference as laid out above, I feel like the task of classifying every access in the spec is not tractable. Practically I want this notion of observability to be, in spirit, the same as the spirit we used to guide the memory model: ideally, the set of optimizations that apply to programs without weak refs should also be applicable to those with weak refs. We need to first agree on what the unit of observability is. An evaluation step (i.e. a reduction step in the operational semantics) itself is too restrictive. Since JS (thanks to your vision @erights!) has such a small surface in the core spec, and depends on a host to do effectful things, I think we can work backwards from the JS-host boundary. Every time we call out to the host, the objects that the host can reach must be assumed to be observable (with some kind of escape hatch to allow the host to do optimizations as well). An initial formulation may be: Let an execution be 0+ evaluation steps. The space of all executions may be thought of a step and the set of all possible tails, which are themselves executions. Let a class of steps be called observed steps. For every observed step, let S_pre be the reachable objects before the step and S_post be the reachable objects after the step. Base case: a step that calls the host is observed. A WeakRef may be emptied out at any step if doing so does not change the S_pre and S_post of any future observed step in any execution. Edit: Note that the above is very permissive, much more permissive than real world compilers because doing that kind of analysis is definitely intractable. I guess I'm saying it seems easier to me to start with the super permissive thing and work backwards. |
Were this the only ideal, we would have adopted a much more permissive memory model, such as other languages (Java, C++) and architectures have. For both, there are opposing ideals, for which we seek a compromise that accommodates a best-of-both of these ideals. For both, the opposing ideal is enabling more reliable static reasoning about correctness --- both formal and informal reasoning. @waldemarhorwat's concerns about quantum-like indeterminate junk (I forget the actual terminology) led us to a stronger memory model than any other comparable language, forcing us to avoid certain optimizations. Here, the comparable issue is reasoning from a program to guarantees about what will not be observably collected. For some X which, by the specified operational state, is reachable from roots, sometimes we wish to allow optimizations which might cause X to be observably collected. However, we need to be clear about when X is reachable from roots in ways that optimizations cannot disrupt, i.e., that guarantee that X cannot be observably collected. I return to the example: function g2(used) {
// a clever enough compiler might have been able to optimize this out:
used.foo;
}
async function f2() {
const o = {};
const gRef = new WeakRef(o);
await 1;
// UNREASONABLE to empty gRef here
g2(o);
} Because the meaning of I do not subscribe to driving the relevant observation criteria from external host effects, though I see the elegance of doing so. Were we to allow this, then a subsystem that had been correct when connected directly to the outside world might become incorrect when connected only to an internal mock of that outside world, because the difference in internal weakref behavior causes something else that is externally observable. |
We called it "quantum garbage". I know the actual optimization itself as "rematerialization", viz. rematerializing an array read.
Very much so! Just like the memory model had to be strong enough for reasoning and weak enough for CPU/compiler reality, so the weak ref spec must also be strong enough for reasoning and weak enough for GC/compiler reality. We both want to arrive at that unknown sweet spot. I am approaching it by identifying the weakest guarantee then strengthening, while you are favoring approaching from the other end of the spectrum. My reasoning is that there is a practical difference between getting implementer consensus for SABs and for WeakRefs. For SABs, the optimizations we wanted verboten weren't written yet. Since SAB was an entirely new API, we weren't asking any engine to check their existing optimizations. This isn't true for WeakRefs though: by saying we don't want to be as permissive as possible, we are literally making the previously unobservable observable. Like you've said, we need to gauge the implementers' appetite for change here, but my feeling is we're in a much more difficult position than with SABs.
That is a good point. However, #31 has already shown that whatever semantics we come up with here must be applicable by host specs that embed JS to their own references of JS objects. I understand your concern for not driving observability wholesale from the host, but I contend the host must have a say in the observability of a GC thing, and thus the correctness of the program. This point is a real-world one: while all JS engines have a tracing GC of varying sophistication, there is higher variety in how DOM nodes are managed. Firefox has a cycle collector (formally, the dual of a GC). Blink AFAIU now has a tracing GC, "Oilpan". AFAIU WebKit does ref counting and has no CC or GC. I'm skeptical we can come up with a set of "must be observably not collected" rules that is palatable for these very different implementations. |
Hi @syg that's a nice summary of the issues. Regarding:
We must. Without being able to reason from safe bounds, we cannot soundly use the spec for much. For example, the cross-address-space distributed acyclic gc use, as well as the js-to-wasm use, cannot be sound without reasoning about the absence of "false" collection signals. |
Let's examine constraints from the other side. If there are never any guarantees about what it not collected, then it is impossible to write a correct program that uses weakrefs to clean something up when "it" won't be further used.
|
@erights, I agree with all these constraints. I do, however, think that there is a lot of room for disagreement on what "it is impossible to write a correct program" means :) I'm quite skeptical that we'll be able to agree on anything that'll restrict implementations' ability to apply future optimizations to which objects can be GC'd. To make that more concrete, consider the case of Web Workers. A Worker can be collected in its entirety if it can't possibly execute code in the future. That is the case if no channel exists to it or it doesn't have any A more interesting example is a Worker that
In the absence of WeakRefs, I think the following holds in that scenario: AFAICT the question under discussion here effectively boils down to what change to this statement the introduction of WeakRefs requires. (Of course there are lots of other scenarios to consider, but I think they don't differ in fundamental ways.) A simple change would be to the following: Of note, this definition allows implementations to introduce optimizations that change whether I'm highly skeptical about our ability to define liveness guarantees that'd constrain an implementation's freedom compared to the above. At the same time, I do think that this actually is a useful definition that allows developers to write programs with guarantees about when a WeakRef will continue to be valid, so perhaps it's sufficient? |
Do we agree that, according to your text, the implementation is not free to collect function g2(used) {
used.foo;
}
async function f2() {
const o = {};
const gRef = new WeakRef(o);
await 1;
// UNREASONABLE to empty gRef here
g2(o);
}
onmessage = f2; |
Also, I'll just be pedantic again and point out that this text doesn't actually state that an implementation is not free to collect except under these conditions. Compare:
|
@erights To be precise, is the intended reason that |
I agree that this is better.
However, in light of this question I want to change the statement slightly: An implementation is only free to collect objects that content can't reach by any code that could execute in the future, excluding through dereferencing weak references. I'm sure that there are better ways to put this. However, with this definition yes, AFAICT an implementation would be free to collect |
To @tschneidereit's point about different tiers earlire, I think it's perfectly reasonable that an implementation will collect Suppose there is nothing on the Then, suppose the host loads a new script that injects a proxy into the |
Before answering the above questions, I'd like to ask about a similar example: function g3(used) {
used.foo();
}
let x = 0;
async function f3() {
const o = {foo() {console.log(++x);}};
const gRef = new WeakRef(o);
await 1;
// UNREASONABLE to empty gRef here
g3(o);
}
onmessage = f3; Does everyone agree that the implementation is not free to collect If so, can you reason from your proposed text to this conclusion? |
I don't understand what would prevent collecting |
o is passed into g3, after that comment - it would certainly be a problem if the spec allowed it to be collected there. |
This issue is pretty subtle, so @ljharb and I talked it over offline and agreed to the following:
|
I agree. We should go to stage 3 with the current understanding of the two hard constraints, both of which must be met. We can then figure out how to meet them during stage 3. |
@erights asked me to give my opinion here based on what I know of how the OCaml compiler handles weak references. There are two mechanisms at play there: optimizations and runtime handling. Regarding optimizations, it's basically a static liveness analysis after program transformation (such as inlining function calls). It is done fairly late in the compilation chain. I don't know how to do a precise enough static analysis when staying at the source code level, so I don't think this approach is viable for the spec if we don't talk about program transformation. Alternatively, we could use a dynamic notion of liveness (something is live if it can be reached from the roots, which include things in the stack, without going through week pointer), and say that it is allowed to null any object that is not live. But I'm afraid this amounts to specifying what a correct GC would be (and weakrefs are just an small addition to that), which requires being able to talk about the runtime state of programs. |
My understanding is pretty close to @brabalan's and I think is a good argument for being more lax than not with guarantees. |
@erights Edit: retracted in light of Lars's comment below. |
If the implementation can ascertain that the WeakRef constructor is the original WeakRef constructor (eg as a result of online profiling) then it can reason that the I think the point I'm trying to make here is that it's not just about reachability but also about how reachability is created -- the clause in the prose about "excluding through weak references" ignores how weak references are created (or not). Another point in the example above is that even if the spec should require the WeakRef to be created in all cases even if it's not observable, the implementation might still be allowed to know enough about how it works that it can create two objects, one to pass to the WeakRef (which will never be seen by anyone) and one to pass to g3. (After which the second o is optimized away and g3 and foo are inlined and the final call of f3 becomes simply The implementation might also move the creation of the |
Really, you wouldn't just inline the call to console.log into f3 after reasoning about reachability of o? |
I retract my agreement. :) |
Hey, now that we seem to agree on the reachability of the identity itself to constitute liveness (in offline discussion), does anyone want to write this up as a PR against the draft specification? |
If folks aren’t in a hurry, I’d be happy to after I’m back from PTO on June
17.
…On Sun, Jun 9, 2019 at 20:11 Daniel Ehrenberg ***@***.***> wrote:
Hey, now that we seem to agree on the reachability of the identity itself
to constitute liveness (in offline discussion), does anyone want to write
this up as a PR against the draft specification?
—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
<#105?email_source=notifications&email_token=AAAXLUOQJDE7MWVGJQ6B26LPZVBV3A5CNFSM4HM5X272YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODXIPJCI#issuecomment-500233353>,
or mute the thread
<https://github.com/notifications/unsubscribe-auth/AAAXLUOUSJCMJHJJ7CWCPPTPZVBV3ANCNFSM4HM5X27Q>
.
|
I believe this is now closeable given that #142 was merged in mid-august. |
The referenced PR comment appears to have been resolved along with issue tc39#105.
The referenced PR comment appears to have been resolved along with issue #105.
Dan has expressed a desire to rephrase the language in the spec around when it's allowed to null out the [[Target]] slot of WeakRefs. In particular, to not tie it to the reachability of the spec object graph.
One off-the-cuff formulation might be a counterfactual:
For a value v in the [[Target]] slot, at any particular point in evaluation, if there does not exist a program that does not use WeakRef or FinalizationGroup APIs on any not-derefed-this-turn WeakRefs that would evaluate to a value w such that SameValue(v, w) is true, then the [[Target]] slot may be replaced with the value empty.
There are trade-offs here. Some of them that I can think of:
Pros:
Cons:
My current opinion is that loose language here is ultimately not desirable. Thoughts, @littledan and @erights?
The text was updated successfully, but these errors were encountered: