Bug 157315 – Speed up array iterators

• Status: RESOLVED
• Resolution: FIXED
• Component: JavaScriptCore

[Keith Miller]

Speedup array iterators

[Keith Miller]

Created attachment 278034 [details]
Patch

[Michael Saboff]

Comment on attachment 278034 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=278034&action=review

r=me

Please provide standard benchmark results.

> Source/JavaScriptCore/ChangeLog:31
> +        like the indexed for loop of without extra arithmetic is small enough to fit into the x86

Extra "of"?

[Keith Miller]

Created attachment 278039 [details]
Patch

[Keith Miller]

Created attachment 278041 [details]
Benchmark results

The !s on the regexp benchmarks are from an issue with the regexes that I was using to parse the builtins. The intrinsics were not properly being parsed. This has been fixed and those regressions are gone in future runs. 

I have also tweaked the for-of benchmark so that it runs in ~30ms locally.

[Keith Miller]

Created attachment 278042 [details]
Patch

[WebKit Commit Bot]

This patch modifies the JS builtins code generator. Please ensure that you have rebaselined any generator test results (i.e., by running `Tools/Scripts/run-builtins-generator-tests --reset-results`)

[Mark Lam]

All EWS bots are sad.  Please fix.

[Keith Miller]

Created attachment 278054 [details]
Patch

[Build Bot]

Comment on attachment 278054 [details]
Patch

Attachment 278054 [details] did not pass mac-debug-ews (mac):
Output: http://webkit-queues.webkit.org/results/1263755

Number of test failures exceeded the failure limit.

[Build Bot]

Created attachment 278058 [details]
Archive of layout-test-results from ews112 for mac-yosemite

The attached test failures were seen while running run-webkit-tests on the mac-debug-ews.
Bot: ews112  Port: mac-yosemite  Platform: Mac OS X 10.10.5

[Build Bot]

Comment on attachment 278054 [details]
Patch

Attachment 278054 [details] did not pass mac-ews (mac):
Output: http://webkit-queues.webkit.org/results/1263800

New failing tests:
js/regress/deltablue-for-of.html

[Build Bot]

Created attachment 278059 [details]
Archive of layout-test-results from ews102 for mac-yosemite

The attached test failures were seen while running run-webkit-tests on the mac-ews.
Bot: ews102  Port: mac-yosemite  Platform: Mac OS X 10.10.5

[Build Bot]

Comment on attachment 278054 [details]
Patch

Attachment 278054 [details] did not pass mac-wk2-ews (mac-wk2):
Output: http://webkit-queues.webkit.org/results/1263793

New failing tests:
js/regress/deltablue-for-of.html

[Build Bot]

Created attachment 278061 [details]
Archive of layout-test-results from ews105 for mac-yosemite-wk2

The attached test failures were seen while running run-webkit-tests on the mac-wk2-ews.
Bot: ews105  Port: mac-yosemite-wk2  Platform: Mac OS X 10.10.5

[Build Bot]

Comment on attachment 278054 [details]
Patch

Attachment 278054 [details] did not pass ios-sim-ews (ios-simulator-wk2):
Output: http://webkit-queues.webkit.org/results/1263796

New failing tests:
js/regress/deltablue-for-of.html

[Build Bot]

Created attachment 278062 [details]
Archive of layout-test-results from ews126 for ios-simulator-wk2

The attached test failures were seen while running run-webkit-tests on the ios-sim-ews.
Bot: ews126  Port: ios-simulator-wk2  Platform: Mac OS X 10.11.4

[Keith Miller]

Created attachment 278064 [details]
Patch

[Darin Adler]

If this is a speed up, then is it OK that the attached benchmark results say "might be 1.0042x slower"?

[Keith Miller]

