Recent improvements to the type checker - Compiler - Swift Forums

Recent improvements to the type checker

Development

Compiler

Slava_Pestov

(Slava Pestov)

June 2, 2026, 2:41pm

With the Swift 6.4 release converging, I thought it would be a good time to detail some of the type checker performance improvements we worked on since I shared the type checker performance roadmap last year. I'm also going to outline a couple of things we plan on looking at next.

Swift 6.4

The disjunction selection and favoring algorithms in Swift 6.3 allowed us to phase out some older, less principled performance optimizations.

The work in Swift 6.4 can be seen as a continuation of this trend. We looked at various instances of slow expression type checking and came up with some simple but effective optimizations which improve performance in a variety of situations. As with last year's work, these new improvements have rendered obsolete certain older, more narrowly targeted heuristics, which makes the compiler easier to maintain and test.

All of the changes I will describe below can be found in the latest Swift 6.4 development snapshots. Please test and report any issues you find!

Disjunction pruning

A quick reminder about terminology. Each reference to an overloaded function name generates a "disjunction constraint", which presents the type checker with a choice between one or more overloaded declarations that share the same name but have different types.

The type checker's goal is to find a compatible set of overload choices from each disjunction. In the "main loop" of the constraint solver, we look at all remaining unsolved disjunctions, together with the currently known type of each argument and result at the call site. These types from the call site are compared against the declared type of each overload in the disjunction.

In Swift 6.3, we only differentiated between overload choices that were "favored" vs. not. Here, "favored" roughly means "likely to succeed and lead to the best overall solution". Disjunctions with favored choices were bumped to the front of the line, and the favored choices in each disjunction were attempted first. If a favored choice succeeds, we then skip everything else.

Favoring works well when each guess is correct, because the solver can avoid backtracking entirely in those situations. Many situations involving arithmetic operators are now solved very quickly in Swift 6.3 thanks to favoring. But favoring cannot make a correct guess every time, because we cannot solve every instance without backtracking; and when favoring makes a wrong guess, we often end up with mismatched types at call sites which result in nothing being favored. The solver then has to attempt each overload in turn, and it may very well turn out that they all fail.

Swift 6.4 introduces what we call disjunction pruning . When we evaluate an overload choice against the call site, we further differentiate between "favored", "not favored", and a third state, "cannot possibly succeed". Once we know an overload choice cannot possibly succeed, the choice is disabled, and disabled overload choices do not need to be attempted, regardless of whether any other overload choice succeeds.

The immediate consequence is to shorten some dead-ends in the search space. However, it becomes more effective in two special situations where it gives the type checker a "guaranteed winning move":

If at any point we find that we have a disjunction where all overload choices except for one are disabled, we can attack this disjunction next, simply by binding that remaining overload choice. Previously, favoring alone would not be sufficient to ensure that this disjunction was always chosen. This has the effect of propagating more type information in the constraint system at no "cost". The resulting constraint simplification might then disable more choices, and so on.

Similarly, if any remaining disjunction has all overload choices disabled, we can attempt it next. There is no benefit to any further exploration, because we're at a dead end.

The second case can come up even when type checking a valid expression. Suppose that favoring makes an incorrect guess, so the current combination of overload choices is inconsistent, but you just don't know it yet. You may still have to explore a bit further, but often you will quickly get to a point where at least one remaining disjunction has all choices disabled. Favoring alone has no reason to pick this disjunction next, so you could get a combinatorial search that was doomed to fail. Now, the solver recognizes that it is in this situation, and backtracks immediately.

Improved binding inference

All of the type checker's overload-related optimizations rely on being able to compare the declared type of each overload choice, against the "currently known" contextual type information at each call site in your expression. If nothing is yet known about the types at a call site---that is, all of the argument...