Closed Bug 1841591 Opened 2 years ago Closed 1 year ago

Investigate where nsTArray<>::Sort is used in necko

Categories

(Core :: Networking, task, P2)

Product:
Core
Component:
Networking
Type:
task

Tracking

()

Status:
RESOLVED FIXED

People

(Reporter: kershaw, Unassigned)

References

Details

(Whiteboard: [necko-triaged][necko-priority-next])

(In reply to Kershaw Chang [:kershaw] from comment #0)

nsTArray<>::Sort is implemented by calling NS_QuickSort, where the order of values is preserved.

Not sure if this is true. Quick sort in its normal form is unstable and I would not expect it to preserve the order of values that are considered to be the same in terms of the sorting condition. I do not know if NS_QuickSort does anything more than normal quick sort here, but I would not expect it.

As bug 1839051, we are working on replacing NS_QuickSort with std::sort (the order is not preserved), so we need to look at where nsTArray<>::Sort in necko and see if we can use std::sort safely.

Currently, the usage of nsTArray<>::Sort in necko are:

There are more places. Those are just the places that seemed potentially sensible to the stability of the sorting from a quick look.

Please note also that for an already sorted array nsTArray<>::InsertElementSorted can be used instead of nsTArray<>::StableSort, both preserve a stable order of equal elements but the first is faster.

Whiteboard: [necko-triaged][necko-priority-review] → [necko-triaged][necko-priority-next]

A complete list of usage is here:

nsTArray<T*> - fine as is.
483	cookieList.Sort(CompareCookiesForSending()); // found in mozilla::net::CookieService::GetCookieStringFromDocument
1106	aCookieList.Sort(CompareCookiesForSending()); // found in mozilla::net::CookieService::GetCookiesForURI
1600	gwNeighbors.Sort(NeighborComparator()); // found in mozilla::net::NetlinkService::CalculateIDForFamily

nsTArray<RefPtr<T>> -> StandardSortRefPtrArray
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
501	mExpirationArray.Sort(ExpirationComparator()); // found in mozilla::net::SSLTokensCache::EvictIfNecessary
1419	mExpirationArray.Sort(ExpirationComparator()); // found in mozilla::net::CacheStorageService::MemoryPool::PurgeExpired
1457	mFrecencyArray.Sort(FrecencyComparator()); // found in mozilla::net::CacheStorageService::MemoryPool::PurgeByFrecency

Other probably trivially copy assignable - fine as is
556	removedIterList.Sort(CompareCookiesByIndex()); // found in mozilla::net::CookieStorage::AddCookie
762	purgeList.Sort(CompareCookiesByAge()); // found in mozilla::net::CookieStorage::PurgeCookiesWithCallbacks
778	purgeList.Sort(CompareCookiesByIndex()); // found in mozilla::net::CookieStorage::PurgeCookiesWithCallbacks
81	aBlocklist.Sort(BlocklistEntryComparator()); // found in mozilla::net::InitializeBlocklist

Other TBD - probably not fine
224	alpnList.Sort(AlpnComparator()); // found in mozilla::net::SVCB::GetAllAlpn
1641	linkNamesToHash.Sort(LinknameComparator()); // found in mozilla::net::NetlinkService::CalculateIDForFamily

The nsTArray<RefPtr<T>> ones will be handled by bug 1842130. The rest needs a closer look.

No longer blocks: 1839051
Depends on: 1839051

We ended up to have no need for any special handling of nsTArray<RefPtr<T>>. This means all existing comparators that worked with the NS_QuickSort implementation of nsTArray should also work with the std::sort based one out of the box as expected.

There is one exception to this: std::sort can call the comparator with left and right referencing the very same element (I assume they can optimize away an if this way when looping), which is something the old NS_QuickSort did never do and might lead to problems if the comparator is not prepared for it or even explicitly asserts that the two elements are different instances. But those problems did already fall out when landing bug 1839051.

So I do not think there is too much left to do for this bug, once bug 1839051 sticks for a while without specific regressions in necko.

Flags: needinfo?(kershaw)

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

We ended up to have no need for any special handling of nsTArray<RefPtr<T>>. This means all existing comparators that worked with the NS_QuickSort implementation of nsTArray should also work with the std::sort based one out of the box as expected.

There is one exception to this: std::sort can call the comparator with left and right referencing the very same element (I assume they can optimize away an if this way when looping), which is something the old NS_QuickSort did never do and might lead to problems if the comparator is not prepared for it or even explicitly asserts that the two elements are different instances. But those problems did already fall out when landing bug 1839051.

So I do not think there is too much left to do for this bug, once bug 1839051 sticks for a while without specific regressions in necko.

Thanks! That's good to know.
Looks like bug 1839051 is stuck for a while, so I'll close this bug.

Status: NEW → RESOLVED
Closed: 1 year ago
Flags: needinfo?(kershaw)
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.