784294 - self-host some Array extras

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Till Schneidereit [:till]]

All or most of the Array extras specified in http://es5.github.com/x15.4.html#x15.4.4 (15.4.4.13 to 15.4.4.22) can be implemented more efficiently in JS.

Do that.

Comment 1

[Norbert Lindenberg]

Ecma now has an official HTML version of the ES5.1 spec:
http://ecma-international.org/ecma-262/5.1/#sec-15.4.4

Comment 2

[Till Schneidereit [:till]]

Attachment: Part 1: Convert some extras

This patch converts the following array extras to self-hosted JS:
- lastIndexOf
- indexOf
- forEach
- some
- every
- reduce
- reduceRight

The result passes our test suites as well as all tests in test262 we passed before.

The code uses the exact names the spec uses for the implemented algorithms to make following them easier.

I haven't factored out any of the common functionality from the various functions as that caused quite a heavy performance degradation in my testing. I'm not sure why this is (and haven't investigated much), but my guess would be that my simple testing kernels are inlined with the current code and weren't inlined with code that invoked other self-hosted code.

If that guess is correct, we might want to look into tweaking our inlining decisions. But then again, maybe it'll just go away with IonMonkey.

Comment 3

[Jeff Walden [:Waldo]]

Comment on attachment 656003 [details] [diff] [review]
Part 1: Convert some extras

Review of attachment 656003 [details] [diff] [review]:
-----------------------------------------------------------------

Why is TO_UINT32 named that way, and not named ToUint32?

::: js/src/builtin/array.js
@@ +6,5 @@
> +function ArrayIndexOf(searchElement/*, fromIndex*/) {
> +    /* Step 1. */
> +    var O = %ToObject(this);
> +
> +    /* Step 2-3. */

"Steps" (and every other place you refer to more than one step at once).

@@ +56,5 @@
> +    if (len === 0)
> +        return -1;
> +
> +    /* Step 5. */
> +    var n = arguments.length > 1 ? %ToInteger(arguments[1]) : len;

Spec language would have |len - 1| here, please.  (It'd come to the same thing in the end, but best to Simon-says here.)

@@ +68,5 @@
> +    else
> +        k = n;
> +
> +    /* Step 8. */
> +    for (; k > -1; k--) {

>= 0 to read like the spec, please.

@@ +92,5 @@
> +    if (!IsCallable(callbackfn))
> +        %ThrowError(JSMSG_NOT_FUNCTION, callbackfn);
> +
> +    /* Step 5. */
> +    var T = arguments.length > 1 ? arguments[1] : void 0;

Can you use |undefined| here, or does that not work due to some quirk of the self-hosting scaffolding?  (I'd consider it a low-priority-ish bug if it can't work.)

@@ +182,5 @@
> +            %_CallFunction(T, O[k], k, O, callbackfn);
> +        }
> +    }
> +
> +    /* Step 8. (implicit) */

It would be slightly nicer to just have |return void 0;| here, rather than the "implicit" bit.

@@ +216,5 @@
> +        accumulator = arguments[1];
> +    } else {
> +        /* Step 5. */
> +        if (len === 0)
> +            %ThrowError(JSMSG_EMPTY_ARRAY_REDUCE, 0, 'Array.prototype.reduce');

Technically these three lines aren't required for correctness, but it's probably better to be consistent with the spec.

@@ +247,5 @@
> +
> +function ArrayStaticReduce(list, callbackfn) {
> +    if (arguments.length < 2)
> +        %ThrowError(JSMSG_MISSING_FUN_ARG, 0, 'Array.reduce');
> +    %_CallFunction(list, callbackfn, ArrayReduce);

This isn't passing along a specified initialValue.  I think you're going to have to do something like this:

    if (arguments.length < 2)
        %ThrowError(JSMSG_MISSING_FUN_ARG, 0, 'Array.reduce');
    if (arguments.length > 2)
        %_CallFunction(list, callbackfn, arguments[2], ArrayReduce);
    else
        %_CallFunction(list, callbackfn, ArrayReduce);

Bleh.  Something rest-parameter-ish would be ideal here, except for the length-affecting possibility and the uncertain perf worries raised in some previous self-hosting bug thread I remember reading in the last few days.

@@ +274,5 @@
> +        accumulator = arguments[1];
> +    } else {
> +        /* Step 5. */
> +        if (len === 0)
> +            %ThrowError(JSMSG_EMPTY_ARRAY_REDUCE, 0, 'Array.prototype.reduceRight');

Again not strictly necessary, but probably better to have than not.

@@ +276,5 @@
> +        /* Step 5. */
> +        if (len === 0)
> +            %ThrowError(JSMSG_EMPTY_ARRAY_REDUCE, 0, 'Array.prototype.reduceRight');
> +        var kPresent = false;
> +        for (; k > -1; k--) {

>= 0

@@ +290,5 @@
> +    }
> +
> +    /* Step 9. */
> +    /* Step a (implicit), and d. */
> +    for (; k > -1; k--) {

>= 0

Comment 4

[Jeff Walden [:Waldo]]

Frankly, I'm fine with not commoning when the spec algorithms themselves don't common.  Commoning just makes it harder to reason about correctness, in my book, even for relatively small bits of code as here.

Comment 5

[Terrence Cole [:terrence]]

FWIW, when I uncommoned these in jsarray.cpp it was a huge readability win.

Comment 6

[Norbert Lindenberg]

Comment on attachment 656003 [details] [diff] [review]
Part 1: Convert some extras

Review of attachment 656003 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/builtin/array.js
@@ +1,5 @@
> +/* This Source Code Form is subject to the terms of the Mozilla Public
> + * License, v. 2.0. If a copy of the MPL was not distributed with this
> + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
> +
> + /* ES5 15.4.4.14. */

The current version is 5.1. (Comment applies multiple times.) There have been a few changes between 5 and 5.1 that affect these functions, and Jeff's comments on lines 60 and 186 hit on such changes.

@@ +10,5 @@
> +    /* Step 2-3. */
> +    var len = TO_UINT32(O.length);
> +
> +    /* Step 4. */
> +    if (len === 0)

JavaScript style guides seem to agree that if/while/for/try statements should always use braces:
http://javascript.crockford.com/code.html#compound%20statements
http://docs.jquery.com/JQuery_Core_Style_Guidelines#Blocks
(Comment applies multiple times.)

@@ +30,5 @@
> +        /* Step b. */
> +        if (k < 0)
> +            k = 0;
> +    } else {
> +        k = n;

This is step 7.a. Why not keep the logic the same as in the spec?

if (n >= 0) {
   // 7a
} else {
   // 8a-b
}

@@ +34,5 @@
> +        k = n;
> +    }
> +
> +    /* Step 9. */
> +    for (; k < len; k++) {

A while loop would match the spec more closely. (Comment applies multiple times.)

@@ +60,5 @@
> +    var n = arguments.length > 1 ? %ToInteger(arguments[1]) : len;
> +
> +    /* Step 6-7. */
> +    var k;
> +    if (n > len - 1)

This looks like a correct transformation of the spec, but not the simplest one possible.

@@ +86,5 @@
> +    /* Step 2-3. */
> +    var len = TO_UINT32(O.length);
> +
> +    /* Step 4. */
> +    if (arguments.length == 0)

Is this necessary? If the caller doesn't provide callbackfn, the runtime is supposed to fill in undefined, which IsCallable should be able to handle. (Comment applies multiple times.)

Also, why == and not ===? (Comment applies multiple times.)

@@ +92,5 @@
> +    if (!IsCallable(callbackfn))
> +        %ThrowError(JSMSG_NOT_FUNCTION, callbackfn);
> +
> +    /* Step 5. */
> +    var T = arguments.length > 1 ? arguments[1] : void 0;

undefined is seriously broken in the current self-hosted environment:
https://bugzilla.mozilla.org/show_bug.cgi?id=785294

@@ +109,5 @@
> +    /* Step 8. */
> +    return true;
> +}
> +
> +function ArrayStaticEvery(list, callbackfn/*, thisArg*/) {

Why do we need this? It's not in the spec.

@@ +148,5 @@
> +    /* Step 8. */
> +    return false;
> +}
> +
> +function ArrayStaticSome(list, callbackfn/*, thisArg*/) {

Why do we need this? It's not in the spec.

@@ +185,5 @@
> +
> +    /* Step 8. (implicit) */
> +}
> +
> +function ArrayStaticForEach(list, callbackfn/*, thisArg*/) {

Why do we need this? It's not in the spec.

@@ +244,5 @@
> +    /* Step 10. */
> +    return accumulator;
> +}
> +
> +function ArrayStaticReduce(list, callbackfn) {

Why do we need this? It's not in the spec.

@@ +302,5 @@
> +    /* Step 10. */
> +    return accumulator;
> +}
> +
> +function ArrayStaticReduceRight(list, callbackfn) {

Why do we need this? It's not in the spec.

@@ +306,5 @@
> +function ArrayStaticReduceRight(list, callbackfn) {
> +    if (arguments.length < 2)
> +        %ThrowError(JSMSG_MISSING_FUN_ARG, 0, 'Array.reduceRight');
> +    %_CallFunction(list, callbackfn, ArrayReduceRight);
> +}

I'm glad to see that this file doesn't end with an unterminated comment anymore - that comment, combined with the lack of syntax error reporting, has cost me quite some time!

Comment 7

[Jeff Walden [:Waldo]]

Comment on attachment 656003 [details] [diff] [review]
Part 1: Convert some extras

Review of attachment 656003 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/builtin/array.js
@@ +1,5 @@
> +/* This Source Code Form is subject to the terms of the Mozilla Public
> + * License, v. 2.0. If a copy of the MPL was not distributed with this
> + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
> +
> + /* ES5 15.4.4.14. */

Hmm, that's actually kind of strange.  I was under the impression none of these algorithms had changed since mid-2009, in the ES5 days.  I'll have to look and see sometime.  I was working from the ECMA webpage version, which is actually a little odd as usually I consult the ES5 PDF.

@@ +10,5 @@
> +    /* Step 2-3. */
> +    var len = TO_UINT32(O.length);
> +
> +    /* Step 4. */
> +    if (len === 0)

Those style guides aren't gospel.  Here, I think we want to be roughly consistent with existing SpiderMonkey style, which doesn't brace single-line statements.

@@ +30,5 @@
> +        /* Step b. */
> +        if (k < 0)
> +            k = 0;
> +    } else {
> +        k = n;

Fair point on ordering here, I should have mentioned it too.

@@ +34,5 @@
> +        k = n;
> +    }
> +
> +    /* Step 9. */
> +    for (; k < len; k++) {

I'm kind of ambivalent about for-loops versus while-loops here.  The latter may be closer, but the former's more readable, and trivially understandable as the latter.  Meh is my opinion here, I think.

@@ +86,5 @@
> +    /* Step 2-3. */
> +    var len = TO_UINT32(O.length);
> +
> +    /* Step 4. */
> +    if (arguments.length == 0)

At least in v8, where I suspect some of this was gleaned from, I believe they optimize self-hosted functions to not generate |undefined| for out-of-bounds accesses, or to not check for them.  Probably we don't do that (...now?), doesn't hurt to leave it should we do likewise sometime.

Fair enough on == versus ===.  In this case the length will always be a number, and so it doesn't matter, but yeah, we should use === whenever possible, and I should have noticed and requested it.  To the extent it's slower, we should improve our optimizations to handle those cases.

@@ +92,5 @@
> +    if (!IsCallable(callbackfn))
> +        %ThrowError(JSMSG_NOT_FUNCTION, callbackfn);
> +
> +    /* Step 5. */
> +    var T = arguments.length > 1 ? arguments[1] : void 0;

Yeah, probably the global-variable not working thing.

@@ +109,5 @@
> +    /* Step 8. */
> +    return true;
> +}
> +
> +function ArrayStaticEvery(list, callbackfn/*, thisArg*/) {

We implemented Array.* versions of more or less all the prototype methods as a convenience thing, years ago.  This is what JSFUN_GENERIC_NATIVE triggers (or used to trigger) -- creation of both X.prototype.y and X.y methods.  At the very least, this isn't the bug to change that.

Comment 8

[Norbert Lindenberg]

> Hmm, that's actually kind of strange.  I was under the impression none of
> these algorithms had changed since mid-2009, in the ES5 days.  I'll have to
> look and see sometime.  I was working from the ECMA webpage version, which
> is actually a little odd as usually I consult the ES5 PDF.

The changes are just clarifications, not behavioral changes. Quoting Annex F:

15.4.4.15: Clarified that the default value for fromIndex is the length minus 1 of the array.

15.4.4.18: In step 9 of the algorithm, undefined is now the specified return value.

15.4.4.22: In step 9.c.ii the first argument to the [[Call]] internal method has been changed to undefined for consistency with the definition of Array.prototype.reduce.

> We implemented Array.* versions of more or less all the prototype methods as
> a convenience thing, years ago.  This is what JSFUN_GENERIC_NATIVE triggers
> (or used to trigger) -- creation of both X.prototype.y and X.y methods.  At
> the very least, this isn't the bug to change that.

Thanks for the clarification.

Comment 9

[Till Schneidereit [:till]]

Attachment: Part 1: Convert some extras, v2

Thanks for the detailed reviews!

New patch currently try-servering here:
https://tbpl.mozilla.org/?tree=Try&rev=1171b29f076f

> Why is TO_UINT32 named that way, and not named ToUint32?

Because it uses a macro provided by builtins/macros.py, which I didn't change after importing it from V8 at all. I should really go through that file and see how much is even usable for us. Maybe we should just get rid of 90% of it.

> > + /* ES5 15.4.4.14. */
> 
> The current version is 5.1. (Comment applies multiple times.) There have
> been a few changes between 5 and 5.1 that affect these functions, and Jeff's
> comments on lines 60 and 186 hit on such changes.

That's really pretty strange: I used the spec at http://es5.github.com/ which claims to be up to date. Will work with the PDF from now on.

> JavaScript style guides seem to agree that if/while/for/try statements
> should always use braces:
> http://javascript.crockford.com/code.html#compound%20statements
> http://docs.jquery.com/JQuery_Core_Style_Guidelines#Blocks
> (Comment applies multiple times.)

I agree with Waldo: keeping the style similar to what SpiderMonkey uses elsewhere seems more important than what other style guides are saying. This will mostly be read by SpiderMonkey hackers, after all.

> @@ +60,5 @@
> > +    var n = arguments.length > 1 ? %ToInteger(arguments[1]) : len;
> > +
> > +    /* Step 6-7. */
> > +    var k;
> > +    if (n > len - 1)
> 
> This looks like a correct transformation of the spec, but not the simplest
> one possible.

Actually using Math.min would certainly be easier, but it might cause a JIT to not optimize as well as without that call. I think being safe about that is the right thing here.

> I'm glad to see that this file doesn't end with an unterminated comment
> anymore - that comment, combined with the lack of syntax error reporting,
> has cost me quite some time!

Yeah, sorry about that. I can see how you'd seriously trip over that.

Comment 10

[Mozilla RelEng Bot]

Try run for 1171b29f076f is complete.
Detailed breakdown of the results available here:
    https://tbpl.mozilla.org/?tree=Try&rev=1171b29f076f
Results (out of 212 total builds):
    exception: 3
    success: 127
    warnings: 77
    failure: 5
Builds (or logs if builds failed) available at:
http://ftp.mozilla.org/pub/mozilla.org/firefox/try-builds/[e-mail]-1171b29f076f

Comment 11

[Till Schneidereit [:till]]

Let's try this again after fixing a stupid omission:
http://tbpl.mozilla.org/?tree=Try&rev=d6f025deb333

Comment 12

[Mozilla RelEng Bot]

Try run for d6f025deb333 is complete.
Detailed breakdown of the results available here:
    https://tbpl.mozilla.org/?tree=Try&rev=d6f025deb333
Results (out of 27 total builds):
    exception: 2
    success: 2
    warnings: 15
    failure: 8
Builds (or logs if builds failed) available at:
http://ftp.mozilla.org/pub/mozilla.org/firefox/try-builds/[e-mail]-d6f025deb333

Comment 13

[Till Schneidereit [:till]]

Urgh, I should probably have gone to sleep instead of pushing half-finished patches to try.

Once more, after sleep and coffee:
https://tbpl.mozilla.org/?tree=Try&rev=d91dc85909a4

Comment 14

[Mozilla RelEng Bot]

Try run for d91dc85909a4 is complete.
Detailed breakdown of the results available here:
    https://tbpl.mozilla.org/?tree=Try&rev=d91dc85909a4
Results (out of 191 total builds):
    exception: 4
    success: 149
    warnings: 38
Builds (or logs if builds failed) available at:
http://ftp.mozilla.org/pub/mozilla.org/firefox/try-builds/[e-mail]-d91dc85909a4

Comment 15

[Till Schneidereit [:till]]

Attachment: Part 1: Convert some extras, v3

The last try run finally looked green, except for the issue in bug 787927.

Once that patch lands, this should be ready, too.

Comment 16

[Till Schneidereit [:till]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/cddd665d83f0

So I haven't done any proper benchmarking in the browser, but in the shell, this set of methods got a 10- to 35-fold speedup when used with simple, inlineable callbacks.

Comment 17

[Till Schneidereit [:till]]

Whoops, wrong link.

https://hg.mozilla.org/integration/mozilla-inbound/rev/a3a7de3e2938

Comment 18

[Ed Morley [:emorley]]

Backed out for failures in browser_dbg_bfcache.js:
https://hg.mozilla.org/integration/mozilla-inbound/rev/9ed5024f9101

Comment 19

[Justin Lebar (not reading bugmail)]

Also, it looks like this may have resulted in a 25% max-heap regression, which is pretty serious!

>Regression :( Trace Malloc MaxHeap increase 23.6% on CentOS (x86_64) release 5 (Final) Mozilla-Inbound
>------------------------------------------------------------------------------------------------------
>    Previous: avg 44332573.333 stddev 86741.467 of 30 runs up to revision e63b3b5dbb2a
>    New     : avg 54804480.000 stddev 1298.846 of 5 runs since revision 67a582c0daf7
>    Change  : +10471906.667 (23.6% / z=120.725)
>    Graph   : http://mzl.la/Q7q5GY
>
>Changeset range: http://hg.mozilla.org/integration/mozilla-inbound/pushloghtml?fromchange=e63b3b5dbb2a&tochange=67a582c0daf7
>
>Changesets:
>  * http://hg.mozilla.org/integration/mozilla-inbound/rev/cddd665d83f0
>    : Till Schneidereit <[e-mail]> - Bug 787927 - Prevent self-hosted JS script from being registered with the debugger
>    : http://bugzilla.mozilla.org/show_bug.cgi?id=787927
>
>  * http://hg.mozilla.org/integration/mozilla-inbound/rev/a3a7de3e2938
>    : Till Schneidereit <[e-mail]> - Bug 784294 - Convert some array extras to self-hosted js implementations. r=Waldo
>
>The following methods are converted:
>- lastIndexOf
>- indexOf
>- forEach
>- some
>- every
>- reduce
>- reduceRight
>    : http://bugzilla.mozilla.org/show_bug.cgi?id=784294
>
>  * http://hg.mozilla.org/integration/mozilla-inbound/rev/67a582c0daf7
>    : Trevor Saunders <[e-mail]> - bug 787308 - clean up table cell interface and move methods to TableCell Interface r=surkov
>    : http://bugzilla.mozilla.org/show_bug.cgi?id=787308
>
>Bugs:
>  * http://bugzilla.mozilla.org/show_bug.cgi?id=787308 - convert table cell accessible implementations to new interface
>  * http://bugzilla.mozilla.org/show_bug.cgi?id=784294 - self-host Array extras
>  * http://bugzilla.mozilla.org/show_bug.cgi?id=787927 - Prevent self-hosted JS script from being registered with the debugger

Comment 21

[Mozilla RelEng Bot]

Try run for 755ad7378a5d is complete.
Detailed breakdown of the results available here:
    https://tbpl.mozilla.org/?tree=Try&rev=755ad7378a5d
Results (out of 309 total builds):
    exception: 4
    success: 278
    warnings: 22
    failure: 5
Builds (or logs if builds failed) available at:
http://ftp.mozilla.org/pub/mozilla.org/firefox/try-builds/[e-mail]-755ad7378a5d

Comment 22

[Mozilla RelEng Bot]

Try run for 755ad7378a5d is complete.
Detailed breakdown of the results available here:
    https://tbpl.mozilla.org/?tree=Try&rev=755ad7378a5d
Results (out of 313 total builds):
    exception: 4
    success: 281
    warnings: 23
    failure: 5
Builds (or logs if builds failed) available at:
http://ftp.mozilla.org/pub/mozilla.org/firefox/try-builds/[e-mail]-755ad7378a5d

Comment 23

[Mozilla RelEng Bot]

Try run for 755ad7378a5d is complete.
Detailed breakdown of the results available here:
    https://tbpl.mozilla.org/?tree=Try&rev=755ad7378a5d
Results (out of 314 total builds):
    exception: 4
    success: 282
    warnings: 23
    failure: 5
Builds (or logs if builds failed) available at:
http://ftp.mozilla.org/pub/mozilla.org/firefox/try-builds/[e-mail]-755ad7378a5d

Comment 24

[Till Schneidereit [:till]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/3da143341145

Let's hope it sticks this time ...

Comment 25

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/3da143341145

Comment 26

[Luke Wagner [:luke]]

I'm sorry to say that I think we should back this out while the dependencies are resolved.  (Bug 791850 can stay as, IIUC, w/o this patch, its code isn't exercised.)

Comment 27

[Phil Ringnalda (:philor)]

Ah, too bad I didn't see that first, I already backed out both of them in https://hg.mozilla.org/mozilla-central/rev/dd68409d7810 for the dependency where it completely broke not just the Jetpack tests but the Jetpack SDK, turning any addon built with it into a constant crasher.

Comment 29

[Till Schneidereit [:till]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/5593cd83590e

Comment 30

[Ed Morley [:emorley]]

https://hg.mozilla.org/mozilla-central/rev/5593cd83590e

Comment 31

[Marco Castelluccio [:marco]]

Is there anything else needed to resolve this bug?

Comment 32

[Till Schneidereit [:till]]

Yes, someone needs to port the remaining Array extras to self-hosted code.

Note that some of those are blocked on bug 772334, though.

Comment 33

[Jesse Ruderman]

Given the regression risk, I think it would be best to mark this FIXED, file a new bug (or bugs) for the remaining bugs, and retcon the summary and dependency lists.

Comment 34

[Till Schneidereit [:till]]

Yeah, I guess that's the right move. Array.sort already has its own bug and I'll create a new one for the remaining extras.

Comment 35

[Andrew McCreight [:mccr8]]

Looks like the patch here landed in 20.

Comment 36

[Scoobidiver (away)]

Backout form Beta:
https://hg.mozilla.org/releases/mozilla-beta/rev/56833fe7db8e