Closed Bug 743634 Opened 12 years ago Closed 12 years ago

Native array method 'reduce' much slower than simple JavaScript implementation

Categories

(Core :: JavaScript Engine, defect)

12 Branch
x86
macOS
defect
Not set
normal

Tracking

()

RESOLVED DUPLICATE of bug 784294

People

(Reporter: sergi, Unassigned)

References

(Depends on 1 open bug, )

Details

Attachments

(1 file)

Attached file reduce_test.html
User Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_7_3) AppleWebKit/535.19 (KHTML, like Gecko) Chrome/18.0.1025.151 Safari/535.19

Steps to reproduce:

When I wanted to substitute a hand-written JavaScript version of [Array.reduce] for the native one, I realized that the hand-written one was much faster than the native one. I attach a simple test that isolates the hand-written reduce and compares it to the native one. In my computer the test consistently gives results that confirm that the hand-written reduce is ~20x faster than the native reduce.


Actual results:

The native [Array.reduce] is much slower than a simple hand-written version of the reduce algorithm.


Expected results:

The native [Array.reduce] should be faster than any hand-written reduce function I could come up with.
Added a URL with a jsperf test-case
Comment on attachment 613260 [details]
reduce_test.html

Changed MIME Type
Attachment #613260 - Attachment mime type: text/plain → text/html
Assignee: nobody → general
Component: Untriaged → JavaScript Engine
Product: Firefox → Core
QA Contact: untriaged → general
I think this is basically bug 462300.
Indeed.

But also note that the testcase is doing an apples-to-oranges comparison, because the reduce implementation in the testcase isn't actually correct.  As a simple example, consider this:

  [1, ,2].reduce(function(a,b) { return a * b; }, 1)

this returns 2, while using the __reduce function in the testcase returns NaN in this situation.  This is a common problem when people try to compare performance of hand-written Array functions to the builtins: the builtins have to do more work than a handwritten function that takes shortcuts based on some sort of assumptions about the array.

(There are other bugs in the attached implementation, by the way, in addition to incorrect hadling of array holes; it handles the situation when func is not callable incorrectly, for example.)
Depends on: 462300
Or to be more clear, once bug 462300 is fixed the built-in reduce will be faster than now, but probably not as fast as the handwritten one in the testcase, because that takes shortcuts that the builtin is just not allowed to take per spec.
I agree that this function is definitely not implementing the spec and that makes a big difference. But while it is true that the attached test doesn't do validity checks and those could increase considerably the time that the function takes, I would hardly call these comparisons apples-to-oranges. Checking for edge cases like the ones you point out shouldn't justify such a huge difference in performance.

As a comparison (apples to oranges, one could say), the hand-written reduce is ~10x faster than the builtin reduce in Chrome-V8 (which I still see as a big difference), while in Firefox the hand-written is ~20x faster.

In fact, while investigating this issue, we made other tests with implementation "by the spec", as V8 implements it. The tests are in the same test-case as the URL I attached when I filed this issue (http://jsperf.com/native-vs-js-reduce/2) and one still can see that the difference of speed remains pretty big.

The implementation of the function in V8 does indeed do some validation checks (https://code.google.com/searchframe#W9JxUuHYyMg/trunk/src/array.js&q=array%20package:http://v8%5C.googlecode%5C.com&l=1267) which would justify the slowdown of the builtin function. The V8 team is looking into it, but they are assuming that by-spec implementation is preventing the function to be optimized.
No longer blocks: WebJSPerf
Depends on: 784288
Depends on: 784294
Status: UNCONFIRMED → RESOLVED
Closed: 12 years ago
Resolution: --- → DUPLICATE
No longer depends on: 784294
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Created:
Updated:
Size: