Can an implementation that never collects anything be compliant?

[syg]

That is, does the spec have the guarantee (in its own terminology) that the GC condemns all unreachable objects in finite time?

[lars-t-hansen]

Supposing there is one, how long do you have to run before you can say for sure that the guarantee is broken?

I can probably think of situations where such a guarantee would be useful but it would likely come at a hefty spec & performance price and I doubt we want it. And unless you can bound the time, what does it really give you?

IMO an implementation that arbitrarily delays collection [1] should be considered compliant.

[1] https://dl.acm.org/citation.cfm?id=802797 "The possibility of incredibly cheap, fantastically large media for storage gives rise to a realistic LISP memory management scheme under which GC may be postponed for days, or even indefinitely [...] Tertiary memory is used to archive pages of the LISP environment which are perhaps reclaimable, but which have not been proven so [...]. Some scenarios are presented [...] by which a requisite compactifying GC would be done “overnight”, or over the weekend. With enough tertiary available, one design could last for over 12 years without a GC."

EDIT: Excerpted more of that abstract

[dtribble]

The simple answer is that ES doesn't currently provide specifications in this area, and we do not propose such a thing, but "indefinite postponement" I would not consider a reasonable implementation. I have some thoughts we can consider

In general, GC is conservative and cannot be guaranteed to even notice that any particular object is unreachable. For example, a compiler could place a captured reference X that is used the first time a function is called together with a value Y that is used all future times. "X" is formally unreachable but most implementations will never notice that. Therefore of course, finalization is also conservative.

So there are two aspects that must be addressed differently:

• GC is conservative
• GC takes non-deterministic time

Specifications need some formal weasel words for properties for that have clear and crisp goal, but that can never actually be guaranteed. Weasel words around that goal itself are usually obfuscating. Hash collision has that flavor (you want them different but cannot guarantee it; how many collisions are OK?). Coming from the world of MUST/SHOULD/MAY, I favor the use of the word "EXPECT". "Hashes for distinct objects are EXPECTED to be different." Similarly, "GC is EXPECTED to reclaim all unreachable objects within finite time."

The time issue, however, is a lot more like the "fairness" property of a scheduler: "a job that is continuously enabled will get to start running in finite time". Engineers occasionally sneer at it because "finite time" could mean "after I ship version 2". But it's a more useful engineering property than it appears: to actually engineer a system, you must achieve fairness by implementing a stronger property (e.g., round robin is bounded fairness where the bound is the number of processes) or it will be buggy. Thus, for example, my one-liner above would obligate systems to GC occasionally even without memory pressure. The committee may prefer to allow reclaimable objects to not get reclaimed when we have plenty of memory, but that has its own cost.

[lars-t-hansen]

Once or twice I've written GCs with a static area to hold permanent objects - runtime and application code and data, collected by dumping a heap image. A static area is mutable however and so is just a kind of old generation where there is an expectation of finding virtually no garbage, and so GCing it is basically pointless. But it is still possible to create some garbage in the static area, eg by storing a pointer into it referencing a new definition of some function (in a younger generation) and making the old definition (in the static area) unreferenced. In particular, it is possible to store a reference to a younger object O into a cell in the static area, and then to make that cell unreferenced by some other store in the static area. If nobody else is referencing O it is now garbage.

Should we expect O to be GC'd? Only if the static area is ever collected. But why would we do that, if there's essentially no hope of finding garbage there?

Non-age-based generational GCs have this problem in general; they select some spaces to collect based on the expectation of how much garbage they will find, and so long as that strategy leads to acceptable memory pressure and GC time, there's no reason ever to consider spaces that are deemed to be full of live data.

Clearly we can require the GC to once in a while spend time on areas it deems contain little or no garbage, but do we really want to do that?

[erights]

See https://web.archive.org/web/20160318124045/http://wiki.ecmascript.org/doku.php?id=strawman:gc_semantics for some old thoughts on specifying garbage collection semantics and its interaction with specified weakness.

[erights]

Clearly we can require the GC to once in a while spend time on areas it deems contain little or no garbage, but do we really want to do that?

https://web.archive.org/web/20160318124045/http://wiki.ecmascript.org/doku.php?id=strawman:gc_semantics suggests the rule:

All objects which are not transitively strongly reachable from roots SHOULD eventually be collected, if needed to prevent the program execution from failing due to memory exhaustion. [emphasis added]

So by that suggestion, the answer to your question is no on two grounds:

• no requirement in any case. This is at most a SHOULD.
• the SHOULD applies only when the alternative is failure by memory exhaustion.

This suggests that we might eventually, in a separate proposal, want to include something like Java's [Runtime.gc()](https://docs.oracle.com/javase/7/docs/api/java/lang/Runtime.html#gc()) whose spec says:

