search

apple / swift-collections

Commonly used data structures for Swift
Apache License 2.0
3.55k stars 270 forks source link

OrderedDictionary.values and OrderedSet Performance Problems when SwiftUI.List is paired with SwiftUI.NavigationStack #334

Closed vanvoorden closed 5 months ago

vanvoorden commented 5 months ago

https://developer.apple.com/forums/thread/741484

Hi! I'm copying this information over from Apple DevForums. My guess here is that there is a potential optimization inside the SwiftUI library itself that can clean up these perf issues… but I'll go ahead and post the details here just in case there is something else inside the OrderedDictionary itself that should be optimized. Thanks!

Information

Checklist

Steps to Reproduce

https://gist.github.com/vanvoorden/1c7c6ed08898de7f4b8619147537c0eb

Hi! Has anyone here seen weird performance problems when passing values from a Collections.OrderedDictionary to a SwiftUI.List inside SwiftUI.NavigationStack? I see some performance problems that go away when switching back to SwiftUI.NavigationView. At this point, I'm not sure if it's a problem in the OrderedDictionary implementation or not. Anyone want to take a look and see if you can help track this down?

For a simple backing store to drive a simple SwiftUI app displaying a List of data, the OrderedDictionary (from swift-collections) has the advantage of giving us the option to access (by an arbitrary key) in constant time. The OrderedDictionary exposes a values property that conforms to RandomAccessCollection. Since we can pass a RandomAccessCollection as data to generate a List, we should hope to be able to pass the OrderedDictionary.values the same way we would pass an Array.

This is leading to some strange performance problems that seem to happen when our List is contained in a NavigationStack (and we push and pop a detail view on the stack). Here is a simple example:

import Collections
import SwiftUI

let NavigationDemoRange = 0...999999

extension Int: Identifiable {
  public var id: Self {
    return self
  }
}

@main struct NavigationDemoApp: App {
  let dictionary = OrderedDictionary(
    uniqueKeys: NavigationDemoRange,
    values: NavigationDemoRange
  )
}

extension NavigationDemoApp {
  var body: some Scene {
    WindowGroup {
      NavigationStack {
        List(
          self.dictionary.values,
          rowContent: { element in
            NavigationLink(
              String(element),
              value: element
            )
          }
        ).navigationDestination(
          for: Int.self,
          destination: { element in
            Text(
              String(element)
            )
          }
        )
      }
    }
  }
}

In this example, we start by defining a NavigationDemoRange that we use to generate 1MM data elements. Our data element is a simple Int, which we mark as Identifiable to make it easier to pass to a List. We then construct a simple OrderedDictionary instance, where every key simply maps to itself (and the values property preserves the intended ordering).

We then create (and present) a NavigationStack that wraps a List that displays every element from our OrderedDictionary.values. We add a simple NavigationLink (and pair with a navigationDestination) to display a "detail view" (which is just a Text element to display the Int).

When we launch this app (on simulator or device), we see a significant hang when tapping an item from the list (pushing a detail view). Popping back appears not to hang, but then pushing another item hangs again.

When we inspect instruments to troubleshoot this hang, we see that our app is spending a lot of time testing our OrderedDictionary.values for equality:

static OrderedDictionary.Values<>.== infix(_:_:)

Adding a breakpoint here and running our app shows that this equality check happens 7 times when the app is launched, 5 times when the detail is pushed, and 5 times when the detail is popped. That is 17 total equality checks to display a list, push a detail, and pop back all driven from data that we defined as immutable (a let constant).

If we try and implement our app on the alternative NavigationLink API (before the introduction of navigationDestination), we see different results. Now, our app launches and we see a significant hang on both pushing and popping a detail view. Instruments confirms we are still spending a lot of the on equality checks. Adding a breakpoint on the check shows us this equality check happens 1 time when the app launches, 24 times when the detail view is pushed, and 12 times when the app is popped. That is 37 total equality checks against data that is (still) an immutable let constant.

We set our NavigationDemoRange to 1MM elements to exaggerate performance problems, but for any amount of data we still see the equality checks occurring the same amount of times.

The OrderedDictionary.values type exposes an elements property that wraps the values with an Array. When we pass OrderedDictionary.values.elements to our List, our performance problems go away:

extension NavigationDemoApp {
  var body: some Scene {
    WindowGroup {
      NavigationStack {
        List(
          self.dictionary.values.elements,
          rowContent: { element in
            NavigationLink(
              String(element)
            ) {
              Text(
                String(element)
              )
            }
          }
        )
      }
    }
  }
}

FWIW, we see the exact same performance problems (number of equality checks) when passing in Collections.OrderedSet (and the problems go away when we pass the OrderedSet.elements property).

That was NavigationStack. What happens if we try this same test with NavigationView?

extension NavigationDemoApp {
  var body: some Scene {
    WindowGroup {
      NavigationView {
        List(
          self.dictionary.values,
          rowContent: { element in
            NavigationLink(
              String(element)
            ) {
              Text(
                String(element)
              )
            }
          }
        )
      }
    }
  }
}

This looks much faster with no noticeable performance problems. Setting a breakpoint confirms that equality is checked once on app launch. Pushing and popping perform no equality checks.

Here is what we know (so far):

What could be causing these performance problems? It's not clear. Most of the sample code from Apple passes an Array when constructing a List, but the List constructor just takes an arbitrary RandomAccessCollection without telling us there are performance implications from rolling our own RandomAccessCollection outside the system Swift types.

Is there some kind of bug in the implementation of OrderedDictionary.Values (and OrderedSet) that would lead to this performance problem? If that was true, why would that performance problem only seem to show up in NavigationStack (and not NavigationView)?

If it's not safe to pass arbitrary RandomAccessCollection types to List, should we always wrap any collection in an Array before constructing a List?

Any more thoughts about this? Any ideas where the performance problem could be caused from?

These have all been tested on 17.0 iPhone simulator and device. The swift-collections version is 1.0.5

Thanks!

Expected behavior

Actual behavior

ingoem commented 5 months ago

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?

vanvoorden commented 5 months ago

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?

vanvoorden commented 5 months ago

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.

vanvoorden commented 5 months ago

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

vanvoorden commented 5 months ago 
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.

vanvoorden commented 5 months ago

https://github.com/apple/swift-collections/pull/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.