Array.prototype.slice on an array with holes is super slow

VERIFIED FIXED in Firefox 28

Status

()

Core
JavaScript Engine
VERIFIED FIXED
4 years ago
4 years ago

People

(Reporter: jandem, Assigned: isk)

Tracking

(Blocks: 1 bug)

unspecified
mozilla28
Points:
---

Firefox Tracking Flags

(firefox28 verified)

Details

(Whiteboard: [qa-])

Attachments

(1 attachment, 5 obsolete attachments)

(Reporter)

Description

4 years ago
Clojurescript has this "[coll [1 2 3]] (transient coll)" test where we're much slower than d8:

d8:  22 ms
SM: 330 ms

The problem is that we're spending almost all of our time in array_slice. See the micro-benchmark below:

d8:  11 ms
SM: 260 ms

If I fill the array instead of leaving holes we are about as fast:

d8: 24 ms
SM: 25 ms

If we can get the test below down to, say, 25 ms we will still be slower than d8 on this test but only ~4x slower instead of 15x.

function f() {
    var arr = new Array(32);
    var t = new Date;
    for (var i=0; i<100000; i++)
	var res = arr.slice();
    print(new Date - t);
    return res;
}
f();

Comment 1

4 years ago
array_slice right now does the slow get-every-property thing if the range being sliced extends past the end of the elements of |this|.  This is because NewDenseCopiedArray can only handle things if the elements passed in are *all* there, not just a leading set of them.  This seems fairly simply optimized.
(Assignee)

Comment 2

4 years ago
Created attachment 828507 [details] [diff] [review]
bug928917.patch

I remove "end <= obj->getDenseInitializedLength()" because I think it is no problem to copy uninitialized element.

array_slice right now does the slow get-every-property thing.
But if obj meets below condition , array_slice get all property at once in jsarray.cpp:2734.
      if (obj->is<ArrayObject>() && end <= obj->getDenseInitializedLength() &&
        !ObjectMayHaveExtraIndexedProperties(obj)) 

> function f() {
>    var arr = new Array(32);
>    var t = new Date;
>    for (var i=0; i<100000; i++)
>	var res = arr.slice();
>    print(new Date - t);
>    return res;
>}
>f();

This test can't meet end <= obj->getDenseInitializedLength().
Because arr is not initialized.
So I change the test to initialize arr ("var arr = new Array(32,0)");
I tried to measure the modified test and get result below.

d8:381
SM:227

SM is much faster than d8.
Attachment #828507 - Flags: review?(jorendorff)
(Assignee)

Updated

4 years ago
Attachment #828507 - Flags: review?(jorendorff) → review?(jdemooij)
(Reporter)

Comment 3

4 years ago
Comment on attachment 828507 [details] [diff] [review]
bug928917.patch

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

Thanks for the patch. This won't work though because NewDenseCopiedArray will try to access elements past the "initialized length" and will either crash or return an array with garbage values (try Array(100000).slice() a few times in the shell, it will likely crash or show random values).
Attachment #828507 - Flags: review?(jdemooij)
(Reporter)

Comment 4

4 years ago
Waldo, what do you think is the best way to fix this? Should we fix this in NewDenseCopiedArray?
Flags: needinfo?(jwalden+bmo)
(Assignee)

Comment 5

4 years ago
Created attachment 830837 [details] [diff] [review]
bug928917.patch

I use array property instead of array length to fill array.
Array.slice will be a faster by this patch.
But still,it is slower than v8.

The following is result.
d8:381
SM:640
Attachment #828507 - Attachment is obsolete: true
Attachment #830837 - Flags: review?(jdemooij)
(Assignee)

Comment 6

4 years ago
Created attachment 831226 [details] [diff] [review]
bug928917.patch

I didn't check boundary.
This patch is improved this point.
Attachment #830837 - Attachment is obsolete: true
Attachment #830837 - Flags: review?(jdemooij)
Attachment #831226 - Flags: review?(jdemooij)
(Assignee)

Updated

4 years ago
Attachment #831226 - Flags: review?(jdemooij) → review?(till)
(Assignee)

