1842130 - Have a special sort variant for nsTArray<RefPtr<T>> that does not affect refcounts and use it

Status: RESOLVED WONTFIX

(Core :: XPCOM, enhancement)

Description

[Jens Stutte [:jstutte]]

The std::sort function uses (sometimes) copy assignments while sorting. In case we have a nsTArray<RefPtr<T>> this can lead to unwanted noise on the pointee's refcount.

Instead of just using HeapSort in these cases (which comes with a performance penalty), we want to have a special variant that takes advantage of knowing that a RefPtr<T> is stored like a T*, such that we can do the sorting pretending to operate on raw pointers.

Furthermore we also want to have the possibility to sort such an array based on the default comparator of T, not just the one from RefPtr<T> (which compares just the pointer values and is also used in some cases).

Comment 1

[Jens Stutte [:jstutte]]

Attachment: Bug 1842130 - Have StandardSortRefPtrArray<pointee_type> for nsTArray. r?#xpcom-reviewers

Depends on D182731

Comment 2

[Jens Stutte [:jstutte]]

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

Depends on D182746

Comment 3

[Jens Stutte [:jstutte]]

Attachment: Bug 1842130 - Use StandardSortRefPtrArray<Animation>. r?#xpcom-reviewers

Depends on D182746

Comment 4

[Jens Stutte [:jstutte]]

Attachment: Bug 1842130 - Use StandardSortRefPtrArray<nsAtom> in AtomSetFromRange. r?#xpcom-reviewers

Depends on D182978

Comment 5

[Jens Stutte [:jstutte]]

Attachment: Bug 1842130 - Use StandardSortRefPtrArray in CollectLRUOriginInfosUntil. r?#dom-storage-reviewers

Depends on D182979

Comment 6

[Jens Stutte [:jstutte]]

Just a note (taken from a chat with Jari):

There might be a potential for a footgun here if the T in nsTArray<RefPtr<T>> HasThreadSafeRefCnt as this might indicate that elements (and thus their comparator result) could change while sorting. Note that at least the refcount should remain always >0 as the array element holds one while sorting.
As nsTArray itself is not thread safe, this is probably true also for the old sort implementation.

With the current state of things we could probably just issue a warning or (static) assert if we want to sort such a T. But all accesses through nsTArray to such T would need to happen under some lock managed elsewhere, anyways, and thus also sorting, IMHO.

Comment 7

[Jens Stutte [:jstutte]]

Our current uses are:

