(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.)
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?
(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.
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.
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.
If M is not garbage, then [A] must keep WC 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.
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
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
