Compiling Rust is NP-hard

https://niedzejkob.p4.team/rust-np/

by lovasoa • 5 years ago

417 208 5 years ago

niedzejkob.p4.team

What's the most efficient algorithm you can write to do this? As it turns out, you can't do well in the worst case — and we'll prove this by a reduction from SAT.

Correction: you can't do well in the worst case, assuming P ≠ NP (where "well" means "in polynomial runtime").

gizmo2• 5 years ago

Pedantic and wrong. Considering there is no known algorithm that can sat solve in P, nobody in the world can do well in the worst case. And if nobody can do it, then you can't do it either, for any you. QED.

FartyMcFarter2• 5 years ago

I'm not a native English speaker, but I thought "you can't do well" is equivalent to "it's impossible to do well", which is how I read the original sentence.

As an aside, I find it a bit ironic that you're complaining about pedantry while interpreting the "you" word literally.

gugagore• 5 years ago

It's awkward to abbreviate "in polynomial time" as "in P". P is a set of (decision) problems. We don't know that 3-SAT is in P. We don't know that it's not.

To say that a solver is not in P is a type error.

OgAstorga• 5 years ago

Your “proof” it’s more like. No one has ever stepped on Mars. Therefore no one will.

Yet another pedantic fallacy.

sischoel2• 5 years ago

While this is an interesting result, isn't basically every compiler NP-hard, because of register allocation?

srl2• 5 years ago

Compilers don't guarantee (or try to find) the absolute optimal allocation, right?

WJW• 5 years ago

This depends on the compiler of course. Most will not because it is not worth it, but I expect that there is at least one compiler out there with the option to exhaustively search the allocation space for that very last nanosecond of runtime optimization. Probably inside an HFT firm somewhere.

chrisseaton2• 5 years ago

No - you can express register allocation as an NP-hard problem if you want to, but you don’t have to and not all compilers do it like that. You don’t need an optimal register allocation - you get into diminishing returns very quickly.

sischoel2• 5 years ago

Yes, I hadn't thought about that before, but of course the difference here is that the Rust compiler cannot just produce a "good enough" result for pattern matching.

antientropic• 5 years ago

