On 29 November 2014 at 22:30, Mark S. Miller <erig...@google.com> wrote:
> On Fri, Nov 28, 2014 at 4:21 AM, Andreas Rossberg <rossb...@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
_______________________________________________
es-discuss mailing list
es-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es-discuss