(In reply to comment #18)
> If this is a speed up, then is it OK that the attached benchmark results say
> "might be 1.0042x slower"?

This is only a speedup for ES6 Array iterators. None of the changed code should run on existing benchmarks so there should not be any change on existing benchmarks. The key results are: 

   for-of-iterate-array-keys                          2.7773+-0.1050     !      4.2695+-0.9896        ! definitely 1.5373x slower
   for-of-iterate-array-values                        2.7475+-0.1398     !      4.0167+-0.4852        ! definitely 1.4620x slower
   arguments-strict-mode                             31.2240+-1.1577     ^     22.1049+-5.9080        ^ definitely 1.4125x faster
   call-spread-apply                                 28.2511+-0.5104     ^     23.8033+-0.1690        ^ definitely 1.1869x faster
   call-spread-call                                  30.9818+-1.2875     ^     26.8812+-0.9353        ^ definitely 1.1525x faster
   deltablue-for-of                                 441.2042+-14.3501    ^    250.3674+-10.8763       ^ definitely 1.7622x faster
   deltablue-varargs                                339.9242+-6.2830     ^    259.8512+-3.2080        ^ definitely 1.3081x faster
   destructuring-arguments                          143.2352+-0.8255     ^     73.2679+-0.3578        ^ definitely 1.9550x faster
   forloopof                                       1055.6493+-15.3923    ^    368.7977+-6.3186        ^ definitely 2.8624x faster
   varargs-construct                                 21.9800+-1.6726     ^     15.6356+-1.8147        ^ definitely 1.4058x faster

It does look like the patch is a slowdown in the baseline performance of ES6 Array iterators since. My guess is this cost comes from the extra virtual call in the ArrayIteratorPrototype.next function. I think that trade off is worth it for the huge DFG/FTL wins from inlining.

[Keith Miller]

Created attachment 278097 [details]
Patch for landing

[WebKit Commit Bot]

Comment on attachment 278097 [details]
Patch for landing

Rejecting attachment 278097 [details] from commit-queue.

Failed to run "['/Volumes/Data/EWS/WebKit/Tools/Scripts/webkit-patch', '--status-host=webkit-queues.webkit.org', '--bot-id=webkit-cq-01', 'apply-attachment', '--no-update', '--non-interactive', 278097, '--port=mac']" exit_code: 2 cwd: /Volumes/Data/EWS/WebKit

Last 500 characters of output:
ource/JavaScriptCore/runtime/MapPrototype.cpp
patching file Source/JavaScriptCore/runtime/SetPrototype.cpp
patching file LayoutTests/ChangeLog
Hunk #1 succeeded at 1 with fuzz 3.
patching file LayoutTests/js/regress/deltablue-for-of-expected.txt
patching file LayoutTests/js/regress/deltablue-for-of.html
patching file LayoutTests/js/regress/script-tests/deltablue-for-of.js

Failed to run "[u'/Volumes/Data/EWS/WebKit/Tools/Scripts/svn-apply', '--force']" exit_code: 1 cwd: /Volumes/Data/EWS/WebKit

Full output: http://webkit-queues.webkit.org/results/1266732

[Keith Miller]

Created attachment 278102 [details]
Patch for landing

[WebKit Commit Bot]

Comment on attachment 278102 [details]
Patch for landing

Clearing flags on attachment: 278102

Committed r200422: <http://trac.webkit.org/changeset/200422>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[Joseph Pecoraro]

Comment on attachment 278102 [details]
Patch for landing

View in context: https://bugs.webkit.org/attachment.cgi?id=278102&action=review

> Source/JavaScriptCore/Scripts/builtins/builtins_model.py:47
> +functionHeadRegExp = re.compile(r"(?:@[\w|=]+\s*\n)*(?:function)\s+\w+\s*\(.*?\)", re.MULTILINE | re.DOTALL)
> +functionIntrinsicRegExp = re.compile(r"^@intrinsic=(\w+)\s*\n", re.MULTILINE | re.DOTALL)
> +functionIsConstructorRegExp = re.compile(r"^@constructor", re.MULTILINE | re.DOTALL)
> +functionNameRegExp = re.compile(r"(?:function)\s+(\w+)\s*\(", re.MULTILINE | re.DOTALL)
> +functionParameterFinder = re.compile(r"^(?:function)\s+(?:\w+)\s*\(((?:\s*\w+)?\s*(?:\s*,\s*\w+)*)?\s*\)", re.MULTILINE | re.DOTALL)

Nit: It seems the `(?:function)` can just be `function` in all of these. I don't see a need for the uncaptured group (?:...) given there is no extra modifiers inside or outside of it. It used to be (?:function|constructor).

> Source/JavaScriptCore/builtins/ArrayIteratorPrototype.js:3
> + * Copyright (C) 2016a Apple Inc. All rights reserved.

Nit: Extra 'a'.

> Source/JavaScriptCore/builtins/ArrayIteratorPrototype.js:32
>      if (this == null)
> -        throw new @TypeError("%ArrayIteratorPrototype%.next requires that |this| not be null or undefined");
> +        throw @TypeError("%ArrayIteratorPrototype%.next requires that |this| not be null or undefined");

Nit: Shouldn't the 'new' still be here? It is in all the other functions.
Nit: Almost everywhere else we have separate error messages for `null` and `undefined`. We should be consistent.

> Source/JavaScriptCore/builtins/ArrayIteratorPrototype.js:36
> +        throw @TypeError("%ArrayIteratorPrototype%.next requires that |this| be an Array Iterator instance");

Nit: Same thing, 'new @TypeError' like all the rest?

> Source/JavaScriptCore/builtins/ArrayIteratorPrototype.js:45
> +    var value = @undefined;

Nit: Leaving off the assignment would be the same thing.

> Source/JavaScriptCore/builtins/ArrayIteratorPrototype.js:67
> +    var value = @undefined;

Nit: Leaving off the assignment would be the same thing.

> Source/JavaScriptCore/builtins/ArrayPrototype.js:53
> +        throw new @TypeError("Array.prototype.keys requires that |this| not be null");

This error message should say "not be undefined"

> Source/JavaScriptCore/builtins/ArrayPrototype.js:65
> +        throw new @TypeError("Array.prototype.entries requires that |this| not be null");

This error message should say "not be undefined"

> Source/JavaScriptCore/builtins/TypedArrayPrototype.js:26
>  // Note that the intrisic @typedArrayLength checks the that the argument passed is a typed array

Grammar: "checks the that the"

> Source/JavaScriptCore/runtime/JSGlobalObject.cpp:563
> +
> +

Nit: extra newline

> LayoutTests/js/regress/script-tests/deltablue-for-of.js:870
> +//for (var i = 0; i < 100; ++i)
> +//    deltaBlue();

This commented out code seems weird. Was it intentional, or just for testing?

[Keith Miller]

Comment on attachment 278102 [details]
Patch for landing

View in context: https://bugs.webkit.org/attachment.cgi?id=278102&action=review

I'll make the changes you requested in another patch since this one has already landed.

>> Source/JavaScriptCore/Scripts/builtins/builtins_model.py:47
>> +functionParameterFinder = re.compile(r"^(?:function)\s+(?:\w+)\s*\(((?:\s*\w+)?\s*(?:\s*,\s*\w+)*)?\s*\)", re.MULTILINE | re.DOTALL)
> 
> Nit: It seems the `(?:function)` can just be `function` in all of these. I don't see a need for the uncaptured group (?:...) given there is no extra modifiers inside or outside of it. It used to be (?:function|constructor).

sure, fixed.

>> Source/JavaScriptCore/builtins/ArrayIteratorPrototype.js:3
>> + * Copyright (C) 2016a Apple Inc. All rights reserved.
> 
> Nit: Extra 'a'.

removed.

>> Source/JavaScriptCore/builtins/ArrayIteratorPrototype.js:32
>> +        throw @TypeError("%ArrayIteratorPrototype%.next requires that |this| not be null or undefined");
> 
> Nit: Shouldn't the 'new' still be here? It is in all the other functions.
> Nit: Almost everywhere else we have separate error messages for `null` and `undefined`. We should be consistent.

Fixed the new. I'd need to double check the extra error cases don't cause us to stop inline the function. While I agree that in the long run we should have consistent error messages, not inlining the next function would not be worthwhile.

>> Source/JavaScriptCore/builtins/ArrayIteratorPrototype.js:36
>> +        throw @TypeError("%ArrayIteratorPrototype%.next requires that |this| be an Array Iterator instance");
> 
> Nit: Same thing, 'new @TypeError' like all the rest?

Fixed.

>> Source/JavaScriptCore/builtins/ArrayIteratorPrototype.js:45
>> +    var value = @undefined;
> 
> Nit: Leaving off the assignment would be the same thing.

Fixed.

>> Source/JavaScriptCore/builtins/ArrayIteratorPrototype.js:67
>> +    var value = @undefined;
> 
> Nit: Leaving off the assignment would be the same thing.

Fixed.

>> Source/JavaScriptCore/builtins/ArrayPrototype.js:53
>> +        throw new @TypeError("Array.prototype.keys requires that |this| not be null");
> 
> This error message should say "not be undefined"

Fixed.

>> Source/JavaScriptCore/builtins/ArrayPrototype.js:65
>> +        throw new @TypeError("Array.prototype.entries requires that |this| not be null");
> 
> This error message should say "not be undefined"

Fixed.

>> Source/JavaScriptCore/builtins/TypedArrayPrototype.js:26
>>  // Note that the intrisic @typedArrayLength checks the that the argument passed is a typed array
> 
> Grammar: "checks the that the"

Fixed.

>> Source/JavaScriptCore/runtime/JSGlobalObject.cpp:563
>> +
> 
> Nit: extra newline

Fixed.

>> LayoutTests/js/regress/script-tests/deltablue-for-of.js:870
>> +//    deltaBlue();
> 
> This commented out code seems weird. Was it intentional, or just for testing?

Whoops, that was for testing. fixed.

[Keith Miller]

rdar://problem/24705498

[Filip Pizlo]

This was a big speed-up on Air.js!

r200421: 2746ms
r200422: 2196ms

Nice! :-)