@Observable pessimizes arrays

@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?

3 Likes

I didn't test it, but I think moving the repeated appending operations to a method of the class should fix the issue?

That doesn't help. Assuming you mean this:

@Observable
class Model2 {
    var array: [Int] = []

    func append_stuff() {
        for i in 0..<100_000 {
            array.append(i)
        }
    }
}

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] = []
}

How about this:

@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)
  }
}
1 Like

I just read an article about this issue, it’s covered at the end

Basically the fix is create an array of all the items and append that instead of appending each individually.

1 Like

It's not quadratic, it's linear... This is what I am getting for @Observable:

It shows time (in seconds) of adding 100K elements depending upon how many elements are in the array already.

Interestingly I'm getting exactly the same behaviour for ObservableObject + Published.
Ditto for this manual code:

class Model2 {
    static var changeCount = 0
    
    var array: [Int] = [] {
        didSet {
            if array != oldValue { Self.changeCount += 1}
        }
    }
}

or this:

        didSet {
            if array.count != oldValue.count { Self.changeCount += 1}
        }

But not this!

        didSet { Self.changeCount &+= array.count }

or simply:

        didSet { Self.changeCount += 1 }

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.

1 Like
let m = Model()
let m_start = Date()
m.append_stuff()
print ("elapsed time: @Observable Model: \(Date().timeIntervalSince (m_start))")

// elapsed time: no observation Model1 : 0.04841804504394531
// elapsed time: @Observable Model2    : 1.30535089969635
// elapsed time: @Observable Model     : 0.04540097713470459

1 Like

I was talking about appending multiple elements, and you're measuring appending a single element.

So, appending 1 element to an array should be O(1), instead in this case it's O(n)

I've edited my original post to clarify.

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.

4 Likes

Another data point. This "manual" model implementation is "fast":

class Model3 {
    static var changeCount = 0
    var array: [Int] = [] {
        didSet {
            Self.changeCount += 1
        }
    }
}

And this one is "slow":

class Model4 {
    static var changeCount = 0
    private var _array: [Int] = []
    
    var array: [Int] {
        get { _array }
        set {
            _array = newValue
            Self.changeCount += 1
        }
    }
}

The usage in both cases is the above test code:

    ...
    m.array.append(i)
    ...

I attribute it to COW happening in the second case but not first.
The second one is what @Observable is doing or so it seems.


Edit: changing Model4's "set" to "_modify" makes it fast.

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.

Expanding @ObservationTracked I get:

{
    @storageRestrictions(initializes: _array)
    init(initialValue) {
      _array = initialValue
    }

    get {
      access(keyPath: \.array)
      return _array
    }

    set {
      withMutation(keyPath: \.array) {
        _array = newValue
      }
    }
}

Seems like the compiler could figure out that there's no need to copy the array, but I dunno.

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.

1 Like

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:

_modify {
  access(keyPath: \.array)
  withMutation(keyPath: \.array) {
    yield &_array
  }
}

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.

withObservationTracking notifies after the value has changed, right? Does that mean SwiftUI uses private API for more information?

There's no fact of the matter here I suppose, but is having lots of elements in an array really a boutique use case?

withObservationTracking notifies the change before the value is changed per the requirement of SwiftUI's model.

No, but doing it VERY rapidly is kinda strange for a model as such.

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?