Removal of WeakMap/WeakSet clear

[Allen Wirfs-Brock]

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
>> es-discuss at mozilla.org
>> https://mail.mozilla.org/listinfo/es-discuss
>> 
>