Exponential Time Complexity in the Swift Type Checker
But the line doesn’t get past the Swift type checker. Instead, it emits an error that the expression is too complex to solve. It doesn’t look complex, does it? It’s 5 integer literals, 4 addition operators, two negation operators and a binding to a
Doubletype.How can an expression containing just 12 entities be “too complex”?
[…]
If you don’t typically combine these features in your code, then you’re unlikely to see the “expression was too complex” error. However, if you are using these features, it isn’t always straightforward to suddenly stop. Mathematics code, large “function”-style expressions and declarative code are easier to write with these features and often require a complete rethink to avoid them.
[…]
A note about this approach though: unlike other languages,
Double(x)is not equivalent tox as Doublein Swift. The constructor works more like another function and since it has multiple overloads on its parameter, it actually introduces another overloaded function into the search space (albeit at a different location in the expression).[…]
Posts like this: “[swift-dev] A type-checking performance case study”, indicate that the Swift developers believe resolving function overloads in the type checker is inherently exponential. Rather than redesigning the type checker to eliminate exponential complexity, they are redesigning the standard library to try and skirt around the issue.
Changing stdlib interfaces is done with an eye toward fixes like SE-0091 that mitigate inherently exponential work.
Most of the proposals around function labels and types are trying to kill type checker tech debt too.
“Rewrite the type checker” is up there on list of things we want to do.
Previously: Speeding Up Slow Swift Build Times, Swift 1.0 Performance and Compilation Times, Slow Swift Array Type Inference, Swift Type-checking Performance Case Study.
