RandomAccessCollection Performance Problems when List is paired with NavigationStack

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):

• OrderedDictionary.Values performs poorly when List is paired with NavigationStack.
• OrderedDictionary.Values performs well when List is paired with NavigationView.
• Array performs well when List is paired with NavigationStack or NavigationView.

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.1 iPhone simulator and device. The swift-collections version is 1.0.5

Thanks!