Closed
Bug 1247283
Opened 7 years ago
Closed 7 years ago
Improve self-hosted Array.sort performance
Categories
(Core :: JavaScript: Standard Library, defect)
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)
4.78 KB,
patch
|
lizzard
:
approval-mozilla-aurora+
|
Details | Diff | Splinter Review |
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 | ||
Updated•7 years ago
|
Assignee: nobody → winter2718
Assignee | ||
Comment 1•7 years ago
|
||
* 2.) ... We begin each sort by _trying_ to create a dense array ...
Comment 2•7 years ago
|
||
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.
Assignee | ||
Comment 3•7 years ago
|
||
haha, the security level was a total accident.
Updated•7 years ago
|
Group: core-security
Assignee | ||
Comment 4•7 years ago
|
||
(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.
Assignee | ||
Comment 5•7 years ago
|
||
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 6•7 years ago
|
||
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+
Comment 8•7 years ago
|
||
bugherder |
https://hg.mozilla.org/mozilla-central/rev/3db255a29b49
Status: NEW → RESOLVED
Closed: 7 years ago
status-firefox47:
--- → fixed
Resolution: --- → FIXED
Target Milestone: --- → mozilla47
Assignee | ||
Updated•6 years ago
|
Target Milestone: mozilla47 → mozilla46
Assignee | ||
Comment 9•6 years ago
|
||
Attachment #8718108 -
Attachment is obsolete: true
Assignee | ||
Comment 10•6 years ago
|
||
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?
Assignee | ||
Comment 11•6 years ago
|
||
Attachment #8723430 -
Attachment is obsolete: true
Attachment #8723430 -
Flags: approval-mozilla-aurora?
Assignee | ||
Comment 12•6 years ago
|
||
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
status-firefox45:
--- → unaffected
status-firefox46:
--- → affected
tracking-firefox46:
--- → +
tracking-firefox47:
--- → +
Keywords: 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+
Comment 15•6 years ago
|
||
bugherderuplift |
https://hg.mozilla.org/releases/mozilla-aurora/rev/6fd65e84392e
Updated•6 years ago
|
Target Milestone: mozilla46 → mozilla47
Version: unspecified → 46 Branch
You need to log in
before you can comment on or make changes to this bug.
Description
•