New issue
Advanced search Search tips
Starred by 1 user
Status: Started
Owner:
Cc:
Components:
HW: All
OS: All
Priority: 2
Type: FeatureRequest

Blocking:
issue 6936



Sign in to add a comment
Unnecessary %StringEqual fallbacks
Project Member Reported by bmeu...@chromium.org, Nov 1 Back to list
In the esprima test of the web-tooling-benchmark we spend like 2-3% of the time in the %StringEqual runtime function (according to --runtime-call-stats), and it seems that the fast majority of the calls compare strings of STRING_TYPE to ONE_BYTE_INTERNALIZED_STRING_TYPE, and the reason that we have STRING_TYPE is because substr and slice create substrings based on the instance type of the full string, which in this case contains some non-ascii characters.

Currently the CSA version of StringEqual bails out for two-byte strings. This should be fairly easy to support tho, also mixed comparisons.

A lot of the calls come from isKeyword, where id is of STRING_TYPE and the other side is a known constant string. We could probably do something in TurboFan here even, if the Interpreter would track SeqString feedback for strict equality.

========================================================================================
Scanner.prototype.isKeyword = function(id) {
    switch (id.length) {
        case 2:
            return (id === 'if') || (id === 'in') || (id === 'do');
        case 3:
            return (id === 'var') || (id === 'for') || (id === 'new') ||
                (id === 'try') || (id === 'let');
        case 4:
            return (id === 'this') || (id === 'else') || (id === 'case') ||
                (id === 'void') || (id === 'with') || (id === 'enum');
        case 5:
            return (id === 'while') || (id === 'break') || (id === 'catch') ||
                (id === 'throw') || (id === 'const') || (id === 'yield') ||
                (id === 'class') || (id === 'super');
        case 6:
            return (id === 'return') || (id === 'typeof') || (id === 'delete') ||
                (id === 'switch') || (id === 'export') || (id === 'import');
        case 7:
            return (id === 'default') || (id === 'finally') || (id === 'extends');
        case 8:
            return (id === 'function') || (id === 'continue') || (id === 'debugger');
        case 10:
            return (id === 'instanceof');
        default:
            return false;
    }
};
========================================================================================

 
esprima.json
12.1 MB View Download
wtb-esprima.js
2.8 MB View Download
Cc: yangguo@chromium.org
Here's a simple micro-benchmark that illustrates the problem with the two-byte strings in the StringEqual builtin.

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

const N = 1e7;
const TESTS = [];

(function() {
  const t = "debuggerLoremIpsum".slice(0, 8);
  const s = "debugger\u1234".slice(0, -1);
  const u = "123456\u1234\u8765Hello World!".slice(0, 8);
  TESTS.push(function stringEqualBothOneByteSeqString() {
    return t === "debugger";
  }, function stringEqualTwoByteAndOneByteSeqString() {
    return s === "debugger";
  }, function stringEqualOneByteAndTwoByteSeqString() {
    return "debugger" === s;
  }, function stringEqualBothTwoByteSeqString() {
    return "123456\u1234\u8765" === u;
  });
})();

function test(fn) {
  var result;
  for (var i = 0; i < N; i += 1) 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.');
}
====================================================================

On V8 ToT we see the following:

====================================================================
$ ./d8-master bench-string-equal.js
stringEqualBothOneByteSeqString: 162 ms.
stringEqualTwoByteAndOneByteSeqString: 446 ms.
stringEqualOneByteAndTwoByteSeqString: 438 ms.
stringEqualBothTwoByteSeqString: 472 ms.
====================================================================

So an unfortunate 3x slow-down once two-byte strings are involved.
Project Member Comment 2 by bugdroid1@chromium.org, Nov 2
The following revision refers to this bug:
  https://chromium.googlesource.com/v8/v8.git/+/f597eec152eb5c5b788c73eaa689553000f5fa36

commit f597eec152eb5c5b788c73eaa689553000f5fa36
Author: Benedikt Meurer <bmeurer@chromium.org>
Date: Thu Nov 02 06:39:34 2017

[builtins] Support two byte strings in StringEqual builtin.

This CL adds support for two byte string comparisons to the StringEqual
builtin, which so far was bailing out to the generic %StringEqual
runtime function whenever any two-byte string was involved. This made
comparisons that involved two-byte strings, either comparing them to
one-byte strings or comparing two two-byte strings, up to 3x slower than
if only one-byte strings were involved.

With this change, all direct string (SeqString or ExternalString)
equality checks are roughly on par now, and the weird performance cliff
is gone. On the micro-benchmark from the bug we go from

  stringEqualBothOneByteSeqString: 162 ms.
  stringEqualTwoByteAndOneByteSeqString: 446 ms.
  stringEqualOneByteAndTwoByteSeqString: 438 ms.
  stringEqualBothTwoByteSeqString: 472 ms.

to

  stringEqualBothOneByteSeqString: 151 ms.
  stringEqualTwoByteAndOneByteSeqString: 158 ms.
  stringEqualOneByteAndTwoByteSeqString: 166 ms.
  stringEqualBothTwoByteSeqString: 160 ms.

which is the desired result. On the esprima test of the
web-tooling-benchmark we seem to improve by 1-2%, which corresponds to
the savings of going to the runtime for many StringEqual comparisons.

Drive-by-cleanup: Introduce LoadAndUntagStringLength helper into the CSA
with proper typing to avoid the unnecessary shifts on 64-bit platforms
when keeping the length tagged initially in StringEqual.

Bug: v8:4913, v8:6365, v8:6371, v8:6936, v8:7022
Change-Id: I566f4b80e217513775ffbd35e0480154abf59b27
Reviewed-on: https://chromium-review.googlesource.com/749223
Reviewed-by: Yang Guo <yangguo@chromium.org>
Commit-Queue: Benedikt Meurer <bmeurer@chromium.org>
Cr-Commit-Position: refs/heads/master@{#49067}
[modify] https://crrev.com/f597eec152eb5c5b788c73eaa689553000f5fa36/src/builtins/builtins-array-gen.cc
[modify] https://crrev.com/f597eec152eb5c5b788c73eaa689553000f5fa36/src/builtins/builtins-string-gen.cc
[modify] https://crrev.com/f597eec152eb5c5b788c73eaa689553000f5fa36/src/builtins/builtins-string-gen.h
[modify] https://crrev.com/f597eec152eb5c5b788c73eaa689553000f5fa36/src/code-stub-assembler.cc
[modify] https://crrev.com/f597eec152eb5c5b788c73eaa689553000f5fa36/src/code-stub-assembler.h
[add] https://crrev.com/f597eec152eb5c5b788c73eaa689553000f5fa36/test/mjsunit/string-equal.js

The %StringEqual fallbacks are gone almost completely.
Sign in to add a comment