Or worse than NP-hard: C++ template instantiation and the C preprocessor are Turing complete. (Except that I believe C++ requires some fixed limit on the maximum instantiation depth, but even so it's still exponential complexity.)

rocqua2• 5 years ago

I believe you can encode paradoxes in C++ templating. Something about two specializations which are mutually impossible because they reference eachother. So you can say:

   A is of type T <=> B is not of type T
   B is of type T <=> A is not of type T

Where <=> is if and only if.

In which case it is paradoxical to say that A is of type T. But also paradoxical to say that A is not of type T.

Banana699• 5 years ago

the C preprocessor are Turing complete

That's surprising, the C preprocessor is pretty crippled. It's creator intentionally made it so people won't abuse it to create full blown mini languages.

Did you get things mixed up or is there actually a way the c preprocessor can be turing-complete ?

adrianN• 5 years ago

If you do a SSA transform of your program the register graphs are chordal. It turns you that coloring chordal graphs is easy: http://web.cs.ucla.edu/~palsberg/course/cs232/papers/HackGoo...

srl2• 5 years ago

TFA notes that rustc is not a particular _efficient_ SAT solver, taking something like 10^4 times as long as a commonly used algorithm [1] would on a small example.

So, I'm curious: what's the _strongest_ case one could make for including a more robust SAT solver as part of the exhaustiveness checking? Is there any reasonable place where this could matter? (Extremely autogenerated code?)

[1] https://en.wikipedia.org/wiki/DPLL_algorithm

ygra• 5 years ago

I was under the impression that cases where it would matter are typically code that wouldn't usually be written. E.g. C# and Java also can solve SAT as part of overload resolution with generic types and it's an interesting peculiarity, but not a pattern that is interesting enough to optimize. Perhaps that's the case here as well.

I could also imagine the compiler code being easy to read, understand and modify are often more valuable traits than compilation speed of highly atypical patterns in a language. But that may well depend on how atypical those are.

trissylegs2• 5 years ago

Rust's proc-macro system makes it pretty easy to create some hard to compile code. but there's many ways to generate very slow compiling code with proc macros.

Quekid5• 5 years ago

One perhaps-interesting use case might be to use the fastest possible solver in the case of compiling generated/foreign code, so basically code that's expected to always compile (but which still needs to be checked for safety).

One could even imagine using it as a first-pass for code and to just fall back to a slower-but-with-better-error-messages type checker if errors are found.

(Of course you'd end up with two orthogonal implementations of the type checker, but that might not even be a bad thing since you'd be easily able to check for inconsistencies between them, aka. type checker bugs.)

gpm• 5 years ago

If you were using rustc as some sort of JIT compiler compile times could become extremely important, and error messages less important, at which point things like this might be worth it.

If you wanted the SAT solver for some other reason (optimization? proving code correct?) it might make sense to use it for this too.

johncolanduoni3• 5 years ago

The fact that most dependently typed languages (which have a much higher propensity for complicated exhaustiveness checking when pattern matching) don’t use a serious SAT solver for this makes me doubt Rust would ever need to.

sanity31415• 5 years ago

Doesn't Liquid Haskell[1] use a SAT solver?

[1] https://ucsd-progsys.github.io/liquidhaskell-blog/

naasking• 5 years ago

Dependent typing goes beyond SMT and SAT, so those languages wouldn't be able to leverage those solvers except in specific circumstances. See the language F* [1], for instance.

[1] https://www.fstar-lang.org/

EdSchouten2• 5 years ago

It's only NP-hard if you want the compiler to give you proper warnings/errors, right? As far as I know, the first matching arm is used. This means that if a compiler doesn't do any analysis on it, but naively generates machine code to compare the value, then there is no complexity at all.

(Not saying that that's acceptable...)

tialaramex4• 5 years ago

Here's what Rust's compiler actually does today:

https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir_bu...

Rust lets you say either "There are four specific possible Clowns, and I want everybody to explicitly deal with that" or you can write #[non_exhaustive] to say "There are several Clowns, right now I defined four of them, but maybe I'll add more some day" in which case you are allowed to only write code for those four Clowns, but everybody else is obliged by the compiler to handle the case with more Clowns than that since they can't depend on there only being four, and they have no idea how to name the additional ones that don't yet exist.

So, a compiler that just punts is not a correct Rust compiler. It needs to do this analysis or it's compiling a different less useful language.

In the real world the (default) exhaustive case is great for types that reflect some truth about the world being modelled, where you really do mean that all the code relying on this enumerated type should refuse to compile and needs re-engineering if your list is subsequently discovered not to really be exhaustive. Teapot not withstanding, there are definitely only five PlatonicSolids, such as Tetrahedron and Cube. The non-exhaustive case is great for types that reflect a truth you know or strongly suspect will change and everybody using your system needs to be prepared for that up front. In 2016 the enumerated list of US FederalHolidays didn't need Juneteenth, but in 2021 it does, we don't want random code to blow up because it had never imagined Congress would make new ones.

EdSchouten2• 5 years ago

Sure. But a naive compiler whose only purpose is to stomp out a poorly optimized executable can safely ignore that annotation, right?

NieDzejkob4• 5 years ago

It still needs to ensure that one of the arms will always match. (just not executing any branch in that case is tricky, because the arms can return values)

remram• 5 years ago

It does not need to check, if it assumes it. mrustc works that way, it is not trying to check code, only compile valid code: https://github.com/thepowersgang/mrustc

This is similar to C/C++'s " undefined behaviors". There are things you can write that aren't valid for the language, but that compilers are not required to catch.

kadoban3• 5 years ago

I had not thought of pattern-exhaustiveness checking like that.

Isn't compiling several languages, including Rust, actually undecidable though? Seems like if your type system or metaprogramming systems are Turing complete, this has to be the case.

So that's ~worse than NP-hard already (though calling it NP-hard is still technically correct).

Zababa• 5 years ago

Rust's type system is undecidable. You can see a few languages listed here: https://3fx.ch/typing-is-hard.html

silon42• 5 years ago

I believe there are limits to recursion (as mentioned in link above), so not strictly true. Perhaps they are too big?

simiones• 5 years ago

This ends up in some discussion about what "compiling" actually means. Is macroexpanding a part of "compiling"?

Most languages with complex type systems avoid Turing completeness by having an explicit limit for all type level expansions - at least, that is how Java and C# do it.

kadoban3• 5 years ago

I think metaprogram expansion has to be considered part of compiling. You have sourcecode, you need machinecode. If the lang says that the process of getting there requires running some metaprogram, so be it.

For Rust I think the type system itself is probably enough though even without that. If neither type checking or metaprogramming are part of compiling, I think your (for hypothetical you) definition of compiling is a bit too restrictive.

CuriousCosmic2• 5 years ago

Compiling a complete language and verifying correctness is undecidable but that's not necessarily what Rust does.

The complier can still fail to compile/verify otherwise correct parts of a program. Because it's only operating on a subset of the entire possible language and it's not verifying all properties of the language, it's not quite undecidable but it is still very much NP-hard.

Languages like C, C++, or Ada on the other hand take the other approach. They compile all parts of the language but make little to no attempt to enforce correctness on all those parts. You see verifying compilers for those languages only allowing a subset that they can actually verify which is the same as Rust.

At the moment Rust the language is what the main Rust compiler says it is but once there are meaningfully different compilers you'll start to notice the issue a bit more and there will likely be parts of the language that one compiler can verify but the other can't (and therefore fail to compile).

kibwen4• 5 years ago

Any hypothetical standards-conformant Rust implementation would have to be as or more restrictive than rustc, not less. Something like mrustc, which performs no borrow checking, would not be allowed to call itself a conformant Rust implementation.

(I say hypothetical because until there's a spec, it's simply not feasible to build a conformant alternative implementation, as you'd need to be bug-for-bug compatible with rustc.)

ncmncm3• 5 years ago

[Rust is] not quite undecidable but it is still very much NP-hard.
Languages like C, C++, or Ada ... make little to no attempt to enforce correctness

Both statements are laughably false, but for different reasons.

Both are based on the Doctrine of Rust Exceptionalism, which requires that Rust is not just a variation on a theme, but fundamentally different from other languages. Like most doctrines, this one is indefensible.

Rust compilation, like C++ and Haskell, is undecideable, not just NP-hard. Non-terminating compilation is artificially curtailed, thus failing to produce an open set of what would have been correct programs.

The Rust compiler performs certain correctness checks that other languages do not. It rejects an infinite set of correct programs that its correctness checks cannot resolve. In this as in all other particulars, Rust is very much on the continuum with other languages. All strongly-typed languages perform a huge variety of correctness checks, some built-in, others programmed, with great success, rejecting the large majority of incorrect programs people write. As a consequence, it is very common for Rust, C++, and Haskell programs to run correctly the first time, once the compiler is satisified.

trissylegs2• 5 years ago

I think in Haskell you need to add:

    {-# LANGUAGE UndecidableInstances #-}

to get an Undecidable type system.

arianvanp4• 5 years ago

There are other language extensions to make the haskell type system undecidable. The classic example is `RankNTypes`

E.g. you can proof that type systems of rank n >= 3 are undecidable. [0]

I think that's why haskell has both Rank2Types and RankNTypes as a language extension. So you can still use higher rank types without running into decidability problems up to rank 2.

[0] https://dl.acm.org/doi/10.1145/182409.182456

arianvanp4• 5 years ago

Type checking /compiling often is conservative for this purpose. It's sound (Rejects all incorrect programs), decideable (There is an algorithm to reject all incorrect programs) but due to Godel's decidability problem they're incomplete (There are always correct programs which the type checker rejects as incorrect).

There are exceptions of course (C++ templating is turing complete; so type-checking is undecidable) but often you want your compiler to be sound and decidable

Also see https://3fx.ch/typing-is-hard.html

(edit: Apparently , as the link I posted shows, rust is indeed undecidable in certain edge cases. However you can usually reason about a subset of the language (Restrict using certain features) that is still decidable. I have the feeling Rust might have such a subset but it's just a fuzzy feeling)

thaumasiotes4• 5 years ago

It's sound (Rejects all incorrect programs), decidable (There is an algorithm to reject all incorrect programs) but due to Godel's decidability problem they're incomplete (There are always correct programs which the type checker rejects as incorrect).

Isn't that the definition of "semidecidable" as distinct from "decidable"? A decidable question is one where you can determine the answer, whatever that answer may be. A semidecidable question is one where, if the answer is yes, you can determine that, and if the answer is no, you may not be able to determine that.

If you can always show that a program is incorrect, but you can't necessarily show that a program is correct, then the correctness of a program isn't decidable.

jcelerier4• 5 years ago

There are exceptions of course

for a definition of "exceptions" being "virtually all languages with a non-trivial static type system and non-zero userbase" as shown in your link.

Java (https://arxiv.org/abs/1605.05274), C# (https://blog.hediet.de/post/how-to-stress-the-csharp-compile...), Scala (https://michid.wordpress.com/2010/01/29/scala-type-level-enc...), Haskell, Rust (https://sdleffler.github.io/RustTypeSystemTuringComplete/), Typescript (https://github.com/Microsoft/TypeScript/issues/14833) ...

Having a type system with generics and not being turing-complete as a result is the exception, not the rule.

LadyCailin• 5 years ago

Sort of a side track, but there’s a great layman’s intro to this in this Veratasium video https://m.youtube.com/watch?v=HeQX2HjkcNo

volta832• 5 years ago

Isn't compiling several languages, including Rust, actually undecidable though?

While Rust is Turing complete, the compiler has a recursion limit, and if you take that into account, then compiling Rust is decidable (you only need to evaluate compilation up to the recursion limit).

ghosty141• 5 years ago

Rusts type system is turing complete if I recall correctly. Obviously, in practice everything is in a way decidable because we have limitations everywhere.

pjmlp• 5 years ago

Same applies to C++ templates by the way, the compilers usually provide an expansion depth flag.

w-m• 5 years ago

Presumably there’s another SAT solver in the realm of the Rust tool chain: cargo surely has one for dependency resolution. This is a big time sink in other package managers (looking at you, Anaconda). Does someone have an insight how solving is implemented in Cargo?

littlestymaar2• 5 years ago

There is one[1] but Rust allows different major versions of the same package to exist in parallel, so dependency resolution is usually trivial unless someone in the dependency tree explicitly adds an upper limit of the acceptable version [2], which is pretty uncommon (I don't think I've ever met one in practice).

[1] https://github.com/rust-lang/cargo/blob/master/src/cargo/cor...

[2] https://doc.rust-lang.org/cargo/reference/specifying-depende...

rocqua2• 5 years ago

he standard representation of such a formula is the conjunctive normal form, or simply: AND-of-ORs. Our previous example would look like this when transformed:

    A and B and (A or B) and (!A or !B)

There is another normal form, the disjunctive normal form. This is in the form of An OR of ANDs. Interestingly, every formula can be represented in this form. And SAT is rather easy to determine for this form.

The catch is that taking a logical formula, and placing it in Disjunctive normal form is actually a rather arduous, non polynomial process.

maweki• 5 years ago

And SAT is rather easy to determine for this form.

Gave me a chuckle, as that's quite an understatement, as the decision procedure is only: is there a single clause and is it just "False"?

The catch is that taking a logical formula, and placing it in Disjunctive normal form is actually a rather arduous, non polynomial process.

Basically writing out all assignments that make the formula true. Potentially exponentially many, as there are 2^n possible assignments of n variables. So this transformation is basically just solving and writing down all models.

mmarx• 5 years ago

The conjunctive normal form can be exponentially large in the worst case as well, though, see the footnote in the article. In practice that is not a problem, since it suffices to find a formula in CNF that is satisfiable precisely when the original formula is satisfiable, even though it might not be equivalent.

donatj• 5 years ago

I had rare occasion to compile a Rust application recently because a prebuilt binary didn’t exist for my platform. It took just over two hours! Coming from primarily Go development recently, I was astonished.

How do you get anything done when the cost of testing an idea is several hours?! I’d feel like the sunk cost fallacy would kick in for even the most lackluster of changes just because you took the time to try it.

swiftcoder2• 5 years ago

What on earth did you compile? I can't recall ever having compiled a rust project that took more than 10 minutes from scratch.

I do have memories of the days when compiling Chromium or AOSP was a 4 hour battle, though :)

jynelson• 5 years ago

The rust compiler itself can take as long as 2 hours on a modern laptop if you do a full stage 2 build. I don't think that's what the top poster was talking about though, it sounded like they had a rust toolchain already.

JD557• 5 years ago

How do you get anything done when the cost of testing an idea is several hours?!

I haven't used rust in production, but usually you can just use `cargo check` to only run the typecheck. Using `cargo build` is also usually much faster than `cargo build --release`.

Having said that, at least in my toy projects it was not uncommon to have to compile using `--release` to run the tests (since otherwise the tests would take forever).

littlestymaar2• 5 years ago

Having said that, at least in my toy projects it was not uncommon to have to compile using `--release` to run the tests (since otherwise the tests would take forever).

Maybe you're already aware of that, but if the reason why your tests are slow is not “your code not being optimized” but “your dependencies not being optimized” then Cargo profile override[1] can save your life. You can have one specific dependency (or all of them) being build in release mode even when you're building you own code in debug mode. The first development build is going to be quite slow, but after that, you're going to have the best of both worlds.

[1] https://doc.rust-lang.org/cargo/reference/profiles.html#over...

yakubin• 5 years ago

Although Rust compile times are rather bad, IME such astronomical compile times are rather a result of terrible code quality, a lot of code doing essentially nothing, just gluing glue, to the point where it's normal to get a 50-60 frames deep stack trace with most functions being named such that it would suggest that all of them do basically the same. Then you look at their bodies and... yep... doing the same, aka nothing.

With Rust, procedural macros add a lot of overhead when compiling, so I try to avoid them.

At work, we have a C++ project which, without using distributed builds with distributed ccache, running on powerful cloud computers, takes 3h+. Code quality is adequate. Debugging anything is a nightmare in such a codebase.

spoiler4• 5 years ago

While I agree that the compile times are bizarre, I don't think we can jump to conclusions such as "such astronomical compile times are rather a result of terrible code quality" without knowing more about what's being compiled and under what conditions it was being compiled!

wongarsu• 5 years ago

In my experience, Rust compilation times aren't that different from what I'm used to in the JavaScript world. Initial compilation takes a minute or two (comparable to the runtime of `npm install` on Windows), when you make changes you usually get incremental compilation within a few seconds.

I guess you can have projects that are just huge and/or run into some pathological case that increases compile time a lot (just like with C++), but for any subsequent compilations you should get very fast incremental builds.

yosefk• 5 years ago

I doubt your compile times were due to pattern matching which TFA demonstrates to be NP-complete, any more than C++'s compile-times are due to the undecidability of template metaprogramming.

(Though I guess one might argue that slow compile times on typical code and rarely-used computationally hard features have the same root cause of not treating fast compile times as a top priority.)

tialaramex4• 5 years ago

Right, and C++ got a lot of its compiler performance for large projects by making this an embarrassingly parallel problem even though the consequences are negative for the main consumers of the code (people, not compilers).

One cost of being embarrassingly parallel is the One Definition Rule. If we can compile N different code units in parallel, but they're all allowed to define things in the same namespace, obviously those definitions might contradict each other and we wouldn't notice. So, the C++ language explicitly forbids this, knowing you'll probably do it anyway, at least by mistake. If (when) you do, that isn't a valid C++ program, but the compiler isn't expected to produce any diagnostic (warning or error). So, you get a binary, but the language doesn't care what that binary does. Maybe it does exactly what you expected. Maybe it does almost exactly what you expected. If not too bad, the One Definition Rule means your compiler was fast and that's what matters.

IshKebab2• 5 years ago

Were you compiling Servo on a Raspberry Pi or something? 2 hours is ridiculous even for Rust.

How do you get anything done when the cost of testing an idea is several hours?

Incremental compilation. Depending on the project you can get the edit compile cycle down to somewhere between 1 second and 5 minutes. It's nowhere near as fast as Go but it's not like anyone is actually making edits then waiting 2 hours for them to compile.

ekidd2• 5 years ago

How do you get anything done when the cost of testing an idea is several hours?!

My Rust compile times are usually between 10 and 30 seconds. Some tricks that help:

- Get a good development machine. I prefer a Dell Precision laptop from the last couple of years, with plenty of cores. A 5-year old laptop with 2 cores will be a lot slower.

- Use Visual Studio Code and the rust-analyzer plugin. This will give you feedback in the editor while you're working.

- Rely on the type system to identify most problems before ever generating code.

- Minimize the use of slow-to-compile libraries that rely on complex generic types. Diesel, for example, is a great library but it's slow to compile.

- Install cargo-watch, and use it to automatically re-run the tests.

Also, remember that incrementally re-compiling a single crate in debug mode will be much faster than building an optimized application and all its dependencies from scratch.

TL;Dr: Rust compilation times are less than ideal, but with a fast laptop and rust-analyzer, it's possible to spend very little time actually waiting for the compiler.

remix2000• 5 years ago

Just get a new machine for a couple zillion bucks, why haven’t we thought of it earlier? :^)

tester342• 5 years ago

jesus christ

rust's compilation times are as terrible as c++'s?

kzrdude• 5 years ago

It's the same ballpark

okamiueru• 5 years ago

I don't know about Him, but at least when working with C++ I feel the compile time is entirely up to deliberate tradeoffs. With better planning and more effort made with forward headers, better implementation boundaries w/pimpl like constructs, and otherwise linking, and avoiding meta-programming entirely, I've not found it to be an issue.

Incremental C++ builds can be lightning fast, or it can be ridiculously slow. I've worked on large projects where change + incremental compile + test was less than 5 seconds. And I've worked with project where no effort was made where the same could take 10 minutes.

IshKebab2• 5 years ago

In my experience Rust is faster for full clean builds, even if you use slow dependencies like Serde.

However C++'s compilation units are smaller than Rust's which helps it to have faster incremental compilation times for small changes.

So, same order of magnitude basically.

tinco3• 5 years ago

Go is geared towards productivity. If you have a problem you can solve adequately in Go, why not just do it in Go?

Because they gained popularity roughly around the same time many people think they are competing languages, but they're really not.

Ruby is my main programming language, if I need something to be fast and/or light weight I switch to Go, sacrificing some comfort. And if I need absolute lowest possible overhead, I switch to Rust, sacrificing a whole lot more comfort. Rust is more expressive than Go, but if your Go project is so large that it needs a stronger typesystem in my opinion you should switch to a language like C# or Scala.

sesm• 5 years ago

Go is geared towards productivity of specific people at specific environment: fresh grads at Google.

spoiler4• 5 years ago

I'm really curious what you were compiling, and if you remember the machine specs (and was the machine under other load at the time). Two hours seems beyond ridiculous.

Also, I'm assuming it was a full (as opposed to an incremental) release build? But even then, I've never had to wait for that long.

lmilcin10• 5 years ago

Two hours is not beyond ridiculous. A lot of projects in the past compiled for way longer than that, days even.

In 90s and early 2000s if you worked on a large desktop application (the size of Office or Photoshop) you could expect to spend a business day waiting for compilation results.

eptcyka• 5 years ago

I've only had 2 hour build times when I was compiling a rust toolchain on an emulated ARM system running on x86.

spockz2• 5 years ago

Compiling linkerd-proxy took me also north of an hour on an Intel 6850k. Most of the time was spent compiling dependencies though. I also compiled envoy proxy which also took more than an hour.

Subsequent rust builds for linkerd-proxy were quite fast. For envoy most time was spent in Bazel itself. Probably because I just did a Bazel build instead of specifying a more specific target.

mkj• 5 years ago

Out of curiousity I tried linkerd2-proxy here on a i5-1145G7 (I guess similar total CPU? Less cores, laptop model, newer). Took 5 minutes but used ~6GB resident. Maybe yours was swapping a lot?

adwn2• 5 years ago

Compiling Servo, a web browser engine, takes 5-6 minutes for an optimized build from scratch on my 6C/12T machine. So no, 2 hour build times are not normal for all but the largest software projects.

genghizkhan• 5 years ago

Compiling paru, an AUR helper for Arch Linux, on the other hand, takes me around 3 - 4 minutes on a 4C/8T i5 for an optimised build. I think Rust compile times might just fall within a narrow range.

lmilcin10• 5 years ago

I have worked for 3 years on a project where it took a whole week to get the code compiled, signed by an external company and deployed to the device so that I could see the results.

I just learned to work without compiling for a long time. Over time my productivity increased and the number of bugs fell dramatically.

Working this way requires you to really think about what you are doing, which is always a good idea.

This was over a decade ago and now I work mostly on Java backends and I am happy that I typically spend days or even weeks without ever compiling the code and that it usually works the first time I run it.

I can't think how I could get back. It looks really strange to me to observe other developers constantly compiling and running their code just to see if it works. It kinda looks as if they did not exactly understand what they are doing because if they did, they would be confident the implementation works.

The only time when I actually run a lot of compile/execute iterations is when I actually don't know how something works. I typically do this to learn, and I typically use a separate toy project for this.

random_kris2• 5 years ago

I am one of those devs that is always compiling and checking if their program is working. I am mainly working with java and still doing this.

Less so than when working with JavaScript. But please teach me your ways hahha

nine_k• 5 years ago

Often you can be certain that you know what tp expect from your own code, but not from dependencies or external systems. So checking that your assumptions about them are right is a major reason to run and rerun your code.

marcosdumay• 5 years ago

I used to use approach, but the new heavily typed languages bring a lot of really nice tools that you only get to use at compile time.

Specifically in Rust, you can use the language to guide you through things like refactoring, thread synchronization, correctness verification and a lot of other things. But you have to run the compiler.

throwawayboise• 5 years ago

First job was in a mainframe environment, compiles were pretty quick but the job queue was so big and developer compiles were low enough priority that it could take hours of wall clock time to turn around.

I don't remember the specifics but while watching the job queue on the terminal screen I discovered that the job priority was editable. So I bumped it up, my compile job ran, and I was happy. I only did this a few times before I got a lecture from the system operations guys that was quite explicit that I should never do this again.

Yes, you figure out how to run code mentally, how to check carefully for typos and syntax errors, etc. No Intellisense then either, that's another modern crutch.

hinkley• 5 years ago

My theory for Java is that it was frog boiling turned cargo culting.

Comparatively speaking Java compilation was very fast at the beginning, so for instance Red-Green-Refactor (RGR) works pretty well. There's a parallel to other creative jobs where sometimes shuffling around the things you already have reveals a pattern that leads to a breakthrough.

But there are other feedback loops that, with J2EE in particular, the cycle times started to creep up, and up, and at some point if you haven't stopped and looked at what you're doing you don't see how crazy things have gotten. RGR still has a place there because you are typically not recompiling everything and you aren't spooling up the application to run unit tests. But making one line changes to see how a page loads is just bonkers amounts of busy work.

One of the bad dynamics is that people more like you also tend to memorize the code, which is both bad for new hires (circular logic does not reveal itself when you introduce one assertion at at time, but does when you get hit with all of them at once), and also incentivizes you push back on refactoring. Because those damned smartasses keep moving things around and they were Just Fine where they were. If that happens you have cemented the entire codebase and anything that is really wrong with it is going to stay wrong until someone proposes a rewrite. And having learned the wrong lessons the first time, we repeat them again in the second iteration.

weavie• 5 years ago

Incremental compilation. Once you get the first build done, subsequent builds are much faster.

Also a project is likely to be split up over multiple crates, so a lot of the changes you make will require building and testing just that one crate.

runevault2• 5 years ago

Isn't incremental compile disabled currently? I thought they found a significant bug and so turned it off until they could validate a fix.

stonemetal12• 5 years ago

If I had to guess it is because all of the dependencies had to be compiled too.

In a normal Rust application you break it up into crates. Crates are the unit of compilation, and are only recompiled when something in the crate changes. In a "normal" developer flow you only touch 1 or two crates at a time so normal developer compile time would be a couple of minutes at most. Even for a new build on a machine most developers would never see the two hour compile time because they would have gotten precompiled dependencies.

Nullabillity• 5 years ago

In a "normal" developer flow you only touch 1 or two crates at a time so normal developer compile time would be a couple of minutes at most.

Obviously this depends on your computer, but generally incremental Rust builds should typically be on the order of seconds, not minutes.

Even for a new build on a machine most developers would never see the two hour compile time because they would have gotten precompiled dependencies.

Cargo doesn't do precompiled dependencies (even between projects on the same machine).

Kaze404• 5 years ago

Compiling for production and compiling for development are two very different processes, with the latter benefiting from less optimizations and incremental compilation. It wouldn't take two hours to test an idea.

glennpratt• 5 years ago

I worked on a Rust project at work for several months. Compile times were not a significant issues for developers where it was generally cached. For example, repeatedly running a test only compiled a small amount of code.

It was a bit slow in CI/CD build environments with no cache, but so are the k8s Go projects I work on (go mod pulling in the world).

The only thing approaching 2 hours I've ever seen is building the compiler from scratch.

gameswithgo• 5 years ago

Short answer is it doesn’t normally take that long. You also don’t have the problem of cgo being slow or ever having to wait for the data race checker to run.

initial compile has to download and compile all dependencies. after that compiling is incremental. still slower than go though

kibwen4• 5 years ago

I suspect the machine you were using was swapping itself to death, because I've never experienced anything resembling that in Rust.

I also presume you were compiling in release mode, which is good for producing extremely fast programs but not something I bother with in regular development (in contrast to Go, which has no distinction between debug and release optimization levels).

How do you get anything done.

The vast majority of my workflow just involves seeing if my code typechecks, for which I don't even need to build the program (so no codegen, no linking). This I do very frequently, as a sanity check on my work. The command for this is `cargo check`. This takes less than a second for small projects, one to five seconds for medium projects, and one to twenty seconds for large projects.

adwn2• 5 years ago

I suspect the machine you were using was swapping itself to death

Good point. I recently upgraded my machine to 64 GiB RAM, because 16 GiB filled up pretty quickly with parallel compilation, several VS Code/rust-analyzer instances and a couple of browser tabs open.

nicetryguy• 5 years ago

I'm pretty excited for the Linux kernel to take three weeks to build.

jackcviers3• 5 years ago

I get this question about large scala codebases too - clean build and test cycles for things on underpowered containers in cloud build pipelines are in the tens of minutes sometimes.

One: my local dev machine has 16 gigs of memory and 16 cores. What takes the tiny docker container with 1 gig and 2 vcpus 30 minutes takes my computer about 1.

Two: Incremental compilation and testOnly make build/test cycles maybe a second / twenty seconds max, and most of that is test runtime on complex property based tests.

You just get by without a clean compile most of the time after you build the project the first time. And really, a lot of builds spend an inordinate amount of time just pulling in external dependencies (which are also cached on my local machine, but not on the containerized builds a lot of the time).

lower5• 5 years ago

For languages with Hindley-Milner typing, like SML and OCaml, it has long been known that type-checking is even worse in the worst case (DEXPTIME hard) [1]. But the programs where this matters aren't what one would write by hand, typically.

[1] https://dl.acm.org/doi/10.1145/96709.96748

contravariant• 5 years ago

To some extent it wouldn't even be surprising for a sufficiently powerful language to be EXPSPACE. Pretty much anything with sufficiently powerful macros would be EXPSPACE, or worse.

Ericson23143• 5 years ago

Note that is is polynomial with respect to the size of the output.

That is to say, pathological expressions don't stay small but induce horrendous searching, but rather merely get a log bigger (and that can cause more trouble for the rest of the program).

That means a heuristic to bail out when something grows a lot probably not violate the users intent and get it back into polynomial time.

chalst• 5 years ago

No, this is the time complexity of type checking before any computation on the terms is performed.

lower5• 5 years ago

Maybe it's a good idea to add a concrete example (can't edit the reply anymore):

OCaml:

  let x1 = fun y -> (y, y) in
  let x2 = fun y -> x1 (x1 y) in
  let x3 = fun y -> x2 (x2 y) in
  let x4 = fun y -> x3 (x3 y) in
  let x5 = fun y -> x4 (x4 y) in
  let x6 = fun y -> x5 (x5 y) in
    x6 (fun z -> z)

Haskell:

  test = let 
    x1 = \y -> (y, y) 
    x2 = \y -> x1 (x1 y) 
    x3 = \y -> x2 (x2 y)
    x4 = \y -> x3 (x3 y) 
    x5 = \y -> x4 (x4 y) 
    x6 = \y -> x5 (x5 y)
    in x6 (\z -> z)

If you can compile these, add x7. The effort increases exponentially as one adds x7, x8 and so on.

NieDzejkob4• 5 years ago

The fact that x1 is \y -> (y, y) is superficial, though. Something like x1 = Just also increases exponentially, and makes clear that using a deduplicated DAG for representing type terms doesn't solve this.

daxfohl• 5 years ago

Formerly id id id id id id id id id... would do it, but looks like someone has put in a fix for that.

Yajirobe• 5 years ago

could you provide a python example?

cletus• 5 years ago

Compiling really is the Achilles heel of Rust I feel. This article really talks about the worst case. As others have noted, Haskell and other languages have this property too.

Here’s another perspective on practical issues [1] that’s worth reading.

Basically, Rust made some understandable but unfortunate design decisions that are hard to walk back or change now.

[1] https://pingcap.com/blog/rust-compilation-model-calamity

shadowgovt• 5 years ago

The points made by the Endsay here are key, and actually a good example of trade-offs in software engineering. It is definitely okay to incorporate an algorithm that is NP-hard into the core of a performant system as long as you can have some expectation that the input size on the NP-hard part will be small. Sometimes, it even allows you to simplify another piece of the problem via pre-computation that allows you to avoid making the piece of the system that accepts large inputs require a costly solution algorithm.

Ericson23143• 5 years ago

Does this mean that rustc should integrate an industrial-strength SAT solver?

Well, this is actually what https://github.com/rust-lang/rfcs/blob/master/text/1868-port... would require. There is already chalk, a logic programming language for traits too.

I don't balk at these things. A good logical / relational toolbox is very useful for a lot of tasks.

not2b• 5 years ago

So just use a SAT solver to check for checking whether pattern matching is exhaustive. Any decent one will have much better performance than the current approach in the Rust compiler for complex cases. The interesting thing about SAT is that although the worst case is exponential (as far as we know until someone proves P = NP), even huge real-life problems (from circuits, program analysis etc) tend to have structure that makes them quickly solvable with a SAT solver. And if not, have a time budget and report "too complex to solve" if exceeded.

thaunatos• 5 years ago

It's worth noting that the author of the arcicle doesn't think it's worth integrating a SAT solver:

Does this mean that rustc should integrate an industrial-strength SAT solver? As hilarious as that would be, I'm advocating no such thing. This will only be a performance issue on pathological examples crafted by bored nerds, and I don't think precious engineering time should be spent on that. Besides, generalizing a SAT algorithm to handle the full expressive power of Rust's patterns might be, to borrow some language from mathematicians, non-trivial.

multifasciatus• 5 years ago

Obviously, every formula can be transformed into this form, by applying the rules of Boolean algebra.

Is it so obvious? Why do so many engineers write with these sort of modifiers (obviously, just, of course, etc.)?

Edit: I am assuming no ill intent from the author. I also use these sorts of modifiers without thinking about them much when writing. I am just curious as to why we as engineers call deeply technical things obvious when they are not.

bombela• 5 years ago

I don't think it's any malice. Just a way to bring up the idea of a sudden realization. Obviously, I could be wrong.

NieDzejkob4• 5 years ago

That sounds like something that could be solved with a linter for prose. Though, I can't think of the search terms that would let me find such a solution, if it exists.

guga42k• 5 years ago

Usually this is a polite way to say that proof/derivation is too long to fit on this page, please look somewhere else if you are interested.

Notable example would be Lev Landau's Theoretical Physics. If you see "obviously" there it is probably not obvious at all and can take good few hours to derive the formula.

joshribakoff• 5 years ago

The good faith interpretation is that the author means in the sense of “it follows then that” as opposed to “if you didn’t realize this upon reading the previous section then something is wrong”

rgoulter• 5 years ago

I liked the model in blogpost: https://status451.com/2016/01/06/splain-it-to-me/

It discusses that there can be different ways sharing information comes across. For some people, sharing information demonstration that you're smart enough to know the thing. For others, sharing information is for others' benefit.

I wouldn't prefer to interpret "obviously" as "you're not as smart/cool as me if you don't know this", but I can see why there are examples that could come across like that. (I'd sooner interpret it as "I'm not claiming to be smart by saying this").

bruce343434• 5 years ago

Roughly related: why not simply[1]

[1] https://news.ycombinator.com/item?id=27415725

estebank• 5 years ago

The actual code that handles exhaustiveness checks has extensive explanations on how it works and what it was inspired by.

https://github.com/rust-lang/rust/blob/master/compiler/rustc...

axilmar• 5 years ago

Regarding Rust's compilation slowness, wouldn't a Rust interpreter be a good solution for developing code? A Rust interpreter would drastically cut down slow compilation times, and then when the final product is needed, the Rust compiler would kick in.

steveklabnik3• 5 years ago

It's not clear that it would, or that the execution time of said interpreter would be fast enough to make it work. Miri interprets Rust code and it is, from what I hear, orders of magnitude slower. And for some applications, even debug builds of Rust are too slow. So it really just depends.

(It is also going to be slower than an interpreter focused on runtime speed would be, the point is more that interpreters aren't magic.)

Compiling Rust is NP-hard

Related Stories