Calling this method suggests that the Java virtual machine expend effort toward recycling unused objects in order to make the memory they currently occupy available for quick reuse. [emphasis added]

We can understand this as modifying the earlier statement to

All objects which are not transitively strongly reachable from roots SHOULD eventually be collected, if suggestGC() is called, or if needed to prevent the program execution from failing due to memory exhaustion. [emphasis added]

[alexweej]

Seems that requirement to clean up 'if needed ... due to memory exhaustion' probably needs strengthening if we are to use the GC feature of JS to do automatic resource collection. It's not just about memory anymore.

[dtribble]

With was host bindings, remote references, device control bindings, handles for large media content like bitmaps and graphics contexts, etc., having the GC driver be "due to memory exhaustion" in the JS runtime is too narrow. You can think of the external systems we interface to as other allocation zones. As soon as you have a system with more than one allocation zone, where objects retained in one zone impact the deallocation of objects in another zone, then simple memory pressure is not sufficient. It's certainly a hard general problem, but the basic minimum is "eventually GC if there's been memory churn or a change in incoming pointers".

So that would apply to a static zone as well: the possibility of GC is typically recorded in changes to remember tables or other inter-generation GC bookkeeping structures.

Thus, I would prefer that we move towards specifying some stronger GC guarantee. I consider that separate from this proposal, however, hence there's no mention of it.

[allenwb]

At least once, in each thread like this I feel compelled to quote this old observation I posted here regarding using GCs as a general purpose resource manager.

George Bosworth, a former colleague of mine and the inventor of Ephemerons, gave an experience report at a ISMM a number of years ago where he discussed GC, finalization, and general resource management. The following is a my reconstruction of his key point:

A modern GC is a heuristics-based resource manager.  The resources it manages generally have very low individual value (a few dozen bytes of memory) and exist is vast numbers.  There is a wide distribution of life-times of these resources, but the majority are highly ephemeral.  The average latency of resource recovery is important but the recovery latency of any individual resource is generally unimportant. The heuristics of a great GC take all of these characteristics into accounts.  When you piggy-back upon a GC  (via finalization, or equivalent mechanism) the management of a different kind of resource you are applying the heuristic of memory resource management to the management of the piggy-backed resources. This is typically a poor fit.  For example, the piggy-backed resource may be of high individual value and exist in limited numbers (George used file descriptors as an example).  A good GC will be a bad resource manager for such resources. 

There are many types of resources that need to be managed in complex systems. Thinking that a GC will serve as a good management foundation for most of those resources is naive. 

[dtribble]

That's a great summary, and generally good guidance. Thank you for posting it here (as well as every other time)!

An important difference now is that the spread of sizes has more orders of magnitude. Thus, a vast number of objects that are a few words (nodes in a virtual dom) manage a vast number of node that are 1-200k (DOM nodes). Because there are so many, we want and expect automatic management. Even though we can manage a vast number of each, the difference in scale between zones results in all the same issue; the small side will have enormous headroom while the big side is thrashing and overwhelmed.

The guidance still seems wise: we would like to make sure we can get reasonable latency of recovery on the big side, which means the small side needs to make occasional progress. But we should still not expect recovery of individual resources.

But because of the wide difference, there's a slippery slope. If individual items on the big side have a distribution of sizes, reasonable code at some point cares that most individuals actually get collected. And of course some programmers will count on individuals getting collected. They cannot count on a latency there, but it might be pretty reasonable to count on eventual collection of each individual.

Does that scaling difference suggest to you how we should balance these concerns?

[allenwb]

Small objects pointing to large objects isn't really the issue as most modern GCs probably have heuristics for effectively recovering large object garbage.

George's point was more about objects (probably small) that contain encoded references to external non-memory entities whose lifecycle need to be explicitly managed. There is no reason to think that GC triggered mechanisms for managing such resources will be suitably timely.

[dtribble]

When I abstracted to "small objects in one allocation zone referring to bigger objects in another zone", I was actually primarily thinking of "small objects that contain encoded references to external entities" e.g., JS objects that has a larger wasm "object" associated with them. That's such a useful pattern and a lot of cases really do map to the same kind of pattern that GCs are good at ... except that of course the objects are in different zones. With weak refs, we can get pretty good at that pattern, while trying to keep people from relying on it for the bad case (e.g., y emphasizing that it's for experts to do conservative finalization or some such).

[allenwb]

I worry that the general belief that "finalization" will take care of such issues distract from the development of more reliable ways to manage such resource dependencies such a cancelable resource subscriptions backed up by, keep-alive, deadline triggered, or app lifecycle triggered reclamation policies.

