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.

1 Like
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