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