Fair enough -- just interpret my email as an aside. :) Dave
On Mar 20, 2011, at 8:57 AM, Mark S. Miller wrote: > Hi Dave, > > 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(N**2) > complexity measure, even if it was never hit in practice. While this O(N**2) > 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. > > > On Sun, Mar 20, 2011 at 7:20 AM, David Herman <dher...@mozilla.com> wrote: > Hi Felix, > > 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. > > Dave > > On Mar 20, 2011, at 3:12 AM, felix wrote: > > > 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. > > _______________________________________________ > > es-discuss mailing list > > es-discuss@mozilla.org > > https://mail.mozilla.org/listinfo/es-discuss > > _______________________________________________ > es-discuss mailing list > es-discuss@mozilla.org > https://mail.mozilla.org/listinfo/es-discuss > > > > -- > Cheers, > --MarkM > <weakmap-alg.pdf>
_______________________________________________ es-discuss mailing list es-discuss@mozilla.org https://mail.mozilla.org/listinfo/es-discuss
