linear-time weak-map gc

Mark S. Miller erights at google.com
Sun Mar 20 08:57:14 PDT 2011


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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/es-discuss/attachments/20110320/81fa7401/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: weakmap-alg.pdf
Type: application/pdf
Size: 384701 bytes
Desc: not available
URL: <http://mail.mozilla.org/pipermail/es-discuss/attachments/20110320/81fa7401/attachment-0001.pdf>


More information about the es-discuss mailing list