linear-time weak-map gc

felix felix8a at gmail.com
Sun Mar 20 03:12:26 PDT 2011


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.


More information about the es-discuss mailing list