396191 - Array literals are significantly slower than new Array()

Status: RESOLVED FIXED

(Core :: JavaScript Engine, enhancement)

Description

[Aiko]

Attachment: benchmark (for browser or shell)

Array literals are supposed to be just syntactic sugar for the equivalent new Array() call (except for sharp variables) but in SpiderMonkey they're much slower. Comparing the bytecodes for these two expressions makes the reason quite obvious: each additional element requires just one opcode in the case of new Array() but three opcodes for the literal.

Bytecode for [2,3,4] :

00000:  callname "Array"
00003:  newinit
00004:  zero
00005:  int8 2
00007:  initelem
00008:  one
00009:  int8 3
00011:  initelem
00012:  int8 2
00014:  int8 4
00016:  initelem
00017:  endinit

Bytecode for new Array(2,3,4) :

00000:  callname "Array"
00003:  int8 2
00005:  int8 3
00007:  int8 4
00009:  new 3

Comment 1

[Brendan Eich [:brendan]]

We should use new Array unless there are sharp variables.

/be

Comment 2

[Blake Kaplan (:mrbkap) (inactive)]

We also have to fall back when there are elisions in the array literal (e.g. [0,,1]).

Comment 3

[Blake Kaplan (:mrbkap) (inactive)]

...and the degenerate 1 (integer) element case.

Comment 4

[Jason Orendorff [:jorendorff]]

Interesting--optimizing this as proposed is actually against the letter of ECMA
262-3, section 11.1.4.  The difference is observable if you replace the global
|Array| with a different constructor.

It could be optimized some other way though.  |[2,3,4]| could generate

  int8 2
  int8 3
  int8 4
  newarray 3

where the (hypothetical) newarray opcode checks to see if |Array| is still the
default, takes a fast path if so, and does the ECMA-compliant dance if not.

(I would be even happier if we did what Opera does with array literals, and
ignore the global |Array| property.)

Comment 5

[Brendan Eich [:brendan]]

(In reply to comment #4)
> Interesting--optimizing this as proposed is actually against the letter of ECMA
> 262-3, section 11.1.4.  The difference is observable if you replace the global
> |Array| with a different constructor.

Or shadow Array in an inner scope(!).

ECMA sucks here (don't blame me! :-P). The right thing is happening for ES4 (no shadowing, and no rebinding of typenames). We should prefigure in fixing this bug. Who will take it?

/be

Comment 6

[Jason Orendorff [:jorendorff]]

Do you mean: we should change SpiderMonkey so that |[2,3,4]| always makes an array regardless of what |Array| is bound to in the local scope?

It would be a pleasure to implement that.

Comment 7

[Brendan Eich [:brendan]]

(In reply to comment #6)
> Do you mean: we should change SpiderMonkey so that |[2,3,4]| always makes an
> array regardless of what |Array| is bound to in the local scope?

Yes. See bug 376957.

/be

Comment 8

[Mike Shaver (:shaver emeritus)]

I don't think we need to avoid the constructor version where there's an elision, we can just push JSVAL_VOID (as we do in the literal case now, see bug 260106).

I was about to start hacking this (at the cost of some code duplication, to minimize invasiveness on the path shared with generators), but then I remembered that I'd have to touch decompilation, so I went back to filing my eyeballs instead.

Comment 9

[Mike Shaver (:shaver emeritus)]

Attachment: use Array() form if we don't have sharp vars and argc != 1

First-pass hack, gives expected gains.  Decompilation hasn't been re-educated yet, which I guess is only really a problem for literals with elisions, other than the aesthetics.  Pushing an explicit |undefined| would probably be a quick path to victory there.

I tweaked Seno.Aiko's righteous benchmark to gc() before every timed function, multiply the reps by 10, and use Date.now() instead of Date-object construction, and get these results:

Before:
Size    Rep.    Literal new Arr Array()
====    =====   ======= ======= =======
2       90000   129     88      91
3       70000   151     100     102
5       40000   126     78      80
9       20000   131     76      78
17      20000   231     139     136
33      20000   452     259     265
65      8000    336     184     181
129     8000    640     362     355
257     8000    1222    685     673
513     3000    949     505     496
1025    1000    623     329     332

After:
Size    Rep.    Literal new Arr Array()
====    =====   ======= ======= =======
2       90000   92      87      92
3       70000   101     99      101
5       40000   79      78      80
9       20000   79      78      78
17      20000   137     136     138
33      20000   259     262     258
65      8000    186     184     183
129     8000    353     360     355
257     8000    680     675     666
513     3000    496     501     496
1025    1000    325     327     327

(Without the extra gc() calls, I was seeing strangeness like |new Array()| being twice as fast as |Array()| for the 33 x 2000 case.)

Comment 10

[Mike Shaver (:shaver emeritus)]

Waldo reminds me that I don't want JSOP_CALLNAME here, to avoid shadowed |Array|, and I suspect that my sharp-detection might not be enough.  Can we turn off sharp variables yet?

(Not wanting JSOP_CALLNAME means I have to touch the decompiler, too.  Humbug.)

Comment 11

[Brendan Eich [:brendan]]

Comment on attachment 294354 [details] [diff] [review]
use Array() form if we don't have sharp vars and argc != 1

>+	  if (pn->pn_head && pn->pn_count != 1 /* I hate you, Array() */

Stop the hate!

The above |if| is indented two spaces too far...

>+	  }

... and so is its closing brace.

/be

Comment 12

[Aiko]

Fixed by the patches in bugs 260106 and 466905.

Comment 13

[Biju]

Still there is difference in speed between 
new Array() vs. Array()

When array size is small "Array()" is slower than "new Array()"
but for array size above 513  "Array()" is faster than "new Array()"


Size  	Repet 	Literal (ms)  	new Array() (ms)  	Array() (ms)
2	9000	11	12	31
3	7000	9	9	26
5	4000	5	6	14
9	2000	3	3	8
17	2000	3	3	8
33	2000	4	4	10
65	800	3	3	6
129	800	5	6	9
257	800	13	14	15
513	300	24	25	51
1025	100	145	163	11

PS: for higher array size firefox crashes (bug 474529)