New issue
Advanced search Search tips
Starred by 2 users
Status: Fixed
Owner:
Closed: Oct 2
Cc:
Components:
HW: All
OS: All
Priority: 1
Type: FeatureRequest

Blocking:
issue 6278
issue 6344



Sign in to add a comment
Polymorphic symbol lookup not well supported
Project Member Reported by bmeu...@chromium.org, May 5 2017 Back to list
Consider the following snippet of code, especially the clone method:

-------------------------------------------------------------
class A {
  static get [Symbol.species]() { return this; }
  clone() { return new this.constructor[Symbol.species](); }
}

class B extends A {
  static get [Symbol.species]() { return this; }
}

function foo(o) { return o.clone(); }
foo(new A());
foo(new B());
-------------------------------------------------------------

The lookup of constructor on this is polymorphic, so TurboFan will generate a diamond that dispatches on the map of this and yields a constant in each case. The problem is that the KEYED_LOAD_IC for this.constructor[Symbol.species] is already MEGAMORPHIC because the IC system cannot deal with polymorphic PROPERTY keyed accesses (yet).

But the graph actually contains all the necessary information in TurboFan already, so we could infer it from the graph, and then get the inlining of the getters.
 
Cc: vegorov@chromium.org
Components: Runtime
Labels: -Priority-2 Priority-1
Status: Started
Summary: Polymorphic symbol lookup not well supported (was: Polymorphic symbol lookup on known constants is not well supported in TurboFan)
Another example from Slava (https://twitter.com/mraleph/status/913817957880549376), where it wouldn't help to get the constant-folding in TurboFan fixed:

===============================================================
const $get = Symbol('dartx.get');
function foo(arr) { return arr[$get](1); }

Array.prototype[$get] = function(index) { return this[index]; }

foo([1, 2]);
foo([1, 2]);
foo([1, []]);
foo([1, 2]);
%OptimizeFunctionOnNextCall(foo);
foo([1, []]);
===============================================================

Here we really need to fix the KEYED_LOAD_IC.
Comment 2 Deleted
Ok, here's the proper micro-benchmark that I actually wanted to do :-)

=================< bench-polymorphic-symbol.js >====================
if (typeof console === 'undefined') console = {log:print};

const sym = Symbol();

class Base {
  constructor() {
    this[sym] = this;
    this.str = this;
  }
};

class A extends Base { };
class B extends Base { };
const o = new A;

const N = 1e8;
const OBJS = [new A, new B];

function testStringMonomorphic() {
  let result = 0;
  for (let i = 0; i < 2 * N; ++i) {
    if (o.str !== undefined) result++;
  }
  return result;
}

function testSymbolMonomorphic() {
  let result = 0;
  for (let i = 0; i < 2 * N; ++i) {
    if (o[sym] !== undefined) result++;
  }
  return result;
}

function testStringPolymorphic() {
  let result = 0;
  for (const o of OBJS) {
    for (let i = 0; i < N; ++i) {
      if (o.str !== undefined) result++;
    }
  }
  return result;
}

function testSymbolPolymorphic() {
  let result = 0;
  for (const o of OBJS) {
    for (let i = 0; i < N; ++i) {
      if (o[sym] !== undefined) result++;
    }
  }
  return result;
}

var TESTS = [
    testStringMonomorphic,
    testSymbolMonomorphic,
    testStringPolymorphic,
    testSymbolPolymorphic
];

function test(fn) {
  var result;
  for (var o of OBJS) result = fn();
  return result;
}

for (var j = 0; j < TESTS.length; ++j) {
  test(TESTS[j]);
}

for (var j = 0; j < TESTS.length; ++j) {
  var startTime = Date.now();
  test(TESTS[j]);
  console.log(TESTS[j].name + ':', (Date.now() - startTime), 'ms.');
}
====================================================================

Running on V8 6.1 and ToT we observe:

====================================================================
$ ./d8-6.1.534.15 bench-polymorphic-symbol.js
testStringMonomorphic: 428 ms.
testSymbolMonomorphic: 429 ms.
testStringPolymorphic: 428 ms.
testSymbolPolymorphic: 5786 ms.
$ ./d8-master bench-polymorphic-symbol.js
testStringMonomorphic: 429 ms.
testSymbolMonomorphic: 431 ms.
testStringPolymorphic: 429 ms.
testSymbolPolymorphic: 5621 ms.
====================================================================

So we get a high performance penalty for using symbols whenever things get polymorphic, up to 13x slow-down actually.
Project Member Comment 4 by bugdroid1@chromium.org, Oct 2
The following revision refers to this bug:
  https://chromium.googlesource.com/v8/v8.git/+/08db4d7652967c1ed12450a73ff53f5d6bbf1fdf

commit 08db4d7652967c1ed12450a73ff53f5d6bbf1fdf
Author: Benedikt Meurer <bmeurer@chromium.org>
Date: Mon Oct 02 12:35:05 2017

[ic] Properly handle polymorphic symbol accesses.

Until now keyed accesses to properties with string or symbol keys were
only optimized properly while the IC was monomorphic and would go
megamorphic as soon as there's another receiver map, even if the name
was still the same (i.e. the same symbol or internalized string). This
was a weird performance-cliff, that'll hurt modern code especially
because for symbols you can only access them via keyed loads and stores.

This CL fixes the state machine inside the ICs to properly transition to
POLYMORPHIC state (and stay there) as long as the new name matches the
previously recorded name. The FeedbackVector and TurboFan were already
able to deal with this and didn't need any updates.

On the micro-benchmark from the tracking bug we go from

  testStringMonomorphic: 429 ms.
  testSymbolMonomorphic: 431 ms.
  testStringPolymorphic: 429 ms.
  testSymbolPolymorphic: 5621 ms.

to

  testStringMonomorphic: 429 ms.
  testSymbolMonomorphic: 429 ms.
  testStringPolymorphic: 429 ms.
  testSymbolPolymorphic: 430 ms.

effectively eliminating the overhead for symbols completely, and
yielding a 13.5x performance boost.

This also seems to yield a 1% improvement on the ARES6 ML benchmark,
because it eliminates the KEYED_LOAD_ICs for the Symbol.species lookups.

Bug:  v8:6367 , v8:6278, v8:6344
Change-Id: I879fe56387b4c56203c1ad8ef8cafb6cc4c32897
Reviewed-on: https://chromium-review.googlesource.com/695108
Reviewed-by: Michael Stanton <mvstanton@chromium.org>
Commit-Queue: Benedikt Meurer <bmeurer@chromium.org>
Cr-Commit-Position: refs/heads/master@{#48261}
[modify] https://crrev.com/08db4d7652967c1ed12450a73ff53f5d6bbf1fdf/src/ic/ic.cc
[add] https://crrev.com/08db4d7652967c1ed12450a73ff53f5d6bbf1fdf/test/mjsunit/compiler/polymorphic-symbols.js

Status: Fixed
The original example is not yet fully fixed, because we don't get the inlining of the constructors right, but the polymorphic access is fixed.
Project Member Comment 6 by bugdroid1@chromium.org, Oct 3
The following revision refers to this bug:
  https://chromium.googlesource.com/v8/v8.git/+/38b489186b713900b54c4777a4a30a063cec9aea

commit 38b489186b713900b54c4777a4a30a063cec9aea
Author: Benedikt Meurer <bmeurer@chromium.org>
Date: Tue Oct 03 06:30:41 2017

[ic] Transition to MEGAMORPHIC when (map, handler) stays the same.

THe change in https://chromium-review.googlesource.com/695108 flushed
out an issue with the IC::UpdatePolymorphicIC logic, where we'd try to
stay MONOMORPHIC or POLYMORPHIC as long as the internalized name doesn't
change. But the calling code already does the internalization for keyed
accesses with Strings, so we need to double check that the same
combination of (map, handler) is not already in the list, and properly
go to MEGAMORPHIC state if there's such a pair already.

This seriously tanked the six-speed-object-literals-ext-es5.js benchmark
on AWFY.

Bug:  v8:6367 , v8:6278, v8:6344
Change-Id: I90ea88d1fe61c165990c0a10d4a8687ffe351986
Reviewed-on: https://chromium-review.googlesource.com/695307
Reviewed-by: Jakob Kummerow <jkummerow@chromium.org>
Commit-Queue: Benedikt Meurer <bmeurer@chromium.org>
Cr-Commit-Position: refs/heads/master@{#48268}
[modify] https://crrev.com/38b489186b713900b54c4777a4a30a063cec9aea/src/ic/ic.cc

Project Member Comment 7 by bugdroid1@chromium.org, Oct 6
The following revision refers to this bug:
  https://chromium.googlesource.com/v8/v8.git/+/99203eeaa366966c87ef30de6a38708df4cf5583

commit 99203eeaa366966c87ef30de6a38708df4cf5583
Author: Benedikt Meurer <bmeurer@chromium.org>
Date: Fri Oct 06 07:37:21 2017

[ic] Allow duplicate (map,handler) pairs in RECOMPUTE_HANDLER state.

This repairs the performance regression on Octane/EarleyBoyer and
JetStream/EarleyBoyer benchmarks.

Bug: chromium:772268,  v8:6367 , v8:6278, v8:6344
Change-Id: Ibc144a35b37c5822f88712550d8db09386241341
Reviewed-on: https://chromium-review.googlesource.com/704574
Reviewed-by: Jaroslav Sevcik <jarin@chromium.org>
Commit-Queue: Benedikt Meurer <bmeurer@chromium.org>
Cr-Commit-Position: refs/heads/master@{#48326}
[modify] https://crrev.com/99203eeaa366966c87ef30de6a38708df4cf5583/src/ic/ic.cc

Sign in to add a comment