Updated

4 years ago
Attachment #831226 - Flags: review?(till) → review?(jdemooij)
(Assignee)

Updated

4 years ago
Assignee: nobody → iseki.m.aa
Status: NEW → ASSIGNED
Comment on attachment 831226 [details] [diff] [review]
bug928917.patch

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

Canceling because I'm not the right reviewer for this.

In the future, please at least comment on why you're changing reviewers. Better yet, ping the selected reviewer on IRC and discuss who would be a good alternative.
Attachment #831226 - Flags: review?(jdemooij)
Oh, I now see you already switched back to jandem. Even more importantly: please at the very least add comments to these switches.
(Reporter)

Comment 9

4 years ago
Comment on attachment 831226 [details] [diff] [review]
bug928917.patch

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

Sorry for the delay.

::: js/src/jsarray.cpp
@@ +2734,5 @@
>      if (!narr)
>          return false;
>      TryReuseArrayType(obj, narr);
>  
> +    AutoIdArray ids(cx, JS_Enumerate(cx, obj));

This will be pretty slow and shouldn't be necessary. I think you should change NewDenseCopiedArray instead.

How about this: use your earlier patch, and at the end of NewDenseCopiedArray change:

    arr->setDenseInitializedLength(vp ? length : 0);

    if (vp)
        arr->initDenseElements(0, vp, length);

to something like this:

    if (vp) {
        JS_ASSERT(src->getDenseInitializedLength() > elementOffset);
        uint32_t numSourceElements = src->getDenseInitializedLength() - elementOffset;
        uint32_t initLength = Min(numSourceElements, length);
        arr->setDenseInitializedLength(initLength);
        arr->initDenseElements(0, vp, initLength);
    } else {
        arr->setDenseInitializedLength(0);
    }

This is completely untested, but something like this should work I think...
(Assignee)

Comment 10

4 years ago
(In reply to Till Schneidereit [:till] from comment #8)
> Oh, I now see you already switched back to jandem. Even more importantly:
> please at the very least add comments to these switches.

I apologize for switching reviewer without comment.
I am careful in the future.
(Assignee)

Comment 11

4 years ago
Created attachment 8336568 [details] [diff] [review]
bug928917.patch

I changed the patch as be pointed out.
It is very fast.

I add test case.
Attachment #831226 - Attachment is obsolete: true
Attachment #8336568 - Flags: review?(jdemooij)
(Reporter)

Comment 12

4 years ago
Comment on attachment 8336568 [details] [diff] [review]
bug928917.patch

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

Thanks for adding a testcase :)

