@Observable makes appending multiple elements into an array quadratic time complexity (so appending a single element is linear, when it should be constant):
import Observation
import Foundation
class Model1 {
var array: [Int] = []
}
@Observable
class Model2 {
var array: [Int] = []
}
let n = 100_000
let m1 = Model1()
let start = Date()
for i in 0..<n {
m1.array.append(i)
}
// Elapsed time 0.03 on my machine
print("elapsed time w/o observation: \(Date().timeIntervalSince(start))")
let m2 = Model2()
let start2 = Date()
for i in 0..<n {
m2.array.append(i)
}
// Elapsed time 0.8 on my machine
print("elapsed time w/@Observable: \(Date().timeIntervalSince(start2))")
Given how the @Observable macro works, how could this be fixed?
Sorry, my mistake. I think the following should work (again, I didn't test it, as my macOS runs 13.6). A general approach is to put all values involved in repeated operations in a wrapping struct. Yes, I agree it's an limitation if it has to be done this way.
extension Array where Element == Int {
mutating func append_stuff() {
for i in 0..<100_000 {
append(i)
}
}
}
@Observable
class Model2 {
var array: [Int] = []
}
@Observable
class Model {
var array: [Int] = []
func append_stuff() {
func _append_stuff(_ a: inout [Int]) {
for i in 0..<100_000 {
a.append(i)
}
}
_append_stuff(&array)
}
}
The crucial difference: is "oldValue" being accessed or not. I guess the reason of the slowdown is this: if you are accessing "oldValue" Swift is providing you with a copy, and this is the time to make this copy is what we see in the timing plot.
I hope this finding could bring us closer to the actual fix.
Sure. I didn't mention this as I thought this is obvious. Of course O(n) is much worse than O(1).
Yes. When comparing O() complexity you need to choose the same number of elements to append / change. Could be 1 element or 100K elements but it must the same number.
Here's my code showing quadratic behavior, if that helps.
@Observable
class Model2 {
var array: [Int] = []
}
let nn = [100_000, 200_000, 300_000, 400_000]
for n in nn {
let m2 = Model2()
let start2 = Date()
for i in 0..<n {
m2.array.append(i)
}
print("append \(n): \(Date().timeIntervalSince(start2))")
}
This is at least part of the solution, yeah. Every time you access m1.array or m2.array directly is treated as an independent mutation, which will undergo a separate exclusivity check and for @Observable properties, send off observation notifications. Passing the property inout and doing the entire update in one inout access will reduce those overheads by accessing the class property only once, thereby undergoing only one exclusivity check and sending out only one observation event. I suspect that the added overhead @ibex10 is still measuring might come from the expanded observation implementation triggering a copy, either because it's using the oldValue in a didSet or is otherwise saving it in its internal implementation.
The real problem is the copying of the array (not presumably constant time things like observation notifications). I was seeing a lot of memcpy when profiling my app.
Luckily the user interaction history wasn't displayed anywhere in the app so I could move it out of the observable.
Yeah, COW happening is consistent with what I was seeing in the profiler.
Perhaps a new didGet (added to Swift, there is no such keyword currently) along with a didSet would do the trick here, given what @Observable needs to do.
The fact that it's implemented using get/set means that the naive code generation will have the get return you a copy to modify, which it will then pass as the parameter to set. But also, the new value isn't committed to the underlying _array property until the modification is complete, doing the assignment inside of a withMutation block. It could be rephrased as a modify coroutine without copying, maybe:
but that would have different behavior from the current implementation, entering withMutation before the caller's mutation of the value begins, and having the withMutation block open for the duration of the access instead of only after it's been completed. @Philippe_Hausler Would that be a valid implementation change?
I am not sure if that would jive with the requirements for interoperation with SwiftUI; it would require testing for sure. The required behavior is that it needs to ensure that the willSet is emitted before any value has changed. Ideally we should also have the didSet edge happen after the value can be retrieved successfully as the new value.
One escape hatch available here is to use the @ObservationIgnored and manually write out where things are accessed and mutated. This can be useful in boutique use cases where the performance is pathological to what models would normally be constrained with.
Actually my app didn't do it very rapidly, that was just the test I wrote to demonstrate the issue. The app, an art app, was appending brush strokes to a history array so I could replay that later. So just appending a few new history events would cause the app to grow sluggish over time.
So if you had an app that showed some large number of things, and you appended a few more, it would get sluggish. Still boutique?
