Proposal: Abstract References
sphink at gmail.com
Wed Oct 22 13:44:47 PDT 2014
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.
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.
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.
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.
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.
> A realistic implementation should seek to avoid allocating the extra
> shadow objects. However, even if not, we are much better off with the
> above scheme than we are with the current slow WeakMap.
Perhaps. But multiple WeakMaps introduce the potential for many more
cycles than a single WeakMap. So I think a final conclusion is premature.
More information about the es-discuss