::: js/src/jsarray.cpp
@@ +2728,5 @@
>      narr = NewDenseAllocatedArray(cx, end - begin);
>      if (!narr)
>          return false;
>      TryReuseArrayType(obj, narr);
> +    if (vp && obj->getDenseInitializedLength() > 0) {

We should add this to NewDenseCopiedArray instead, I think. Also, we can't remove the other loop (the one with the GetElement/SetArrayElement calls), we need it for objects without dense elements. Did the patch pass jstests and jit-tests?
Attachment #8336568 - Flags: review?(jdemooij)
(Assignee)

Comment 13

4 years ago
Created attachment 8336779 [details] [diff] [review]
bug928917.patch

Thanks for reviewing the patch.

I misunderstand DenseElements.
I think DenseElements is below
    [1,2,3,4,5,6,7,8,9,10]
and SparseElements is below.
    [1,,,,5,,,9,10]
But both two array above is dense.

I have one question. What is the SparseElements?


This patch fail four pass below.
    /mozilla-central/js/src/jit-test/tests/basic/shell-watchdog.js
    /mozilla-central/js/src/jit-test/tests/parallel/timeout.js
    /mozilla-central/js/src/jit-test/tests/parallel/timeout-gc.js
    /mozilla-central/js/src/jit-test/tests/basic/timeout-check.js
But top three test is failed without attaching this patch.
Only timeout-check.js is failed by this patch.
timeout-check.js has not Array.slice.
So I don't know why fail this test by this patch.
Attachment #8336568 - Attachment is obsolete: true
Attachment #8336779 - Flags: feedback?(jdemooij)
(Reporter)

Comment 14

4 years ago
Comment on attachment 8336779 [details] [diff] [review]
bug928917.patch

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

(In reply to iseki.m.aa from comment #13)
> I misunderstand DenseElements.
> I think DenseElements is below
>     [1,2,3,4,5,6,7,8,9,10]
> and SparseElements is below.
>     [1,,,,5,,,9,10]
> But both two array above is dense.
> 
> I have one question. What is the SparseElements?

You are right, [1,2,3] is dense. However, dense elements can also have holes, so [1,2,,,3] is still dense. Sparse elements are also used in some cases, for example when there are many holes and using dense elements would waste a lot of memory:

var a = [];
a[10000] = 1; // a now has sparse elements.

When an object has a sparse, indexed property, obj->isIndexed() and ObjectMayHaveExtraIndexedProperties will return |true|. Because your fast path checks ObjectMayHaveExtraIndexedProperties, you don't have to worry about sparse elements.

> But top three test is failed without attaching this patch.
> Only timeout-check.js is failed by this patch.
> timeout-check.js has not Array.slice.
> So I don't know why fail this test by this patch.

Yeah, these test failures look unrelated :)

::: js/src/jsarray.cpp
@@ +2730,1 @@
>      {

Nit: the condition now fits on one line, so move the { to the end of the previous line.

@@ +2732,3 @@
>          if (!narr)
>              return false;
>          TryReuseArrayType(obj, narr);

The same 4 lines appear after this |if|, please move this before the |if| and remove the copy below.

@@ +2732,4 @@
>          if (!narr)
>              return false;
>          TryReuseArrayType(obj, narr);
> +        if (vp && obj->getDenseInitializedLength() > begin) {

Remove "vp &&"

@@ +2732,5 @@
>          if (!narr)
>              return false;
>          TryReuseArrayType(obj, narr);
> +        if (vp && obj->getDenseInitializedLength() > begin) {
> +            uint32_t numSourceElements = obj->getDenseInitializedLength();

This should be obj->getDenseInitializedLength() - begin.

@@ +2737,5 @@
> +            uint32_t initLength = Min(numSourceElements, end - begin);
> +            narr->setDenseInitializedLength(initLength);
> +            narr->initDenseElements(0, &obj->getDenseElement(begin), initLength);
> +        } else {
> +            narr->setDenseInitializedLength(0);

You can remove this |else| branch.
Attachment #8336779 - Flags: feedback?(jdemooij)
(Assignee)

Comment 15

4 years ago
Created attachment 8338269 [details] [diff] [review]
bug928917.patch

Thank you for reviewing.

I fixed the point which pointed out.
Attachment #8336779 - Attachment is obsolete: true
Attachment #8338269 - Flags: review?(jdemooij)
(Reporter)

Comment 16

4 years ago
Comment on attachment 8338269 [details] [diff] [review]
bug928917.patch

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

Great! Do you have access to the Try server? If not, I will push this to Try tomorrow and land it for you.
Attachment #8338269 - Flags: review?(jdemooij) → review+
(Reporter)

Updated

4 years ago
Flags: needinfo?(iseki.m.aa)
Comment on attachment 8338269 [details] [diff] [review]
bug928917.patch

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

Modifying NewDenseCopiedArray to change its semantics is probably a bad idea.  It's a very low-level, fast-pathy sort of thing -- adding edge-case slowness to it is pretty worrisome without a comprehensive audit, and I don't think it's really worth the risk, not while working on the current algorithm implementation.  (I'd want to add stepwise comments to this algorithm before I made that sort of substantial change to it, to be honest.  And it looks like those stepwise comments are definitely desirable, given that we have this not-to-ES5 behavior as noted below, even if it is something we want.)

For a moment I thought this might be double-initializing the contents of the new array, but NewDenseAllocatedArray just allocates the elements without initializing them (except to crash on touch, in debug builds), and the initialized length starts out 0.  So this looks perfect to me.

::: js/src/jit-test/tests/basic/array-slice.js
@@ +4,5 @@
> +    var res = arr.slice(0,10);
> +    assertEq(arr[0],res[0]);
> +    assertEq(arr[1],res[1]);
> +    assertEq(arr[7],res[7]);
> +    assertEq(res.length,10);

Interesting.  This is the right result in ES3 and ES6, but ES5 somehow omitted the penultimate step in Array.prototype.slice to set the final length, so in ES5 technically it should be 8 or so.  I guess if our slice implementation had stepwise comments we'd call this out somehow, but since we don't, and as every browser reports 10 here, there's really nothing to do now.

Updated

4 years ago
Flags: needinfo?(jwalden+bmo)
(Assignee)

Comment 18

4 years ago
(In reply to Jan de Mooij [:jandem] from comment #16)
> Comment on attachment 8338269 [details] [diff] [review]
> bug928917.patch
> 
> Review of attachment 8338269 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> Great! Do you have access to the Try server? If not, I will push this to Try
> tomorrow and land it for you.

Thank you for your reviewing.
I don't have access to the Try server. 
Would you push this to Try?
Flags: needinfo?(iseki.m.aa)
(Assignee)

Comment 19

4 years ago
Sorry, I didn't read the last comment.
Thank you for your commenting.

(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #17)
> Comment on attachment 8338269 [details] [diff] [review]
> bug928917.patch
> 
> Review of attachment 8338269 [details] [diff] [review]:
> -----------------------------------------------------------------
> Modifying NewDenseCopiedArray to change its semantics is probably a bad
> idea.  It's a very low-level, fast-pathy sort of thing -- adding edge-case
> slowness to it is pretty worrisome without a comprehensive audit, and I
> don't think it's really worth the risk, not while working on the current
> algorithm implementation.  (I'd want to add stepwise comments to this
> algorithm before I made that sort of substantial change to it, to be honest.
> And it looks like those stepwise comments are definitely desirable, given
> that we have this not-to-ES5 behavior as noted below, even if it is
> something we want.)

Could you tell me what is the edge-case specifically?
(Reporter)

Comment 21

4 years ago
Try looks good, so I pushed this for you:

https://hg.mozilla.org/integration/mozilla-inbound/rev/0e9832497387

Thanks again for the patch!
(Reporter)

Comment 22

4 years ago
(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #17)

Forgot to reply, thanks for your comment and looking at the patch.

> For a moment I thought this might be double-initializing the contents of the
> new array, but NewDenseAllocatedArray just allocates the elements without
> initializing them (except to crash on touch, in debug builds), and the
> initialized length starts out 0.

Yes same here :)

> So this looks perfect to me.

Great, thanks.
(Assignee)

Comment 23

4 years ago
> (In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #17)
> > Comment on attachment 8338269 [details] [diff] [review]
> > bug928917.patch
> > 
> > Review of attachment 8338269 [details] [diff] [review]:
> > -----------------------------------------------------------------
> > Modifying NewDenseCopiedArray to change its semantics is probably a bad
> > idea.  It's a very low-level, fast-pathy sort of thing -- adding edge-case
> > slowness to it is pretty worrisome without a comprehensive audit, and I
> > don't think it's really worth the risk, not while working on the current
> > algorithm implementation.  (I'd want to add stepwise comments to this
> > algorithm before I made that sort of substantial change to it, to be honest.
> > And it looks like those stepwise comments are definitely desirable, given
> > that we have this not-to-ES5 behavior as noted below, even if it is
> > something we want.)
> 
> Could you tell me what is the edge-case specifically?

Sorry, I misunderstand. Please ignore this comment.
(Assignee)

Updated

4 years ago
Status: ASSIGNED → RESOLVED
Last Resolved: 4 years ago
Resolution: --- → FIXED
(Reporter)

Comment 24

4 years ago
The sheriffs will close this bug once your patch is on mozilla-central :)
Status: RESOLVED → REOPENED
Resolution: FIXED → ---
https://hg.mozilla.org/mozilla-central/rev/0e9832497387
Status: REOPENED → RESOLVED
Last Resolved: 4 years ago4 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla28
(Assignee)

Comment 26

4 years ago
(In reply to Jan de Mooij [:jandem] from comment #24)
> The sheriffs will close this bug once your patch is on mozilla-central :)

Sorry, I didn't well understand about changing status.
When I should change status into RESOLVED? 
Or I should not change status into RESOLVED?
(In reply to iseki.m.aa from comment #26)
> Sorry, I didn't well understand about changing status.
> When I should change status into RESOLVED? 
> Or I should not change status into RESOLVED?

The only time you as a developer set a bug to RESOLVED is when you're marking it as something other than FIXED (or if the fix has landed in another bug).

Specifically, here's a rough outline of scenarios:
- you investigate a bug report and discover that it's not really a bug. Then you mark the bug as RESOLVED/INVALID (with an explanation, of course)
- you realize that a bug has been fixed by a patch that landed in another bug. Then you make this bug depend on the other bug, and mark this one as RESOLVED/FIXED
- you test a bug and realize that it has been fixed, but you don't know what exactly fixed it. Then you mark the bug as RESOLVED/WORKSFORME
- you investigate a bug and realize that the issue has already been reported in another bug. Then you mark the bug as RESOLVED/DUPLICATE and enter the other bug's number in the field that is shown once you select "DUPLICATE"
- you investigate a bug and realize that we won't implement the requested change. Then you mark the bug as RESOLVED/WONTFIX
- you investigate a bug and can't reproduce the issue, and the reporter doesn't react to requests for more information for quite some time. Then you mark the bug as RESOLVED/INCOMPLETE
(Assignee)

Comment 28

4 years ago
(In reply to Till Schneidereit [:till] from comment #27)
> (In reply to iseki.m.aa from comment #26)
> > Sorry, I didn't well understand about changing status.
> > When I should change status into RESOLVED? 
> > Or I should not change status into RESOLVED?
> 
> The only time you as a developer set a bug to RESOLVED is when you're
> marking it as something other than FIXED (or if the fix has landed in
> another bug).
> 
> Specifically, here's a rough outline of scenarios:
> - you investigate a bug report and discover that it's not really a bug. Then
> you mark the bug as RESOLVED/INVALID (with an explanation, of course)
> - you realize that a bug has been fixed by a patch that landed in another
> bug. Then you make this bug depend on the other bug, and mark this one as
> RESOLVED/FIXED
> - you test a bug and realize that it has been fixed, but you don't know what
> exactly fixed it. Then you mark the bug as RESOLVED/WORKSFORME
> - you investigate a bug and realize that the issue has already been reported
> in another bug. Then you mark the bug as RESOLVED/DUPLICATE and enter the
> other bug's number in the field that is shown once you select "DUPLICATE"
> - you investigate a bug and realize that we won't implement the requested
> change. Then you mark the bug as RESOLVED/WONTFIX
> - you investigate a bug and can't reproduce the issue, and the reporter
> doesn't react to requests for more information for quite some time. Then you
> mark the bug as RESOLVED/INCOMPLETE

Thank you for your detailed description.
I understand well when I should change flag.
Thanks a lot.
Jan de Mooij, can you please confirm this is resolved in the latest Beta?
status-firefox28: --- → fixed
Flags: needinfo?(jdemooij)
Whiteboard: [qa-]
(Reporter)

Comment 30

4 years ago
(In reply to Anthony Hughes, QA Mentor (:ashughes) from comment #29)
> Jan de Mooij, can you please confirm this is resolved in the latest Beta?

Sorry for the delay. I tried the testcase in comment 0 and it's still fast.
Flags: needinfo?(jdemooij)
(In reply to Jan de Mooij [:jandem] from comment #30)
> (In reply to Anthony Hughes, QA Mentor (:ashughes) from comment #29)
> > Jan de Mooij, can you please confirm this is resolved in the latest Beta?
> 
> Sorry for the delay. I tried the testcase in comment 0 and it's still fast.

Thanks.
Status: RESOLVED → VERIFIED
status-firefox28: fixed → verified
You need to log in before you can comment on or make changes to this bug.