Closed Bug 1247283 Opened 4 years ago Closed 4 years ago

Improve self-hosted Array.sort performance

Categories

(Core :: JavaScript: Standard Library, defect)

46 Branch
defect
Not set

Tracking

()

RESOLVED FIXED
mozilla47
Tracking Status
firefox45 --- unaffected
firefox46 + fixed
firefox47 + fixed

People

(Reporter: mrrrgn, Assigned: mrrrgn)

Details

(Keywords: regression)

Attachments

(1 file, 2 obsolete files)

Self-hosting Array.sort has caused a performance regression in many real world situations. There are three ways I can think of to fix this (without reverting the self-hosting patch altogether), perhaps all of them will be necessary.

1.) Only switch to self-hosted sorting when the array's length is large, where large is determined by performance testing. We know that self-hosting is fast for very large arrays, but for smaller ones it's obviously not.

2.) Be smarter about handling dense/sparse arrays. We begin each sort by creating a dense array from a sparse one, we could certainly save time there.

3.) Improve the merge sort algorithm itself.
Assignee: nobody → winter2718
* 2.) ... We begin each sort by _trying_ to create a dense array ...
Why is this marked as sec-sensitive?

(In reply to Morgan Phillips [:mrrrgn] from comment #0)
> Self-hosting Array.sort has caused a performance regression in many real
> world situations. There are three ways I can think of to fix this (without
> reverting the self-hosting patch altogether), perhaps all of them will be
> necessary.
> 
> 1.) Only switch to self-hosted sorting when the array's length is large,
> where large is determined by performance testing. We know that self-hosting
> is fast for very large arrays, but for smaller ones it's obviously not.

Is it really slower for smaller arrays, or is that the warmup time? If the latter, then restricting it to longer arrays wouldn't be too productive: if you're sorting multiple shorter arrays, you still want to get the speedup.

> 2.) Be smarter about handling dense/sparse arrays. We begin each sort by
> creating a dense array from a sparse one, we could certainly save time there.

I think this is critical. You can check if the array is dense, and if so skip the entire hole-handling pass.
> 
> 3.) Improve the merge sort algorithm itself.

I guess, but I doubt it's as critical as 2.
haha, the security level was a total accident.
Group: core-security
(In reply to Till Schneidereit [:till] from comment #2)
> Why is this marked as sec-sensitive?
> 
> (In reply to Morgan Phillips [:mrrrgn] from comment #0)
> > Self-hosting Array.sort has caused a performance regression in many real
> > world situations. There are three ways I can think of to fix this (without
> > reverting the self-hosting patch altogether), perhaps all of them will be
> > necessary.
> > 
> > 1.) Only switch to self-hosted sorting when the array's length is large,
> > where large is determined by performance testing. We know that self-hosting
> > is fast for very large arrays, but for smaller ones it's obviously not.
> 
> Is it really slower for smaller arrays, or is that the warmup time? If the
> latter, then restricting it to longer arrays wouldn't be too productive: if
> you're sorting multiple shorter arrays, you still want to get the speedup.
> 
> > 2.) Be smarter about handling dense/sparse arrays. We begin each sort by
> > creating a dense array from a sparse one, we could certainly save time there.
> 
> I think this is critical. You can check if the array is dense, and if so
> skip the entire hole-handling pass.
> > 
> > 3.) Improve the merge sort algorithm itself.
> 
> I guess, but I doubt it's as critical as 2.

Fair points. I'll focus on dense array detection.
Attached patch arrayperf.diff (obsolete) — Splinter Review
Current =>

./arraysort.js
SORTING 200000 ITEMS WITH NON-OPTIMIZED COMPARATOR 1.994 Seconds

Patch applied =>

./arraysort.js
SORTING 200000 ITEMS WITH NON-OPTIMIZED COMPARATOR 0.366 Seconds

A ~5x difference.
Attachment #8718108 - Flags: review?(till)
Comment on attachment 8718108 [details] [diff] [review]
arrayperf.diff

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

Makes sense. r=me with nits addressed.

::: js/src/builtin/Sorting.js
@@ +94,5 @@
>      }
>  
>      // Empty out any remaining elements in the buffer.
>      while (i < sizeLeft) {
> +        array[k] =lBuffer[i];

Nit: missing space after =, here and below.

@@ +117,5 @@
>  }
>  
>  // Iterative, bottom up, mergesort.
>  function MergeSort(array, len, comparefn) {
>      // To save effort we will do all of our work on a dense array,

s/array/list, perhaps?

@@ +119,5 @@
>  // Iterative, bottom up, mergesort.
>  function MergeSort(array, len, comparefn) {
>      // To save effort we will do all of our work on a dense array,
>      // then create holes at the end.
> +    var denseArray = new List();

... and rename this to denseList.
Attachment #8718108 - Flags: review?(till) → review+
https://hg.mozilla.org/mozilla-central/rev/3db255a29b49
Status: NEW → RESOLVED
Closed: 4 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla47
Target Milestone: mozilla47 → mozilla46
Attached patch arrayperf.diff (obsolete) — Splinter Review
Attachment #8718108 - Attachment is obsolete: true
Comment on attachment 8723430 [details] [diff] [review]
arrayperf.diff

*note* We'll need to apply the patch attached to bug 1246860 (also requested for uplift) _before_ this one.

Approval Request Comment
[Feature/regressing bug #]: 1246860 1247465
[User impact if declined]: Broken web pages.
[Describe test coverage new/current, TreeHerder]: Performance testing and the web page in the description of bug 1247465.
[Risks and why]: 
[String/UUID change made/needed]:
Attachment #8723430 - Flags: approval-mozilla-aurora?
Attached patch arrayperf.diffSplinter Review
Attachment #8723430 - Attachment is obsolete: true
Attachment #8723430 - Flags: approval-mozilla-aurora?
Comment on attachment 8723436 [details] [diff] [review]
arrayperf.diff

*note* We'll need to apply the patch attached to bug 1246860 (also requested for uplift) _before_ this one.

Approval Request Comment
[Feature/regressing bug #]: 1247465 1246860
[User impact if declined]: Broken web pages.
[Describe test coverage new/current, TreeHerder]: Performance testing and the web page noted in the description of bug 1247465.
[Risks and why]: 
[String/UUID change made/needed]:
Attachment #8723436 - Flags: approval-mozilla-aurora?
Marking affected for 46; tracking since this is a regression
Comment on attachment 8723436 [details] [diff] [review]
arrayperf.diff

Fix for perf regression in 46. Please uplift to aurora.
Attachment #8723436 - Flags: approval-mozilla-aurora? → approval-mozilla-aurora+
Target Milestone: mozilla46 → mozilla47
Version: unspecified → 46 Branch
You need to log in before you can comment on or make changes to this bug.