Type checker impact of reducing occurences of highly overloaded functions (==)?

Using Swift
1

Hey all, I have a question about the performance impact of highly overloaded functions; == specifically. Specifically, about the potential impact of reducing the number of overloads in a build using the Swift 6.3 compiler, and whether any optimizations of this nature will remain effective after adopting Swift 6.4.

I think most folks reading this will already know that == is highly overloaded in any Swift codebase. My codebase has over 17,000 in total, on top of the numerous overloads in the Swift Standard Library and Apple libraries like Foundation, SwiftUI, etc. A representative file one of my coworkers checked listed 500 potential candidates to type check the statement _ = (==).

Inevitably, build times have gone up and uses of == have become a target for reducing build times; specifically, the implementations of == for our network models. We've found that switching from a series of lhs.a == rhs.a && lhs.b == rhs.b expressions to a series of individual guards using != can reduce build times, presumably because there are far less != implementations than == in the Swift stdlib, and because the large expressions have been broken down.

These functions take over 200ms to type-check, which might make it worth the cost in writing un-idiomatic Swift, though this is something that I personally would like to avoid. I'd also like to avoid solutions that replace == with some different symbol, like a unicode == doppelganger, though obviously that option is very much on the table.

So, the subject of my question: what if we don't implement "normal" Equatable at all? We'd find and replace all our impls of Equtable with a new protocol that uses a common == implementation:

public protocol MyEquatable: Equatable {
    
    static func isEqual(lhs: Self, rhs: Self) -> Bool
    
}


extension MyEquatable {
    
    public static func ==(lhs: Self, rhs: Self) -> Bool {
        isEqual(
            lhs: lhs,
            rhs: rhs
        )
    }
    
}

That said, we don't have a good enough intuition for the impact of removing == impls to understand the impact of this; even if we reduce the number of == candidates visible in a given file, we might only be halving that number at best with this approach. We might try to benchmark this approach regardless, but I thought I'd ask here to see if anyone has any insights into the algorithmic complexities at work in type checking == uses.

5 Likes
Ways to reduce compilation time incurred by highly overloaded functions (==)?
2

Sorry, to be clear, your codebase has over 17,000 distinct overloads of ==, or 17,000 types that conform to Equatable?

If a type conforms to Equatable, its == function is strongly typed as (Self, Self) -> Bool and, generally speaking, shouldn't participate in overload resolution if neither argument is an instance of Self. Such overloads are pruned from the search space early.

Every type that conforms to Equatable also has a member !=, it's just that the standard library provides a default implementation of !=. So I would expect the search space for == and != to be approximately equal in that regard.

Can you give an example of the types of lhs, lhs.a, lhs.b, etc.? What about the signature of the function where the above expression lives?

If you're seeing the existence of distinct == implementations affect overload resolution time, that's somewhat surprising to me as the number of distinct implementations shouldn't really matter. That would be worth a bug against the Swift compiler.

1 Like
3

Unfortunately that's not right, the time to type check an expression that involves a call to == will take time linear in the number of overloads in the best case, because at the very least the type checker must look at each overload once. Whether the type conforms to Equatable or not doesn't actually matter, and indeed not every overload of == witnesses the Equatable.== requirement. Sometimes the the == overloads are even the first thing the type checker tries in turn before looking at the rest of the expression.

Operator lookup is global in Swift, even if the operator is declared as a member. So type checking a call to != generally takes less time than a call to == (unless you define a ton of custom != overloads for some reason).

@xedin recently experimented with filtering out the overloads of == that correspond to Equatable.== implementations in name lookup, so that they don't generate disjunction choices at all. While the general idea still has merit (and for other operators too, it's not really specific to ==), it's somewhat tricky, for several reasons.

Sometimes, the concrete overloads are actually load-bearing from a performance standpoint, because they allow the type checker to skip the generic overloads in situations where the concrete type is known. For several examples in the type_checker_perf collection, this can actually make the difference between an expression type checking successfully and failing with a "reasonable time" error.

For example, BinaryInteger defines a generic heterogeneous overload of == in a protocol extension with signature <Self: BinaryInteger, Other: BinaryInteger> (Self, Other) -> Bool, which can be used like this:

let x: Int = 0
let y: Int8 = 1

_ = (x == y)

Another slightly problematic situation is that sometimes you find code in the wild like foo == .bar where the only way to resolve .bar is to by consider each overload in turn, because the type of foo isn't known yet when the type checker starts looking at the ==. A related situation is foo == false (or any other literal on the RHS, whose type cannot be considered until the overload choice has been made).

