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