[erights]

Small objects pointing to large objects isn't really the issue as most modern GCs probably have heuristics for effectively recovering large object garbage.

While the motivation to focus on is indeed cross-zone garbage, I actually don't understand the above claim. Within a single heap managed by a single conservative gc,

if

• a tiny object t strongly points at a huge object h,
• h is not otherwise retained,
  • t is not actually strongly reachable from roots,
  • but the conservative gc never notices that t is unreachable,

then it will fail to reclaim h no matter what its mechanisms for large objects are.

Given that tiny objects can be treated conservatively, anything they point to, even locally, may leak. You cannot and should not count on any individual h ever being collected. Whether within or between zones, and matter what the size, we should never count on gc to reclaim any one particular thing. Conservative gc gives us a statistical expectation only. For the real motivating use cases---building conservative inter-zone gc from conservative local gc---this is enough.

[allenwb]

@erights

I'm not really sure what new point you are trying to make. I believe we all agree that conservative collectors are leaky collectors. Hence in a conservative collector any resource management scheme that is trigger by the collection of a specific object will be unreliable.

[littledan]

I think, in practice, we will face a world where nobody collects everything eventually, but an implementation which never collects anything would not be ecosystem-compatible. I don't have a good idea about how to formalize this middle state (I am skeptical we can/should formalize it). I think we signed up for being OK with this property by promoting WeakRefs to Stage 2.

[erights]

@allenwb

I'm not really sure what new point you are trying to make. ... Hence in a conservative collector any resource management scheme that is trigger by the collection of a specific object will be unreliable.

The point I'm trying to make is that a conservative collector is already locally unreliable, but in practice collects enough to be useful, usually, with no guarantees. We can use weakrefs to compose local conservative collectors into a distributed acyclic conservative collector. Just like the collection of a specific local object by a local conservative collector is unreliable, so the collection of a specific object by the resulting distributed acyclic conservative collector will be unreliable. The question is, does the distributed collector collect enough to be useful, usually, with no guarantees? Experience with similar systems suggests the answer is yes. We'll see.

[hotsphink]

The current implementation of the SpiderMonkey GC, with a hypothetical WeakRef implementation added, would make it fairly easy to accidentally construct scenarios where some WeakRefs are never collected. It would merely require creating some WeakRefs in a Realm that then stops allocating, and then never have too much overall memory pressure. (The granularity is coarser than a Realm, but that's the closest spec construct.) >90% of the time we will collect a subset of Realms, and usually those will only be the Realms that have experienced a decent amount of allocation. (In a browser, there are other reasons why we might collect all Realms, so it may be observed more as a long delay, but we're working on removing most of those too.)

Depending on how WeakRefs and finalizers end up being used, we may be forced to set a bit on dormant Realms if they contain any WeakRefs, and force them to be included them in any GC (or at least collect them more often.) It would basically mean that using a WeakRef would turn on a "go slow" bit -- though unless the Realm is really huge, the impact should be fairly limited.

Even worse, we could be forced to add a time-based heuristic to trigger WeakRef Realm collection, again depending on how these are used in practice. Hopefully dominant implementations won't cave to prompt finalization demands of users, so we won't have to go this far. But it's a possible end state, and it would make it even more likely for users to end up relying on finalizers for inappropriate resources.

This sort of thing is unavoidably part of adding WeakRefs or finalizers, so we've already signed up for these sorts of headaches to some extent. I'm just bringing it up to explain why I'm strongly in favor of declaring non-collecting implementations to be compliant.

[erights]

I agree. However, I have a quibble on a side point that does not affect your conclusion:

The granularity is coarser than a Realm, but that's the closest spec construct.

It is indeed coarser than Realm. I believe the relevant spec constructs are "agent" and "agent cluster".

[hotsphink]

The granularity is coarser than a Realm, but that's the closest spec construct.

It is indeed coarser than Realm. I believe the relevant spec constructs are "agent" and "agent cluster".

I'm talking about the granularity specific to our GC implementation. It's called a Zone internally, mostly because we had already used a dozen other synonyms (compartment, region, arena, ...). The mapping between Zones and Realms (or tabs, or agent clusters) is not fixed and we keep changing it.

I had never heard of agents or agent clusters before, but an agent cluster is definitely too broad -- a Zone would never include the Web Worker children of an HTML page, for example.

[littledan]

That is, does the spec have the guarantee (in its own terminology) that the GC condemns all unreachable objects in finite time?

tl;dr no

We spent some time discussing the invariants for garbage collection in various issues, and reached Stage 3 on rather weak invariants that take into account that some objects just won't be collected. It seems impractical to make a stronger guarantee.