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

Reply via email to