Here is another slow expression to demonstrate the disjunction pruning optimization I talked about earlier.

Suppose you declare a variable of implicitly unwrapped optional type:

var x: Int! = ...

The value of x is stored like an ordinary optional "Int?", but a reference to x from inside an expression is presented as a disjunction---the type of the reference is either "Int", or "Int?". If both lead to a solution, we favor the "Int?" choice; otherwise, we get the "Int" choice, and the compiler then lowers the reference to a runtime check.

Now, consider this expression:

let result = x + x + x + x + x + x

It takes the Swift 6.3 compiler a third of a second to type check this expression, and now its instant with recent main snapshots. What changed?

Well, in 6.3, disjunction selection doesn't have much to go on, so we fall back to selecting the disjunction with the fewest number of active choices at each step.

The implicitly unwrapped optional has fewer choices (2) than + (around 30), so we bind the first IUO, and our picture looks sort of like this, where the _ represent type variables yet to be bound:

let result = Int? + _ + _ + _ + _ + _

We then select the next disjunction, which again will be one of the IUOs, and attempt a choice:

let result = Int? + Int? + _ + _ + _ + _

In fact, Swift 6.3 will bind all IUO disjunctions first, and there are 2^6 possible combinations:

let result = Int? + Int? + Int? + Int? + Int? + Int?
let result = Int? + Int? + Int? + Int? + Int? + Int
let result = Int? + Int? + Int? + Int? + Int + Int?
let result = Int? + Int? + Int? + Int? + Int + Int
...

Of these 2^N combinations, exactly one, where we select the "Int" choice from every IUO disjunction, can be extended to a solution, because in fact + has no overloads that take Optional<Int>:

let result = Int + Int + Int + Int + Int + Int

We must consider all combinations though, and so the simply rest fail.

With latest Swift from main, things go differently. We still bind the first IUO first:

let result = Int? + _ + _ + _ + _ + _

But before we select the next disjunction, we run the new disjunction pruning pass. Since + has no overloads where the first argument matches the type "Int?", we end up disabling all active choices in the first + disjunction.

Now, disjunction selection sees that one of the remaining disjunctions has zero active choices. This means the current partial solution cannot be extended to a full solution no matter what choices we make, so we backtrack.

We attempt the next choice in the first IUO:

let result = Int + _ + _ + _ + _ + _

This time, some choices from the first + disjunction are pruned, but nothing fails. We select the second IUO disjunction:

let result = Int + Int? + _ + _ + _ + _

With these choices so far, pruning is again able to detect that there are no suitable choices for the first + that take an "Int" and an "Int?", so we are left with zero active choices and we attempt the second choice in the second IUO:

let result = Int + Int + _ + _ + _ + _

This continues:

let result = Int + Int + Int? + _ + _ + _
let result = Int + Int + Int + _ + _ + _
let result = Int + Int + Int + Int? + _ + _
let result = Int + Int + Int + Int + _ + _
...
let result = Int + Int + Int + Int + Int + Int

At this stage, we've bound all the IUO disjunctions in linear time, and only the + disjunctions remain.

The optimizations that were already existing in Swift 6.3 take over. Disjunction selection favors the (Int, Int) -> Int overload choice in each +, these favored choices succeed, and the rest of the problem is solved without further backtracking.

@slava So the disjunction checks all this before the operator itself runs? That’s cool.
When developing something like this do you usually test the performance of cases that got worse? Like I believe an expression that resolves with Int?s might be slightly slower now, though not much because it would still be linear.
@vini We have a collection of fast and slow expressions in the test suite that I’m building up by screening bug reports. When an expression is sped up we move it from “slow” to “fast” and add an expectation that it type checks successfully, with a much lower operation limit than the default “reasonable time” limit. This helps catch small regressions and it’s satisfying gradually moving more expressions to the “fast” directory!