18 ms·

The Swift compiler is slow due to how types are inferred

266 points by paraboul 2y ago

jshier 2y ago
They never will, since it's also one of Swift'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'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.
- fooker 2y ago
  >chronically under resourced This is very true, Apple sees compiler jobs as a cost center.
- tmpz22 2y ago
  I think this is a unfair characterization. Yes Apple's developer ecosystem has a lot of fair complaints, I've personally run into the issues in this article particularly with newer APIs like SwiftData's #Predicate macro. But we just saw two days ago a lot of concerted issues to fix systemic problems like XCode the editor, or with compile times with Explicit Module improvements. I think you're painting with too heavy a brush. Apple clearly is dedicating resources to long-tail issues. We just saw numerous examples two days ago at WWDC24.
  - jshier 2y ago
    No, this is just the typical Apple cycle I alluded too. Improvements are saved up for WWDC, previewed, then regress over the next year as other work is done, only for the process to repeat. They've demonstrated small improvements practically every year, yet the compiler continues to regress in build performance. Notably, the explicit module build system you mentioned regresses my small project's build time by 50% on an M1 Ultra. And even without it, overall build performance regressed 10 - 12% on the same project.
  - plorkyeran 2y ago
    Explicit modules make build times worse, not better. Yes, this is the exact opposite of what Apple claims they do, and I am genuinely baffled by the disconnect. Usually Apple's marketing is at least directionally true even if they overstate things, but in this case the project appears to have entirely failed to deliver on what it was supposed to do but it's still being sold as if it succeeded. On top of that, the big thing we didn't see announced this year was anything at all related to addressing the massive hit to compile times that using macros causes.
- adamnemecek 2y ago
  [flagged]
fooker 2y ago
This is not a fixable flaw. Solving these constraints efficiently can definitely get you a Turing award, it's basically the SAT problem. 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.
- coldpie 2y ago
  It sort of is fixable, though. If you think about it, the problem is a bunch of functions are all mapped to one of a small set of names: +*/, etc. That is, the operators. If we didn't try to cram all this functionality into a tiny handful of symbols because of some weak analogy they have with basic math operations[1], then the compiler would have far fewer name conflicts to try to disambiguate, and the problem goes away on its own. Like yeah, the problem still exists if we made a few dozen functions all called "a", but the solution is to not do that, not give up on an otherwise fine type system. I'm convinced operator overloading is an anti-feature. It serves two purposes: 1) to make a small set of math operations easier to read (not write), in the case where there are no mistakes and all readers perfectly understand the role of each operator; and, 2) to make library developers feel clever. Operator-named functions are strictly worse than properly named functions for all other uses. Yes, yes, person reading this comment, I know you like them because they make you feel smart when you write them, and you're going to reply with that one time in university that you really needed to solve a linear algebra problem in C++ for some reason. But they really are terrible for everyone who has to use that code after you. They're just badly named functions, they're un-searchable, they make error messages unreadable, and they are the cause the naming conflict that is at the root of the linked blog post. It's time to ditch operator overloading. [1] Or because they look like the same symbol used in some entirely other context, god, please strike down everyone who has ever written an operator-/ to combine filesystem paths.
  - Apocryphon 2y ago
    So you’re saying one potential solution is to use the APL character set?
  - fooker 2y ago
irdc 2y ago
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.
- jandrese 2y ago
  At the very least it seems like the compiler could math out how many possible states it is about to check and if the value is unreasonable instantly error out instead of trying to chew on it for over half a minute before giving up.
- rudedogg 2y ago
  These type inference landmines are all over the place with SwiftUI too. I run into them with View/Shape/Color frequently
- cerved 2y ago
  I'm not sure I would draw the same conclusion, stricter requirements on typing is less cumbersome these days with better auto complete and LLMs
  - deleted 2y ago
    [deleted]
- hinkley 2y ago
  Deltas and caches need some work too. It's a little unfortunate that my compile time is more affected by the amount of code that didn't change than the code I changed. One of the features of Rational was that it would distribute precompiled headers around. Whoever changed the header files had to pay to recompile them, but everyone else just got the results instead.
liuliu 2y ago
The math type inference example makes the usual claim that "what if Swift can replace Python" a non-starter. As someone who have to deal with this on frequent basis, it is pretty sad. (I maintains s4nnc and a fork of PythonKit).
- manmal 2y ago
  Does this improve when declaring all variables with explicit types before using them in expressions?
  - liuliu 2y ago
    Yeah, but people do like to write y = .log(x * 0.1) + (1.24).squareRoot() type of expressions for what Python did best (NumPy and PyTorch).
- wiseowise 2y ago
  > what if Swift can replace Python What a ridiculous statement. I’m willing to bet everything I have in life that this is never going to happen.
  - liuliu 2y ago
    In retrospective, yes. But Swift for TensorFlow and similar projects received much attention at a time. (Also see Mojo as another attempt).
  - fire_lake 2y ago
    Probably not Swift, but you know at some point Python will be surpassed in popularity by something else right? This has happened many times to programming languages in the past.
