I landed some performance improvements for the Swift type checker recently, and I'm currently finishing up the next set of changes which I hope to merge soon.
-
So the constraint solver has an extra step between solving constraints and selecting a disjunction; it tries to attempt a _type variable binding_. It looks at the set of unsolved conversion constraints and tries to "guess" one of them, and binds that type variable.
The problem here is to basically compute the domain for each type variable--the set of possible concrete types it might have.
Often, constraint systems have quite simple domains, finite sets for example (and in SAT it's just {0, 1}). In Swift's case, the set of "all possible types" is infinite, because of generics, and quite complicated, so we cannot represent a domain exactly, but we can apply some rough heuristics.
If we can prove that a type variable's domain consists of exactly one type, we can bind it to that type variable, and if we can prove the domain is empty, we can bind it to anything; no matter what, some constraint will fail.
In binding inference, we had an existing optimization that would consider types that have no proper subtypes. For example, if you have
$T0 conv Int
Then in fact we know that Int (like almost all structs, and all user-defined structs) has no proper subtypes, that is, types that convert to it. So we can always bind $T0 to Int in this case.
I generalized this idea further. Suppose you instead have:
Int conv $T0
You can't apply the same optimization here, and just say that $T0 is Int. In Swift, _every_ type has supertypes; those are an optional wrapping the type, the existential types to which this type conforms, and the special standard library AnyHashable type, which is a supertype of every concrete type that conforms to Hashable.
-
In binding inference, we had an existing optimization that would consider types that have no proper subtypes. For example, if you have
$T0 conv Int
Then in fact we know that Int (like almost all structs, and all user-defined structs) has no proper subtypes, that is, types that convert to it. So we can always bind $T0 to Int in this case.
I generalized this idea further. Suppose you instead have:
Int conv $T0
You can't apply the same optimization here, and just say that $T0 is Int. In Swift, _every_ type has supertypes; those are an optional wrapping the type, the existential types to which this type conforms, and the special standard library AnyHashable type, which is a supertype of every concrete type that conforms to Hashable.
But suppose you also have a conformance constraint, and you know that $T0 must conform to some protocol, say BinaryInteger:
Int conv $T0
$T0 conforms BinaryIntegerWell, existential types cannot conform to protocols in Swift, so we can rule out the possibility that $T0 is existential. It might still be Optional<Int> or AnyHashable, perhaps, but those don't conform to BinaryInteger either.
So now, we can "prove" that $T0's domain contains exactly one type, and so we can bind $T0 to Int.
What if you end up in a situation where you're looking at this?
Int conv $T0
$T0 conforms SequenceWell, Int doesn't conform to Sequence, and neither does Optional<Int> or AnyHashable, so we've made a conflicting set of overload choices; we just haven't realized it yet, because the domain of $T0 is the empty set.
Now we _do_ realize it, and bind Int to $T0 anyway; this fails the conformance constraint, and in some cases, it fails it much sooner than it would have otherwise, reducing wasted time spent in dead ends.
-
But suppose you also have a conformance constraint, and you know that $T0 must conform to some protocol, say BinaryInteger:
Int conv $T0
$T0 conforms BinaryIntegerWell, existential types cannot conform to protocols in Swift, so we can rule out the possibility that $T0 is existential. It might still be Optional<Int> or AnyHashable, perhaps, but those don't conform to BinaryInteger either.
So now, we can "prove" that $T0's domain contains exactly one type, and so we can bind $T0 to Int.
What if you end up in a situation where you're looking at this?
Int conv $T0
$T0 conforms SequenceWell, Int doesn't conform to Sequence, and neither does Optional<Int> or AnyHashable, so we've made a conflicting set of overload choices; we just haven't realized it yet, because the domain of $T0 is the empty set.
Now we _do_ realize it, and bind Int to $T0 anyway; this fails the conformance constraint, and in some cases, it fails it much sooner than it would have otherwise, reducing wasted time spent in dead ends.
There are more tricks possible by considering multiple adjacent constraints.
An existing optimization would compute the join of two types (the least common supertype) in a situation like this:
Foo conv $T0
Bar conv $T0The implementation of joins() was old and incomplete though and it missed many common situations. I rewrote it to model Swift's subtyping rules faithfully. I got it to compute meets. Unlike joins, where all types are subtypes of the universal Any type, the meet can be empty. For example, suppose that Foo and Bar are classes:
$T0 conv Foo
$T0 conv BarBy the previous rules, we cannot bind $T0 to Foo or Bar, because Foo and Bar might have proper subtypes (one might be a subclass of the other).
But if neither is a subclass of the other, then $T0's domain is empty, and we can bind $T0 to Foo or Bar at this point, and backtrack.
There are a few more combinations, for example if you have this:
Int conv $T0
$T0 conv Optional<String>There is no type for $T0 that is a supertype of Int but also a subtype of Optional<String>.
-
There are more tricks possible by considering multiple adjacent constraints.
An existing optimization would compute the join of two types (the least common supertype) in a situation like this:
Foo conv $T0
Bar conv $T0The implementation of joins() was old and incomplete though and it missed many common situations. I rewrote it to model Swift's subtyping rules faithfully. I got it to compute meets. Unlike joins, where all types are subtypes of the universal Any type, the meet can be empty. For example, suppose that Foo and Bar are classes:
$T0 conv Foo
$T0 conv BarBy the previous rules, we cannot bind $T0 to Foo or Bar, because Foo and Bar might have proper subtypes (one might be a subclass of the other).
But if neither is a subclass of the other, then $T0's domain is empty, and we can bind $T0 to Foo or Bar at this point, and backtrack.
There are a few more combinations, for example if you have this:
Int conv $T0
$T0 conv Optional<String>There is no type for $T0 that is a supertype of Int but also a subtype of Optional<String>.
I've got a few more things cooking, but that's enough for now. There are more details in the description for my latest PR, which links to the previous PR, which also links to the one before that: https://github.com/swiftlang/swift/pull/87669
-
But suppose you also have a conformance constraint, and you know that $T0 must conform to some protocol, say BinaryInteger:
Int conv $T0
$T0 conforms BinaryIntegerWell, existential types cannot conform to protocols in Swift, so we can rule out the possibility that $T0 is existential. It might still be Optional<Int> or AnyHashable, perhaps, but those don't conform to BinaryInteger either.
So now, we can "prove" that $T0's domain contains exactly one type, and so we can bind $T0 to Int.
What if you end up in a situation where you're looking at this?
Int conv $T0
$T0 conforms SequenceWell, Int doesn't conform to Sequence, and neither does Optional<Int> or AnyHashable, so we've made a conflicting set of overload choices; we just haven't realized it yet, because the domain of $T0 is the empty set.
Now we _do_ realize it, and bind Int to $T0 anyway; this fails the conformance constraint, and in some cases, it fails it much sooner than it would have otherwise, reducing wasted time spent in dead ends.
@slava > Well, existential types cannot conform to protocols in Swift, so we can rule out the possibility that $T0 is existential.
except the ones that do (Error and
@objcprotocols). I wouldn’t be surprised if there are more in the future. Hopefully this isn’t a loadbearing part of the optimizations! -
I've got a few more things cooking, but that's enough for now. There are more details in the description for my latest PR, which links to the previous PR, which also links to the one before that: https://github.com/swiftlang/swift/pull/87669
@slava I admire how you can explain this type of thing with such clarity.
-
@slava > Well, existential types cannot conform to protocols in Swift, so we can rule out the possibility that $T0 is existential.
except the ones that do (Error and
@objcprotocols). I wouldn’t be surprised if there are more in the future. Hopefully this isn’t a loadbearing part of the optimizations!@jrose Of course, but we know which protocols are self-conforming, so we skip those. As long as self-conformance remains "opt-in", it will be fine.
(In one of the cases where I got a speedup from this, the protocol was SIMD which is unlikely to self-conform in the near future :))
-
I landed some performance improvements for the Swift type checker recently, and I'm currently finishing up the next set of changes which I hope to merge soon.
There are two main improvements. The first is a new "disjunction pruning" optimization to help skip impossible overload choices, and the second set of improvements concern implicit conversions and the constraints they generate.
-
@slava I admire how you can explain this type of thing with such clarity.
@gregtitus @slava This *type* of thing, amirite?
-
I've got a few more things cooking, but that's enough for now. There are more details in the description for my latest PR, which links to the previous PR, which also links to the one before that: https://github.com/swiftlang/swift/pull/87669
@slava Thank you for the great explanation! This went right into my notes.
-
I landed some performance improvements for the Swift type checker recently, and I'm currently finishing up the next set of changes which I hope to merge soon.
There are two main improvements. The first is a new "disjunction pruning" optimization to help skip impossible overload choices, and the second set of improvements concern implicit conversions and the constraints they generate.
@slava color me naive but do we cache the precious result of a type checker when it was super expensive? It still doesn’t help you with the first time but…
-
R relay@relay.infosec.exchange shared this topic
