linear-time weak-map gc

felix felix8a at
Tue Mar 22 02:22:47 PDT 2011

On Sun, Mar 20, 2011 at 8:14 AM, Jason Orendorff
<jason.orendorff at> wrote:
> 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.

you might be able to minimize that cost by marking known ephemeron
keys with an extra typecode bit when you encounter them.  most
type-switch logic should ignore that ephemeron-key bit, but gc can
switch on typecode+ephemeron-key-bit, so you only incur an extra
conditional branch for some subset of live ephemeron keys.  of course
if type bits are scarce, this might not be a good trade-off.

More information about the es-discuss mailing list