Trivially-Identical-Sample: Measuring the Performance Improvements from SE-0494

Community Showcase
1

Trivially-Identical-Sample: Measuring the Performance Improvements from SE-0494

SE-0494 was the first evolution proposal I coauthored. This is now landed in the 6.4 toolchain and is available from the new Xcode 27 Beta to begin testing in your own products.

The Evolution Proposal added a new set of “performance hook” APIs to the Swift Standard Library. The isTriviallyIdentical(to:) methods are alternatives to testing collections for value equality. The proposal itself presents some abstract and theoretical arguments for why the isTriviallyIdentical(to:) operation could save performance compared to a traditional == check for value equality. But one of the questions I get asked is how these changes could affect real-world performance. Where's the data? And that's fair. The evolution proposal does not directly present measurements or benchmarks.

The Trivially-Identical-Sample repo is a fork of the sample-food-truck repo from Apple. It's a SwiftUI project that displays many data model elements in a Table view component. With a little refactoring we can set up an experiment. Our view component needs to sort a list of data models: this is an O(n log n) operation. We could potentially display this view component many times even when our data models have not changed: we can trade memory for speed and memoize our sorted values. If the input to our sorted values has not changed… then the sorted values themselves have not changed.

But now we get to look at the memoization itself. How exactly do we determine “what changed”? Do we compare our inputs for value equality? That's an O(n) operation that might be performing more work than necessary. If all we care about is “something might have changed” we can try migrating to isTriviallyIdentical(to:) and return in constant time.

The repo fork shows how to set this experiment up with Xcode Instruments Signposts. We measure our test group and our control group for the aggregate time spent blocking our MainActor and we see about 13 percent faster performance from isTriviallyIdentical(to:).

But… there's more to the story. The repo also spends some time discussing under what situations a different experiment could show us that isTriviallyIdentical(to:) leads to slower performance. At the end of the day the isTriviallyIdentical(to:) methods are not always “fast buttons”. Sometimes they are… but sometimes they are not. Eventually it would be your responsibility to make that choice for yourself and your products.

Please let me know if you have any more questions about all this. Thanks!

7 Likes
2

This is the question I keep running into trying to apply SE-0494 outside a sample, so I will
add a production data point since you mentioned that is the thing people ask for.

We have a SwiftUI list whose contents are derived state - sorted and filtered - over a
collection that a store writes to continuously. Consumer app, half a million or so users, so
the list is on screen constantly while new elements arrive behind it. Structurally it is your
food truck Table, except nobody ever stops adding orders.

The part I cannot get comfortable with is not the performance, it is knowing whether the
memo is working at all. Since isTriviallyIdentical(to:) returning false makes no promise
about equality, a memo whose input is rebuilt upstream every update returns false every
time, recomputes every time, and looks completely healthy. There is no error and no warning.
It is indistinguishable from the case where it is doing its job.

Signposts around update() give duration, which answers a different question. On a small
collection the sort is fast enough that a hit and a miss are within noise of each other, so
the number I actually want is buried in the number I can measure. What I have ended up doing
instead is incrementing two counters at the identity check itself, one per branch, and
reading the ratio - a memo that is genuinely memoising has a hit rate, and one that is
silently missing reads zero. It is trivial code, but it is the only thing that told me the
truth. Would a debug-only counter of that kind be worth adding to the sample? It seems more
useful to a product engineer evaluating this than the aggregate timing is, because it
answers "is this doing anything" before you get to "is this faster".

On the batching idea Rick suggested offline - slicing the collection so older slices keep
their identity and only the newest one changes - I would be interested in whether anyone has
made that hold in the general case. It works for us when the derived state is sorted by
arrival order, because then the old slices really are stable and merging pre-sorted slices is
cheap. But as soon as there is a search filter, or the sort key is anything other than
arrival, a single new element can reorder across a slice boundary and every slice downstream
of it is dirty again. So the requirement seems to be that the derived state composes per
batch, not merely that the input is sliced per batch, which is a stronger condition than it
first looks.

Which leaves the question I think is the real one: identity preservation is a property of the
upstream you often do not own. Whether the same buffer comes back out of a store, a
repository layer or a framework's fetch is an implementation detail nobody documents, and
SE-0494 makes that detail load-bearing. Has anyone worked out a reliable way to establish
which upstreams preserve identity, short of instrumenting it and watching?

1 Like
3

Hmm… good questions! I'm not sure I have one right answer to all these problems but I can try and help brainstorm some suggestions for more discussion:

  • One of the first use cases documented in the proposal and what was probably emphasized most during the review was using isTriviallyIdentical(to:) as a memoization guard for an operation that is linear. The example from the proposal was filtering: if we know that filtering is O(n) and we know that value-equality is also O(n) then isTriviallyIdentical(to:) running in O(1) is a compelling alternative to test our inputs for memoization. Sorting is linearithmic: O(n log n). In general isTriviallyIdentical(to:) is not always a compelling alternative: we would probably want to pay the cost of O(n) value equality if it means we can skip a O(n log n) sort.
  • The Trivially-Identical-Sample measures performance improvements when isTriviallyIdentical(to:) is used to memoize input before sorting. But that is also dependent on some knowledge about the infra that an engineer might not always have: We know that our repository Store does preserve a consistent identity as much as possible.
  • If a product engineer does not have a lot of knowledge about their upstream data and whether or not it does or does not preserve a consistent identity by default then my general advice would be that isTriviallyIdentical(to:) makes a lot of sense in a memoization algorithm when computing your output is linear time. If computing your output is greater than linear time and you do not know your upstream data source preserves identity by default you might not want isTriviallyIdentical(to:): you would generally prefer to pay the price of value equality.
  • Composing filtering and sorting is composing a linear time operation with a linearithmic time operation. If the user has specified a valid search query you can choose isTriviallyIdentical(to:) on your input values before the filter operation. If the user has not specified a valid search query you can choose == on your input values before the sort operation. You kind of have the best of both worlds here: The O(1) memoization check to reduce the amount of O(n) operations and a O(n) memoization check to reduce the amount of O(n log n) operations.
  • You see there a lot of "probablys" and "general advices" and "might nots". The real answer is: it all depends. Measuring your changes against data at real-world scale before and after would be very important before making this change in production.

Hope this helps! Please let me know if you have any more questions I can help brainstorm some more ideas. Thanks!

1 Like
4

Which leaves the question I think is the real one: identity preservation is a property of the
upstream you often do not own.

What is this upstream in your case? Ask the owners to have identity preserved? :slight_smile:

Something tangentially related often bothers me. Suppose you have an array of one million integers and a single element changes. With willSet/didSet, ObservableObject, or Observable, you are told only that the array changed; the information about exactly which element changed, and what its old and new values were, is lost.

As a result, downstream code must either recover that information by diffing the arrays or rebuild the entire derived representation from scratch. Both approaches are O(n), even though the update could theoretically have been handled in O(1) time if the mutation information had been somehow preserved.

1 Like
5

It's not O(1)… but collections built from CHAMP structural sharing like HashTreeCollections can get you "what changed" in O(log n).

6

The upstream is ours, which makes the answer slightly embarrassing: "ask the owners" means asking ourselves. And it still does not help as much as it should, which I think is the actually interesting bit.

Identity preservation is not expressed anywhere. It is not in the type, not in the signature, not in a doc comment. It is an accident of how someone wrote a function, and it holds until a colleague makes a perfectly reasonable refactor - maps over a collection to normalise one field, say - and quietly returns a new buffer every time. Nothing fails. The tests pass. The memo just silently stops memoising, and as I said above there is no observable difference between that and it working. Owning the code means I can go and read it; it does not mean I get told when it changes.

So the answer I have landed on is that this belongs in a test rather than in a conversation. Since isTriviallyIdentical(to:) returning true is a real guarantee, you can assert on it: fetch from the store twice with nothing mutated in between and assert identity holds. It is three lines, it is deterministic, and it converts an invisible performance property into a red test on the day someone breaks it. That is the thing I was reaching for with the hit/miss counters and never quite got to - the counters tell you the memo is dead once it is in production, whereas the test tells you at the point somebody kills it.

Rick, the linear versus linearithmic framing is the part I am taking away, and I had been thinking about it wrong. I had been asking "which check is cheaper", which is the wrong question, because the check is not the cost - the recompute is. The way I would now say it is that the confidence you need in your upstream should scale with how expensive a false negative is. For an O(n) filter, a miss costs you the filter, so a cheap O(1) guess that is sometimes wrong is a good deal. For an O(n log n) sort, a miss costs meaningfully more, so paying O(n) to be certain is worth it unless you actually know the upstream holds identity - and per the above, "know" should mean there is a test, not that you read the code once.

tera, I think your point is the same problem one floor up. Observation tells you the array changed but not which element; isTriviallyIdentical(to:) returning false tells you something might have changed but not what. Both are conservative signals, and in both cases you rebuild the derived state not because you know you need to but because you cannot prove you do not. Which is why the CHAMP answer is interesting beyond performance: a structure that can tell you what changed turns a "might" into a "did", and the memoisation question mostly evaporates.

1 Like
7

Yes. I think this sounds like a good general best practice to start from.