Potential for stack overflow with large app states

[mluisbrown]

It seems that there is a potential with TCA to run into a stack overflow if the AppState / RootState becomes large enough.

In the project I'm working on we are using the ReactiveSwift fork of TCA and we had one sub state of the App State that was huge, around 8KB. With reactive frameworks and uni-directional data flow frameworks like TCA, ReSwift etc it's common to have quite a lot of stack frames.

The stack size on iOS is 1MB, so with a large enough app state, it's not that difficult to get into a stack overflow situation. In our case our app was only crashing on device, not in the simulator. That is because on macOS (simulator) the stack size is much larger: 8MB.

I posted about this on the Swift Forums too: https://forums.swift.org/t/possible-compiler-bug-related-to-deeply-nested-enums/47241

Our solution was to use a copy on write wrapper for the larger properties of the problematic states so that they are stored I the heap and not on the stack.

I'm just throwing this out there as it could be a problem that other people will face. Certainly with ReactiveSwift you can get a pretty big number of stack frames (over 100). I'm no sure if the same is true of Combine.

This issue also affects ReSwift, as can be seen here: https://bugs.swift.org/browse/SR-11093

Curious to know if others have seen this, and what mitigations you might have used.

[stephencelis]

We've hit something like this before in isowords, where we were using a recursive data structure to hold onto the cube state. We modeled the 3-by-3 game cube using Three<Three<Three<CubeState>>>, which looked like this:

struct Three<A> {
  var first: A
  var second: A
  var third: A
}

Just a triply-nested one of these was enough to crash our app, though we're not sure if the issue was stack size.

Our solution was to box these fields in an array: https://github.com/pointfreeco/isowords/blob/f77002115e1344d945345ac17c3e3f4ffe0b753b/Sources/SharedModels/Three.swift#L55

It's a blunt tool to do the job and introduced some potential for runtime crashes if we ever index outside expected bounds, but has worked well enough for us. Would definitely be interested in your wrapper type if that helps. I also wonder if a property wrapper could strategically be used for this kind of thing?

@Heap // Game state is rather large, store it on the heap
var gameState: GameState

[RabugenTom]

I believe this hypothetic @Heap is functionally equivalent to my @CoW property wrapper:

@propertyWrapper
public struct CoW<T> {
  private final class Ref {
    var val: T
    init(_ v: T) { val = v }
  }
  private var ref: Ref

  public init(wrappedValue: T) { ref = Ref(wrappedValue) }
  
  public var wrappedValue: T {
    get { ref.val }
    set {
      if !isKnownUniquelyReferenced(&ref) {
        ref = Ref(newValue)
        return
      }
      ref.val = newValue
    }
  }
}

//Restore automatic protocol conformance:
extension CoW: Equatable where T: Equatable {
  public static func == (lhs: CoW<T>, rhs: CoW<T>) -> Bool {
    lhs.wrappedValue == rhs.wrappedValue
  }
}

extension CoW: Hashable where T: Hashable {
  public func hash(into hasher: inout Hasher) {
    hasher.combine(wrappedValue)
  }
}

extension CoW: Decodable where T: Decodable {
  public init(from decoder: Decoder) throws {
    let container = try decoder.singleValueContainer()
    let value = try container.decode(T.self)
    self = CoW(wrappedValue: value)
  }
}

extension CoW: Encodable where T: Encodable {
  public func encode(to encoder: Encoder) throws {
    var container = encoder.singleValueContainer()
    try container.encode(wrappedValue)
  }
}

This allocates the wrappedValue storage on the heap (via the class Ref<T>) and it uses Copy-on-Write in the setter of the storage if more than one thing is referencing it. If only one reference is known, no copy is performed and the boxed value is directly modified. I guess other implementations will be similar.