I agree it's a bug, but it's not completely trivial to solve. I think eventually, some (mostly minor, hopefully) source breaks will be needed.

13 Likes
4

To answer @grynspan 's original question, all our examples look like this:

public final class Foo: Equatable {
     var a: String?
     var b: Bar
     var c: Baz
 
     public init(...) { ... }
    
     public static func ==(lhs: Foo, rhs: Foo) -> Bool {
           lhs.a == rhs.a &&
             lhs.b == rhs.b && 
             lhs.c == rhs.c
     }
      
}

Though the examples that take > 200ms generally have more members. I counted as few as 6 fields in the shortest one.

I agree it's a bug, but it's not completely trivial to solve. I think eventually, some (mostly minor, hopefully) source breaks will be needed.

I'm assuming that this would look something like Eq in rust, with an alternate spelling for the static func developers implement to conform to Equatable? That's kind of what I was going for with the MyEquatable example. Or is there some more sophisticated way to do this that lets folks continue to implement a == function without hurting compile times?

1 Like
5

FWIW this also seems to be the approach from the derived conformance:

But I can't tell if that was chosen specifically for the performance reasons you saw.

6

I bumped into this same problem and found a few tricks which could improve the type checking significantly (2…10×) if applied manually or (better?) taken to use by the compiler synthesis.

In my case, several deeply nested (TCA-style) enums with payloads turned out slow to type check. When letting the compiler generate Equatable conformance, the -Xfrontend -debug-time-function-bodies build option reported between 90…100 ms of time spent type checking the generated __derived_enum_equals function.

The compiler synthesis for enums and structs is documented to generate code like follows:

enum SomeEnum<T...> {
  case A, B(Int), C(String, Int)

  @derived
  @_implements(Equatable, ==(_:_:))
  func __derived_enum_equals(a: SomeEnum<T...>,
                             b: SomeEnum<T...>) -> Bool {
    switch (a, b) {
    case (.A, .A):
      return true
    case (.B(let l0), .B(let r0)):
      guard l0 == r0 else { return false }
      return true
    case (.C(let l0, let l1), .C(let r0, let r1)):
      guard l0 == r0 else { return false }
      guard l1 == r1 else { return false }
      return true
    default: return false
  }
}

struct SomeStruct<T...> {
  var x: Int
  var y: String

  @derived
  @_implements(Equatable, ==(_:_:))
  func __derived_struct_equals(a: SomeStruct<T...>,
                               b: SomeStruct<T...>) -> Bool {
    guard a.x == b.x else { return false; }
    guard a.y == b.y else { return false; }
    return true;
  }
}

When I added a manual static func == (lhs: Self, rhs: Self) -> Bool with similar hand-written logic, the build time remained equally high as the compiler-generated version.

But two observations reduced the type checking time significantly:

  1. Firstly, it might be pretty to switch over the inputs as a pair (a, b), handling all possible case pairs for more. But it's actually less work to first case-split the lhs, and then only match the rhs against that particular case.
  2. Using guard case lhs = rhs or guard case .foo(x, y) = rhs (yes, with just one = sign!) seems a clever way to constrain the type checker to only consider the one and only == that we're interested in.

Taking these to the above example snippet would look like this:

extension SomeEnum: Equatable {
  static func == (a: Self, b: Self) -> Bool {
    switch a {
    case .A:
      guard case .A = b else { return false }
    case .B(let l0):
      guard case .B(l0) = b else { return false }
    case .C(let l0, let l1):
      guard case .C(l0, l1) = b else { return false }
    }
    return true
  }
}

extension SomeStruct: Equatable {
  static func == (a: Self, b: Self) -> Bool {
    guard case a.x = b.x, case a.y = b.y else { return false }
    return true
  }
}

Applying the same trick to my original case, reduced the type checking time from 90.53ms (of __derived_enum_equals) to just 5.28ms, an over 17× improvement on my slightly old machine! Even for more ordinary enum definitions, I'm observing a speedup of 2× or more.

(I recorded these timings on an Apple M2 Max using the latest Swift 6.4 compiler from Xcode 27 beta 4, FWIW.)

Now I wonder if these tricks could be adopted by DerivedConformanceEquatableHashable.cpp?

6 Likes
7

One subtlety here, I believe: case .B(l0) = b and case .C(l0, l1) = b are going to exercise the pattern match operator ~=, not directly ==. While it's true that ~= has a default implementation in the standard library in terms of == for types that are Equatable, someone could provide their own ~= overload and change the behavior of that synthesized implementation to something other than what a synthesized implementation written with direct references to == would produce.

I wonder if some of the speedup you're seeing is actually due to that change. It makes sense that you'd see faster type-checking performance by removing concrete uses of == from the AST, replacing them with a ~= that has far fewer overloads and is in this case generic; it pushes the complexity to runtime resolution of the conformance instead. Do you see similar results if you change that to the following?

