1247283 - Improve self-hosted Array.sort performance

Status: RESOLVED FIXED

(Core :: JavaScript: Standard Library, defect)

Description

[Morgan Phillips [:mrrrgn]]

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.

Comment 1

[Morgan Phillips [:mrrrgn]]

* 2.) ... We begin each sort by _trying_ to create a dense array ...

Comment 2

[Till Schneidereit [:till]]

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.

Comment 3

[Morgan Phillips [:mrrrgn]]

haha, the security level was a total accident.

Comment 4

[Morgan Phillips [:mrrrgn]]

(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.

Comment 5

[Morgan Phillips [:mrrrgn]]

Attachment: arrayperf.diff

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.

Comment 6

[Till Schneidereit [: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.

Comment 7

[Pulsebot]

https://hg.mozilla.org/integration/mozilla-inbound/rev/3db255a29b49

Comment 8

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/3db255a29b49

Comment 9

[Morgan Phillips [:mrrrgn]]

Attachment: arrayperf.diff

Comment 10

[Morgan Phillips [:mrrrgn]]

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]:

Comment 11

[Morgan Phillips [:mrrrgn]]

Attachment: arrayperf.diff

Comment 12

[Morgan Phillips [:mrrrgn]]

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]:

Comment 13

[Liz Henry (:lizzard Please n-i to RyanVM, jcristau, or pascal)]

Marking affected for 46; tracking since this is a regression

Comment 14

[Liz Henry (:lizzard Please n-i to RyanVM, jcristau, or pascal)]

Comment on attachment 8723436 [details] [diff] [review]
arrayperf.diff

Fix for perf regression in 46. Please uplift to aurora.

Comment 15

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/releases/mozilla-aurora/rev/6fd65e84392e