Removal of WeakMap/WeakSet clear

[Allen Wirfs-Brock]

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.

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 (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.

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.

There is no change in the GC latency of an object uses 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 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?  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).

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).

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