linear-time weak-map gc

Jason Orendorff jason.orendorff at
Sun Mar 20 08:14:04 PDT 2011

On Sun, Mar 20, 2011 at 5:12 AM, felix <felix8a at> wrote:
> I haven't tried implementing this, so no idea how well it works in practice.

I thought of this. It would definitely work. However, it requires an
extra conditional branch for each object marked by the GC. So relative
to the algorithm described on the wiki, there's savings of O(W^2) and
a cost of O(L) with a fairly small constant factor.

Dave is right that the spec shouldn't include an algorithm.
Implementations will measure performance and choose the algorithm
that's best in practice.

It's weird, though--specifying anything about WeakMap reachability at
all is a lot like specifying proper tail calls: it's hard to say what
you mean without being a lot more concrete about the abstract machine
the language runs on than you would be otherwise. The real requirement
is simply that the WeakMap not observably consume space for entries
that can't be queried. Maybe we could just say that.


More information about the es-discuss mailing list