Very long compilation times with custom &+ and &* but not with + and *

This small program (a reduced case of long compilation times from one of my projects) takes 8 seconds to compile:

protocol Vector {
  associatedtype Element
}

extension Vector {  
  static func &+(lhs: Self, rhs: Self) -> Self { fatalError() }
  static func &+(lhs: Self, rhs: Element) -> Self { fatalError() }
  static func &+(lhs: Element, rhs: Self) -> Self { fatalError() }
  static func &*(lhs: Self, rhs: Self) -> Self { fatalError() }
  static func &*(lhs: Self, rhs: Element) -> Self { fatalError() }
  static func &*(lhs: Element, rhs: Self) -> Self { fatalError() }
}

func foo(a: Int, b: Int, c: Int, d: Int) -> Int {
  return 12 &* a &+ 34 &* b &+ 56 &* c &+ d
}
Details
% swiftc --version
Apple Swift version 5.4.2 (swiftlang-1205.0.28.2 clang-1205.0.19.57)
Target: x86_64-apple-darwin20.5.0

% time swiftc test.swift
swiftc test.swift 7.70s user 0.29s system 99% cpu 8.022 total

But if all the &+ and &* are replaced with + and *, then it will compile in less than a quarter of a second.


Does anyone know why this is?

Might it be that something (particular to &+ and &*) was missed during the recent improvements of the type checker?

I have not had the opportunity to check this with Xcode 13 yet, maybe it's been resolved there?

1 Like

My results putting that code in an empty package and running a clean build:

Xcode 12.5.1 Xcode 13 (beta 3)
3.3 seconds 1.2 seconds

Before putting it in a package, I ran swiftc (5.4.2) a few times manually. First run was ~7 seconds, but subsequent runs held at ~3 seconds.

The biggest difference between &+ and &* versus + and * with respect to the expression type checker is the overload sets. The overload sets of &+ and &* do not have concrete overloads for numeric types; in the standard library, there are only concrete overloads of these operators for SIMD types. If the constraint solver (the system that implements type inference) finds a solution with concrete overloads, then generic overloads are skipped. + and * do have concrete overloads for numeric types, so using these operators with Int operands will not cause the solver to explore any generic overload space.

Generic overloads make overload resolution an exponentially hard problem because of the way generic arguments are inferred in the constraint solver. Generic arguments are only bound once the solver has selected an overload for each operator in the expression. So, in a case with several generic operators chained together, e.g. a + b + c + d , the solver has to first bind each + to an overload before any generic arguments are attempted, because only then does the solver have the complete set of possible bindings for those generic arguments. In most cases, the solver can't determine that an overload won't work until a generic argument is bound, requirements are checked on that type, etc. In the worst case, the solver attempts all permutations with repetition of the overloads, and fails this many times before finding the correct set of overload bindings.

There's another interesting property of the &+ overload (sub)set:

FixedWidthInteger extension.&+ : <Self where Self : FixedWidthInteger> (Self.Type) -> (Self, Self) -> Self
SignedInteger extension.&+ : <Self where Self : FixedWidthInteger, Self : SignedInteger> (Self.Type) -> (Self, Self) -> Self

which is that both of these overloads work for Int arguments. Because there are 2 overloads that work for &+, the solver finds 2(# of calls to &+) solutions (in this case, 8 solutions). I implemented a heuristic to mitigate this form of exponential solution space for a handful of arithmetic operators because the RangeReplaceableCollection operator overload sets have the same problem, and I plan to generalize this heuristic for all operators.

8 Likes

It looks like we can probably remove the SignedInteger & FixedWidthInteger overloads from consideration--they're a remaining detail of Swift 3 source compatibility--which should improve the situation somewhat.

4 Likes

(follow-up: Mark legacy overloads of &+ and &- unavailable. by stephentyrone · Pull Request #38723 · apple/swift · GitHub)

2 Likes
Terms of Service

Privacy Policy

Cookie Policy