nsTArray<RefPtr<T>> -> StandardSortRefPtrArray
216	aMatches->Sort(AnimationPtrComparator<RefPtr<dom::Animation>>()); // found in mozilla::FindAnimationsForCompositor
616	aAnimations.Sort(AnimationPtrComparator<RefPtr<Animation>>()); // found in mozilla::dom::DocumentOrShadowRoot::GetAnimations
3777	aAnimations.Sort(AnimationPtrComparator<RefPtr<Animation>>()); // found in mozilla::dom::Element::GetAnimationsWithoutFlush
193	clientList.Sort(MatchAllComparator()); // found in mozilla::dom::Clients::MatchAll
155	tracks.Sort(AudioTrackCompare); // found in mozilla::dom::MediaStreamAudioSourceNode::AttachToRightTrack
163	aRetval.Sort(PerformanceEntryComparator()); // found in mozilla::dom::Performance::GetEntries
469	aRetval.Sort(PerformanceEntryComparator()); // found in mozilla::dom::PerformanceMainThread::GetEntries
66	aRetval.Sort(PerformanceEntryComparator()); // found in mozilla::dom::PerformanceObserverEntryList::GetEntries
78	aRetval.Sort(PerformanceEntryComparator()); // found in mozilla::dom::PerformanceObserverEntryList::GetEntriesByType
99	aRetval.Sort(PerformanceEntryComparator()); // found in mozilla::dom::PerformanceObserverEntryList::GetEntriesByName
6589	originInfos.Sort(OriginInfoAccessTimeComparator()); // found in mozilla::dom::quota::QuotaManager::CollectLRUOriginInfosUntil
378	instanceList.Sort(InstanceTimeComparator()); // found in mozilla::SMILTimedElement::UpdateInstanceTime
1534	mAvailableFonts.Sort(FontEntryStandardFaceComparator()); // found in gfxFontFamily::SortAvailableFonts
3437	mRecs.Sort(FrecencyComparator()); // found in mozilla::net::CacheIndex::FrecencyArray::SortIfNeeded
2422	aResult.Sort(CompareCookiesCreationTime()); // found in mozilla::net::CookieService::GetCookiesSince
306	cookiesList->Sort(CompareCookiesForSending()); // found in mozilla::net::CookieServiceChild::GetCookieStringFromDocument
343	accessPoints.Sort([](const RefPtr<nsIWifiAccessPoint>& ia, // found in nsWifiMonitor::DoScan

nsTArray<UniquePtr<T>> -> maybe StandardSortRefPtrArray ?
5316	data->mTimeouts.Sort(comparator); // found in mozilla::dom::WorkerPrivate::RunExpiredTimeouts

Comment 8

[Jens Stutte [:jstutte]]

Attachment: Bug 1842130 - Use StandardSortRefPtrArray<PerformanceEntry> for nsTArray<RefPtr<PerformanceEntry>>, r?#xpcom-reviewers

Depends on D183257

Comment 9

[Jens Stutte [:jstutte]]

Attachment: Bug 1842130 - Use StandardSortRefPtrArray<Client> for nsTArray<RefPtr<Client>>, r?#xpcom-reviewers

Depends on D183467

Comment 10

[Jens Stutte [:jstutte]]

Attachment: Bug 1842130 - Use StandardSortRefPtrArray<AudioStreamTrack> for nsTArray<RefPtr<AudioStreamTrack>>, r?#xpcom-reviewers

Depends on D183468

Comment 11

[Jens Stutte [:jstutte]]

Attachment: Bug 1842130 - Use StandardSortRefPtrArray<SMILInstanceTime> for nsTArray<RefPtr<SMILInstanceTime>>, r?#xpcom-reviewers

Depends on D183469

Comment 12

[Jens Stutte [:jstutte]]

Attachment: Bug 1842130 - Use StandardSortRefPtrArray<gfxFontEntry> for nsTArray<RefPtr<gfxFontEntry>>, r?#xpcom-reviewers

Depends on D183470

Comment 13

[Jens Stutte [:jstutte]]

Attachment: Bug 1842130 - Use StandardSortRefPtrArray<CacheIndexRecordWrapper> for nsTArray<RefPtr<CacheIndexRecordWrapper>>, r?#xpcom-reviewers

Depends on D183471

Comment 14

[Jens Stutte [:jstutte]]

Attachment: Bug 1842130 - Use StandardSortRefPtrArray<nsICookie> for nsTArray<RefPtr<nsICookie>>, r?#xpcom-reviewers

Depends on D183472

Comment 15

[Jens Stutte [:jstutte]]

Attachment: Bug 1842130 - Use StandardSortRefPtrArray<Cookie> for nsTArray<RefPtr<Cookie>>, r?#xpcom-reviewers

Depends on D183473

Comment 16

[Jens Stutte [:jstutte]]

Attachment: Bug 1842130 - Use StandardSortRefPtrArray<nsIWifiAccessPoint> for nsTArray<RefPtr<nsIWifiAccessPoint>> and adjust sort condition. r?#xpcom-reviewers

Depends on D183474

Comment 17

[Jens Stutte [:jstutte]]

Attachment: Bug 1842130 - Use StandardSortRefPtrArray<TimeoutInfo> for nsTArray<UniquePtr<TimeoutInfo>>. r?#xpcom-reviewers

Depends on D183475

Comment 18

[Jens Stutte [:jstutte]]

Attachment: Bug 1842130 - Use StandardSortRefPtrArray<CacheEntry> for nsTArray<RefPtr<CacheEntry>>. r?#xpcom-reviewers

Depends on D183510

Comment 19

[Emilio Cobos Álvarez (:emilio)]

Wdyt of naming this something else? It's not really about RefPtr<> since it also works for UniquePtr or so right? StandardSortSmartPtr?

Comment 20

[Jens Stutte [:jstutte]]

(In reply to Emilio Cobos Álvarez (:emilio) from comment #19)

Wdyt of naming this something else? It's not really about RefPtr<> since it also works for UniquePtr or so right? StandardSortSmartPtr?

Yeah, it started for RefPtr only but then I had to add the other variants. However it will probably not cover nsCOMPtr as we have nsCOMArray, so I wonder if SmartPtr is the right name here.

Comment 21

[Emilio Cobos Álvarez (:emilio)]

ni? to elaborate on how to remove StandardSortRefPtr

Comment 22

[Emilio Cobos Álvarez (:emilio)]

See the incoming patch, which works and should avoid all these.

Comment 23

[Emilio Cobos Álvarez (:emilio)]

Attachment: Bug 1842130 - Remove StandardSortRefPtrArray in favor of making Sort() do the fast thing. r=jstutte

This is on top of D182978, and seems to work.

Comment 24

[Jens Stutte [:jstutte]]

This bug is obsolete thanks to :emilio's template magic we plumbed into the nsTArray::Sort patch. I'll check the remaining patches for comments/details I still want to address elsewhere, but they are obsolete here.