Open Bug 1259007 Opened 4 years ago Updated 1 year ago

Further optimizations to self-hosted Array.sort

Categories

(Core :: JavaScript: Standard Library, defect)

defect
Not set

Tracking

()

Tracking Status
firefox48 --- affected

People

(Reporter: till, Unassigned)

References

Details

Attachments

(2 files, 8 obsolete files)

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)
Attached patch MergeSort.patch (obsolete) — Splinter Review
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+
`std_Array`, not `std_Array_sort`.

var x = []; x[0] = 1;  - is there some efficient way to do this without touching the prototype?
`std_Object_setPrototypeOf` makes it slow, `_DefineDataProperty` too... Nice... no way to use Arrays here.
Attached patch MergeSort.patch (obsolete) — Splinter Review
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)
Apologies, I took a quick look and believed it was an intermittent.
Flags: needinfo?(winter2718)
Attached patch MergeSort.patch (obsolete) — Splinter Review
Attachment #8734261 - Attachment is obsolete: true
Flags: needinfo?(vic99999)
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.
Attached patch MergeSort.patch (obsolete) — Splinter Review
updated patch
Attachment #8734850 - Attachment is obsolete: true
Attached patch MergeSort.patch (obsolete) — Splinter Review
Attachment #8799112 - Attachment is obsolete: true
Attached patch MergeSort.patch (obsolete) — Splinter Review
Attachment #8801574 - Attachment is obsolete: true
Attached patch MergeSort.patch (obsolete) — Splinter Review
Attached patch MergeSort.patch (obsolete) — Splinter Review
Attachment #8802385 - Attachment is obsolete: true
Attachment #8802392 - Attachment is obsolete: true
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.