OrderedDictionary.values and OrderedSet Performance Problems when SwiftUI.List is paired with SwiftUI.NavigationStack about swift-collections HOT 6 CLOSED

The OrderedSet equality operator simply calls elementsEqual. It does not test for referential equality as array does. It probably should though. Could this be the cause of the issue?

from swift-collections.

The OrderedSet equality operator simply calls elementsEqual. It does not test for referential equality as array does.

https://github.com/apple/swift-collections/blob/main/Sources/OrderedCollections/OrderedSet/OrderedSet.swift#L287

@ingoem Hmm… the underlying storage of the OrderedSet appears to be a ContiguousArray value type. AFAIK the ContiguousArray is copy-on-write and does hold its own reference pointer that could be used to return early from a "linear" comparison. So we are comparing two "value" types… but those value types might hold a reference type and we might assume those value types are smart enough to exit early if those references are equal… we think?

Maybe it's a good idea… if OrderedSet.elementsEqual is not defined in swift-collections that means we get the default Sequence implementation of elementsEqual which doesn't know we have a copy-on-write backing store? If we implement our own elementsEqual (for OrderedSet) then we can take advantage of that and forward the elementsEqual check to the underlying ContiguousArray value type?

Be that as it may… it's still a little weird that the "modern" SwiftUI.NavigationStack leads to dozens of equality checks just to push and pop a view while the "legacy" SwiftUI.NavigationView seems to work without those checks. I'm not sure there could be anything about the implementation of OrderedSet (or OrderedDictionary) that could be "fooling" SwiftUI… but maybe there is?

from swift-collections.

https://github.com/apple/swift/blob/main/stdlib/public/core/ContiguousArray.swift#L1318-L1321

@ingoem It looks like ContiguousArray can return early from a reference equality check.

https://github.com/apple/swift/blob/main/stdlib/public/core/SequenceAlgorithms.swift#L319-L336

And the default implementation of elementsEqual performs a linear scan.

from swift-collections.

@lorentey Any thoughts about migrating these equality checks to forward through to ContiguousArray?

from swift-collections.

diff --git a/Sources/OrderedCollections/OrderedDictionary/OrderedDictionary+Values.swift b/Sources/OrderedCollections/OrderedDictionary/OrderedDictionary+Values.swift
index 2977363..630aaf5 100644
--- a/Sources/OrderedCollections/OrderedDictionary/OrderedDictionary+Values.swift
+++ b/Sources/OrderedCollections/OrderedDictionary/OrderedDictionary+Values.swift
@@ -387,7 +387,7 @@ extension OrderedDictionary.Values: MutableCollection {
 extension OrderedDictionary.Values: Equatable where Value: Equatable {
   @inlinable
   public static func ==(left: Self, right: Self) -> Bool {
-    left.elementsEqual(right)
+    left._base._values == right._base._values
   }
 }

This diff fixes my perf issues and still passes the swift-collections tests. I'm still seeing 17 equality checks just to push and pop a List… but those checks are at least fast now.

from swift-collections.

#335 was merged and these equality checks are now fast when comparing equal identities… I'm still not clear why SwiftUI would need dozens of equality checks to compare a let constant collection against itself… but I'm not sure there's anything left to do to optimize this from swift-collections for now.

from swift-collections.