temp123789246 2y ago
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?
- deleted 2y ago
  [deleted]
- tines 2y ago
  Is it that Haskell, at least, doesn't support overloading in the same way as Swift? I don't know either of them well enough to be sure. It seems like there's a combinatorial explosion of possible overloads in Swift, whereas if you implement a function with the same ergonomics in Haskell (e.g. a printf-like function), the only thing the compiler has to do is ask "Does type X have an implementation for typeclass Show? Yes? Done." Essentially Haskell solved this overload inference problem in the same way that iterators solve the M*N problem for basic algorithms: convert all these disparate types to a single type, and run your algorithm on that.
  - ackfoobar 2y ago
    "Does type X have an implementation for typeclass Y" isn't always easy to answer. https://aphyr.com/posts/342-typing-the-technical-interview https://aphyr.com/posts/342-typing-the-technical-interview
    - tines 2y ago
      That post, while awesome (as is the rest of aphyr's stuff), is a lot to wade through to get to the point you're trying to convey. Can you spell it out for me?
      - ackfoobar 2y ago
        That typeclass resolution can encode some heavy computation, the example being n-queens in the article.
peppertree 2y ago
I have a feeling it'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.
ajkjk 2y ago
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?
- novok 2y ago
  There are a bunch of other chokepoints, but type inference is a big part of it: https://github.com/apple/swift/blob/main/docs/CompilerPerformance.md https://github.com/apple/swift/blob/main/docs/CompilerPerfor... Another thing I would add to swift as a flag is to make imports based on specific files vs. an abstract "module", there is a lot of repeated work that happens because of that last time I looked.
- floxy 2y ago
  Yes, I've never written a line of Swift, but these cases don't seem to be of the usual variety that cause Hindley-Milner to blow up. It seems like the Swift compiler source is available, and these test cases are small. This is encouragement for someone to spend a small amount of time digging into this, just for the curiosity of it. And I mean, just something like, fire it up in the debugger, start the compiler on one of these test cases, interrupt the when it looks like it is "hung", but before it times out. Step through the code a bit, to identify the handful of functions that that we're looping through, and then report out what you find, and your best guess, the algorithm is implemented correctly and is hopelessly intractable, or "hey, didn't we already check down this branch previously?". I'll give you my next upvote on HN. https://static.aminer.org/pdf/20170130/pdfs/popl/o8rbwxmj6h2cxf7qdezlupsbgn5u40wn.pdf https://static.aminer.org/pdf/20170130/pdfs/popl/o8rbwxmj6h2... https://github.com/apple/swift https://github.com/apple/swift
- hinkley 2y ago
  It's very hard to track time complexity when you nest multiple layers of delegation.
Decabytes 2y ago
I'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/documentation assumes you are using Xcode. 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'm just wary because Apple really doesn't have any incentive to support it. 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
- giancarlostoro 2y ago
  The only thing holding it back is Apple not investing into making it happen. Swift is in a weird spot where it has so much potential, but without investment in the tooling for other platforms (which is uncommon for Apple in general) it just wont happen, at least not as quickly as it could.
  - refulgentis 2y ago
    I wouldn't describe Swift itself as having so much potential: I loved it and advocated for it, for years. After getting more experience on other platforms and having time to watch how it evolved, or didn't as per TFA, it's...okay to mediocre compared to peers - Kotlin, Dart, Python come to mind. If Foundation was genuinely cross platform and open source, that description becomes more plausible for at least some subset of engineers. * (for non-Apple devs, Foundation ~= Apple's stdlib, things like dateformatting) I don't mean to be argumentative, I'm genuinely curious what it looks like through someone else's eyes and the only way to start that conversation is taking an opposing position. I am familiar with an argument it's better than Rust, but I'd very curious to understand if "better than" is "easier to pick up" or "better at the things people use Rust for": i.e. I bet it is easier to read & write, but AFAIK it's missing a whole lot of what I'll call "necessary footguns for performance" that Rust offers. * IIRC there is a open source Foundation intended for Linux? but sort of just thrown at the community to build.
PaulHoule 2y ago
One of the interesting tradeoffs in programming languages is compile speed vs everything else. If you'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've been blown away by the "uv" 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. On the other hand, there's a less popular argument that the focus on speed is a reason why we can't have nice things and, for people working on smaller systems, languages should be focused on other affordances so we have things like https://www.rebol.com/ https://www.rebol.com/ One area I've thought about a lot is the design of parsers: for instance there is a drumbeat you hear about Lisp being "homoiconic" 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. As for the kind of problem he's worried about (algorithms that don't scale) one answer is compilation units and careful caching.
- kettlecorn 2y ago
  > One of the interesting tradeoffs in programming languages is compile speed vs everything else. In the case of Rust it's more of a cultural choice. Early people involved in the language pragmatically put everything else (correctness, ability to ship, maintainability, etc.) before compilation speed. Eventually the people attracted to contribute to the language weren't the sort that prioritized compilation speed. Many of the early library authors reflected that mindset as well. That compounds and eventually it's very difficult to crawl out from under. I suspect the same is true for other languages as well. It's not strictly a bad thing. It's a tradeoff but my point is that it's less of an inevitability than people think.
  - throwaway894345 2y ago
    I think most people haven't used many languages that prioritize compilation speed (at least for native languages) and maybe don't appreciate how much it can help to have fast feedback loops. At least that's the feeling I get when I watch the debates about whether Go should add a bunch more static analysis or not--people argue like compilation speed doesn't matter at all, while _actually using Go_ has convinced me that a fast feedback loop is enormously valuable (although maybe I just have an attention disorder and everyone else can hold their focus for several minutes without clicking into HN, which is how I got here).
