On 27 November 2014 at 19:40, Allen Wirfs-Brock <[email protected]> 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. > > 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).
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. 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. > 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). At least in V8, we have various internal uses of ephemeral data structures anyway. In contrast, there is only one use of weak references, which is for persistent handles in the API, and we have plans to get rid of that. ;) But more to the point, weak properties are far more complicated than just weak references. At least if you want to avoid substantial secondary costs for object accesses (see my mail from a while ago). /Andreas > 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
