Further optimizations to self-hosted Array.sort

NEW
Unassigned

Status

()

3 years ago
2 years ago

People

(Reporter: till, Unassigned)

Tracking

Trunk
Points:
---

Firefox Tracking Flags

(firefox48 affected)

Details

Attachments

(2 attachments, 8 obsolete attachments)

(Reporter)

Description

3 years ago
Created attachment 8733845 [details]
Example JS of optimized sort

Split from bug 715181, see bug 715181 comment 127.

Mrrrgn, can you take a look at this and see whether we should take it?

4esn0k, can you turn this into a proper patch so we can land it?
Attachment #8733845 - Flags: feedback?(winter2718)
Flags: needinfo?(vic99999)

Comment 1

3 years ago
Created attachment 8733927 [details] [diff] [review]
MergeSort.patch
Flags: needinfo?(vic99999)
Comment on attachment 8733845 [details]
Example JS of optimized sort

This does indeed improve performance. Thanks for filing this !
Attachment #8733845 - Flags: feedback?(winter2718) → feedback+
Comment on attachment 8733927 [details] [diff] [review]
MergeSort.patch

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

Thanks for the patch ! :) Moving to a buffer is alright, but we need to use List instead of std_Array_sort, see the failing test:

Morgans-MacBook-Pro:_DBG.OBJ mrrrgn$ ../tests/jstests.py dist/bin/js ecma_6/Array/sort
## ecma_6/Array/sort_holes.js: rc = 3, run time = 0.50141
uncaught exception: Illegally touched the array's setter!
(Unable to print stack trace)
REGRESSION - ecma_6/Array/sort_holes.js
[2|1|0|0] 100% ======================================================>|   1.6s
REGRESSIONS
    ecma_6/Array/sort_holes.js
FAIL
* to a single buffer
(In reply to Morgan Phillips [:mrrrgn] from comment #2)
> Comment on attachment 8733845 [details]
> Example JS of optimized sort
> 
> This does indeed improve performance. Thanks for filing this !

We'll need to see how much of this performance boost came from using std_Array_sort, which we need to avoid.
Attachment #8733845 - Flags: feedback+

Comment 6

3 years ago
`std_Array`, not `std_Array_sort`.

var x = []; x[0] = 1;  - is there some efficient way to do this without touching the prototype?

Comment 7

3 years ago
`std_Object_setPrototypeOf` makes it slow, `_DefineDataProperty` too... Nice... no way to use Arrays here.

Comment 8

3 years ago
Created attachment 8734261 [details] [diff] [review]
MergeSort.patch

without `std_Array`
Attachment #8733927 - Attachment is obsolete: true
(In reply to 4esn0k from comment #7)
> `std_Object_setPrototypeOf` makes it slow, `_DefineDataProperty` too...
> Nice... no way to use Arrays here.

Yeah, I was going to suggest trying _DefineDataProperty but wasn't sure it would perform as well as List :( Thanks for the new patch. :)
Comment on attachment 8734261 [details] [diff] [review]
MergeSort.patch

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

Nice. I'll land this after a try run. :)
Attachment #8734261 - Flags: review+
I had to back this out because it broke a test: https://treeherder.mozilla.org/logviewer.html#?job_id=24640920&repo=mozilla-inbound

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

For the record, this showed up in the try run in comment 11.
Flags: needinfo?(winter2718)
Flags: needinfo?(vic99999)
The devtools test failure in that try run is also happening when this landed: https://treeherder.mozilla.org/logviewer.html#?job_id=24640238&repo=mozilla-inbound
Apologies, I took a quick look and believed it was an intermittent.
Flags: needinfo?(winter2718)

Comment 16

3 years ago
Created attachment 8734850 [details] [diff] [review]
MergeSort.patch
Attachment #8734261 - Attachment is obsolete: true
Flags: needinfo?(vic99999)

Comment 17

3 years ago
I do not know what is wrong and how to investigate this.
Previous patch changed the behaviour of `sort`, when `comparefn` is incorrect.
I have updated the patch to use `comparefn(...) <= 0` as it was before.

Comment 18

2 years ago
Created attachment 8799112 [details] [diff] [review]
MergeSort.patch

updated patch
Attachment #8734850 - Attachment is obsolete: true

Comment 19

2 years ago
Created attachment 8801574 [details] [diff] [review]
MergeSort.patch
Attachment #8799112 - Attachment is obsolete: true

Comment 20

2 years ago
Created attachment 8802385 [details] [diff] [review]
MergeSort.patch
Attachment #8801574 - Attachment is obsolete: true

Comment 21

2 years ago
Created attachment 8802392 [details] [diff] [review]
MergeSort.patch

Comment 22

2 years ago
Created attachment 8802393 [details] [diff] [review]
MergeSort.patch
Attachment #8802385 - Attachment is obsolete: true
Attachment #8802392 - Attachment is obsolete: true

Comment 23

2 years ago
Created attachment 8821737 [details] [diff] [review]
1259007-MergeSort.patch

Could you try this patch?
Attachment #8802393 - Attachment is obsolete: true
You need to log in before you can comment on or make changes to this bug.