[Edit: I cleaned the code and removed a few functions I'm implementing for backward compatibility with my codebase]

[dannyhertz]

Wow, love this! Will take it for a spin.

[dannyhertz]

I too have run into similar cryptic crashes from somewhat large substates. @mluisbrown would you mind sharing the COW strategy you have been using? Aka, how did you decide which structs to use COW and what COW implementation did you use? Using a super simple Box type for some substates (without explicit custom COW) seemed to help us get passed a certain level, but we are still occasionally seeing these crashes as the state grows.

[mluisbrown]

Would definitely be interested in your wrapper type if that helps. I also wonder if a property wrapper could strategically be used for this kind of thing?

would you mind sharing the COW strategy you have been using? Aka, how did you decide which structs to use COW and what COW implementation did you use?

@stephencelis & @dannyhertz:

Our CoW property wrapper for some of the bigger state properties:

private final class Ref<T: Equatable>: Equatable {
    var val: T
    init(_ v: T) {
        self.val = v
    }

    static func == (lhs: Ref<T>, rhs: Ref<T>) -> Bool {
        lhs.val == rhs.val
    }
}

@propertyWrapper
public struct Box<T: Equatable>: Equatable {
    private var ref: Ref<T>

    public init(_ x: T) {
        self.ref = Ref(x)
    }

    public var wrappedValue: T {
        get { ref.val }
        set {
            if !isKnownUniquelyReferenced(&ref) {
                ref = Ref(newValue)
                return
            }
            ref.val = newValue
        }
    }

    public var projectedValue: Box<T> {
        self
    }
}

Most of the implementation came from Apple's own Optimisation tips for Swift.

We then use it like this (one example):

public struct FundingState: Equatable {
    @Box var linkingAccountState: LinkingAccountState?
    @Box var fundingAccountsState: FundingAccountsState?
    @Box var makeDepositState: MakeDepositState?
    @Box var internalTransferState: InternalTransferState?
    @Box var withdrawalState: WithdrawalState?

    public init(
        linkingAccountState: LinkingAccountState? = nil,
        fundingAccountsState: FundingAccountsState? = nil,
        makeDepositState: MakeDepositState? = nil,
        internalTransferState: InternalTransferState? = nil,
        withdrawalState: WithdrawalState? = nil
    ) {
        self._linkingAccountState = .init(linkingAccountState)
        self._fundingAccountsState = .init(fundingAccountsState)
        self._makeDepositState = .init(makeDepositState)
        self._internalTransferState = .init(internalTransferState)
        self._withdrawalState = .init(withdrawalState)
    }
}

The _ prefix allows you to directly access the underlying wrapper type (eg Box<T> in this case). Previously this state was an enum which more correctly models the fact that only one of these sub-states can exist at any one time, but we had to convert it to a struct to be able to use our property wrapper.

We use MemoryLayout to know which parts of our state are the biggest and should be converted to use the CoW wrapper.

Credits to @gtsiap for implementing the above 🙏

[cala4]

@mluisbrown sorry to revive an old topic.

Using your Box property wrapper, what's the advantage of instantiating the Box properties accessing them with _ in the initializer instead of instantiating the directly without using _? Both seem to work just fine or am I missing something?

Basically, what the difference of doing

self._linkingAccountState = .init(linkingAccountState)
instead of
self.linkingAccountState = linkingAccountState

Thanks in advance!

[jagreenwood]

I wanted to mention that the way this showed up in my app was EXC_BAD_ACCESS crashes during certain app flows only on device. Using @Box as noted by @mluisbrown on my larger state types resolved the crash.

[mackoj]

Hi, we did get a similar bug(EXC_BAD_ACCESS) that happen only on device in our app and spent a good amount of time on it with DTS.

What we find is that passing a certain threshold(between 22Kb and 26Kb) of a type size iOS will stack overflow thus EXC_BAD_ACCESS. For us it append the first time CurrentValueSubject.value.modify is called aka the first time we try to access to the AppState. In order to fix this we did reduce the size the of the AppState(by removing state variable that use generics or improve our implementation by reducing as mush as possible indirect enum with generics used in appState) and it fixed it.

func bytesFormater(bytes: Int) -> String {
  let bf = ByteCountFormatter()
  bf.allowedUnits = .useAll
  bf.countStyle = .file
  bf.includesUnit = true
  bf.isAdaptive = true
  return bf.string(fromByteCount: Int64(bytes))
}

print("AppState size: \(bytesFormater(bytes: MemoryLayout.size(ofValue: state)))")

Hope it helps,

[peterkovacs]

Another source of stack overflow is Effect.concatenate with a very large number of effects, even if they're effectively Effect.none.

For example, you might walk through an IdentifiedArray of substates and calculate a cancellation effect for those states that need to be cancelled, and returning a .none otherwise, then bundling up the result with a .concatenate.

Changing to a .merge removes the potential for the overflow.

[ferologics]

FYI https://forums.swift.org/t/willset-causing-copy-on-write-types-to-copy-on-mutations/52103