Sniffnoy 2y ago
Wait, in Swift it's illegal to multiply an int by a double?? So you would have to explicitly cast index to a double? I definitely didn't expect that!
- manmal 2y ago
  One could overload the * infix operator to support this type of multiplication. It just doesn’t come with the standard library.
- jshier 2y ago
  No cast, just a conversion, depending on how you want the math to work. int * double would usually be Double(int) * double.
- wlesieutre 2y ago
  You could overload * if you really don't want to convert the int manually
- redwoolf 2y ago
  I think this is the correct way to handle this. I don’t know how many times I’ve been stymied by integer arithmetic and precision loss by implicit conversion. How should this be handled? Should the int be converted to a double before the operation, should the double be converted to int before the operation, or should the result be converted to an int or a double? As someone who writes code in many languages in a day, these implicit conversion rules can be difficult to remember. It’s best to enforce the developer to be explicit about the intention.
  - Dylan16807 2y ago
    > Should the int be converted to a double before the operation, should the double be converted to int before the operation, or should the result be converted to an int or a double? Isn't it pretty evident that implicit conversions should only go from integer to floating point? > precision loss by implicit conversion That's a reasonable worry, but "Int" in general is only safe to store 32 bits, and 32 bit integers will losslessly convert to doubles.
pajuc 2y ago
It's really hard for me to read past Lattner's quote. "Beautiful minimal syntax" vs "really bad compile times" and "awful error messages". I know it's not helpful to judge in hindsight, lots of smart people, etc. But why on earth would you make this decision for a language aimed at app developers? How is this not a design failure? 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. Can someone shed some light on this to make it appear less stupid? Because I'm sure there must be something less stupid going on.
- refulgentis 2y ago
  Here's some light to make it appear less stupid: He doesn't claim its not a design failure. He doesn't say they sat down and said "You know what? Lets do beautiful minimal syntax but have awful error messages & really bad compile times" The light here is recursive. As you lay out, it is extremely s̶t̶u̶p̶i̶d̶ unlikely that choice was made, actively. Left with an unlikely scenario, we take a step back and question if we have any assumptions: and our assumption is they made the choice actively.
  - jb1991 2y ago
    The world is this even saying.
    - jerbear4328 2y ago
      The designers of the language didn't intend for it to end up this way, it just worked out like it did. GP is pointing out that their parent assumed it was intentionally choosing pretty syntax over speed, when it was more likely for them to start with the syntax without considering speed.
      - pajuc 2y ago
        What's the difference between "choosing pretty syntax over speed" and "start with syntax without considering speed"?
tantalor 2y ago
> they’re invalid swift If this isn't valid why are we even taking about it? The compiler should report syntax error or something
- deleted 2y ago
  [deleted]
- redwoolf 2y ago
  That’s the point. It’s invalid swift syntax, but it takes >40 seconds to tell you that.
- Jtsummers 2y ago
  The point is that it's valid syntax (invalid syntax is found in an earlier phase of compilation and would report much faster). It's invalid in Swift's type system, and it takes it 42 seconds (in the string example) and 8 seconds (in the math expression one) for it to tell you that it can't type-check it in a reasonable time and then it quits.
  - tantalor 2y ago
    "Reasonable time" is subjective. What happens if you don't limit the time? Guesses: 1. Successfully compiles 2. Reports an error 3. Never halts 4. Nobody knows
- Dylan16807 2y ago
  If there was just the right overload hiding somewhere, it wouldn't be an error and it would take a similar amount of time. This is just the easiest way to show off the problem, which is how long it takes to check.
vlovich123 2y ago
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.
- jerf 2y ago
  I think it would also be interesting for the compiler to modify the source code (with a flag, presumably, or possibly through the local LSP server) with the solved result as needed. This would also feedback to the programmer what the problem is, what the compiler thought the solution is (and under the circumstances, while it can't be "wrong" there's a decent chance it is suboptimal or not what the programmer expected), and not require future caching. I kind of feel like that for more advanced languages this sort of back-and-forth between the type checker and the language has some potential to it.
  - irq-1 2y ago
    Why not make it a warning if the compiler leaves the happy path? The fix is easy for the programmer (enums, casting, etc.) and could be left unfixed if the programmer knows its OK (meaning it wont take 42 seconds and give an error.) The LSP would have to know when the compiler ran into this, but if the compiler can identify the type explosion problem, it can tell the LSP.
