Andreas Rossberg (2014-10-27T14:00:25.000Z)
On 24 October 2014 22:13, Mark S. Miller <erights at google.com> wrote:
> On Fri, Oct 24, 2014 at 4:19 AM, Andreas Rossberg <rossberg at google.com>
> wrote:
>> On 22 October 2014 16:45, Mark S. Miller <erights at google.com> wrote:
>> > On Tue, Oct 21, 2014 at 11:59 PM, Andreas Rossberg <rossberg at google.com>
>> > wrote:
>> >> On 21 October 2014 22:31, Mark S. Miller <erights at google.com> wrote:
>> >> >> in saying that [weak maps] are not designed to work efficiently in
>> >> >> that
>> >> >> manner.
>> >> >
>> >> > Actually, they are. The problem is that initial implementations date
>> >> > from
>> >> > before we appreciated the need for the transposed representation. The
>> >> > best
>> >> > thing TC39 can do for the future of WeakMaps is to proceed assuming
>> >> > the
>> >> > transposed representation.
>> >>
>> >> While I sympathise, let me clarify that this still remains a
>> >> conjecture. AFAIK, nobody has proved it empirically in a JS
>> >> implementation yet, we don't know in detail how complex such an
>> >> implementation would be, and what side effects it might have on
>> >> general performance (e.g., via added polymorphism). It's most likely
>> >> not as easy or as clear a win as you may think it is.
>> >
>> > The following code is an existence proof of sorts that, given only the
>> > WeakMap mechanisms you've already built + one bit of magic whose
>> > feasibility
>> > I hope we don't need to debate. I use ES5 here to make clear that no
>> > other
>> > magic or unengineered features are assumed.
>> >
>> >
>> > var WeakMap;
>> >
>> > (function() {
>> >    'use strict';
>> >
>> >    var SlowWeakMap = WeakMap;
>> >
>> >    function FastWeakMap() {
>> >      var token = Object.freeze(Object.create(null));
>> >      return Object.freeze({
>> >        get: function(key) {
>> >          var shadow = key.[[Shadow]];
>> >          return shadow ? shadow.get(token) : void 0;
>> >        },
>> >        set: function(key, value) {
>> >          var shadow = key.[[Transposer]]
>> >          if (!shadow) {
>> >            shadow = new SlowWeakMap();
>> >            key.[[Transposer]] = shadow;
>> >          }
>> >          shadow.set(token, value);
>> >        },
>> >        clear: function() {
>> >          token = Object.freeze(Object.create({}));
>> >        }
>> >      });
>> >    }
>> >
>> >    // Don't do this until it is a complete shim
>> >    // WeakMap = FastWeakMap;
>> >
>> >  }());
>> >
>> > The magic is that each object, whether frozen or not, would need in
>> > effect
>> > one extra internal mutable [[Shadow]] property.
>> >
>> > Clearly, this expository implementation is suboptimal in many ways. But
>> > it
>> > demonstrates the following:
>> >
>> > * It provides the full complexity measure gains that a realistic
>> > implementation would have.
>> >
>> > * For each of these objects, an extra SlowWeakMap instance is allocated
>> > as
>> > its shadow.
>> >
>> > * For each access, an extra indirection through this SlowWeakMap is
>> > therefore needed.
>> >
>> > * 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.
>> >
>> > 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.
>> >
>> > Of course, we should proceed towards realistic implementations asap and
>> > get
>> > actual empirical data. But the above demonstration establishes that the
>> > issue in this thread should be considered settled.
>>
>> I appreciate your analysis, but I respectfully disagree with your
>> conclusion.
>>
>> - The extra slot and indirection for the [[Shadow]] property is an
>> extra cost (V8 already has a very similar mechanism to implement
>> "hidden properties" as provided by its API (and in fact, hash codes),
>> but it is known to be (too) slow).
>>
>> - Optimising away this slot is difficult -- for starters, because it
>> will have various secondary effects (e.g., every add/remove of an
>> object to/from a weak map will potentially result in a layout change
>> for that object, increasing spurious polymorphism, and potentially
>> invalidating/deoptimising existing code).
>>
>> - Worse, when you flatten weak properties into objects, then even GC
>> could cause object layouts to change, which is a whole new dimension
>> of complexity.
>
> Already answered:
>
> On Wed, Oct 22, 2014 at 2:26 PM, Mark Miller <erights at gmail.com> wrote:
>> [...] When the WeakMap is known to necessarily live longer than its keys,
>> as for class-private state, then those shadow properties can even be
>> exempted from the [ephemeron] key-mark-check.

