609835 - Array functions are slower than Chrome (Peacekeeper arrayCombined test)

Status: NEW

(Core :: JavaScript Engine, defect)

Description

[Trev]

User-Agent:       Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.2.12) Gecko/20101026 Firefox/3.6.12
Build Identifier: Mozilla/5.0 (Windows NT 5.1; rv:2.0b8pre) Gecko/20101104 Firefox/4.0b8pre

In the arrayCombined test of Peacekeeper, it benchmarks the following functions:

concat
join
pop
push
reverse
sort
slice
splice

Because of a bug in the test, only the first two actually run on arrays with data (though it also does empty arrays as well).  The others mostly run on an empty array (first 2 iterations have data, the other 9998 iterations are empty).

I've created a test file that runs all the iterations against an empty array and the first two against an array with 10 elements.  My times are below:

FF4:
Concat: 572ms
Join: 526ms
EmptyConcat: 250ms
EmptyJoin: 52ms
EmptyPop: 71ms
EmptyPush: 112ms
EmptyReverse: 23ms
EmptySort: 21ms
EmptySlice: 90ms
EmptySplice: 255ms

Chrome7:
Concat: 99ms
Join: 584ms
EmptyConcat: 74ms
EmptyJoin: 26ms
EmptyPop: 28ms
EmptyPush: 28ms
EmptyReverse: 26ms
EmptySort: 97ms
EmptySlice: 63ms
EmptySplice: 68ms

The Join, EmptyReverse, and EmptySort are all faster in FF but the others are faster in Chrome.

I wasn't sure if this should be filed as individual bugs.

Reproducible: Always

Steps to Reproduce:
1.  Open test12c.html in FF and Chrome
2.  Notice the speed difference for each of the functions
3.
Actual Results:  
FF is slower than Chrome

Expected Results:  
FF should be as fast or faster than Chrome

Comment 1

[Trev]

Attachment: test12b.html - Original Peacekeeper Test

This is the test that Peacekeeper actually runs in case.  My times if I run this file is:

FF: 332ms
Chrome: 155ms

Comment 2

[Trev]

Attachment: test12c.html

This is the test case that highlights each of the individual functions.

Comment 3

[Boris Zbarsky [:bzbarsky]]

Note bug 592786.

Though given comment 0 I think we should be pushing back on the bogus benchmark instead of trying to "optimize" it....

Comment 4

[Boris Zbarsky [:bzbarsky]]

Oh, nevermind.  This is just about ArrayCombined, so bug 592786 is not relevant.

Concat is sort of expected at the moment, but I dunno what the deal with EmptySplice is....

Comment 5

[Luke Wagner [:luke]]

Wow, looking at array_concat, there is definitely room for improvement.  I'm seeing aobj->getProperty on a dense array and pairs of calls to GetArrayElement/SetArrayElement in a hot loop.

Comment 6

[Boris Zbarsky [:bzbarsky]]

Uh, yes.  Filed bug 609896.

Comment 7

[Trev]

Attachment: test12c.html

I found a bug in the test case.  The EmptyPush should be EmptyShift and should be timing shift instead of pop.  My times for this function are:

FF: EmptyShift: 102ms
Chrome: EmptyShift: 44ms

Comment 8

[Trev]

Attachment: test12c.html

I found another issue with my test case.  The EmptyPop and EmptyShift functions are also doing a push(undefined).  So, I've created a new "UndefinedPush" function to time that and removed the push from EmptyPop and EmptyShift.  FF is still slower in all three changed functions:

FF
EmptyPop: 21ms
EmptyShift: 48ms
UndefinedPush: 95ms

Chrome:
EmptyPop: 16ms
EmptyShift: 28ms
UndefinedPush: 27ms

Comment 9

[Trev]

Attachment: test12d.html

This is a new test that shows the worst offending functions.  It also runs them the same number of times that are run in the original test.  They are:

