New issue
Advanced search Search tips
Starred by 1 user
Status: Fixed
Owner:
Closed: Nov 3
Cc:
Components:
HW: All
NextAction: ----
OS: All
Priority: 1
Type: Bug



Sign in to add a comment
Gracefully handle out-of-bounds loads
Project Member Reported by bmeu...@chromium.org, Nov 2 Back to list
Currently V8 doesn't deal well with out-of-bounds element loads in the KeyedLoadIC, but rather immediately transitions the IC to MEGAMORPHIC state (except for Strings which were fixed recently with  http://crbug.com/v8/7014 ). This was sort of a good strategy in the past when we actively advised developers to be careful with out-of-bounds accesses, however we still see this pattern a lot in the wild. One especially interesting version of the pattern is a loop like this:

while ((element = array[i++]) != null) {
  ...
}

This loop pumps all entries from the array (assuming that null or undefined are not valid entries) and stops on the first out-of-bounds read. The KeyedLoadIC here will go MEGAMORPHIC right when the loop finished for the first time. This pattern is popular for example in jQuery, as described in various places:

- http://ripsawridge.github.io/articles/blink-mysterium/
- https://github.com/jquery/jquery/pull/3769
- https://github.com/jquery/sizzle/pull/407

Ideally we'd convince everyone to not do this. But of course this is not possible, and due to the amazing self-healing in JavaScript, it's really hard to spot and avoid these kinds of bugs. So instead we should mitigate the problem and deal with these bugs gracefully, avoiding unnecessary performance cliffs.

Here's a micro-benchmark that illustrates the problem:

===========< bench-oob.js >====================================
"use strict";

function testInBounds(...args) {
  return args[0];
}
function testOutOfBounds(...args) {
  return args[1];
}

const N = 1e7;
const F = [testInBounds, testOutOfBounds];

function test(f, n) {
  var result;
  for (var i = 0; i < n; ++i) {
    result = f(1);
  }
  return result;
}

// Warmup
test(x => x, 50);
for (var i = 0; i < 10; ++i) {
  for (var f of F) test(f, 50);
}

// Measure
for (var f of F) {
  var start = Date.now();
  var o = test(f, N);
  var end = Date.now();
  print(f.name + ": " + (end - start) + " ms.");
}
===============================================================

On V8 ToT we see:

===============================================================
$ ./d8-master bench-oob.js
testInBounds: 106 ms.
testOutOfBounds: 288 ms.
===============================================================

So almost 3x worse for this very simple example.

We also hit this problem in the six-speed rest benchmarks:

- https://github.com/mozilla/arewefastyet/blob/master/benchmarks/six-speed/tests/rest.es5
- https://github.com/mozilla/arewefastyet/blob/master/benchmarks/six-speed/tests/rest.es6

Although these are arguably very bad tests.
 
Cc: mathias@chromium.org
Project Member Comment 2 by bugdroid1@chromium.org, Nov 3
The following revision refers to this bug:
  https://chromium.googlesource.com/v8/v8.git/+/b7168573ed011113746873fd92b71e8bcc9dddb1

commit b7168573ed011113746873fd92b71e8bcc9dddb1
Author: Benedikt Meurer <bmeurer@chromium.org>
Date: Fri Nov 03 07:35:14 2017

[turbofan] Generalized OOB support for KeyedLoadIC.

This extends the support in TurboFan and the ICs for OOB loads to also
apply to typed arrays and receivers whose prototype chain is protected
by the "no elements" protector (aka the Array protector). TurboFan will
generate code to materialize undefined instead when it sees a load that
has the OOB bit set and add an appropriate code dependency on the global
protector. For typed arrays it doesn't even need to check the global
protector since elements are never looked up in the prototype chain
for typed arrays.

In the simple micro-benchmark from the bug we go from

  testInBounds: 103 ms.
  testOutOfBounds: 289 ms.

to

  testInBounds: 103 ms.
  testOutOfBounds: 102 ms.

which fixes the 3x slowdown and thus addresses the performance cliff. In
general it's still beneficial to make sure that you don't access out of
bounds, especially once we introduce a bounds check elimination pass to
TurboFan.

This also seems to improve the jQuery benchmark on the Speedometer test
suite by like 1-2% on average. And the SixSpeed rest benchmarks go from

  rest-es5: 25 ms.
  rest-es6: 23 ms.

to

  rest-es5: 6 ms.
  rest-es6: 4 ms.

so a solid 5.7x improvement there.

Bug: v8:6936,  v8:7014 ,  v8:7027 
Change-Id: Ie99699c69cc40057512e72fd40ae28107216c423
Reviewed-on: https://chromium-review.googlesource.com/750089
Commit-Queue: Benedikt Meurer <bmeurer@chromium.org>
Reviewed-by: Benedikt Meurer <bmeurer@chromium.org>
Reviewed-by: Tobias Tebbi <tebbi@chromium.org>
Cr-Commit-Position: refs/heads/master@{#49095}
[modify] https://crrev.com/b7168573ed011113746873fd92b71e8bcc9dddb1/src/code-stub-assembler.cc
[modify] https://crrev.com/b7168573ed011113746873fd92b71e8bcc9dddb1/src/compiler/js-native-context-specialization.cc
[modify] https://crrev.com/b7168573ed011113746873fd92b71e8bcc9dddb1/src/compiler/js-native-context-specialization.h
[modify] https://crrev.com/b7168573ed011113746873fd92b71e8bcc9dddb1/src/feedback-vector.cc
[modify] https://crrev.com/b7168573ed011113746873fd92b71e8bcc9dddb1/src/ic/accessor-assembler.cc
[modify] https://crrev.com/b7168573ed011113746873fd92b71e8bcc9dddb1/src/ic/handler-configuration-inl.h
[modify] https://crrev.com/b7168573ed011113746873fd92b71e8bcc9dddb1/src/ic/handler-configuration.cc
[modify] https://crrev.com/b7168573ed011113746873fd92b71e8bcc9dddb1/src/ic/handler-configuration.h
[modify] https://crrev.com/b7168573ed011113746873fd92b71e8bcc9dddb1/src/ic/ic.cc
[modify] https://crrev.com/b7168573ed011113746873fd92b71e8bcc9dddb1/src/ic/ic.h

Cc: jkummerow@chromium.org
It seems that we now have two bits in the LoadHandler that essentially express the same: "convert hole to undefined" and "allow out of bounds" both mean that the prototype chain needs to be checked and then undefined is returned. I guess we could unify those?

WDYT verwaest@?
Status: Fixed
Project Member Comment 5 by bugdroid1@chromium.org, Nov 4
The following revision refers to this bug:
  https://chromium.googlesource.com/v8/v8.git/+/fd150c79884f4ae522dd5c80350e90f4d8a7a2ba

commit fd150c79884f4ae522dd5c80350e90f4d8a7a2ba
Author: Benedikt Meurer <bmeurer@chromium.org>
Date: Sat Nov 04 12:06:31 2017

[turbofan] Generate the correct bounds when the array protector isn't valid.

The condition for bounds check generation was not in sync with the
condition that was used for the actual access, which lead to invalid
memory accesses when the array protector was invalid.

Tbr: tebbi@chromium.org
Bug:  chromium:781506 ,  chromium:781494 ,  chromium:781457 ,  chromium:781285 ,  chromium:781381 ,  chromium:781380 , v8:6936,  v8:7014 ,  v8:7027 
Change-Id: Ia5b2ad02940292572ed9b37abd3f9ffaa6d7a26b
Reviewed-on: https://chromium-review.googlesource.com/753590
Reviewed-by: Benedikt Meurer <bmeurer@chromium.org>
Commit-Queue: Benedikt Meurer <bmeurer@chromium.org>
Cr-Commit-Position: refs/heads/master@{#49124}
[modify] https://crrev.com/fd150c79884f4ae522dd5c80350e90f4d8a7a2ba/src/compiler/js-native-context-specialization.cc
[add] https://crrev.com/fd150c79884f4ae522dd5c80350e90f4d8a7a2ba/test/mjsunit/regress/regress-crbug-781506-1.js
[add] https://crrev.com/fd150c79884f4ae522dd5c80350e90f4d8a7a2ba/test/mjsunit/regress/regress-crbug-781506-2.js
[add] https://crrev.com/fd150c79884f4ae522dd5c80350e90f4d8a7a2ba/test/mjsunit/regress/regress-crbug-781506-3.js

Project Member Comment 6 by bugdroid1@chromium.org, Nov 20
The following revision refers to this bug:
  https://chromium.googlesource.com/v8/v8.git/+/a9a1671345fa28c23856cc15e73ed24af400dd2a

commit a9a1671345fa28c23856cc15e73ed24af400dd2a
Author: Benedikt Meurer <bmeurer@google.com>
Date: Mon Nov 20 09:43:35 2017

[cleanup] Rename "array protector" to "no elements protector".

The "array protector" now guards the Object.prototype, the
Array.prototype and the String.prototype, so the name was a
bit misleading nowadays. So the new name "no elements protector"
was chosen.

Bug: v8:6936,  v8:7014 ,  v8:7027 
Change-Id: I9a9d7caa2caf0ac9e78cc6658de2f0506970dfa2
Reviewed-on: https://chromium-review.googlesource.com/778162
Reviewed-by: Michael Starzinger <mstarzinger@chromium.org>
Reviewed-by: Camillo Bruni <cbruni@chromium.org>
Commit-Queue: Benedikt Meurer <bmeurer@chromium.org>
Cr-Commit-Position: refs/heads/master@{#49471}
[modify] https://crrev.com/a9a1671345fa28c23856cc15e73ed24af400dd2a/src/builtins/builtins-array-gen.cc
[modify] https://crrev.com/a9a1671345fa28c23856cc15e73ed24af400dd2a/src/builtins/builtins-call-gen.cc
[modify] https://crrev.com/a9a1671345fa28c23856cc15e73ed24af400dd2a/src/code-stub-assembler.cc
[modify] https://crrev.com/a9a1671345fa28c23856cc15e73ed24af400dd2a/src/code-stub-assembler.h
[modify] https://crrev.com/a9a1671345fa28c23856cc15e73ed24af400dd2a/src/compiler/js-builtin-reducer.cc
[modify] https://crrev.com/a9a1671345fa28c23856cc15e73ed24af400dd2a/src/compiler/js-call-reducer.cc
[modify] https://crrev.com/a9a1671345fa28c23856cc15e73ed24af400dd2a/src/compiler/js-native-context-specialization.cc
[modify] https://crrev.com/a9a1671345fa28c23856cc15e73ed24af400dd2a/src/elements.cc
[modify] https://crrev.com/a9a1671345fa28c23856cc15e73ed24af400dd2a/src/heap/heap.h
[modify] https://crrev.com/a9a1671345fa28c23856cc15e73ed24af400dd2a/src/heap/setup-heap-internal.cc
[modify] https://crrev.com/a9a1671345fa28c23856cc15e73ed24af400dd2a/src/ic/accessor-assembler.cc
[modify] https://crrev.com/a9a1671345fa28c23856cc15e73ed24af400dd2a/src/ic/ic.cc
[modify] https://crrev.com/a9a1671345fa28c23856cc15e73ed24af400dd2a/src/isolate.cc
[modify] https://crrev.com/a9a1671345fa28c23856cc15e73ed24af400dd2a/src/isolate.h
[modify] https://crrev.com/a9a1671345fa28c23856cc15e73ed24af400dd2a/src/objects.cc
[modify] https://crrev.com/a9a1671345fa28c23856cc15e73ed24af400dd2a/test/cctest/test-api.cc
[modify] https://crrev.com/a9a1671345fa28c23856cc15e73ed24af400dd2a/tools/v8heapconst.py

Sign in to add a comment