1839051 - Substitute NS_QuickSort with std:sort everywhere

Status: RESOLVED FIXED

(Core :: XPCOM, enhancement)

Description

[Jens Stutte [:jstutte]]

NS_QuickSort is known to have a worst case quadratic performance and that it can lead to over-recursion and subsequent stack overflows. std::sort uses an introsort algorithm these days, which avoids these caveats.

This increases also the type safety, as NS_QuickSort uses void* and just memmoves the elements regardless their eventual move or copy assignment operators.

Comment 1

[Jens Stutte [:jstutte]]

Attachment: WIP: Bug 1839051 - Substitute NS_QuickSort usage with std::sort. r?#xpcom-reviewers

Comment 2

[Jens Stutte [:jstutte]]

Attachment: Bug 1839051 - Use std::sort for nsTArray and deprecate NS_QuickSort. r?#xpcom-reviewers

Comment 3

[Jens Stutte [:jstutte]]

Attachment: Bug 1839051 - Use nsTArray::Sort in the nsXULSortService. r?#xpcom-reviewers

Depends on D181339

Comment 4

[Jens Stutte [:jstutte]]

My current understanding here is, that std::sort uses both move and copy assignments, while the combination of std::make_heap and std::sort_heap relies only on move assignments. I did not find a possibility to tell std::sort to do something different wtr.

Furthermore copy assignments might have other unexpected side effects (like fiddling with the refcount of referenced objects or deep, expensive copies of entire object trees) that need to be understood one by one. Still std::sort should be used for the large majority of cases, as heap sort has a linear increasing overhead in comparison (2 * N * log(n) comparisons) and behaves processor-cache unfriendly on large arrays.

A possibility is to move the decision on which algorithm to use up the call chain like in the proposed WIP patch for nsTArray, with std::sort being the default case. We also could think about some support for index-based sorting with auxiliary index arrays that would avoid to copy/move big objects at all (we have some hand-made cases of this, as well).

My gut feeling for choosing would then be:

• std::sort based Sort for small objects with trivial copy assignments (memcpy like).
• HeapSort for arbitrary (also big) objects but bounded, relatively small array sizes.
• IndexSort (yet to be defined based on std::sort, returning a sorted index array) for big objects in (potentially) big arrays

where "small array size" and "big object" are fuzzy and in some cases might merit explicit performance tests for hot code paths.

In the meantime TB folks fixed bug 1498313, which was the most frequent offender here and triggered this activity to some extent. There is probably no real urge to act, but slowly we should clean this sorting mess up, IMHO. I might come back here but not very soon, if anybody wants to pick this up feel free to take over bug and patches.

Comment 5

[Jens Stutte [:jstutte]]

It seems there is some prior analysis also on bug 1082580.

Comment 6

[Jens Stutte [:jstutte]]

Note that bug 1626570 explicitly introduced CopyableTArray which would probably tell us that nsTArray as such is not meant to be copyable.

Comment 7

[Jens Stutte [:jstutte]]

(sorry for the noise)

Comment 8

[Jens Stutte [:jstutte]]

Attachment: Bug 1839051 - Use nsTArray::Sort for Sort and have also StableSort in nsCOMArray. r?#xpcom-reviewers

Depends on D181339

Comment 9

[Jens Stutte [:jstutte]]

Attachment: Bug 1839051 - Use nsTArray::StableSort in the txNodeSorter. r?#xpcom-reviewers

Depends on D181889

Comment 10

[Jens Stutte [:jstutte]]

Attachment: Bug 1839051 - Use nsTArray::Sort in the SpanningCellSorter. r?#xpcom-reviewers

Depends on D181890

Comment 11

[Jens Stutte [:jstutte]]

OK, I admit I continue to look into this - slowly.

Comment 12

[Jens Stutte [:jstutte]]

Attachment: Bug 1839051 - Use nsTArray::Sort in KeyboardLayout. r?#xpcom-reviewers

Depends on D181891

Comment 13

[Jens Stutte [:jstutte]]