- JackYoustra 2y ago
  I don't think it comes up in obscure corner cases now with SwiftUI's builder types being concrete, especially with overloaded callbacks like in ForEach Edit: I just remembered my favorite one: I had a view where the compile times doubled with every alert I added to it.
- fweimer 2y ago
  I think the challenge here is that it only happens for a type error, not a successful compilation. Each time this happens, the programmer would try to fix the type error, usually invalidating the cache. I'm not so sure the problem is intractable because it's so well-structured. Someone would have to look at it and check that there aren't any low-hanging fruits. The challenge might be that anyone who could fix this could make much more impactful contributions to the compiler. But it's hard to know without trying.
tinganho 2y ago
Isn’t the channel variable declared and inferred as an int32? Can’t see why the overload isn’t resolved directly?
- extrabajs 2y ago
  The problem isn’t that the type inference can’t figure out that it’s a number (it can). Subtyping makes inference difficult. There may be a function somewhere which takes arguments that could be made to accept a string and an int32 (or whatever other number type that literal could be).
withoutboats3 2y ago
I'm suspicious about the truth of this claim. I don'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's these "expressive" features which have made type inference in Swift far more computationally complex, not type inference itself. And certainly not bidirectional type inference; the author of this post's definition of this concept isn'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 & child nodes). I don't know if the mistake comes from the post author or Chris Lattner, and I don't know if the word "bidirectional" is relevant to Swift's typing; I don't know if Swift has a formal description of its type system or that formal description is bidirectional or not. EDIT: watching the video the Chris Lattner quote comes from, it appears the mistake about the word "bidirectional" 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't make this distinction, causing the problems he describes. "Bottom up" type checking is just a specific pattern of bidirectional type checking. 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. cf: https://arxiv.org/abs/1908.05839 https://arxiv.org/abs/1908.05839
- lamontcg 2y ago
  I'd trade type inference for expressibility (function and operator overloading in particular). But this seems to currently be a heretical opinion.
  - Tuna-Fish 2y ago
    Rust took the other road: error[E0277]: cannot add `i64` to `i32` 1i32 + 2i64; ^ no implementation for `i32 + i64` It bothered me at first, there are a lot of explicit annotations for conversions when dealing with mixed precision stuff. But I now feel that it was the exactly correct choice, and not just because it makes inference easier.
putzdown 2y ago
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.
ebri 2y ago
All those Swiftie haters
deleted 2y ago
[deleted]
erichocean 2y ago
There are fast type inference algorithms available today, such as MLStruct. [0] [0] https://github.com/hkust-taco/mlstruct https://github.com/hkust-taco/mlstruct
ashdnazg 2y ago
Our CI posts a list of shame with the 10 worst offending expressions on every PR as part of the build and test results. So far it'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.
mrkeen 2y ago
HM works great for me. Let's try it elsewhere instead of blaming the algorithm! {-# LANGUAGE OverloadedStrings #-} -- Let strings turn into any type defining IsString {-# LANGUAGE GeneralizedNewtypeDeriving #-} -- simplify/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 = "127.0.0.1" let username = "steve" let password = "1234" let channel = "11" let url = "http://" <> username <> ":" <> password <> "@" <> address <> "/api/" <> channel <> "/picture" 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) Do we think I've captured the combinatorics well enough? The url expression is 9 adjoining expressions, where each expression (and pair of expressions, and triplet of expressions ...) could be 1 of at least 31 types. $ ghc --version The Glorious Glasgow Haskell Compilation System, version 9.0.2 $ time ghc -fforce-recomp foo.hs [1 of 1] Compiling Main ( foo.hs, foo.o ) Linking foo ... real 0m0.544s user 0m0.418s sys 0m0.118s Feels more sluggish than usual, but bad combinatorics shouldn't just make it slightly slower. I tried compiling the simplest possible program and that took `real 0m0.332s` so who knows what's going on with my setup...
- ash_gti 2y ago
  Your example is different than the example in the post. Specifically, `channel = 11`, an integer. If it was a string then it parses very quickly.
  - mrkeen 2y ago
    If what your saying is true (the type is fixed as an integer), then it's even easier in tfa's case. No inference necessary. In my code channel is not a string, it's one type of the 31-set of (String, Foo01, Foo02, .., Foo30). So it needs to be inferred via HM. > If it was a string then it parses very quickly. "Parses"? I don't think that's the issue. Did you try it? ----- EDIT ------ I made it an Int let channel = 11 :: Int instance IsString Int where fromString = undefined instance Semigroup Int where (<>) = undefined real 0m0.543s user 0m0.396s sys 0m0.148s
