Swift Type-checking Performance Case Study
John McCall (via Ole Begemann):
The standard library team asked the compiler team to take a look at the performance of the type-checker. Their observation was that several in-progress additions to the standard library were causing a disproportionate increase in the time it required to compile a simple-seeming expression, and they were concerned that this was going to block library progress. This is the resulting analysis.
[…]
In general, it is expected that changes to the source code can cause non-linear increases in type-checking time. For one, all type systems with some form of generic type propagation have the ability to create exponentially-large types that will generally require exponential work to manipulate. But Swift also introduces several forms of disjunctive constraint, most notably overload resolution, and solving these can require combinatorial explosions in type-checker work.
[…]
Note that there have been proposals about restricting various kinds of implicit conversions. Those proposals are not pertinent here; the implicit conversion are not a significant contributor to this particular problem. The real problem is overloading.