Concat - 10,000 times with array of 10 and 100 length.  1 time with 500 length, 200 length, and 50 length.
EmptyPop - 499,875 times
EmptyShift - 499,875 times
UndefinedPush - 1,000,000 times (the array it pushes into only reaches 100 length before the next iteration)

I've tested the UndefinedPush (array.push(undefined)) with pushing a number to see if it is any different and it wasn't.  So, UndefinedPush is really just a benchmark for array.push().

My times are:

FF
Concat: 78ms
EmptyPop: 22ms
EmptyShift: 51ms
UndefinedPush: 68ms

Chrome:
Concat: 6ms
EmptyPop: 17ms
EmptyShift: 31ms
UndefinedPush: 15ms

Comment 10

[Boris Zbarsky [:bzbarsky]]

UndefinedPush is all array-allocation bound.  35% of the time is vm_fault...

If I exclude kernel time (so look at the remaining 65% of the time only), then:

  20% is tracer-generated code
  20% RefillFinalizableFreeList self time
   9% PR_Unlock (called from Refill...)
  32% js_NewEmptyArray self time
  14% under array_push

Comment 11

[Boris Zbarsky [:bzbarsky]]

Worth retesting this once bug 692847 is fixed....

Comment 12

[Boris Zbarsky [:bzbarsky]]

And in particular, it makes emptypop and emptyshift really fast, as expected.  Much faster than Chrome.

Comment 13

[Trev]

The latest nightly is a lot faster with the latest test.  These are the numbers:

Nightly:
Concat: 27ms
EmptyPop: 4ms
EmptyShift: 7ms
UndefinedPush: 30ms

Chrome:
Concat: 6ms
EmptyPop: 12ms
EmptyShift: 29ms
UndefinedPush: 14ms

But with the changes to Peacekeeper, the empty and undefined ones are no longer pertinent.  I'll update the test.

Comment 14

[Trev]

Attachment: arrayCombined tests

This test file splits up the arrayCombined into 7 pieces: concat, join, pop & shift, reverse, sort, slice, and splice.  It runs each one 5000 times.  It should be dealing with the same array sizes that are in the Peacekeeper test.

Comment 15

[Trev]

My numbers on Windows XP are (first number is Aurora, second is Nightly, third is Chrome):

Concat:     557ms     79ms     7ms
Join:       348ms    328ms   105ms
PopShift:   501ms    187ms    28ms
Reverse:     36ms     71ms    25ms
Sort:      1736ms   1736ms   778ms
Slice:       39ms     38ms     3ms
Splice:      59ms     36ms    15ms

Comment 16

[Jan de Mooij [:jandem]]

Attachment: Shell testcase

This is still at least 2x slower than V8.

d8:  963 ms
SM: 2170 ms

What's interesting, if |run| only has the array literals I get:

d8:   2 ms
SM: 106 ms

Maybe v8 is using their COW arrays here. We should investigate.

The array methods also seem to be slower.

Comment 17

[Till Schneidereit [:till]]

We got a lot better on the shell test case, but are still slower than d8:
SM: 1103ms
d8: 867ms
JSC: 1109ms

The arrayCombined tests, however, are really bad.

Chrome Canary:
Concat: 5ms
Join: 62ms
PopShift: 23ms
Reverse: 8ms
Sort: 341ms
Slice: 3ms
Splice: 4ms

current Nightly:
Concat: 75ms
Join: 91ms
PopShift: 70ms
Reverse: 25ms
Sort: 157ms
Slice: 21ms
Splice: 29ms

So, sorting is great, everything else pretty bad.

Comment 18

[Mayank Bansal]

Nightly:
Concat: 14ms
Join: 35ms
PopShift: 13ms
Reverse: 6ms
Sort: 107ms
Slice: 10ms
Splice: 8ms

Chrome:
Concat: 1ms
Join: 40ms
PopShift: 17ms
Reverse: 3ms
Sort: 382ms
Slice: 1ms
Splice: 2ms