pshirshov 2y ago
Scala does essentially the same and a lot faster, so it's not a fundamental limitation.
w10-1 2y ago
This article doesn't even mention the new type checker and constraint solver. The compiler is open-source, and discussed on open forums. Readers would love some summary/investigation into slow-down causes and prospects for fixes.
dmurray 2y ago
> 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 +. This really seems like a design flaw. If there are 59,049 overloads for string concatenation, surely either - one of them should be expressive enough to allow concatenation with an integer, which we can do after all in some other languages - 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. Is this unreasonable? Probably there's some theorem about why I'm wrong.

266 points by paraboul 2y ago

They never will, since it's also one of Swift'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'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.

fooker 2y ago
>chronically under resourced This is very true, Apple sees compiler jobs as a cost center.
tmpz22 2y ago
I think this is a unfair characterization. Yes Apple's developer ecosystem has a lot of fair complaints, I've personally run into the issues in this article particularly with newer APIs like SwiftData's #Predicate macro. But we just saw two days ago a lot of concerted issues to fix systemic problems like XCode the editor, or with compile times with Explicit Module improvements. I think you're painting with too heavy a brush. Apple clearly is dedicating resources to long-tail issues. We just saw numerous examples two days ago at WWDC24.
- jshier 2y ago
  No, this is just the typical Apple cycle I alluded too. Improvements are saved up for WWDC, previewed, then regress over the next year as other work is done, only for the process to repeat. They've demonstrated small improvements practically every year, yet the compiler continues to regress in build performance. Notably, the explicit module build system you mentioned regresses my small project's build time by 50% on an M1 Ultra. And even without it, overall build performance regressed 10 - 12% on the same project.
- plorkyeran 2y ago
  Explicit modules make build times worse, not better. Yes, this is the exact opposite of what Apple claims they do, and I am genuinely baffled by the disconnect. Usually Apple's marketing is at least directionally true even if they overstate things, but in this case the project appears to have entirely failed to deliver on what it was supposed to do but it's still being sold as if it succeeded. On top of that, the big thing we didn't see announced this year was anything at all related to addressing the massive hit to compile times that using macros causes.
adamnemecek 2y ago
[flagged]

fooker 2y ago

This is not a fixable flaw. Solving these constraints efficiently can definitely get you a Turing award, it's basically the SAT problem. 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.

coldpie 2y ago
It sort of is fixable, though. If you think about it, the problem is a bunch of functions are all mapped to one of a small set of names: +*/, etc. That is, the operators. If we didn't try to cram all this functionality into a tiny handful of symbols because of some weak analogy they have with basic math operations[1], then the compiler would have far fewer name conflicts to try to disambiguate, and the problem goes away on its own. Like yeah, the problem still exists if we made a few dozen functions all called "a", but the solution is to not do that, not give up on an otherwise fine type system. I'm convinced operator overloading is an anti-feature. It serves two purposes: 1) to make a small set of math operations easier to read (not write), in the case where there are no mistakes and all readers perfectly understand the role of each operator; and, 2) to make library developers feel clever. Operator-named functions are strictly worse than properly named functions for all other uses. Yes, yes, person reading this comment, I know you like them because they make you feel smart when you write them, and you're going to reply with that one time in university that you really needed to solve a linear algebra problem in C++ for some reason. But they really are terrible for everyone who has to use that code after you. They're just badly named functions, they're un-searchable, they make error messages unreadable, and they are the cause the naming conflict that is at the root of the linked blog post. It's time to ditch operator overloading. [1] Or because they look like the same symbol used in some entirely other context, god, please strike down everyone who has ever written an operator-/ to combine filesystem paths.
- Apocryphon 2y ago
  So you’re saying one potential solution is to use the APL character set?
- fooker 2y ago

irdc 2y ago

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.

jandrese 2y ago
At the very least it seems like the compiler could math out how many possible states it is about to check and if the value is unreasonable instantly error out instead of trying to chew on it for over half a minute before giving up.
rudedogg 2y ago
These type inference landmines are all over the place with SwiftUI too. I run into them with View/Shape/Color frequently
cerved 2y ago
I'm not sure I would draw the same conclusion, stricter requirements on typing is less cumbersome these days with better auto complete and LLMs
- deleted 2y ago
  [deleted]
hinkley 2y ago
Deltas and caches need some work too. It's a little unfortunate that my compile time is more affected by the amount of code that didn't change than the code I changed. One of the features of Rational was that it would distribute precompiled headers around. Whoever changed the header files had to pay to recompile them, but everyone else just got the results instead.

liuliu 2y ago

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

manmal 2y ago
Does this improve when declaring all variables with explicit types before using them in expressions?
- liuliu 2y ago
  Yeah, but people do like to write y = .log(x * 0.1) + (1.24).squareRoot() type of expressions for what Python did best (NumPy and PyTorch).
wiseowise 2y ago
> what if Swift can replace Python What a ridiculous statement. I’m willing to bet everything I have in life that this is never going to happen.
- liuliu 2y ago
  In retrospective, yes. But Swift for TensorFlow and similar projects received much attention at a time. (Also see Mojo as another attempt).
- fire_lake 2y ago
  Probably not Swift, but you know at some point Python will be surpassed in popularity by something else right? This has happened many times to programming languages in the past.

