self-host some Array extras

RESOLVED FIXED in Firefox 21

Status

()

defect
RESOLVED FIXED
7 years ago
6 years ago

People

(Reporter: till, Assigned: till)

Tracking

(Depends on 2 bugs)

Other Branch
mozilla20
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(firefox20 disabled, firefox21 fixed)

Details

(Whiteboard: [leave open][js:t], URL)

Attachments

(1 attachment, 2 obsolete attachments)

(Assignee)

Description

7 years ago
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.
(Assignee)

Comment 2

7 years ago
Posted patch Part 1: Convert some extras (obsolete) — Splinter Review
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.
Attachment #656003 - Flags: review?(jwalden+bmo)
(Assignee)

Updated

7 years ago
Blocks: 743634
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
Attachment #656003 - Flags: review?(jwalden+bmo) → review+
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.
FWIW, when I uncommoned these in jsarray.cpp it was a huge readability win.
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 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.
> 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.
(Assignee)

Comment 9

7 years ago
Posted file Part 1: Convert some extras, v2 (obsolete) —
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.
Attachment #656003 - Attachment is obsolete: true
Attachment #657706 - Flags: review+
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/tschneidereit@gmail.com-1171b29f076f
(Assignee)

Comment 11

7 years ago
Let's try this again after fixing a stupid omission:
http://tbpl.mozilla.org/?tree=Try&rev=d6f025deb333
Status: NEW → ASSIGNED
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/tschneidereit@gmail.com-d6f025deb333
(Assignee)

Comment 13

7 years ago
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
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/tschneidereit@gmail.com-d91dc85909a4
(Assignee)

Updated

7 years ago
Depends on: 787927
(Assignee)

Comment 15

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

Once that patch lands, this should be ready, too.
Attachment #657706 - Attachment is obsolete: true
Attachment #657889 - Flags: review+
(Assignee)

Comment 16

7 years ago
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.
Whiteboard: [leave open]
Depends on: 789117
Backed out for failures in browser_dbg_bfcache.js:
https://hg.mozilla.org/integration/mozilla-inbound/rev/9ed5024f9101
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 <tschneidereit@gmail.com> - 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 <tschneidereit@gmail.com> - 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 <trev.saunders@gmail.com> - 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
Whiteboard: [leave open] → [leave open][js:t]
(Assignee)

Updated

7 years ago
Depends on: 772334
No longer blocks: 784288
Depends on: 784288
Depends on: 664769
Duplicate of this bug: 602132
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/tschneidereit@gmail.com-755ad7378a5d
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/tschneidereit@gmail.com-755ad7378a5d
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/tschneidereit@gmail.com-755ad7378a5d
Depends on: 811606
Depends on: 811612
Depends on: 811616
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.)
Depends on: 811625
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.
Depends on: 811694
Duplicate of this bug: 743634
Is there anything else needed to resolve this bug?
(Assignee)

Comment 32

7 years ago
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

7 years ago
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.
(Assignee)

Comment 34

7 years ago
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.
Status: ASSIGNED → RESOLVED
Last Resolved: 7 years ago
Resolution: --- → FIXED
Summary: self-host Array extras → self-host some Array extras
(Assignee)

Updated

7 years ago
No longer blocks: 715181

Updated

7 years ago
Depends on: 815010
Looks like the patch here landed in 20.
Target Milestone: --- → mozilla20

Updated

6 years ago
No longer blocks: 602132

Updated

6 years ago
No longer blocks: 743634

Updated

6 years ago
Depends on: 844406

Updated

6 years ago
Blocks: 868369

Updated

6 years ago
Depends on: 902822
You need to log in before you can comment on or make changes to this bug.