linear-time weak-map gc

David Herman dherman at mozilla.com
Sun Mar 20 08:59:21 PDT 2011


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 <dherman at 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 at mozilla.org
> > https://mail.mozilla.org/listinfo/es-discuss
> 
> _______________________________________________
> es-discuss mailing list
> es-discuss at mozilla.org
> https://mail.mozilla.org/listinfo/es-discuss
> 
> 
> 
> -- 
>     Cheers,
>     --MarkM
> <weakmap-alg.pdf>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/es-discuss/attachments/20110320/a2926842/attachment.html>


More information about the es-discuss mailing list