temp123789246 2y ago

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?

deleted 2y ago
[deleted]
tines 2y ago
Is it that Haskell, at least, doesn't support overloading in the same way as Swift? I don't know either of them well enough to be sure. It seems like there's a combinatorial explosion of possible overloads in Swift, whereas if you implement a function with the same ergonomics in Haskell (e.g. a printf-like function), the only thing the compiler has to do is ask "Does type X have an implementation for typeclass Show? Yes? Done." Essentially Haskell solved this overload inference problem in the same way that iterators solve the M*N problem for basic algorithms: convert all these disparate types to a single type, and run your algorithm on that.
- ackfoobar 2y ago
  "Does type X have an implementation for typeclass Y" isn't always easy to answer. https://aphyr.com/posts/342-typing-the-technical-interview https://aphyr.com/posts/342-typing-the-technical-interview
  - tines 2y ago
    That post, while awesome (as is the rest of aphyr's stuff), is a lot to wade through to get to the point you're trying to convey. Can you spell it out for me?
    - ackfoobar 2y ago
      That typeclass resolution can encode some heavy computation, the example being n-queens in the article.

peppertree 2y ago

I have a feeling it'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.

ajkjk 2y ago

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?

novok 2y ago
There are a bunch of other chokepoints, but type inference is a big part of it: https://github.com/apple/swift/blob/main/docs/CompilerPerformance.md https://github.com/apple/swift/blob/main/docs/CompilerPerfor... Another thing I would add to swift as a flag is to make imports based on specific files vs. an abstract "module", there is a lot of repeated work that happens because of that last time I looked.
floxy 2y ago
Yes, I've never written a line of Swift, but these cases don't seem to be of the usual variety that cause Hindley-Milner to blow up. It seems like the Swift compiler source is available, and these test cases are small. This is encouragement for someone to spend a small amount of time digging into this, just for the curiosity of it. And I mean, just something like, fire it up in the debugger, start the compiler on one of these test cases, interrupt the when it looks like it is "hung", but before it times out. Step through the code a bit, to identify the handful of functions that that we're looping through, and then report out what you find, and your best guess, the algorithm is implemented correctly and is hopelessly intractable, or "hey, didn't we already check down this branch previously?". I'll give you my next upvote on HN. https://static.aminer.org/pdf/20170130/pdfs/popl/o8rbwxmj6h2cxf7qdezlupsbgn5u40wn.pdf https://static.aminer.org/pdf/20170130/pdfs/popl/o8rbwxmj6h2... https://github.com/apple/swift https://github.com/apple/swift
hinkley 2y ago
It's very hard to track time complexity when you nest multiple layers of delegation.

Decabytes 2y ago

I'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/documentation assumes you are using Xcode. 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'm just wary because Apple really doesn't have any incentive to support it. 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

giancarlostoro 2y ago
The only thing holding it back is Apple not investing into making it happen. Swift is in a weird spot where it has so much potential, but without investment in the tooling for other platforms (which is uncommon for Apple in general) it just wont happen, at least not as quickly as it could.
- refulgentis 2y ago
  I wouldn't describe Swift itself as having so much potential: I loved it and advocated for it, for years. After getting more experience on other platforms and having time to watch how it evolved, or didn't as per TFA, it's...okay to mediocre compared to peers - Kotlin, Dart, Python come to mind. If Foundation was genuinely cross platform and open source, that description becomes more plausible for at least some subset of engineers. * (for non-Apple devs, Foundation ~= Apple's stdlib, things like dateformatting) I don't mean to be argumentative, I'm genuinely curious what it looks like through someone else's eyes and the only way to start that conversation is taking an opposing position. I am familiar with an argument it's better than Rust, but I'd very curious to understand if "better than" is "easier to pick up" or "better at the things people use Rust for": i.e. I bet it is easier to read & write, but AFAIK it's missing a whole lot of what I'll call "necessary footguns for performance" that Rust offers. * IIRC there is a open source Foundation intended for Linux? but sort of just thrown at the community to build.

PaulHoule 2y ago

One of the interesting tradeoffs in programming languages is compile speed vs everything else. If you'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've been blown away by the "uv" 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. On the other hand, there's a less popular argument that the focus on speed is a reason why we can't have nice things and, for people working on smaller systems, languages should be focused on other affordances so we have things like https://www.rebol.com/ https://www.rebol.com/ One area I've thought about a lot is the design of parsers: for instance there is a drumbeat you hear about Lisp being "homoiconic" 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. As for the kind of problem he's worried about (algorithms that don't scale) one answer is compilation units and careful caching.