Attachment: Bug 1839051 - Remove include nsQuickSort.h from some more files. r?#xpcom-reviewers

Comment 14

[Jens Stutte [:jstutte]]

Attachment: WIP: Bug 1839051 - Have StandardSortRefPtrArray<PointeeType> for nsTArray. r?#xpcom-reviewers

Depends on D182731

Comment 15

[Jens Stutte [:jstutte]]

Attachment: WIP: Bug 1839051 - Use StandardSortRefPtrArray for nsTArray<RefPtr<dom::Animation>>. r?#xpcom-reviewers

Depends on D182746

Comment 16

[Jens Stutte [:jstutte]]

I hit 1815524 often enough while testing to consider it a dependency.

Comment 17

[Phabricator Automation]

Comment on attachment 9342273 [details]
WIP: Bug 1839051 - Have StandardSortRefPtrArray<PointeeType> for nsTArray. r?#xpcom-reviewers

Revision D182746 was moved to bug 1842130. Setting attachment 9342273 [details] to obsolete.

Comment 18

[Phabricator Automation]

Comment on attachment 9342274 [details]
WIP: Bug 1839051 - Use StandardSortRefPtrArray for nsTArray<RefPtr<dom::Animation>>. r?#xpcom-reviewers

Revision D182747 was moved to bug 1842130. Setting attachment 9342274 [details] to obsolete.

Comment 19

[Jens Stutte [:jstutte]]

Recap of the plan:

• this bug's scope finishes with removing any direct usage of NS_QuickSort from central. In doing so it uses a conservative default for nsTArrays of elements that are not trivially copy assignable and adds some paranoia debug code.
• Bug 1842130 wants to introduce better/faster handling for the special case of nsTArray<RefPtr<T>>. We probably do not want to land this bug until we have that, too.
• Bug 1842134 collects the remaining improvements for other arrays of elements that are not trivially copy assignable. Those can be worked out one by one as they come in.
• Bug 1839052 will remove the dead code of NS_QuickSort once it's really dead.
• Bug 1842136 shall provide some explainer on when and how to use which sorting variants.
• We may want to have another bug to remove the most paranoia debug code from nsTArray::Sort and/or switch from warnings to (static?) asserts once we verified all existing uses.

Comment 20

[Jens Stutte [:jstutte]]

Attachment: Bug 1839051 - Use std::sort in InitPropertyInfos. r?#xpcom-reviewers

Depends on D181339

Comment 21

[Jens Stutte [:jstutte]]

Attachment: WIP: Bug 1839051 - Use std::sort in InitPropertyInfos. r?#xpcom-reviewers

Depends on D181339

Comment 22

[Jens Stutte [:jstutte]]

Attachment: UsesOfSort.txt

I checked via searchfox our current uses of nsTArray<T>::Sort for things we want to change.

Comment 23

[Jens Stutte [:jstutte]]

Attachment: UsesOfSort.txt

Comment 24

[Jens Stutte [:jstutte]]

Attachment: Bug 1839051 - Have a trivially move assignable and constructible StartupCacheEntry::KeyValuePair. r?#xpcom-reviewers

Depends on D182731

Comment 25

[Jens Stutte [:jstutte]]

Attachment: Bug 1839051 - Suppress some warnings about not being trivially move assignable/constructible. r?#xpcom-reviewers

Depends on D185065

Comment 26

[Phabricator Automation]

Comment on attachment 9346747 [details]
Bug 1839051 - Suppress some warnings about not being trivially move assignable/constructible. r?#xpcom-reviewers

Revision D185066 was moved to bug 1842134. Setting attachment 9346747 [details] to obsolete.

Comment 27

[Jens Stutte [:jstutte]]