    case .B(let l0):
      guard case .B(let r0) = b, l0 == r0 else { return false }
    case .C(let l0, let l1):
      guard case .C(let r0, let r1) = b, l0 == r0, l1 == r1 else { return false }
3 Likes
8

Also FWIW if you are checking the performance of __derived_enum_equals in debug mode I think there are still some known performance bottlenecks:

1 Like
9

Yes, it seems the speedup is mostly due to that change. If I took your suggestion and went back to comparing the payloads with ==, the type checking time is back in the original ballpark of __derived_enum_equals.

If only there was a way to disambiguate the == which I wanted to call… :thinking: But there is a way! I can introduce a little generic helper function:

@inline(always)
private func eq<T: Equatable>(_ a: T, _ b: T) -> Bool { a == b }

…and replace the == checks with calls to My::eq (My module disambiguated just in case), like so:

    case .B(let l0):
      guard case .B(let r0) = b, My::eq(l0, r0) else { return false }
    case .C(let l0, let l1):
      guard case .C(let r0, let r1) = b, My::eq(l0, r0), My::eq(l1, r1) else { return false }

This change appears to speed up type checking even further!

For the enum WorstCase (closed source, but 22 cases with 0…5 payload values of all kinds) which it took up to 90…100 ms to type check yesterday, I introduced the candidate == implementations following implementations like these:

static func `equals via eq`(lhs: Self, rhs: Self) -> Bool {
  switch lhs {
  case .a(let l0): guard case .a(let r0) = rhs, My::eq(l0, r0) else { return false }
  // ...
  }
  return true
}

static func `equals via ~=`(lhs: Self, rhs: Self) -> Bool {
  switch lhs {
  case .a(let l0): guard case .a(l0) = rhs else { return false }
  // ...
  }
  return true
}

static func `equals via ==`(lhs: Self, rhs: Self) -> Bool {
  switch lhs {
  case .a(let l0): guard case .a(let r0) = rhs, l0 == r0 else { return false }
  // ...
  }
  return true
}

Then compiled the file (^⌘B) in the project in Xcode 27 beta 4 with -Xfrontend -debug-time-function-bodies enabled, and recorded the following average timings from 5 runs:

enum WorstCase equality mean ± std [ms] speedup
equals via eq 2.88 ± 0.09 25.70×
equals via ~= 4.70 ± 0.40 15.74×
equals via == 72.28 ± 0.74 1.02×
__derived_enum_equals 74.03 ± 1.16 (current)

(This is the same type which used to measure at 90 ms before, now pretty stable at 74 ms.)

The same project also has a struct PrettySlow: Equtable with 13 nontrivial stored properties, with __derived_struct_equals spending . Making similar use of My::eq, ~=, or ==, I recorded the following timings for it:

struct PrettySlow equality mean ± std [ms] speedup
equals via eq 0.94 ± 0.08 33.50×
equals via ~= 3.17 ± 0.31 9.90×
equals via == 27.46 ± 0.52 1.14×
__derived_struct_equals 31.36 ± 0.49 (current)

So in both cases, a pretty significant compile-time improvement of 25…33×.

I should point out that the one-time cost of type checking My::eq(_:_:) is reported to be about 2 ms. If the compiler adopted a workaround like this in its Equatable synthesis, maybe the function could find its way to the runtime unless there's a better way to disambiguate the binary Equatable.== operator without a type checking cost.

3 Likes
10

I'm aware of the issue with ___chkstk_darwin blowing out with large value types. As a workaround, making use of indirect cases has worked around the issue ok for us.

Another known workaround is to wrap the bodies of all cases of a switch in an immediately evaluated closure. But that would definitely hurt the type checking performance again, because there's just more code and we have to also take into account the early returns:

static func ==(lhs: Self, rhs: Self) -> Bool {
  switch lhs {
  case .a(let l0):
    guard ({
      guard .a(let r0) = rhs, My::eq(l0, r0) else { return false }
      return true
    }()) else { return false }
  // ...
  }
  return true
}

Never mind that it's also pretty ugly!

In any case, this thread was primarily about type checking performance, not runtime, and like @allevato said in the thread, this is best left for the IR generation so everybody benefits. (I wonder if there's a GitHub issue?)

1 Like