kettlecorn 2y ago
> One of the interesting tradeoffs in programming languages is compile speed vs everything else. In the case of Rust it's more of a cultural choice. Early people involved in the language pragmatically put everything else (correctness, ability to ship, maintainability, etc.) before compilation speed. Eventually the people attracted to contribute to the language weren't the sort that prioritized compilation speed. Many of the early library authors reflected that mindset as well. That compounds and eventually it's very difficult to crawl out from under. I suspect the same is true for other languages as well. It's not strictly a bad thing. It's a tradeoff but my point is that it's less of an inevitability than people think.
- throwaway894345 2y ago
  I think most people haven't used many languages that prioritize compilation speed (at least for native languages) and maybe don't appreciate how much it can help to have fast feedback loops. At least that's the feeling I get when I watch the debates about whether Go should add a bunch more static analysis or not--people argue like compilation speed doesn't matter at all, while _actually using Go_ has convinced me that a fast feedback loop is enormously valuable (although maybe I just have an attention disorder and everyone else can hold their focus for several minutes without clicking into HN, which is how I got here).

Sniffnoy 2y ago

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

manmal 2y ago
One could overload the * infix operator to support this type of multiplication. It just doesn’t come with the standard library.
jshier 2y ago
No cast, just a conversion, depending on how you want the math to work. int * double would usually be Double(int) * double.
wlesieutre 2y ago
You could overload * if you really don't want to convert the int manually
redwoolf 2y ago
I think this is the correct way to handle this. I don’t know how many times I’ve been stymied by integer arithmetic and precision loss by implicit conversion. How should this be handled? Should the int be converted to a double before the operation, should the double be converted to int before the operation, or should the result be converted to an int or a double? As someone who writes code in many languages in a day, these implicit conversion rules can be difficult to remember. It’s best to enforce the developer to be explicit about the intention.
- Dylan16807 2y ago
  > Should the int be converted to a double before the operation, should the double be converted to int before the operation, or should the result be converted to an int or a double? Isn't it pretty evident that implicit conversions should only go from integer to floating point? > precision loss by implicit conversion That's a reasonable worry, but "Int" in general is only safe to store 32 bits, and 32 bit integers will losslessly convert to doubles.

pajuc 2y ago

It's really hard for me to read past Lattner's quote. "Beautiful minimal syntax" vs "really bad compile times" and "awful error messages". I know it's not helpful to judge in hindsight, lots of smart people, etc. But why on earth would you make this decision for a language aimed at app developers? How is this not a design failure? 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. Can someone shed some light on this to make it appear less stupid? Because I'm sure there must be something less stupid going on.

refulgentis 2y ago
Here's some light to make it appear less stupid: He doesn't claim its not a design failure. He doesn't say they sat down and said "You know what? Lets do beautiful minimal syntax but have awful error messages & really bad compile times" The light here is recursive. As you lay out, it is extremely s̶t̶u̶p̶i̶d̶ unlikely that choice was made, actively. Left with an unlikely scenario, we take a step back and question if we have any assumptions: and our assumption is they made the choice actively.
- jb1991 2y ago
  The world is this even saying.
  - jerbear4328 2y ago
    The designers of the language didn't intend for it to end up this way, it just worked out like it did. GP is pointing out that their parent assumed it was intentionally choosing pretty syntax over speed, when it was more likely for them to start with the syntax without considering speed.
    - pajuc 2y ago
      What's the difference between "choosing pretty syntax over speed" and "start with syntax without considering speed"?

tantalor 2y ago

> they’re invalid swift If this isn't valid why are we even taking about it? The compiler should report syntax error or something

deleted 2y ago
[deleted]
redwoolf 2y ago
That’s the point. It’s invalid swift syntax, but it takes >40 seconds to tell you that.
Jtsummers 2y ago
The point is that it's valid syntax (invalid syntax is found in an earlier phase of compilation and would report much faster). It's invalid in Swift's type system, and it takes it 42 seconds (in the string example) and 8 seconds (in the math expression one) for it to tell you that it can't type-check it in a reasonable time and then it quits.
- tantalor 2y ago
  "Reasonable time" is subjective. What happens if you don't limit the time? Guesses: 1. Successfully compiles 2. Reports an error 3. Never halts 4. Nobody knows
Dylan16807 2y ago
If there was just the right overload hiding somewhere, it wouldn't be an error and it would take a similar amount of time. This is just the easiest way to show off the problem, which is how long it takes to check.

vlovich123 2y ago

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.

jerf 2y ago
I think it would also be interesting for the compiler to modify the source code (with a flag, presumably, or possibly through the local LSP server) with the solved result as needed. This would also feedback to the programmer what the problem is, what the compiler thought the solution is (and under the circumstances, while it can't be "wrong" there's a decent chance it is suboptimal or not what the programmer expected), and not require future caching. I kind of feel like that for more advanced languages this sort of back-and-forth between the type checker and the language has some potential to it.
- irq-1 2y ago
  Why not make it a warning if the compiler leaves the happy path? The fix is easy for the programmer (enums, casting, etc.) and could be left unfixed if the programmer knows its OK (meaning it wont take 42 seconds and give an error.) The LSP would have to know when the compiler ran into this, but if the compiler can identify the type explosion problem, it can tell the LSP.
