linear-time weak-map gc

felix felix8a at gmail.com
Tue Mar 22 02:22:47 PDT 2011


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