linear-time weak-map gc
I have a note on the wiki page offering a less algorithmic approach to specifying weak maps. I don't think we should be putting GC algorithms in the spec at all; that would be overspecification. Instead, we should just focus on defining reachability, and leave implementors free to compute reachability with whatever algorithms best fit their engines.
If people think they would be helpful, non-normative, suggestive algorithms might have a place in the spec. But IMO normative algorithms would be a mistake.
On Sun, Mar 20, 2011 at 5:12 AM, felix <felix8a at gmail.com> wrote:
I haven't tried implementing this, so no idea how well it works in practice.
I thought of this. It would definitely work. However, it requires an extra conditional branch for each object marked by the GC. So relative to the algorithm described on the wiki, there's savings of O(W^2) and a cost of O(L) with a fairly small constant factor.
Dave is right that the spec shouldn't include an algorithm. Implementations will measure performance and choose the algorithm that's best in practice.
It's weird, though--specifying anything about WeakMap reachability at all is a lot like specifying proper tail calls: it's hard to say what you mean without being a lot more concrete about the abstract machine the language runs on than you would be otherwise. The real requirement is simply that the WeakMap not observably consume space for entries that can't be queried. Maybe we could just say that.
It's weird, though--specifying anything about WeakMap reachability at all is a lot like specifying proper tail calls: it's hard to say what you mean without being a lot more concrete about the abstract machine the language runs on than you would be otherwise. The real requirement is simply that the WeakMap not observably consume space for entries that can't be queried. Maybe we could just say that.
Yeah. The perfect is the enemy of the good when it comes to specifying these kinds of features. We don't have a formal semantics for the rest of the language anyway, so we shouldn't be aiming for a formal cost model, too. Instead I think we need a combination of as-precise-as-reasonably-possible informal English in the spec with the best tests we can come up with for evaluating implementations.
Come to think of it, evaluating implementations for proper tail calls is a little easier, at least in implementations with fixed-size stacks and stack overflow exceptions. I'm not quite sure how you write weak map tests that check memory consumption, unless implementations expose heap size measurements. (They'd be especially hard to automate, but I'd rather have the ability to test manually than none at all.)
Anyone have experience with this from, say, the JVM and its weak references?
I think you misunderstand the purpose of posting this algorithm. Before Felix's algorithm, to the best of my knowledge all documented and/or implemented ephemeron collection algorithms had a worst case O(N2) complexity measure, even if it was never hit in practice. While this O(N2) term lurked there, some JavaScript engine implementors were rightly nervous about accepting WeakMaps into the spec; considering even vetoing WeakMaps at the May meeting for this reason.
Before I saw Felix's algorithm, to address these misgivings, Andreas Gal and I were working on one, draft attached for historical interest, that also gets rid of the O(N**2) but is inferior in all dimensions to Felix's algorithm. (Thanks also to Gil Tene for helping with the explanatory approach in that draft.) Once I saw Felix's algorithm, I encouraged him to post it, so we could lay this question to rest.
As for whether any particular JavaScript engine should use Felix's algorithm or one that makes different tradeoffs (e.g., a rare O(N**2) in exchange for a lower constant overhead in the typical case), we should clearly leave to implementors. There is indeed nothing normative about this.
Fair enough -- just interpret my email as an aside. :)
typically this is seen as a quality of implementation issue. Note the we (and most other language specs.) don't say much (or anything) about GC in general. In one sense we don't need to say anything else about WeakMaps because it would be a lower quality implementation to retain objects in one that are provably not accessible. However, because of the long history of such poor implementations we need to say say just enough to make it clear what we expect.
It is something I'm sure I can draft when the time comes, but it isn't the most pressing matter.
typically this is seen as a quality of implementation issue. Note the we (and most other language specs.) don't say much (or anything) about GC in general. In one sense we don't need to say anything else about WeakMaps because it would be a lower quality implementation to retain objects in one that are provably not accessible. However, because of the long history of such poor implementations we need to say say just enough to make it clear what we expect.
It is something I'm sure I can draft when the time comes, but it isn't the most pressing matter.
Sure. I shouldn't have caused a diversion about what goes in the spec. I have a reasonably clear picture of how to do it anyway.
I am still curious how people write tests to evaluate the quality of weak references. Obviously you can expose lower-level, non-standard API's that provide metrics, but I wonder if there's any way to write standard code that tests weakly held data. I'm guessing there isn't. Again, this isn't pressing.
On Mar 20, 2011, at 6:53 PM, David Herman wrote:
typically this is seen as a quality of implementation issue. Note the we (and most other language specs.) don't say much (or anything) about GC in general. In one sense we don't need to say anything else about WeakMaps because it would be a lower quality implementation to retain objects in one that are provably not accessible. However, because of the long history of such poor implementations we need to say say just enough to make it clear what we expect.
It is something I'm sure I can draft when the time comes, but it isn't the most pressing matter.
Sure. I shouldn't have caused a diversion about what goes in the spec. I have a reasonably clear picture of how to do it anyway.
I am still curious how people write tests to evaluate the quality of weak references. Obviously you can expose lower-level, non-standard API's that provide metrics, but I wonder if there's any way to write standard code that tests weakly held data. I'm guessing there isn't. Again, this isn't pressing.
You can't test weakmap behaviour in any real way, at least not without exposing really specific details of gc implementation. To do so you'd have to require fairly explicit GC algorithms, and details about what an implementation is allowed to do in terms of lowering and what not, and when GC may occur.
I'm honestly not sure you can even test that a "weak map" is weak at all.
On Sun, Mar 20, 2011 at 8:14 AM, Jason Orendorff <jason.orendorff at gmail.com> wrote:
On Sun, Mar 20, 2011 at 5:12 AM, felix <felix8a at gmail.com> wrote:
I haven't tried implementing this, so no idea how well it works in practice.
I thought of this. It would definitely work. However, it requires an extra conditional branch for each object marked by the GC. So relative to the algorithm described on the wiki, there's savings of O(W^2) and a cost of O(L) with a fairly small constant factor.
you might be able to minimize that cost by marking known ephemeron keys with an extra typecode bit when you encounter them. most type-switch logic should ignore that ephemeron-key bit, but gc can switch on typecode+ephemeron-key-bit, so you only incur an extra conditional branch for some subset of live ephemeron keys. of course if type bits are scarce, this might not be a good trade-off.
so, the gc algorithm described at harmony:weak_maps#abstract_gc_algorithm has a worst-case runtime of O(L+W*W) where L is the number of live objects, and W is the number of entries in live weak maps.
O(W*W) happens because the algorithm scans all weak-map entries for keys that are known to be live, then marks the values associated with those live keys. in the pathological case, each weak-map scan will discover one live key, and marking that key's value will cause another weak-map key to be marked live, which will be discovered in the next weak-map scan, etc.
I suspect in practice the pathological case is rare, and all live weak-map entries will usually be discovered in a small number of scans, making it closer to O(L+W) than O(L+W*W), but the potential for worst-case quadratic behavior is annoying.
so, the algorithm below has a worst-case runtime of O(L+W), at the cost of O(W) additional memory (which can be reserved beforehand whenever a weak-map is created or grown).
the basic idea is, when we mark a weak map live, there are two cases to consider for each entry in the weak map: 1, if we know the key is live, we can mark the value live. 2, if we don't know the key is live, we can remember the fact that the key is a "guard" for the value. later, if we mark an object that's a guard, we also mark the values it's guarding.
the full algorithm looks like this:
let guardedby[] be a table that maps an object k to a list of objects [v0,v1,...] color all objects white color all roots gray while there are gray objects, pick a gray object x { // normal gc marking for every y directly reachable from x { if y is white, color y gray } // special handling for weak-map entries if x is a weak map { for every k,v in x { if v is white { if k is gray or black { color v gray } else { // we don't know yet if k is live, but we'll find out eventually append v to guardedby[k] } } } } // special handling for objects known to be weak-map keys for every v in guardedby[x] { // v was added to guardedby[x] because it's in a live weak map, // and we now know its key is live, therefore v is live if v is white, color v gray } color x black }
I haven't tried implementing this, so no idea how well it works in practice.
so, the gc algorithm described at http://wiki.ecmascript.org/doku.php?id=harmony:weak_maps#abstract_gc_algorithm has a worst-case runtime of O(L+W*W) where L is the number of live objects, and W is the number of entries in live weak maps. O(W*W) happens because the algorithm scans all weak-map entries for keys that are known to be live, then marks the values associated with those live keys. in the pathological case, each weak-map scan will discover one live key, and marking that key's value will cause another weak-map key to be marked live, which will be discovered in the next weak-map scan, etc. I suspect in practice the pathological case is rare, and all live weak-map entries will usually be discovered in a small number of scans, making it closer to O(L+W) than O(L+W*W), but the potential for worst-case quadratic behavior is annoying. so, the algorithm below has a worst-case runtime of O(L+W), at the cost of O(W) additional memory (which can be reserved beforehand whenever a weak-map is created or grown). the basic idea is, when we mark a weak map live, there are two cases to consider for each entry in the weak map: 1, if we know the key is live, we can mark the value live. 2, if we don't know the key is live, we can remember the fact that the key is a "guard" for the value. later, if we mark an object that's a guard, we also mark the values it's guarding. the full algorithm looks like this: let guardedby[] be a table that maps an object k to a list of objects [v0,v1,...] color all objects white color all roots gray while there are gray objects, pick a gray object x { // normal gc marking for every y directly reachable from x { if y is white, color y gray } // special handling for weak-map entries if x is a weak map { for every k,v in x { if v is white { if k is gray or black { color v gray } else { // we don't know yet if k is live, but we'll find out eventually append v to guardedby[k] } } } } // special handling for objects known to be weak-map keys for every v in guardedby[x] { // v was added to guardedby[x] because it's in a live weak map, // and we now know its key is live, therefore v is live if v is white, color v gray } color x black } I haven't tried implementing this, so no idea how well it works in practice.