On Nov 28, 2014, at 4:21 AM, Andreas Rossberg wrote:
> On 27 November 2014 at 19:40, Allen Wirfs-Brock <al...@wirfs-brock.com> wrote:
>> On Nov 27, 2014, at 1:17 AM, Andreas Rossberg wrote:
>>> The discussion here still makes various untested assumptions about the
>>> transposed representation. With respect to .clear in particular, it
>>> seems to assume that this representation does not normally need the
>>> ability to iterate (internally) over the keys of a weak map. AFAICT,
>>> that is incorrect. Both the implementation we discussed in the V8
>>> team, and from what I heard, the implementation in IE, maintain a list
>>> of all its keys for each weak map. Otherwise, when a map dies, you
>>> couldn't generally kill the entries and the values associated with
>>> them easily and in a timely manner. (And of course, this list means
>>> almost twice the space usage for a map, because you duplicate part of
>>> the information.)
Based upon you description below, it isn't clear you you means by a
"transposed" representation. I this something you are actually using in V8?
What you describe below sounds like a fairly conventional (non inverted) map
representation.
some more comments below
>>>
>>
>> ...
>
> 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. In the
> transposed implementation you describe that is not the case. If the
> map dies, the value will survive another (major GC) cycle. Under
> memory pressure that can increase the rate of major GCs.
It isn't clear what you mean by "ephemeral weak map implementation". Is this a
ephemeron-based design or is this some other key map scheme (reference??).
If the later, what does "ephemeral" relate to? Does it assume that the keys are
more ephemeral than the map.
Whether there is a delayed value collection issue probably depends upon the
patterns of usage and the overall design of the GC. If the keys are generally
more ephemeral than the maps then this probably won't be a problem. If the
maps are generally more ephemeral than the keys and the GC is a
multi-generation collator then the map is likely to have already been collected
by the the time the inverted map in a key object is scanned.
>
> To achieve timely reclamation in the former implementation, the GC
> maintains a list of all live weak maps, and traverses it during the
> atomic pause in the final marking phase (in an incremental GC). If you
> wanted to do the analog in the transposed representation, then the GC
> would dually need to maintain a list of all _keys_, and always
> traverse all of that. That would clearly be very expensive (there are
> typically far more keys than maps). The more practical solution is to
> have one such list per weak map, so that you only iterate over
> relevant keys of maps that have died. Alas, every map gets a list of
> its keys.
>
> If you don't want to do that, then you'll have inferior GC behaviour
> with the transposed representation. In addition, you'll have to
> implement the whole weak property mechanism, and make every access to
> a key/value pair require an indirection through such a weak reference.
But doesn't this design have have complexity that is similar to a ephemeron
table solution? In particular, doesn't it result in key/value circularities if
a value is or references the same WeakMap as the inverted map key value? To
avoid this won't the inverted map essentially have to have ephemeron table
semantics?
Allen
_______________________________________________
es-discuss mailing list
es-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es-discuss