(In reply to Jens Stutte [:jstutte] from comment #19)

Recap of the plan:

• this bug's scope finishes with removing any direct usage of NS_QuickSort from central. In doing so it uses a conservative default for nsTArrays of elements that are not trivially copy assignable and adds some paranoia debug code.
• Bug 1842130 wants to introduce better/faster handling for the special case of nsTArray<RefPtr<T>>. We probably do not want to land this bug until we have that, too.
• Bug 1842134 collects the remaining improvements for other arrays of elements that are not trivially copy assignable. Those can be worked out one by one as they come in.
• Bug 1839052 will remove the dead code of NS_QuickSort once it's really dead.
• Bug 1842136 shall provide some explainer on when and how to use which sorting variants.
• We may want to have another bug to remove the most paranoia debug code from nsTArray::Sort and/or switch from warnings to (static?) asserts once we verified all existing uses.

Thanks to :emilios precious hints on how to do the template magic to know the T in RefPtr<T> we could reduce the number of patches significantly.

• this bug's initial patch does introduce anything needed inside nsTArray, the remaining patches remove any other direct usage of NS_QuickSort from central, most of the times in favor of using nsTArray.
• Bug 1842130 is not needed anymore.
• Bug 1842134 changes scope to deal with elements not being trivially move assignable or copyable.
• Bug 1839052 will remove the dead code of NS_QuickSort once it's really dead.
• Bug 1842136 shall provide some explainer on when and how to use which sorting variants.

Comment 28

[Phabricator Automation]

Comment on attachment 9346745 [details]
Bug 1839051 - Have a trivially move assignable and constructible StartupCacheEntry::KeyValuePair. r?#xpcom-reviewers

Revision D185065 was moved to bug 1846695. Setting attachment 9346745 [details] to obsolete.

Comment 29

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/720e6863c41a
Use std::sort for nsTArray and deprecate NS_QuickSort. r=emilio,nika,janv,dom-storage-reviewers
https://hg.mozilla.org/integration/autoland/rev/82525b11a7c3
Use std::sort in InitPropertyInfos. r=emilio
https://hg.mozilla.org/integration/autoland/rev/658568fe9662
Use nsTArray::Sort in the nsXULSortService. r=xpcom-reviewers,emilio
https://hg.mozilla.org/integration/autoland/rev/20a850a4fd7e
Use nsTArray::Sort for Sort and have also StableSort in nsCOMArray. r=necko-reviewers,kershaw,emilio,places-reviewers,mak
https://hg.mozilla.org/integration/autoland/rev/2ab1e27d5945
Use nsTArray::StableSort in the txNodeSorter. r=peterv,emilio
https://hg.mozilla.org/integration/autoland/rev/8443a22a399d
Use nsTArray::Sort in the SpanningCellSorter. r=xpcom-reviewers,emilio
https://hg.mozilla.org/integration/autoland/rev/5204b97e40bc
Use nsTArray::Sort in KeyboardLayout. r=xpcom-reviewers,emilio,win-reviewers,rkraesig
https://hg.mozilla.org/integration/autoland/rev/94a4c163e417
Remove include nsQuickSort.h from some more files. r=emilio

Comment 30

[Iulian Moraru]

Backed out for causing assertion failures on NotificationController.cpp.
This happens on multiple jobs.

• Push with failures

• Failure log example 1

• Failure log example 2

• Backout link

[task 2023-12-04T20:12:30.919Z] 20:12:30     INFO - TEST-START | accessible/tests/mochitest/hypertext/test_update.html
[task 2023-12-04T20:12:30.920Z] 20:12:30     INFO - GECKO(1661) | [Parent 1661, Main Thread] WARNING: NS_ENSURE_SUCCESS(rv, rv) failed with result 0x80004005 (NS_ERROR_FAILURE): file /builds/worker/checkouts/gecko/chrome/nsChromeRegistry.cpp:182
[task 2023-12-04T20:12:30.921Z] 20:12:30     INFO - GECKO(1661) | [Parent 1661, Main Thread] WARNING: 'NS_FAILED(rv)', file /builds/worker/checkouts/gecko/chrome/nsChromeProtocolHandler.cpp:73
[task 2023-12-04T20:12:30.936Z] 20:12:30     INFO - GECKO(1661) | [Parent 1661, Main Thread] WARNING: Failed to retarget HTML data delivery to the parser thread.: file /builds/worker/checkouts/gecko/parser/html/nsHtml5StreamParser.cpp:1227
[task 2023-12-04T20:12:31.381Z] 20:12:31     INFO - GECKO(1661) | Assertion failure: aIdx >= 0 && bIdx >= 0 && aIdx != bIdx, at /builds/worker/checkouts/gecko/accessible/base/NotificationController.cpp:544
[task 2023-12-04T20:12:31.384Z] 20:12:31     INFO -  Initializing stack-fixing for the first stack frame, this may take a while...
[task 2023-12-04T20:12:56.082Z] 20:12:56     INFO - GECKO(1661) | #01: std::__1::__introsort<std::__1::_ClassicAlgPolicy, nsTArray_Impl<mozilla::a11y::AccTreeMutationEvent*, nsTArrayInfallibleAllocator>::Sort<mozilla::a11y::NotificationController::ProcessMutationEvents()::AccIdxComparator>(mozilla::a11y::NotificationController::ProcessMutationEvents()::AccIdxComparator const&)::{lambda(auto:1 const, auto:2 const)#1}&, mozilla::ArrayIterator<mozilla::a11y::AccTreeMutationEvent*&, nsTArray_Impl<mozilla::a11y::AccTreeMutationEvent*, nsTArrayInfallibleAllocator> > >(mozilla::ArrayIterator<mozilla::a11y::AccTreeMutationEvent*&, nsTArray_Impl<mozilla::a11y::AccTreeMutationEvent*, nsTArrayInfallibleAllocator> >, mozilla::ArrayIterator<mozilla::a11y::AccTreeMutationEvent*&, nsTArray_Impl<mozilla::a11y::AccTreeMutationEvent*, nsTArrayInfallibleAllocator> >, nsTArray_Impl<mozilla::a11y::AccTreeMutationEvent*, nsTArrayInfallibleAllocator>::Sort<mozilla::a11y::NotificationController::ProcessMutationEvents()::AccIdxComparator>(mozilla::a11y::NotificationController::ProcessMutationEvents()::AccIdxComparator const&)::{lambda(auto:1 const, auto:2 const)#1}&, std::__1::iterator_traits<mozilla::ArrayIterator<mozilla::a11y::AccTreeMutationEvent*&, nsTArray_Impl<mozilla::a11y::AccTreeMutationEvent*, nsTArrayInfallibleAllocator> > >::difference_type) [/builds/worker/fetches/MacOSX14.0.sdk/usr/include/c++/v1/__algorithm/sort.h:561]
[task 2023-12-04T20:12:56.083Z] 20:12:56     INFO - GECKO(1661) | #02: mozilla::a11y::NotificationController::ProcessMutationEvents() [accessible/base/NotificationController.cpp:538]
[task 2023-12-04T20:12:56.083Z] 20:12:56     INFO - GECKO(1661) | #03: mozilla::a11y::NotificationController::WillRefresh(mozilla::TimeStamp) [accessible/base/NotificationController.cpp:989]
[task 2023-12-04T20:12:56.083Z] 20:12:56     INFO - GECKO(1661) | #04: nsRefreshDriver::TickObserverArray(unsigned int, mozilla::TimeStamp) [layout/base/nsRefreshDriver.cpp:0]
[task 2023-12-04T20:12:56.084Z] 20:12:56     INFO - GECKO(1661) | #05: nsRefreshDriver::Tick(mozilla::layers::BaseTransactionId<mozilla::VsyncIdType>, mozilla::TimeStamp, nsRefreshDriver::IsExtraTick) [layout/base/nsRefreshDriver.cpp:2734]
[task 2023-12-04T20:12:56.084Z] 20:12:56     INFO - GECKO(1661) | #06: mozilla::detail::RunnableFunction<nsRefreshDriver::EnsureTimerStarted(nsRefreshDriver::EnsureTimerStartedFlags)::$_1>::Run() [xpcom/threads/nsThreadUtils.h:549]
[task 2023-12-04T20:12:56.085Z] 20:12:56     INFO - GECKO(1661) | #07: mozilla::RunnableTask::Run() [xpcom/threads/TaskController.cpp:550]
[task 2023-12-04T20:12:56.085Z] 20:12:56     INFO - GECKO(1661) | #08: mozilla::TaskController::DoExecuteNextTaskOnlyMainThreadInternal(mozilla::detail::BaseAutoLock<mozilla::Mutex&> const&) [xpcom/threads/TaskController.cpp:0]
[task 2023-12-04T20:12:56.086Z] 20:12:56     INFO - GECKO(1661) | #09: mozilla::TaskController::ExecuteNextTaskOnlyMainThreadInternal(mozilla::detail::BaseAutoLock<mozilla::Mutex&> const&) [xpcom/threads/TaskController.cpp:0]
[task 2023-12-04T20:12:56.086Z] 20:12:56     INFO - GECKO(1661) | #10: mozilla::TaskController::ProcessPendingMTTask(bool) [xpcom/threads/TaskController.cpp:485]
[task 2023-12-04T20:12:56.086Z] 20:12:56     INFO - GECKO(1661) | #11: mozilla::detail::RunnableFunction<mozilla::TaskController::TaskController()::$_0>::Run() [xpcom/threads/nsThreadUtils.h:549]
[task 2023-12-04T20:12:56.087Z] 20:12:56     INFO - GECKO(1661) | #12: nsThread::ProcessNextEvent(bool, bool*) [xpcom/threads/nsThread.cpp:1202]
[task 2023-12-04T20:12:56.087Z] 20:12:56     INFO - GECKO(1661) | #13: NS_ProcessPendingEvents(nsIThread*, unsigned int) [xpcom/threads/nsThreadUtils.cpp:445]
[task 2023-12-04T20:12:56.087Z] 20:12:56     INFO - GECKO(1661) | #14: nsBaseAppShell::NativeEventCallback() [widget/nsBaseAppShell.cpp:88]
[task 2023-12-04T20:12:56.088Z] 20:12:56     INFO - GECKO(1661) | #15: nsAppShell::ProcessGeckoEvents(void*) [widget/cocoa/nsAppShell.mm:542]
[task 2023-12-04T20:12:56.123Z] 20:12:56     INFO - GECKO(1661) | #16: __CFRUNLOOP_IS_CALLING_OUT_TO_A_SOURCE0_PERFORM_FUNCTION__ [/System/Library/Frameworks/CoreFoundation.framework/Versions/A/CoreFoundation + 0x83d52]
[task 2023-12-04T20:12:56.124Z] 20:12:56     INFO - GECKO(1661) | #17: __CFRunLoopDoSource0 [/System/Library/Frameworks/CoreFoundation.framework/Versions/A/CoreFoundation + 0x83cf1]
[task 2023-12-04T20:12:56.124Z] 20:12:56     INFO - GECKO(1661) | #18: __CFRunLoopDoSources0 [/System/Library/Frameworks/CoreFoundation.framework/Versions/A/CoreFoundation + 0x83b0b]
[task 2023-12-04T20:12:56.125Z] 20:12:56     INFO - GECKO(1661) | #19: __CFRunLoopRun [/System/Library/Frameworks/CoreFoundation.framework/Versions/A/CoreFoundation + 0x8283a]
[task 2023-12-04T20:12:56.125Z] 20:12:56     INFO - GECKO(1661) | #20: CFRunLoopRunSpecific [/System/Library/Frameworks/CoreFoundation.framework/Versions/A/CoreFoundation + 0x81e3e]
[task 2023-12-04T20:12:56.139Z] 20:12:56     INFO - GECKO(1661) | #21: RunCurrentEventLoopInMode [/System/Library/Frameworks/Carbon.framework/Versions/A/Frameworks/HIToolbox.framework/Versions/A/HIToolbox + 0x2fabd]
[task 2023-12-04T20:12:56.140Z] 20:12:56     INFO - GECKO(1661) | #22: ReceiveNextEventCommon [/System/Library/Frameworks/Carbon.framework/Versions/A/Frameworks/HIToolbox.framework/Versions/A/HIToolbox + 0x2f7d5]
[task 2023-12-04T20:12:56.140Z] 20:12:56     INFO - GECKO(1661) | #23: _BlockUntilNextEventMatchingListInModeWithFilter [/System/Library/Frameworks/Carbon.framework/Versions/A/Frameworks/HIToolbox.framework/Versions/A/HIToolbox + 0x2f579]
[task 2023-12-04T20:12:56.217Z] 20:12:56     INFO - GECKO(1661) | #24: _DPSNextEvent [/System/Library/Frameworks/AppKit.framework/Versions/C/AppKit + 0x41039]
[task 2023-12-04T20:12:56.218Z] 20:12:56     INFO - GECKO(1661) | #25: -[NSApplication(NSEvent) _nextEventMatchingEventMask:untilDate:inMode:dequeue:] [/System/Library/Frameworks/AppKit.framework/Versions/C/AppKit + 0x3f880]
[task 2023-12-04T20:12:56.218Z] 20:12:56     INFO - GECKO(1661) | #26: -[GeckoNSApplication nextEventMatchingMask:untilDate:inMode:dequeue:] [widget/cocoa/nsAppShell.mm:196]
[task 2023-12-04T20:12:56.219Z] 20:12:56     INFO - GECKO(1661) | #27: -[NSApplication run] [/System/Library/Frameworks/AppKit.framework/Versions/C/AppKit + 0x3158e]
[task 2023-12-04T20:12:56.219Z] 20:12:56     INFO - GECKO(1661) | #28: -[GeckoNSApplication run] [widget/cocoa/nsAppShell.mm:0]
[task 2023-12-04T20:12:56.219Z] 20:12:56     INFO - GECKO(1661) | #29: nsAppShell::Run() [widget/cocoa/nsAppShell.mm:0]
[task 2023-12-04T20:12:56.220Z] 20:12:56     INFO - GECKO(1661) | #30: nsAppStartup::Run() [toolkit/components/startup/nsAppStartup.cpp:297]
[task 2023-12-04T20:12:56.220Z] 20:12:56     INFO - GECKO(1661) | #31: XREMain::XRE_mainRun() [toolkit/xre/nsAppRunner.cpp:5680]
[task 2023-12-04T20:12:56.220Z] 20:12:56     INFO - GECKO(1661) | #32: XREMain::XRE_main(int, char**, mozilla::BootstrapConfig const&) [toolkit/xre/nsAppRunner.cpp:5889]
[task 2023-12-04T20:12:56.221Z] 20:12:56     INFO - GECKO(1661) | #33: XRE_main(int, char**, mozilla::BootstrapConfig const&) [toolkit/xre/nsAppRunner.cpp:5945]
[task 2023-12-04T20:12:56.221Z] 20:12:56     INFO - GECKO(1661) | #34: main [browser/app/nsBrowserApp.cpp:445]
[task 2023-12-04T20:12:56.222Z] 20:12:56     INFO - GECKO(1661) | [Utility 1662, IPC I/O Child] WARNING: [F7FEC8A9D1E078AE.D0140879CBF6B7B5]: Ignoring message 'EVENT_MESSAGE' to peer 1.1 due to a missing broker: file /builds/worker/checkouts/gecko/ipc/glue/NodeController.cpp:352
[task 2023-12-04T20:12:56.222Z] 20:12:56     INFO - GECKO(1661) | [Utility 1662, IPC I/O Child] WARNING: [F7FEC8A9D1E078AE.D0140879CBF6B7B5]: Ignoring message 'EVENT_MESSAGE' to peer 1.1 due to a missing broker: file /builds/worker/checkouts/gecko/ipc/glue/NodeController.cpp:352
[task 2023-12-04T20:12:56.223Z] 20:12:56     INFO - GECKO(1661) | [Utility 1662, IPC I/O Child] WARNING: [F7FEC8A9D1E078AE.D0140879CBF6B7B5]: Ignoring message 'EVENT_MESSAGE' to peer 1.1 due to a missing broker: file /builds/worker/checkouts/gecko/ipc/glue/NodeController.cpp:352
[task 2023-12-04T20:12:56.223Z] 20:12:56     INFO - GECKO(1661) | [Utility 1662, Main Thread] WARNING: Shutting down Utility process early due to a crash!: file /builds/worker/checkouts/gecko/ipc/glue/UtilityProcessChild.cpp:350
[task 2023-12-04T20:12:56.224Z] 20:12:56     INFO - TEST-INFO | Main app process: exit 1
[task 2023-12-04T20:12:56.224Z] 20:12:56     INFO - Buffered messages logged at 20:12:30
[task 2023-12-04T20:12:56.224Z] 20:12:56     INFO - must wait for load
[task 2023-12-04T20:12:56.225Z] 20:12:56     INFO - Buffered messages logged at 20:12:31
[task 2023-12-04T20:12:56.225Z] 20:12:56     INFO - TEST-PASS | accessible/tests/mochitest/hypertext/test_update.html | Wrong text before child removal 

Comment 31

[Jens Stutte [:jstutte]]

Attachment: Bug 1839051 - Make AccIdxComparator resilient against calls with a==b. r?Jamie

std::sort used by nsTARray::Sort expects the comparator to be tolerant
for being called to compare the very same element with itself.

Depends on D182731

Comment 32

[Jens Stutte [:jstutte]]

Clearing ni?, see the patch from comment 31.

Comment 33

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/89e544af9515
Use std::sort for nsTArray and deprecate NS_QuickSort. r=emilio,nika,janv,dom-storage-reviewers
https://hg.mozilla.org/integration/autoland/rev/960c75f2fa84
Use std::sort in InitPropertyInfos. r=emilio
https://hg.mozilla.org/integration/autoland/rev/26e7d1c0c9bd
Use nsTArray::Sort in the nsXULSortService. r=xpcom-reviewers,emilio
https://hg.mozilla.org/integration/autoland/rev/25783c0a55fb
Use nsTArray::Sort for Sort and have also StableSort in nsCOMArray. r=necko-reviewers,kershaw,emilio,places-reviewers,mak
https://hg.mozilla.org/integration/autoland/rev/3d5c67636039
Use nsTArray::StableSort in the txNodeSorter. r=peterv,emilio
https://hg.mozilla.org/integration/autoland/rev/b1ceb98da7f0
Use nsTArray::Sort in the SpanningCellSorter. r=xpcom-reviewers,emilio
https://hg.mozilla.org/integration/autoland/rev/f0156aab73a0
Use nsTArray::Sort in KeyboardLayout. r=xpcom-reviewers,emilio,win-reviewers,rkraesig
https://hg.mozilla.org/integration/autoland/rev/cafb666850da
Remove include nsQuickSort.h from some more files. r=emilio
https://hg.mozilla.org/integration/autoland/rev/e84648aa607a
Make AccIdxComparator resilient against calls with r=Jamie=b.

Comment 34

[Norisz Fay [:noriszfay]]

https://hg.mozilla.org/mozilla-central/rev/89e544af9515
https://hg.mozilla.org/mozilla-central/rev/960c75f2fa84
https://hg.mozilla.org/mozilla-central/rev/26e7d1c0c9bd
https://hg.mozilla.org/mozilla-central/rev/25783c0a55fb
https://hg.mozilla.org/mozilla-central/rev/3d5c67636039
https://hg.mozilla.org/mozilla-central/rev/b1ceb98da7f0
https://hg.mozilla.org/mozilla-central/rev/f0156aab73a0
https://hg.mozilla.org/mozilla-central/rev/cafb666850da
https://hg.mozilla.org/mozilla-central/rev/e84648aa607a

Comment 35

[Emilio Cobos Álvarez (:emilio)]

Nice, thanks for landing this Jens!