8 ms·
Why is Swift so slow (timeout) in compiling this code? (2022)
- _w5kd 3y ago[flagged]
- danpalmer 3y agoI recommend reducing the warning limit on slow compilation in Swift. -Xfrontend -warn-long-function-bodies=<limit-ms> -Xfrontend -warn-long-expression-type-checking=<limit-ms> Set these to ~100ms and add a few explicit types whenever they log, and compile time will be significantly improved. Swift is a slow compiler in exceptional cases, maybe in the 99th percentile, but when you know where this is happening it's fairly trivial to avoid it and keep the compiler nimble and stay productive as an engineer.
- iainmerrick 3y agoIn this particular case, adding an explicit type didn’t help at all. I’ve worked in a large Swift project with those timeout warnings enabled, and didn’t find them too helpful. They showed up a lot and it was rarely obvious how to quickly fix them. Possibly it would have been useful if those warnings were enabled from the start and developers had always fixed them proactively. I’m skeptical that that could work in a big fast-moving team project, though.
- danpalmer 3y agoI think it's reasonable to have a warnings-are-errors approach even in medium sized teams, or if not quite that approach perhaps a "warnings go in the bug tracker" approach. I'm far from a Swift expert, but I usually found I could reduce the compilation time with ~10 mins of work. When I turned these on for a small codebase (60k lines, ~50% of an engineer split across 3 people), it only took a few hours to solve all the instances of this, and they were mostly obvious cases where a 100 line function could be split into 3 and solve the issue.
- addaon 3y agoWarnings-as-errors is a great policy in general, but these are non-deterministic warnings based on compile time wall timing. Coworker working on a slower computer than you? He can run into hundreds of errors after a pull that you introduced but couldn't see, what now? Running something intensive in the background? You can't compile successfully any more. Not ideal.
- danpalmer 3y agoThat's true, but a setting of 100ms is a few orders of magnitude higher than expressions should be so it's quite possible to make this fairly reliable.
- addaon 3y agoThe problem is that if this ever catches anything, then there's things that it almost catches. And you have no way of telling if you have something expression that takes 99 ms on your machine, so will take 101 ms on your coworkers'. The appropriate way to deal with this in general is to have separate warning and error thresholds, where the difference between the two is greater than the variance between machines, e.g. 50 ms and 100 ms; at least in this case when your coworker checks out a broken build he can see that warnings were introduced in your commit in a CI build log and track it down to the source.
- 3y ago
- titzer 3y ago> it's fairly trivial to avoid it and keep the compiler nimble Personally I think it's the job of tools to make humans productive instead of the other way around.
- danpalmer 3y agoI see what you mean, but in this case it's that the Swift compiler is keeping you productive by doing a ton of work for you, and asking for a little clarity every now and again so that it doesn't have to do exhaustive searches of what you mean.
- deleted 3y ago[deleted]
- londons_explore 3y agoFor OP's specific case, wouldn't it be better to just special case the compiler to detect that it is a large vector, and pick the same datatype for all elements of the vector? Suddenly an exponential search becomes linear.
- stonemetal12 3y agoYou would think the part of the compiler that parses integer literals would assign them the type integer, making this close to a no op for the type checker.
- slavapestov 3y agoNot the case when you have polymorphic literals, like in Swift or Haskell: let x: Int = 123 let y: Double = 123 But it looks like here the problem was not the type checker anyway.
- tambourine_man 3y agoI was very excited when Swift was announced. I always hated ObjC’s syntax and Swift’s looked awesome. Today I get the felling that Swift is a science project used by millions and backed by a trillion dollar company.
- klodolph 3y agoI used to see the compiler run away, consuming all available RAM and CPU, back in the early days of Mac OS X. So this is not necessarily something unique to Swift. Then there was the ill-fated garbage collection system that got bolted onto Objective C. At some point after the compiler got fixed, ARC was added, and the GC was deprecated, in 2012, is the point in time when Cocoa development felt solid (to me). I don’t know how you’d escape this. Other platforms have their own problems. As far as I can tell, they’re all science projects, because our understanding of language design and library design keeps changing.
- tambourine_man 3y agoPerhaps, but I feel Swift was too ambitious too early.
- klodolph 3y agoI think a certain amount of ambition is necessary if you’re making a language for general use. You get important feedback from real-world use, and that means you need a population of developers willing to take risks on new languages. If we go by the Objective C timeline, Swift will be pretty good in the year 2042.
- iainmerrick 3y agoAt some point after the compiler got fixed, ARC was added, and the GC was deprecated, in 2012, is the point in time when Cocoa development felt solid (to me). Seconded -- Obj-C was really nice to work with at that time. I do like a lot of the new stuff in Swift, but in many ways it’s a return to the bad old days in terms of the overall dev experience.
- jws 3y agoIn this case, Swift is being, lets say suboptimal, compiling an 8MB array of integers. It's worth mentioning another, more common, cause. There can be computational cost explosion when Swift resolves the types for function calls (and operators). You notice it when you get the "too complex" error, but you may be tolerating slow compiles which are just slightly less than too complex. A few explicit type annotations in these situations can do wonders for speeding your development cycle. Edit: redact I unfortunately can't tell you how to find these. Maybe a "give it a go with reduced complexity limit" compiler flag would help find them. Edit: Add see reply below for answer.
- stephencanon 3y agoAs a sibling mentioned, -warn-long-function-bodies=<limit-ms> and -warn-long-expression-type-checking=<limit-ms> can flag these for you. That said, we should also get these to be fast enough that we have to introduce new flags that take µs instead of ms.
- cmeacham98 3y agoLots of uses on that thread are suggesting this is some sort of design constraint or tradeoff - but I really am not sure I agree. I understand this might not be a high priority, because it's a somewhat contrived usecase rare to matter in "the real world", but I strongly suspect this must be due to bug(s) in the compiler. I cannot think of a single reason it _has_ to be this way per the design of the language.
- layer8 3y agoNot a bug, but probably a naive algorithm where a more sophisticated algorithm with much lower algorithmic complexity could be used.
- danpalmer 3y agoThere are different algorithms for type checking that impose different requirements on users. The Java approach is roughly: write types everywhere, keep them simple (and limited in scope), it's easy for the compiler to infer the types. The Haskell/ML approach is roughly: know a lot about strong type systems, be purely functional, infer most of the types, produce bad error messages when you can't. The Swift approach attempts to be the best of both worlds, lots of inference, strong capabilities in expressing complex types, but the trade-off is that it can't use the inference algorithms of either of the above examples. I believe Swift necessarily has poor time complexity in type checking – it can't be better with the design it has and requirements it puts on authors.
- kaba0 3y agoRust’s type system seems to be ideal in this respect, and is not prone to timing out, so it is likely some design issue with Swift.
- danpalmer 3y agoOn the contrary, Rust's type system moves more of that effort on to the developer – there's a reason why Rust has a much steeper learning curve than Swift. The trade-off is a somewhat rare sharp edge for Swift and a much easier onboarding, vs Rusts noticeably harder onboarding and more predictable sharp edges.
- hgs3 3y agoHuge literals do occur in programmatically generated source code. I'm working on a project now where I generate C source code with large, static tables. Paraphs this is not a common scenario for Swift's target use cases.
- d0100 3y agoI reported once that the Go compiler would oom when I had an array literal with quite a few entries It might have just been a few kb of text but I couldn't compile even with 16gb ram
- Joker_vD 3y ago> I wouldn't be surprised if "parse and compile 8MB of integer literals" isn't a very well optimized code path in the compiler, because nobody is parsing and compiling 8MB of integer literals outside of artificial exercises like this Actually, no. There is no portable "incbin" in C/C++, so one way to bake assets into the .rodata section is to convert a binary file into a huge "const unsigned char data[8192567] = { 0xFF, 0xD8, 0xFF, 0xE0, ... }" string and stash it into a .h or .c file. And yes, people do that often enough that gcc and clang actually had to optimize for this case specifically.
- tinus_hn 3y agoActually the xbm image format is c files like this with a long array of hexadecimal numbers. https://en.m.wikipedia.org/wiki/X_BitMap https://en.m.wikipedia.org/wiki/X_BitMap
- ajross 3y ago> Actually, no. There is no portable "incbin" in C/C++ I kinda hate this kind of argument. I mean, it's true, as .incbin is a GNU assembler directive (FWIW: binutils/llvm objcopy is a better mechanism still for this sort of thing in most contexts, as it doesn't involve source compilation of any kind). But it leads ridiculous design decisions, like "I'm going to write 8MB of source code instead of doing the portability work on my own to turn that data into a linkable symbol". There's a huge gulf in the space between "non-portable" and "impossible". In this case, the problem is trivially solved on every platform ever. Trivial problems should employ trivial solutions, even where they have to involve some per-platform engineering.
- jimbokun 3y agoThe link to the GitHub gist in the first message is returning a 404. Is there a link to the original code?
- c-fe 3y agoI have not managed to find it either, but based on the comments the issue seems to be with the testing of the algorithm, which contains something like ``` list = [1,2,3,4,5,6 ..., 7999, 8000] ``` i.e. a written out literal, that the swift compiler has trouble type-checking if everything in there is an int.
- slavapestov 3y agoLooks like the time was being spent in LLVM, not the type checker as everyone is assuming here: https://forums.swift.org/t/why-is-swift-so-slow-timeout-in-compiling-this-code/61382/5 https://forums.swift.org/t/why-is-swift-so-slow-timeout-in-c...
- thegreatbeanz 3y agoInteresting that the two highest functions in that trace relate to Bitcode serialization and GlobalISel. Why is Swift serializing Bitcode if it is also running ISEL in the same compile?
- marksands07 3y agoIs there anyone on the compiler team that also plays a role in llvm development and optimizations? Or is there anyone on the llvm core team that cares about optimizations that would directly benefit Swift? If there's no one available that either can or is willing to optimize llvm, this feels like a worst case scenario. I'm curious what steps need to be taken to see actual compiler performance gains as it relates to llvm.
- shusaku 3y agoI ran into a similar problem in a Fortran code, where a huge array was being assigned a bunch of literals one by one. The optimizing compiler slowed down substantially (though not to this extent), who knows what it hoped to find…
- codetrotter 3y agoI had a similar problem with Swift and some data. In the end what I ended up doing was to import it as JSON or binary plist or something at runtime. Not great. But at least I could compile my code again.
- iainmerrick 3y agoI know this is about Swift, but: Rust compiled in about a minute and the runtime was 2 secs That seems really slow as well! Since reading the same thing in JSON only takes a fraction of a second. I think it would be well worthwhile speeding up this kind of thing. Obviously a million-element static array isn’t common usage, but if you can find and fix the bottlenecks there, it will help make everyday usage faster too in lots of small ways.
- tialaramex 3y agoIn Rust you can include_bytes! a file if the situation is that you just want a whole bunch of data, as is often the case with practical systems, (the result of the include_bytes! macro is a &'static [u8; N] ie an immutable reference to an array of N unsigned bytes which lives forever). So for example you can write code which cares how long firmware.bin is, without needing to ensure the code is updated appropriately, and yet doesn't bake firmware.bin inside your finished binary, by writing something like const fw_length = include_bytes!("firmware.bin").len(); and the compiler can see we don't actually want the array at runtime, just its length, so the data evaporates from the output software. Parsing a programming language is just always going to be slower than just reading a file into memory, which is why Rust had include_bytes! from the outset and it's silly that C didn't do likewise even in 1989, let alone C++ in 1998. This particular exercise wants a machine-word size integer, so in Rust that's isize, but you could isize::from_le_bytes() or whatever with chunked conversions, which will happen at runtime but ought to go very much faster than parsing text.
- iainmerrick 3y agoOkay, but the question I’m asking is, why does the basic version take 60 seconds to compile? Why not 6 seconds, or 60 milliseconds? If there’s a good and insurmountable reason why it must be a minute and no less, okay. But I’d be amazed if there aren’t some easy wins to be made that could speed it up by a decent amount. That’s not worth doing just because of the silly million-element array case, of course; but if you can make that silly case faster, lots of more important use cases will get faster too.
- stephc_int13 3y agoCompilation time for most modern languages (Rust, Zig, Swift) is, to say the least, not great. I consider this a major hindrance for productivity. Fast iteration/test cycle is the best way to stay in the flow while fixing small bugs on the go. I'd say the limit for me is about five seconds, but I find it much better when I can keep it below one second. I think that Jai is engineered to have fast compilation in debug mode, I hope that will be the case once released.
- bsaul 3y agoZig is slow as well ??
- quic5 3y agoThe biggest bottleneck in Zig's case is LLVM. That's why they implement fast alternative backends for development. See: https://kristoff.it/blog/zig-new-relationship-llvm/ https://kristoff.it/blog/zig-new-relationship-llvm/
- bsaul 3y agolooks like the project's now abandonned : https://github.com/ziglang/zig/projects/2 https://github.com/ziglang/zig/projects/2
- hsn915 3y agoThis comment suggests otherwise: https://github.com/ziglang/zig/issues/89#issuecomment-1221188076 https://github.com/ziglang/zig/issues/89#issuecomment-122118... Although I'm not sure the "self hosted compiler" is the same as "llvm free backend".
- stefncb 3y agoIt's not. The self-hosted compiler still uses llvm, and it's still slow because of it.
- 3y ago
- bsaul 3y agoMy most frustating error with swiftc is the switch on enum "not being able to complete in acceptable time" (or something like that). Basically, when you want an exhaustive check on combination of enums, you're often reaching the limits of the compiler. something like this enum State { case A, … } switch (fromState, toState) { case (.A, .B): … } in which you want to make sure you didn't forget a combination.
- cellularmitosis 3y agoAt what sort of combinatorial size are you encountering this?
- bsaul 3y agoa switch over a pair of two values of the same enum type, containing 18 cases (some with associated values). It breaks at around 50 cases in the switch.
- littlestymaar 3y agoLooks like swiftc needs to embed a performant SAT solver ;) (I could not find the link anymore, but I remember reading a blog post about how Rust `match` statement are in fact solving an instance of SAT).
- slavapestov 3y agoSwift uses the algorithm from this paper: https://os.unil.cloud.switch.ch/tind-customer-epfl/07596cb2-d52f-4f11-9ae5-fb00f6276bbf?response-content-disposition=attachment%3B%20filename%2A%3DUTF-8%27%27p61-liu.pdf&response-content-type=application%2Fpdf&AWSAccessKeyId=ded3589a13b4450889b2f728d54861a6&Expires=1685543026&Signature=UN7oSRJf6O5eCZ%2FFHjMB6%2FN%2BwpU%3D https://os.unil.cloud.switch.ch/tind-customer-epfl/07596cb2-...
- munificent 3y agoI implemented a prototype version of the algorithm in that paper when exploring exhaustiveness checking for pattern matching in Dart. I found it pretty easy to understand, but also really easy to get it to generate huge combinatorially large spaces. Some careful memoization and deduplication helped, but even so I never got the performance to a state I felt comfortable with. Instead, I went with Luc Maranget's classic approach and figured out a way to adapt it to a language with subtyping (with a ton of work from Johnni Winther to figure out all of the hard complex cases around generics): https://github.com/dart-lang/language/blob/main/accepted/future-releases/0546-patterns/exhaustiveness.md https://github.com/dart-lang/language/blob/main/accepted/fut... The performance (in the prototype!) was dramatically better. You can always make pattern matching go combinatorial, but I haven't seen any real-world switches get particularly slow with our approach yet, and we have some fairly large tests of matching on tuples of enums.
- stephc_int13 3y agoSo I was curious and tried to compile/run a similar code on my machine with tcc. 1M elements array, included in the source code, then sorted with a random C quicksort implementation I found while googling (far from optimal) Compilation time : 154ms on first run, 95ms on successive runs. Run time : 693ms on first run, ~105ms on successive runs. The CPU is a 13900K.
- stephc_int13 3y agoI tried the same code with clang instead of tcc. Compilation time is 700-800ms. Run time is about half as tcc, compiled with -O3 (45-55ms)
- KerrAvon 3y agosounds right - tcc is a fast compiler, not an optimizing one. clang is faster than many, but optimizations take time to run.
- stephc_int13 3y agoYes, absolutely, this is a tradeoff. Running C code at 50% max speed is OK for me when running debug builds. Clang being slower to compile is not an issue because I can use tcc. Unfortunately I can't use all those nice C++ features with tcc.
- stephc_int13 3y agoAlso, it depends on the type of code. I tried to replace the quicksort with a radix sort, and the difference is much closer on this better optimized code (15ms vs 17ms).
- JohnMakin 3y agoReminds me a little bit of the time in an intermediate programming course where we had to write a variety of programs and the input was an enormous string containing the entire novel "Jane Eyre." I discovered very quickly that building a string by concatenating the input one word at a time in Java, my preferred language at that time, was a huge mistake, because of the way string literals work in Java. StringBuilder to the rescue! At first I was astounded at how slow it was, but when I learned how the underlying language semantics worked, it made sense.
- jandrese 3y agoWow, that's a fantastic exercise for a computer science class. Most classes only work on programs so small that students don't really get a feel for how things scale.
- JohnMakin 3y agoIt was one of my more memorable ones. It had ~50 exercises that I recall, and the core of the program was supposed to compute a word frequency list on the words in the novel (with a blacklist of words like common adjectives etc). The twist was you had to do it with a particular programming paradigm in mind each time - functional, object oriented, MVC, REST API, anything you could think of. It was very eye opening solving the exact same problem in so many different ways.
- smasher164 3y agoMy thinking for ways to avoid this scenario are: - If there is no concrete type that you can infer for the given literal, throw a type error. - If there is no concrete type that you can infer for the given literal, fall back to a default, e.g. Int. But this sort of situation is why backtracking during type inference can lead to pathological behavior.
- tbarbugli 3y agoTangent to this but Swift is slow in surprising ways: json decoding and decoding strings into date objects are insanely slow. Both are common operations for an iOS app (eg client/server app that decodes a json encoded payload) and I have no idea why not solved years ago. Another surprise is that Apple’s protobuf generator is able to produce iodiomatic Swift, the same is not true for Kotlin :)
- Alifatisk 3y agoThis might be an off-topic question but is Swift considered high-performance language? If not, is this a surprise?