JackYoustra 2y ago
I don't think it comes up in obscure corner cases now with SwiftUI's builder types being concrete, especially with overloaded callbacks like in ForEach Edit: I just remembered my favorite one: I had a view where the compile times doubled with every alert I added to it.
fweimer 2y ago
I think the challenge here is that it only happens for a type error, not a successful compilation. Each time this happens, the programmer would try to fix the type error, usually invalidating the cache. I'm not so sure the problem is intractable because it's so well-structured. Someone would have to look at it and check that there aren't any low-hanging fruits. The challenge might be that anyone who could fix this could make much more impactful contributions to the compiler. But it's hard to know without trying.

tinganho 2y ago

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

extrabajs 2y ago
The problem isn’t that the type inference can’t figure out that it’s a number (it can). Subtyping makes inference difficult. There may be a function somewhere which takes arguments that could be made to accept a string and an int32 (or whatever other number type that literal could be).

withoutboats3 2y ago

I'm suspicious about the truth of this claim. I don'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's these "expressive" features which have made type inference in Swift far more computationally complex, not type inference itself. And certainly not bidirectional type inference; the author of this post's definition of this concept isn'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 & child nodes). I don't know if the mistake comes from the post author or Chris Lattner, and I don't know if the word "bidirectional" is relevant to Swift's typing; I don't know if Swift has a formal description of its type system or that formal description is bidirectional or not. EDIT: watching the video the Chris Lattner quote comes from, it appears the mistake about the word "bidirectional" 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't make this distinction, causing the problems he describes. "Bottom up" type checking is just a specific pattern of bidirectional type checking. 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. cf: https://arxiv.org/abs/1908.05839 https://arxiv.org/abs/1908.05839

lamontcg 2y ago
I'd trade type inference for expressibility (function and operator overloading in particular). But this seems to currently be a heretical opinion.
- Tuna-Fish 2y ago
  Rust took the other road: error[E0277]: cannot add `i64` to `i32` 1i32 + 2i64; ^ no implementation for `i32 + i64` It bothered me at first, there are a lot of explicit annotations for conversions when dealing with mixed precision stuff. But I now feel that it was the exactly correct choice, and not just because it makes inference easier.

putzdown 2y ago

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.

ebri 2y ago

All those Swiftie haters

deleted 2y ago

[deleted]

erichocean 2y ago

There are fast type inference algorithms available today, such as MLStruct. [0] [0] https://github.com/hkust-taco/mlstruct https://github.com/hkust-taco/mlstruct

ashdnazg 2y ago

Our CI posts a list of shame with the 10 worst offending expressions on every PR as part of the build and test results. So far it'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.

mrkeen 2y ago

HM works great for me. Let's try it elsewhere instead of blaming the algorithm! {-# LANGUAGE OverloadedStrings #-} -- Let strings turn into any type defining IsString {-# LANGUAGE GeneralizedNewtypeDeriving #-} -- simplify/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 = "127.0.0.1" let username = "steve" let password = "1234" let channel = "11" let url = "http://" <> username <> ":" <> password <> "@" <> address <> "/api/" <> channel <> "/picture" 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) Do we think I've captured the combinatorics well enough? The url expression is 9 adjoining expressions, where each expression (and pair of expressions, and triplet of expressions ...) could be 1 of at least 31 types. $ ghc --version The Glorious Glasgow Haskell Compilation System, version 9.0.2 $ time ghc -fforce-recomp foo.hs [1 of 1] Compiling Main ( foo.hs, foo.o ) Linking foo ... real 0m0.544s user 0m0.418s sys 0m0.118s Feels more sluggish than usual, but bad combinatorics shouldn't just make it slightly slower. I tried compiling the simplest possible program and that took `real 0m0.332s` so who knows what's going on with my setup...

ash_gti 2y ago
Your example is different than the example in the post. Specifically, `channel = 11`, an integer. If it was a string then it parses very quickly.
- mrkeen 2y ago
  If what your saying is true (the type is fixed as an integer), then it's even easier in tfa's case. No inference necessary. In my code channel is not a string, it's one type of the 31-set of (String, Foo01, Foo02, .., Foo30). So it needs to be inferred via HM. > If it was a string then it parses very quickly. "Parses"? I don't think that's the issue. Did you try it? ----- EDIT ------ I made it an Int let channel = 11 :: Int instance IsString Int where fromString = undefined instance Semigroup Int where (<>) = undefined real 0m0.543s user 0m0.396s sys 0m0.148s

pshirshov 2y ago

Scala does essentially the same and a lot faster, so it's not a fundamental limitation.

w10-1 2y ago

This article doesn't even mention the new type checker and constraint solver. The compiler is open-source, and discussed on open forums. Readers would love some summary/investigation into slow-down causes and prospects for fixes.

dmurray 2y ago

> 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 +. This really seems like a design flaw. If there are 59,049 overloads for string concatenation, surely either - one of them should be expressive enough to allow concatenation with an integer, which we can do after all in some other languages - 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. Is this unreasonable? Probably there's some theorem about why I'm wrong.