On Nov 27, 2014, at 11:49 AM, Brendan Eich wrote:
> (Nit-correcting along with comments and questions in-line, just trying to
> parse what you mean, not snarking -- except for the first comment :-D.)
>
> Allen Wirfs-Brock 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.)
>>> > > So from that perspective at least, .clear is not an issue.
>>
>> Since I made this assertion that 'clear' interfere with with an inverted
>> implementation of WeakMap/Set I'll explain what I'm thinking.
>>
>> First, here is my design for an inverted implementation:
>>
>> Every object internally maintains a table (probably a hash table if it
>> contains more than a few elements) that is used to implement WeakMap/Set.
>> Entry in the table is a key/value pair where the key is a WeakMap/Set
>> instance. Values are arbitrary ES values. Let's call such a table an
>> "inverted map" and generically refer to such WeakMaps/Sets as WCs.
>
> (Water Closet? Just curious what the C stands for :-P.)
Collection
>
>> A WC object has no instance specific state (other than the state required of
>> all objects, such as [[Prototype]] etc.
>>
>> The WeakMap 'set' method applied to a WeakMap M with arguments k and v works
>> by accessing the inverted map of k and creating an entry in the inverted map
>> with key: M and value: k
>
> value: v, right?
oops, right
>
>> (or updating the value field with v with an entry for M already exists).
>>
>> WeakMap get/set/has/delete work similarly by accessing keys' inverted map
>> using M as the key.
>
> [A] This means M must be mapped to WC, via some internal member or
> (side-)side-table.
M is an instance of a WC, eg, M is a WeakMap which is a kind of WC
>
>> Note that since such a WC instance does not contain any references to its
>> keys (or values) it does not prevent an object that is used as one of its
>> keys from being garbage collected. When an object is GC'd its inverted map
>> is, of course, also discarded.
>
> In this sense the inverted map is atomic, featureless, just an identity --
> like a symbol, but hidden from inspection. It could be a symbol, even.
No, a WC instance is atomic, featureless, etc. internally. Externally it
expose a WeakMap or WeakSet api.
The inverted map is part of the implementation level represent of an Object.
It is a map-like data structure in the same sense that the own roperties of an
object might be implemented using a map-like data structure
>
>> There is no change in the GC latency of an object uses
>
> ("used")
>
>> as a WeakMap key. If the only reference to an object used as a value in a
>> Weakmap is from a single inverted map entry, then that value object should
>> be GC's
>
> "GC'ed"
>
>> when its key value is GC'ed.
>>
>> So far great, none of this requires anything special from the GC. But what
>> if there are no references to a WC instance other than from the keys of
>> inverted maps?
>
> If M is garbage then its connection [A] to its WC or WCs won't be considered
> by the GC. Just confirming that you are presuming M is garbage in this
> paragraph.
yes
>
> If M is not garbage, then [A] must keep WC alive.
I think you are seeing an additional pointer that I didn't intend. M is a WC so
there is no [A]. There concern is about the reference from the key side of k's
inverted map. It should keep M alive.
>
>> In that case the WC instance should be considered garbage, but if the
>> inverted map keys are normal strong object references such should-be-garbage
>> WC instance won't be recognized as such. (This might not be a very big deal
>> if we were only talking about the WC instances as they are small and
>> presumably not very numerous, but retaining those instances also cause any
>> corresponding inverted map value references to be retained).
>
> That's not clear to me: if a WC is implemented using a symbol, and nothing
> else references that symbol, then (unlike string-equated property keys, where
> a new name could be computed later), the WC-keyed entries can be purged.
But WC instances do have mutable state (their [[Prototype]] and [[Exstensible]]
internal slots. Plus you might use a WC as the key of a WC, so that means a WC
instance also needs to have it's own internally mutable inverted map to such
usages.
>
>> We can fix this by having the GC treat all key entries of inverted maps as
>> weak references. Note that this requires weak reference support in the GC
>> (definitely a complication) but does not require that the GC implement
>> ephemeron semantics (a bigger complication).
>
> I would appreciate a reply to the previous comment ("That's not clear to me")
> before going on. This may be just a clarifying point, or a tangent, with
> respect to the feasibility of .clear for maps with inverted representations,
> but I hope it will clarify things so no one (including me!) goes down a bogus
> path.
>
> /be
hope it's clearer now
Allen
>
>>
>> Note that nothing above requires (or allows) enumerating the entries of a
>> WC. Explicit enumeration operations or a 'clear' method would require some
>> way to enumerate the objects that are used as keys of a WC.
>>
>> This is the end of my assumed inverted WC design and why I assert that a
>> clear method is incompatible with it.
>>
>> Lets explore how we can extend this design to support iteration (of the sort
>> need to implement 'clear'). To do iteration we need to have some way to
>> find all of the objects that are used as keys of a WC. Since were are using
>> an inverted representation (and assuming we don't want to examine all
>> objects to see if the WC is a key in its inverted map). We need a way to
>> efficiently find all objects that are used as key of a particular WC. The
>> obvious way to do that would be to add to the internal state of a WC a list
>> of all active key values. This would need to be a list represented using
>> weak references. Otherwise, it would prevent key objected from being
>> properly GC'ed. So, at the very least, clear or other iteration requires an
>> additional weak reference list for each WC (or perhaps a likely less
>> efficient single global weak list) that would not otherwise be needed.
>>
>> Allen
>>
>>
>> _______________________________________________
>> es-discuss mailing list
>> [email protected]
>> https://mail.mozilla.org/listinfo/es-discuss
>>
>
_______________________________________________
es-discuss mailing list
[email protected]
https://mail.mozilla.org/listinfo/es-discuss