The Swift compiler is slow due to how types are inferred

I&#x27;m suspicious about the truth of this claim. I don&#x27;t think bidirectional typechecking is the problem in itself: the problem trying to do type inference when you have some extremely flexible operator overloading, subtyping, and literal syntax features. It&#x27;s these &quot;expressive&quot; features which have made type inference in Swift far more computationally complex, not type inference itself.<p>And certainly not <i>bidirectional type inference</i>; the author of this post&#x27;s definition of this concept isn&#x27;t even right (bidirectional typing refers to having a distinction between typing judgements which are used to infer types and those which are used to restrict types, not moving bidirectionally between parent nodes &amp; child nodes). I don&#x27;t know if the mistake comes from the post author or Chris Lattner, and I don&#x27;t know if the word &quot;bidirectional&quot; is relevant to Swift&#x27;s typing; I don&#x27;t know if Swift has a formal description of its type system or that formal description is bidirectional or not.<p>EDIT: watching the video the Chris Lattner quote comes from, it appears the mistake about the word &quot;bidirectional&quot; is his. Bidirectional type systems are an improvement over ordinary type systems in exactly the direction he desires: they distinguish which direction typing judgements can be used (to infer or check types), whereas normal formal descriptions of type systems don&#x27;t make this distinction, causing the problems he describes. &quot;Bottom up&quot; type checking is just a specific pattern of bidirectional type checking.<p>Regardless, the problem with Swift is that a literal can have any of an unbound arity of types which implement a certain protocol, all of which have supertypes and subtypes, and the set of possibilities grows combinatorially because of these language features.<p>cf: <a href="https:&#x2F;&#x2F;arxiv.org&#x2F;abs&#x2F;1908.05839" rel="nofollow">https:&#x2F;&#x2F;arxiv.org&#x2F;abs&#x2F;1908.05839</a>

One of the interesting tradeoffs in programming languages is compile speed vs everything else.<p>If you&#x27;ve ever worked on a project with a 40 minute build (me) you can appreciate a language like go that puts compilation speed ahead of everything else. Lately I&#x27;ve been blown away by the &quot;uv&quot; package manager for Python which not only seems to be the first correct one but is also so fast I can be left wondering if it really did anything.<p>On the other hand, there&#x27;s a less popular argument that the focus on speed is a reason why we can&#x27;t have nice things and, for people working on smaller systems, languages should be focused on other affordances so we have things like<p><a href="https:&#x2F;&#x2F;www.rebol.com&#x2F;" rel="nofollow">https:&#x2F;&#x2F;www.rebol.com&#x2F;</a><p>One area I&#x27;ve thought about a lot is the design of parsers: for instance there is a drumbeat you hear about Lisp being &quot;homoiconic&quot; but if you had composable parsers and your language exposed its own parser, and if every parser also worked as an unparser, you could do magical metaprogramming with ease similar to LISP. Python almost went there with PEG but stopped short of it being a real revolution because of... speed.<p>As for the kind of problem he&#x27;s worried about (algorithms that don&#x27;t scale) one answer is compilation units and careful caching.

I&#x27;m a big fan of the idea of Swift as a cross platform language general purpose langauge, but it just feels bad without Xcode. The Vscode extension is just okay, and all of the tutorials&#x2F;documentation assumes you are using Xcode.<p>A lot of the issues that Swift is currently facing are the same issues that C# has, but C# had the benefit of Mono and Xamarin, and in general more time. Plus you have things like JetBrains Rider to fill in for Visual Studio. Maybe in a few years Swift will get there, but I&#x27;m just wary because Apple really doesn&#x27;t have any incentive to support it.<p>Funnily enough, the biggest proponent of cross platform Swift has been Miguel De Icaza, Gnome creator, and cofounder of Mono the cross platform C# implementation pre .net core. His Swift Godot project even got a shout out recently by Apple

They never will, since it&#x27;s also one of Swift&#x27;s greatest strengths. What they may, eventually, do is dedicate the resources to minimize the negative aspects of the system while documenting clear ways to mitigate the biggest issues. Unfortunately Apple&#x27;s dev tools org is chronically under resourced, which means improvements to the inference system and its diagnostics come and go as engineers are allowed to work on it. Occasionally it will improve, only to then regress as more features are added to the language, and then the cycle continues.

It&#x27;s really hard for me to read past Lattner&#x27;s quote. &quot;Beautiful minimal syntax&quot; vs &quot;really bad compile times&quot; and &quot;awful error messages&quot;.<p>I know it&#x27;s not helpful to judge in hindsight, lots of smart people, etc.<p>But why on earth would you make this decision for a language aimed at app developers? How is this not a design failure?<p>If I read this article correctly, it would have been an unacceptable decision to make users write setThreatLevel(ThreatLevel.midnight) in order to have great compile times and error messages.<p>Can someone shed some light on this to make it appear less stupid? Because I&#x27;m sure there must be something less stupid going on.

It looks to me as if there’s a solution to this problem based on the precompilation of sparse matrices. I’ll explain. If you have a function (or operator) call of the form fn(a, b), and you know that fn might accept 19 types (say) in the “a” place and 57 types in the “b” place, then in effect you have a large 2d matrix of the a types and the b types. (For functions taking a larger number of arguments you have a matrix with larger dimensionality.) The compiler’s problem is to find the matrix cell (indeed the first cell by some ordering) that is non-empty. If all the cells are empty, then you have a compiler error. If at least one cell is non-empty (the function is implemented for this type combination), then you ask “downward” whether the given arguments values can conform to the acceptable types. I know that there’s complexity in this “downward” search, but I’m guessing that the bulk of the time is spent on searching this large matrix. If so, then it’s worth noting that there are good ways of making this kind of sparse matrix search very fast, almost constant time.

