Removal of WeakMap/WeakSet clear

Mark S. Miller erights at google.com
Tue Dec 2 10:15:12 PST 2014


Good. I think we're coming to a mutual understanding. By "scavenge" I
mean exactly your "minor collection". I think collecting typical
garbage during minor collection, rather than promoting/tenuring it, is
desperately important, and dominates the other efficiency
considerations mentioned in this thread. Of the common scenario, you
say:

> In a minor collection nothing is collected, because it doesn't handle
> ephemerons at all.

which clears up my confusion from your earlier claim

> the value in a (map,key,value) triple can be reclaimed _immediately_
> (in the same cycle) when _either_ the map _or_ the key dies.

In the common scenario, as of the moment of the minor collection, the
key and value are unreachable, but v8 collects neither. Instead, both
are expensively promoted/tenured.

Of the transposed scenario, you say:

> In both minor or major collection both m and v are immediately
> reclaimed, because neither is strongly reachable at that point

which shows the asymmetry, and that v8 is effectively optimizing for
the wrong side of that asymmetry. By adopting what Allen and I refer
to as the transposed representation (as opposed to your transposed
representation), you'd instead be able to say of the common scenario

> In both minor or major collection both k and v are immediately
> reclaimed, because neither is strongly reachable at that point

which would be much more valuable than any other efficiency issue
discussed in this thread.

In any case, we now both understand that you can't have both at the
moment of a minor collection because, as we agree, a minor collection

> doesn't handle ephemerons at all.

You have to choose one side or the other. Why optimize for the
transposed scenario rather than the common one?




On Tue, Dec 2, 2014 at 9:23 AM, Andreas Rossberg <rossberg at google.com> wrote:
> On 29 November 2014 at 22:30, Mark S. Miller <erights at google.com> wrote:
>> On Fri, Nov 28, 2014 at 4:21 AM, Andreas Rossberg <rossberg at google.com> wrote:
>> [...]
>>> With a normal ephemeral weak map implementation, like the one in V8,
>>> the value in a (map,key,value) triple can be reclaimed _immediately_
>>> (in the same cycle) when _either_ the map _or_ the key dies.
>>
>> Hi Andreas, it is at this claim that I get confused. This is certainly
>> not true for a normal *ephemeron* map implementation, and is not true
>> for any ephemeron implementation I've read about, including years of
>> prior postings here on es-discuss. If this is true for v8, great!
>> Please walk me through what the v8 implementation does under the
>> following scenario:
>>
>> m = new WeakMap();
>> non_garbage_var = m;
>> //... stuff not changing whether m is garbage
>> //... scavenge
>> {
>>     const k = {};
>>     const v = [k, m];
>>     m.set(k, v);
>> }
>> //...assume that variables k and v are no longer reachable.
>> //...scavenge
>>
>> // m has remained non-garbage the whole time.
>> // Immediately after the scavenge above, have k and/or v been either
>> collected or promoted?
>
> In a minor collection nothing is collected, because it doesn't handle
> ephemerons at all.
>
> If a major collection happens after the block, then both k and v (or
> any such cycle, for that matter) are reclaimed during that collection.
> (Ignoring complications like incremental marking, which might already
> have marked k and v live while the block was still active.)
>
> In a transposed representation for weak maps with key lists, a minor
> collection would not collect anything either, because k would still be
> reachable from m through its list of keys (and minor doesn't handle
> ephemerons specially). A major collection would be able to remove k
> from m's key list and reclaim it.
>
>
>> I am also interested in the transposed scenario:
>>
>> k = {};
>> non_garbage_var = k;
>> //... stuff not changing whether k is garbage
>> //... scavenge
>> {
>>     const m = new WeakMap();
>>     const v = [k, m];
>>     m.set(k, v);
>> }
>> //...assume that variables m and v are no longer reachable.
>> //...scavenge
>>
>> // k has remained non-garbage the whole time.
>> // Immediately after the scavenge above, have m and/or v been either
>> collected or promoted?
>
> In both minor or major collection both m and v are immediately
> reclaimed, because neither is strongly reachable at that point (unless
> the WeakMap is pretenured, which would make it survive the minor).
>
> However, in a transposed representation for weak maps, a minor
> collection would no longer reclaim anything, because m would actually
> be reachable from k (and minor collections do not handle ephemerons
> specially). A major collection would still reclaim both m and v
> immediately, _presuming_ m has a list of keys, which it can traverse
> to find k and remove itself from it. If that wasn't the case, the
> major collection could _not_ reclaim m or v in this cycle.
>
> So having a list of keys in the transposed map representation
> potentially causes some keys to survive a _minor_ collection, but
> prevents values from surviving a _major_ collection. Independent of
> that, the transposed map representation makes scenario 2 worse wrt
> minor collections.
>
>> If the existing v8 implementation efficiently collects v as of the
>> second scavenge in both scenarios, or even if there is any known way
>> of doing so efficiently (that also deals with the general ephemeron
>> issue), I would be pleasantly astonished. My assumptions would indeed
>> be wrong, and I would indeed need to revisit all conclusions that
>> followed from these assumptions.
>>
>> Do we have such good news?
>>
>> Just to be explicit, my assumptions are:
>>
>> Scavenging, in order to be as super efficient as it needs to be,
>> avoids any ephemeron collection algorithm during the scavenge itself.
>
> All ephemeron collections are visited in the final atomic pause of the
> marking phase of a major GC cycle, which will only mark values life
> that still have strongly reachable keys. All others are collected by
> the following sweeping phase.
>
> However, if by "scavenging" you meant minor GC then that does not
> handle ephemeron collections at all.
>
> /Andreas
>
>
>> A normal non-transposed ephemeron map implementation will promote k
>> and v as of the second scavenge in the first scenario, which is the
>> only safe option that postpones the ephemeron part of the gc
>> algorithm.
>>
>> A normal non-transposed ephemeron map implementation will collect m
>> and v as of the second scavenge in the second scenario, since these
>> are collected merely by the classic scavenge without awareness of
>> ephemeron issues.
>>
>> A transposed ephemeron map implementation will collect k and v as of
>> the second scavenge in the first scenario, since these are collected
>> merely by the classic scavenge without awareness of ephemeron issues.
>>
>> A transposed ephemeron map implementation will promote m and v as of
>> the second scavenge in the second scenario, which is the only safe
>> option that postpones the ephemeron part of the gc algorithm for
>> transposed map representations.
>>
>>
>> --
>>     Cheers,
>>     --MarkM



-- 
    Cheers,
    --MarkM


More information about the es-discuss mailing list