[swift-dev] A type-checking performance case study

[John McCall]

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.

Thanks go to Doug Gregor for being a sounding board for a lot of ideas that came up during this investigation.

1. Introduction

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.  Nonetheless, for any particular problem, there are usually things we can do to avoid or limit that combinatorial explosion, and so it is always reasonable to take a look.

Some background for the rest of this discussion.  The current semantics for name lookup, member or otherwise, are that all possible matches are dropped into an overload set with no explicit ranking between them.  If solutions can be found with multiple overloads, they are disambiguated (hopefully) using the ambiguity resolution rules.  Some aspects of the ambiguity resolution rules do apply to declarations in the abstract; for example, there is a rule that prefers a solution that picks a function with a strictly-more-specialized signature.  However, in general, such rules cannot be applied immediately during type-checking.  This is because of the "score" system in which solutions are ranked according to the kind and number of various undesired implicit conversions they perform: for example, it is possible that a solution using a more-specialized function will end up requiring more undesired conversions and thus rank worse.  Therefore, the type-checker must find all possible solutions and only then rank them, which often prohibits short-circuits of the combinatorial explosion.

2. The problem

Okay, concrete stuff.  The expression in question is:

  (0..<5).lazy.map { String($0) }

The types of '0' and '5' are not immediately constrained; in fact, it will turn out that they can only be constrained by assigning them their default literal type.  Many expressions that are expensive to type-check feature this property, because the assignment of default types must occur very late in type-checking, as a matter of last resort.

'..<' has two overloads, one requiring the value type to be Comparable and a more specialized one which also requires it to be Strideable.  They yield different types.

'lazy' is a member name and therefore can only be resolved when the base type is known.  As it happens, in both cases the overload set will end up the same: a small number of overloads from various protocol extensions.  The proposed library change adds several of these, greatly exacerbating the explosion.  All of these definitions yield different types.

'map' is a member name and therefore can only be resolved when the base type is known.  It has a small number of overloads in different types and protocol extensions.

'String.init' has a huge number of overloads, somewhere around fifty.

3. Current type-checker behavior

The type-checker ends up taking the right basic approach for solving this: it experimentally picks one of the overloads for '..<', then an overload for '.lazy', then an overload for '.map', then an overload for 'String.init'.

As the constraint system is progressively solved, it will turn out that the value type of the integer literals will propagate all the way down to be the type of '$0' and hence of the argument to String.  This sort of propagation could, in general, require the literals to have a specific type.  In this case, since 'String(x)' will take basically anything, the literals are not constrained, and we will end up defaulting their types.  I mention this only to underline why the type-checker cannot apply this defaulting quickly.

Because the literals end up needing to be defaulted, and because there are two possible default types for integer literals (we will use 'Double' if 'Int' does not work), the basic combinatoric formula for this constraint system is something like 2 x 4 x 4 x 50 x 2 x 2.  (I don't remember the actual numbers of overloads.)  This is why type-checking is slow.

4. Possible solutions

As a patch to the problem, I recognized that many of those 50 overloads of 'String.init' were not viable due to argument-label mismatches, but were only being recognized as such in the innermost loop.  (The rule here is that you cannot pass a tuple value and have it automatically "explode" to match the parameter list; the syntactic call arguments must structurally match the parameters.  This was an accepted proposal with corresponding compiler implementation from Februrary.  Unfortunately, it turns out that our enforcement of this is inconsistent.)  It was simple enough to avoid this by marking the overloads as non-viable upon lookup; it even turns out that we already has this heuristic, and it just hadn't kept pace with the language change.  So this limits the explosion in this case.

There are various other type-checking heuristics that might also have helped with this.  For example, the overload sets of 'lazy' are the same in both cases; this is something that could theoretically be observed without expanding the overload set of '..<', and in some cases this might allow some downstream type-checking to proceed outside of any contingencies.  I don't know that it would have significantly helped in this case, however.

Anything beyond that will require language changes.

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.

One very drastic solution to this problem would be to eliminate non-labelled overloads.  (A perhaps more-reasonable way to describe this is to say that argument labels are a part of the name, and therefore two declarations with different labels are not overloads.)  That is, given the syntactic form of an expression, we would always be able to find a single function that it could invoke.  The current argument-labelling design of the language does make this more palatable than it was in earlier iterations.  However, I don't think it's palatable enough: this change would be very limiting, and in particular I think we are very unlikely to accept it for operators or single-argument initializers.

A less drastic solution suggests itself when we examine the nature of these overloads.  '..<', 'lazy', and 'map' all obey an implicit hierarchy of overloads, each imposing stricter constraints than the last.  Furthermore, specifically for 'lazy' and 'map', this hierarchy actually follows the explicit hierarchy of types and the protocols they conform to.  Perhaps we could use this to declare that certain declarations unconditionally hide declarations with the same name from "base" types: for example, a declaration from a concrete type would always hide a declaration from a protocol (or an extension thereof) that the type declares conformance to, and a declaration from a protocol would hide a declaration from a protocol it is derived from.  (This rule could still be implemented in the presence of conditional conformances, but it would be more difficult to apply "statically" during type-checking; we might have to compute a full solution before we could recognize that an overload was actually hidden by a conditional conformance.)  In this case, I believe this would have left us with only a single overload to consider for both 'lazy' and 'map', greatly reducing the combinatorial space of solutions.  Of course, it's also possible that this would remove viable solutions.

5. Actions and recommendations

I've landed the viability-limiting patch as 563057ca980fb9a8fce899184761a812164dc9d2.  Hopefully it sticks.

I strongly recommend that we pursue declaration hiding as a language change.  Even independent of type-checker performance, this seems quite defensible as a language direction, since it makes it much easier to reason about overloading in the presence of protocol extensions and so on.  However, there are still a lot of major open questions with the design.

John.