HM works great for me. Let&#x27;s try it elsewhere instead of blaming the algorithm!<p><pre><code> {-# LANGUAGE OverloadedStrings #-} -- Let strings turn into any type defining IsString {-# LANGUAGE GeneralizedNewtypeDeriving #-} -- simplify&#x2F;automate defining IsString import Data.String (IsString) main = do -- Each of these expressions might be a String or one of the 30 Foo types below let address = &quot;127.0.0.1&quot; let username = &quot;steve&quot; let password = &quot;1234&quot; let channel = &quot;11&quot; let url = &quot;http:&#x2F;&#x2F;&quot; &lt;&gt; username &lt;&gt; &quot;:&quot; &lt;&gt; password &lt;&gt; &quot;@&quot; &lt;&gt; address &lt;&gt; &quot;&#x2F;api&#x2F;&quot; &lt;&gt; channel &lt;&gt; &quot;&#x2F;picture&quot; print url newtype Foo01 = Foo01 String deriving (IsString, Show, Semigroup) newtype Foo02 = Foo02 String deriving (IsString, Show, Semigroup) -- ... eliding 27 other type definitions for the comment newtype Foo30 = Foo30 String deriving (IsString, Show, Semigroup) </code></pre> Do we think I&#x27;ve captured the combinatorics well enough?<p>The <i>url</i> expression is 9 adjoining expressions, where each expression (and pair of expressions, and triplet of expressions ...) could be 1 of at least 31 types.<p>$ ghc --version<p><pre><code> The Glorious Glasgow Haskell Compilation System, version 9.0.2 </code></pre> $ time ghc -fforce-recomp foo.hs<p><pre><code> [1 of 1] Compiling Main ( foo.hs, foo.o ) Linking foo ... real 0m0.544s user 0m0.418s sys 0m0.118s </code></pre> Feels more sluggish than usual, but bad combinatorics shouldn&#x27;t just make it <i>slightly</i> slower.<p>I tried compiling the simplest possible program and that took `real 0m0.332s` so who knows what&#x27;s going on with my setup...

Our CI posts a list of shame with the 10 worst offending expressions on every PR as part of the build and test results.<p>So far it&#x27;s working quite nicely. Every now and then you take a look and notice that your modules are now at the top, so you quickly fix them, passing the honour to the next victim.

Does anyone know why, anecdotally, it seems like the slowness of type inference is more of a pain point in Swift than in Ocaml, Rescript, Purescript, Haskell, etc?

One could argue that anything that anything that makes the development process itself more efficient, as opposed to the compiling, is worth it since programmers themselves ain’t getting any faster anytime soon, but timing out after more than 40 seconds on a state-of-the-art CPU because of a handful of lines is just ridiculous.

The times here seem unreasonably bad even with the bad algorithm. Something else has got to be going on. Maybe kind of hidden factorial complexity when it tries every combination?

The combinatorial explosion is intractable but since it only seems to come up in really obscure corner cases, I wonder if the typical inference scenarios can be solved by having the compiler cache the AST across invocations so that inference only needs to be performed on invalidated parts of the AST as it’s being typed instead of waiting for the user to invoke the compiler.

This article doesn&#x27;t even mention the new type checker and constraint solver.<p>The compiler is open-source, and discussed on open forums. Readers would love some summary&#x2F;investigation into slow-down causes and prospects for fixes.

The math type inference example makes the usual claim that &quot;what if Swift can replace Python&quot; a non-starter. As someone who have to deal with this on frequent basis, it is pretty sad.<p>(I maintains s4nnc and a fork of PythonKit).

I have a feeling it&#x27;s going to be nearly impossible to replace it without breaking a lot of existing code, since the syntax will have to be a lot more explicit.

This is not a fixable flaw. Solving these constraints efficiently can definitely get you a Turing award, it&#x27;s basically the SAT problem.<p>And without this type system, swift is just Objective C in a prettier syntax, so Apple has to bite the bullet and bear with it.

There are fast type inference algorithms available today, such as MLStruct. [0]<p>[0] <a href="https:&#x2F;&#x2F;github.com&#x2F;hkust-taco&#x2F;mlstruct">https:&#x2F;&#x2F;github.com&#x2F;hkust-taco&#x2F;mlstruct</a>

Wait, in Swift it&#x27;s illegal to multiply an int by a double?? So you would have to explicitly cast index to a double? I definitely didn&#x27;t expect that!

Isn’t the channel variable declared and inferred as an int32? Can’t see why the overload isn’t resolved directly?

Scala does essentially the same and a lot faster, so it&#x27;s not a fundamental limitation.

&gt; they’re invalid swift<p>If this isn&#x27;t valid why are we even taking about it? The compiler should report syntax error or something

All those Swiftie haters

&gt; The issue is caused by using the + operator with the channel Int and a String literal. Thanks to the standard library’s 17 overloads of + and 9 types adopting the ExpressibleByStringLiteral Protocol, the swift compiler can’t rule out that there might be a combination of types and operators that make the expression valid, so it has to try them all. Just considering that the five string literals could be one of the possible nine types results in 59,049 combinations, but I suspect that’s a lower bound, since it doesn’t consider the many overloads of +.<p>This really seems like a design flaw. If there are 59,049 overloads for string concatenation, surely either<p>- one of them should be expressive enough to allow concatenation with an integer, which we can do after all in some other languages<p>- or, the type system should have some way to express that no type reachable by concatenating subtypes of String can ever get concatenated to an integer.<p>Is this unreasonable? Probably there&#x27;s some theorem about why I&#x27;m wrong.