How would that generally be "known" up-front, though? Even if you were
allowed to dynamically analyse the whole heap and code, you couldn't
easily predict relative life times.

> More to the point, when the instance (transientKey) retains the WeakMap (via
> instance retains class retains methods retains field designators), then GC
> will never cause this layout change.

With everything being mutable in JavaScript, none of these
retains-relations are necessarily invariant, as far as I can see. And
even if they were, this would already be a very expensive check to
make for every private field you add. It is a pretty limited scenario,
too. It would not remove the general problem of the GC having to be
able to rewrite object layouts, nor other use cases being unexpectedly
slow. (VMs are already terrible at handling _explicit_ property
deletion efficiently.)

>> - On the other hand, if you do _not_ do this flattening, performance
>> is unlikely to ever be competitive with true private properties (we
>> internally introduced private symbols in V8, exactly because the extra
>> indirection for hidden properties was too costly).
>
> Exactly. For WeakMaps representing private state, they should engage exactly
> the kind of runtime machinery once associated with private symbols,

Private symbols do not require weakness, however. That makes them both
much cheaper and much easier to implement.

In summary, there are two basic use cases for 'relations':

- permanent (key outlives object)
- temporary (object outlives key)

These two use cases come with different performance implications.
Transient properties seem suboptimal in either case:

- They are less efficient than private symbols for the permanent case,
even if you manage to flatten (which is complicated).

- They are less efficient than normal weak maps for the temporary
case, even if you do _not_ flatten (far worse if you flatten).

Unless we can come up with some real clever heuristics for -- cheaply
and reliably! -- distinguishing the two use cases at creation time of
each relation, I expect that transient properties are going to be
significantly inferior to the alternatives in terms of performance.
And that is still ignoring the implementation complexity (and
potential space overhead that I did not mention in my bullet list).

> but without breaking membrane transparency.

I'm still not sure I understand how this affects membranes
specifically. A membrane would never pass a proxied object to a
non-proxied function from the same side. So functions accessing (or
testing for) private state on an object are a non-issue in that
scenario, because this access never crosses the membrane, does it?
After all, membranes work just fine with builtins or host objects
(otherwise they would be useless).

/Andreas
d at domenic.me (2014-11-18T23:00:17.901Z)
On 24 October 2014 22:13, Mark S. Miller <erights at google.com> wrote:

> Already answered:
>
> On Wed, Oct 22, 2014 at 2:26 PM, Mark Miller <erights at gmail.com> wrote:
>> [...] When the WeakMap is known to necessarily live longer than its keys,
>> as for class-private state, then those shadow properties can even be
>> exempted from the [ephemeron] key-mark-check.

How would that generally be "known" up-front, though? Even if you were
allowed to dynamically analyse the whole heap and code, you couldn't
easily predict relative life times.

> More to the point, when the instance (transientKey) retains the WeakMap (via
> instance retains class retains methods retains field designators), then GC
> will never cause this layout change.

With everything being mutable in JavaScript, none of these
retains-relations are necessarily invariant, as far as I can see. And
even if they were, this would already be a very expensive check to
make for every private field you add. It is a pretty limited scenario,
too. It would not remove the general problem of the GC having to be
able to rewrite object layouts, nor other use cases being unexpectedly
slow. (VMs are already terrible at handling _explicit_ property
deletion efficiently.)

> Exactly. For WeakMaps representing private state, they should engage exactly
> the kind of runtime machinery once associated with private symbols,

Private symbols do not require weakness, however. That makes them both
much cheaper and much easier to implement.

In summary, there are two basic use cases for 'relations':

- permanent (key outlives object)
- temporary (object outlives key)

These two use cases come with different performance implications.
Transient properties seem suboptimal in either case:

- They are less efficient than private symbols for the permanent case,
even if you manage to flatten (which is complicated).

- They are less efficient than normal weak maps for the temporary
case, even if you do _not_ flatten (far worse if you flatten).

Unless we can come up with some real clever heuristics for -- cheaply
and reliably! -- distinguishing the two use cases at creation time of
each relation, I expect that transient properties are going to be
significantly inferior to the alternatives in terms of performance.
And that is still ignoring the implementation complexity (and
potential space overhead that I did not mention in my bullet list).

> but without breaking membrane transparency.

I'm still not sure I understand how this affects membranes
specifically. A membrane would never pass a proxied object to a
non-proxied function from the same side. So functions accessing (or
testing for) private state on an object are a non-issue in that
scenario, because this access never crosses the membrane, does it?
After all, membranes work just fine with builtins or host objects
(otherwise they would be useless).