On 10/22/2014 02:26 PM, Mark Miller wrote:
>
>
> On Wed, Oct 22, 2014 at 1:44 PM, Steve Fink <sphink at gmail.com
> <mailto:sphink at gmail.com>> wrote:
>
>     On 10/22/2014 07:45 AM, Mark S. Miller wrote:
>     >
>     > * Only objects that have been used as keys in FastWeakMaps would
>     ever
>     > have their [[Shadow]] set, so this could also be allocated on
>     demand,
>     > given only a bit saying whether it is present. Besides this
>     storage of
>     > this bit, there is no other effect or cost on any non-weakmap
>     objects.
>     >
>     > * Since non-weakmap code doesn't need to test this bit, there is
>     zero
>     > runtime cost on non-weakmap code.
>     >
>     > * Whether an object has been used as a key or not (and therefore
>     > whether an extra shadow has been allocated or not), normal non-weak
>     > property lookup on the object is unaffected, and pays no
>     additional cost.
>
>     Maybe it's because I work on a garbage collector, but I always
>     think of
>     the primary cost of WeakMaps as being the GC. The above analysis
>     doesn't
>     take GC into account.
>
>
> I should have been more explicit, but GC costs are almost my entire
> point. These costs aside, my FastWeakMaps are more expensive in all
> ways than SlowWeakMaps, though only by a constant factor, since each
> FastWeakMap operation must also perform the corresponding SlowWeakMap
> operation.

Ah, sorry, I totally missed your point.

>
>
>     In the straightforward iterative implementation, you record all of the
>     live WeakMaps found while scanning through the heap. Then you go
>     through
>     them, checking each key to see if it is live. For each such key, you
>     recursively mark the value. This marking can discover new live
>     WeakMaps,
>     so you iterate to a fixed point.
>
>
> That is when you find yourself doing an ephemeron collection. The
> point of the transposed representation is to collect most ephemeron
> garbage using conventional collection. Consider

Ok, I get it now, and completely agree with your analysis, with the
caveat that supporting [[Shadow]] gives me the heebie-jeebies. It turns
a read into a write, for one thing. (The read of the key, I mean.) Could
the extra shadow table be kept separate from the key object? I know!
Let's use a WeakMap! :-)

> Here's the key important thing: In a generational collector, at this
> point we'd typically postpone ephemeron collection. To do so, we would
> complete the mark phase conventionally, by simply marking the values
> held by slowField. This marks slowValue, causing it to get promoted to
> the next older generation. THIS IS EXPENSIVE.

Yes, this is a big deal.

>
>     In the current web, this implementation seems to work fine. The worst
>     case is O(n^2) in the size of the heap, which is pretty much fatal if
>     you ever hit it. But that requires lots of paths through multiple
>     WeakMaps, and in practice, it seems WeakMaps aren't being used much.
>     I've never seen our WeakMap marking phase show up as a significant
>     cost.
>
>
> Chicken and egg. If WeakMaps are used for private state (and
> trademarks and...), they will be used a lot. But they will only be
> used for those things if it isn't fatally slow to do so.

Yes, I fully expect WeakMaps to start mattering soon-ish, though I'm
still procrastinating on doing anything about our current implementation.

>
>
>     For an algorithmically more robust solution, you could add a check
>     whenever marking an object. The check would test whether the object is
>     (or might be) used as a WeakMap key. This would slow down marking all
>     objects, so in practice you want to be clever about avoiding the test.
>
>
> Yeah, I'm very curious about whether this can be made cheap enough
> that implementations would be willing to do it. If so, then everything
> is much better, whether we transpose the representation or not.

We'll probably all end up at some messy point in the middle. Maybe a
fast initial pass without the checks. It'll be something that depends on
a bunch of assumptions for normal-case performance, but doesn't
completely break down in the pathological cases.
 
>
>
>     Anyway, my point is that WeakMaps have serious GC ramifications,
>     possibly extending to non-key objects, and any performance impact
>     analysis of using WeakMaps more extensively is incomplete without
>     considering GC costs.
>
>
> Exactly! I should have been clearer that these were the only costs I
> am concerned about here. Regarding all other costs, my example code
> only adds expense.

If I had read more closely, I probably would have noticed that...

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/es-discuss/attachments/20141022/6e8e86ce/attachment.html>

On 10/22/2014 02:26 PM, Mark Miller wrote:

> I should have been more explicit, but GC costs are almost my entire
> point. These costs aside, my FastWeakMaps are more expensive in all
> ways than SlowWeakMaps, though only by a constant factor, since each
> FastWeakMap operation must also perform the corresponding SlowWeakMap
> operation.

Ah, sorry, I totally missed your point.

> That is when you find yourself doing an ephemeron collection. The
> point of the transposed representation is to collect most ephemeron
> garbage using conventional collection. Consider

Ok, I get it now, and completely agree with your analysis, with the
caveat that supporting [[Shadow]] gives me the heebie-jeebies. It turns
a read into a write, for one thing. (The read of the key, I mean.) Could
the extra shadow table be kept separate from the key object? I know!
Let's use a WeakMap! :-)

> Here's the key important thing: In a generational collector, at this
> point we'd typically postpone ephemeron collection. To do so, we would
> complete the mark phase conventionally, by simply marking the values
> held by slowField. This marks slowValue, causing it to get promoted to
> the next older generation. THIS IS EXPENSIVE.

Yes, this is a big deal.

> Chicken and egg. If WeakMaps are used for private state (and
> trademarks and...), they will be used a lot. But they will only be
> used for those things if it isn't fatally slow to do so.

Yes, I fully expect WeakMaps to start mattering soon-ish, though I'm
still procrastinating on doing anything about our current implementation.

> Yeah, I'm very curious about whether this can be made cheap enough
> that implementations would be willing to do it. If so, then everything
> is much better, whether we transpose the representation or not.

We'll probably all end up at some messy point in the middle. Maybe a
fast initial pass without the checks. It'll be something that depends on
a bunch of assumptions for normal-case performance, but doesn't
completely break down in the pathological cases.

> Exactly! I should have been clearer that these were the only costs I
> am concerned about here. Regarding all other costs, my example code
> only adds expense.

If I had read more closely, I probably would have noticed that...