Compiling Rust is NP-hard
niedzejkob.p4.team
niedzejkob.p4.team
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.
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)
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)
So, while id id has type ('a -> 'a) -> ('a -> 'a), this is stored in memory by a pointer structure that amounts to let 'b = ('a -> 'a) in ('b -> 'b). The type of id id id would become let 'b = ('a -> 'a) in let 'c = ('b -> 'b) in ('c -> 'c). This grows linearly. If one were to write out the types without sharing then their size would grow exponentially.
Apparently that's been fixed. I can't confirm because that's not something I ever check the type of.
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).
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.
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.
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).
(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.)
Presuming a formal spec that rustc happens to enforce, another compiler could simply try longer to resolve types before giving up, admitting some set of programs that rustc gives up on.
The thing we're talking about here has changed after Rust 1.0, Rust 1.0 shipped with a rule that said if you match integers you have to provide a default. In lots of code that feels natural. But not everywhere. If you match all possible integers (e.g. for a i8 that's from -128 to 127), the compiler would say "Not good enough" until you write the default match it will never actually need.
That was fixed with feature(exhaustive_integer_patterns) in 2018 or so AIUI.
But you could imagine Rust being standardised with the old behaviour and, even though it's clearly possible to write a compiler which implements feature(exhaustive_integer_patterns) that would then be non-standard because Rust programs lacking the default match for integers are forbidden in the standard.
> 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.
With Rust though a significant part of the value in things like the borrow checker is that it has the assertion that if you break the rules set out by the "standard", the code doesn't compile. Even Haskell doesn't make the mistake of trying to enforce something like that (instead it's libraries that normally add that verification but those aren't part of the standard).
My point is that Rust has language requirements that force the language compilable by the compilers to never be close to or equally covering the entire language defined by the "standard".
There will be normal (and emphasis on normal) programs that will not be compilable in Rust on certain compilers but will work just fine on others due to the search space on the type solver or the borrow checker blowing up. These issues will also likely pop up in between versions of the same compiler when changes to the internal representation cause certain cases to fall outside the search space.
The only thing the Rust devs can actually do to solve this problem is to add arbitrary restrictions to the language spec based on the limitations of existing compilers.
This issue isn't unique to Rust but basically every other major language has gotten around the problem by not making it a problem in the first place.
---
This comes back to the point in my original comment. Rust the language based on the compiler will likely not be consistent within Rust the language based on the "spec" (whatever it ends up being). There will be normal code that fails to compile due to seemingly arbitrary changes triggering combinatorial explosions.
With C, C++, Haskell, etc this issue can pop up but the features that can invoke this problem are far more rare, are more self contained, and are easier to diagnose (i.e. template explosions which are localised vs the borrow checker which can be very much not localised).
The original comment was very much a critique of Rust and by no means some type of Rust exceptionalism.
{-# LANGUAGE UndecidableInstances #-}
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.
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)
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.
In my opinion, OP is incorrect and those systems are sound but indecidable.
By this definition, program incorrectness isn't semidecidable either - the compiler will accept all correct [incorrect] formulas, and will either reject or accept incorrect [correct] formulas.
Take the Halting program for example: For a program p which halts, you can determine whether it will halt in finite time (because by definition it halts). However, there is no semidecidable algorithm for "this program runs infinitely long".
For example the following algorithm is for typechecking is decideable:
typechecks :: Program -> Bool
typechecks _ = false
The algorithm is even sound. It rejects all incorrect programs.
However it is not complete. It might also reject correct programs (In this case it rejects all correct programs).
Of course you want a as little conservative typechecker without getting into trouble. But it's always conservative to some extent. Preferably you would both be sound _and_ complete. But the problem is that any reasonable logic system can't proof its own consistency. Hence we can't have both. However we can get "as close as we possibly can".
That's not really how I understand the "semi" in the terminology. For a decidable question, you can recognize when the answer is yes, and you can recognize when the answer is no. For a semidecidable question, you can recognize when the answer is yes.
It doesn't take much of a stretch to describe that as cutting your capabilities in "half".
The way I usually think about this is that with full decidability, you can rule something in or out. With semidecidability, you can rule something in, but you can't rule things out.
That framework extends well to the situation described above, where if the compiler chooses to compile a program, then the typing in that program was valid, and if the compiler chooses to complain about the typing, we can't draw any conclusions. It doesn't match your example; you can't rule anything in or out.
Given a definition for a well-typed program, you get a set W of Program of the well-typed programs. You can ask whether W is decidable or semidecidable -- i.e., whether there is some (partial) computable function f : Program -> Bool with the above properties.
The example you give is certainly computable, but it has nothing to do with the set W, so it says nothing about (semi)decidability of the typechecking decision problem.
However, it is a valid trying to find the largest subset of W that is (semi)decidable. Or trying to redefine what it means to be well-typed so that it is (semi)decidable!
One interesting case of a programming language without a semidecidable typechecking problem is Lean. The typechecker they've implemented will both reject or time out on valid programs (so the typechecker is at least a computable function in a sense), but in practice these cases don't really occur.
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.
Even then; Undecidability is a bit spectrumy. e.g. RankNTypes become sort of decideable again in the presence of explicit type annotations
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).
But you could in theory write a Rust compiler whose compile-time runtime is fully Turing-complete; and that compile-time runtime would be conformant to the Rust language spec. (Just, nobody would want to use it, because “unbounded runtime” isn’t a property people tend to want from their compilers.)
Only if your theory allows for infinite storage...
Of course, I didn't check ad infinitum. <rim shot>
In fact, since rustc is "the spec" today, that's kind of how it is ""specified"".
Any implementation that does not conform to that would be... non-conforming... or using your own point-of-view, they would be implementing some programming language, but that language wouldn't be "Rust".
Then the question is not if Rust programs type-check in finite time, but rather, whether they type check in <= N steps. And e.g. the current implementation answers that question very quickly by just trying.
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?)
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.
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.)
If you wanted the SAT solver for some other reason (optimization? proving code correct?) it might make sense to use it for this too.
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.
I do have memories of the days when compiling Chromium or AOSP was a 4 hour battle, though :)
Sometimes it is just that someone drank the Kool-aid and made everything a template. Then split their code across hundreds of tiny files and did the one big massive include at the top of every file that pulls in everything.
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).
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...
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.
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.
(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.)
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.
It will fail at link time if you link everything into the same library. Even here there is an escape: there are ways to mark something as a weak symbol and than the linker won't complain about more than one definition.
See your OS documentation for how this works on your implementation. (though don't be surprised if the documentation is wrong...)
did you use LTO ? It always catches ODR issues for me. There is also GNU Gold's --detect-odr-violations switch.
Though I've been tempted to write a paper for C++ to make it defined behavior. I know it works in some form on most implementations even though it isn't legal. Thus there seems to be some other use cases for it that could/should be formalized. If anyone can give me other examples of why you want to do this and what the rules are on each platform I'll take a shot at it.
it definitely does not, every time I had an ODR issue that caused actual bugs. For instance, dynamic_cast not working because a typeid was defined in two shared objects, etc.
What would be the behaviour you expect if you have
a.cpp:
int constant() { return 123; }
b.cpp:
int constant() { return 456; }
c.cpp:
int constant();
int main() { return constant(); }
e.g. here with gcc, if a and b are put into shared libraries, the return value depends on the order in which the libraries are passed to g++ when linking. e.g.
g++ c.cpp a.so b.so
g++ c.cpp b.so a.so
Gcc also has the concept of weak symboles which if invoked (and the linker supports it) would allow you to make one of the two weaker than the others and then the whole doesn't depend on link order. Visual C++ also seems to have something like this, but I'm sure it is different.
Like I said, I want to write a paper to make it defined - but the paper will be a lot longer than would fit in a response here, and depending on information that I currently don't know.
This use case isn't an ODR violation. Its just using the linker to mock an interface.
> It will fail at link time if you link everything into the same library.
That is an ODR violation, although there are variations on this pattern that are not required to be detectable. Template instantiation is an easy way to get a silent ODR violation.
> 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.
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.
I've gotten by with much less for personal projects. But Rust will make very efficient use of (say) an 8-core i9 if you have one.
rust's compilation times are as terrible as c++'s?
AAA games need less resources than those tree walkers
Edit: I quickly realised, this might only because of Rust's—in my opinion—superior type system and tooling, so maybe it just requires less waiting for compilations than when working C++.
Edit 2: I've never actually measured Rust compilation times, but even for large-ish graphical codebases (wezterm, alacritty, bevy games) I've compiled from scratch, it felt noticeably faster even then.
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.
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.
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.
Sure the tooling around it (besides the compiler itself) was the dumbest 21st century tooling I've seen (this was ~6 years ago), but it was quick to learn, quick to write, quick to compile and quick to run so who am I to complain.
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.
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.
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.
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.
Less so than when working with JavaScript. But please teach me your ways hahha
This is a problem for many reasons. One is that this may help you get something working, but with lack of deep understanding the outcome will likely be subpar if only because not all problems that you could have predicted will show themselves on execution.
Another is that it basically shrinks the part of brain that is necessary for understanding and predicting behavior of your code (figuratively). Sort of like driving with GPS makes me helpless without it.
Try to write larger stretches of code without compilation.
Try to focus on modularizing your application so that you can reason about modules separately. This is always a good idea, but it is even more important when you need to be able to predict how something works without trying it.
When you have finally compiled your code and it failed, do not immediately go to fix the problem. Try to spend a moment to learn from the failure and improve your process so that you minimize chance of this happening in the future.
Ask yourself, what you could have done to prevent this problem from happening? Could you have specified some function or module better? Could you have simplified your code to be able to better reason about it? Would it help if you have spent a bit more time getting acquainted with this internal or external library before you decided to use it?
From my experience, most of this comes down to following things:
- defining your modules and APIs correctly -- badly defined modules make it difficult to predict the behavior,
- finding simple solutions to problems -- complex solutions tend to make it difficult to predict behavior,
- using only tools you understand,
- only interacting with existing code after you have understood how it works (I typically at least look over the code that I plan to use),
- thinking hygiene (make sure you base your work on hard facts and not beliefs),
- refactoring, refactoring, refactoring -- first solution to the problem is rarely optimal. I write something that works and then immediately keep refactoring it removing any unnecessary complexity until I am satisfied. Don't leave refactoring for later -- when you have just written a piece of code it is easiest to change it.
- as much as possible, writing your code in a way that it is not even allowed to produce wrong result. This is very large topic so I won't explain. There is a lot of techniques that you can research.
For example when I am interacting with a codebase for the first time and I want to implement something I just keep bashing and throwing shit at the wall untill something sticks. After that I start working more in line of what you described.
Just make sure you keep actual development separate from learning the tool if you care for your results and especially reliability.
Now, I use various ways to learn the tools and codebase. Running PoC for my idea or maintaining separate toy project helps me with maintaining hygiene.
For example, for the past year I have been spending a lot of time learning reactive programming with RxJava and Reactor. I have created a dozen small projects illustrating various ideas for making reactive APIs, processing pipelines, separating business logic from infrastructure, composing reactive modules, etc.
I did this with aim of purposeful learning rather than writing production code, even though some of these in the end migrated to be part of production codebase.
I am now at a level where I can, again, write large swaths of modules, libraries but now using reactive paradigm, with a very good chance of it working correctly, which for me validates that I more or less understand what is going on.
As I mentioned, if I don't understand a dependency or external system I make separate toy project where I can rapidly experiment and learn.
Think of it as having fun in a aircraft simulator. You play with it so that you are prepared to fly the actual plane.
Also checking your assumptions by trying to see if the code works is a problem in itself. A lot of these broken assumptions will not break your code immediately but maybe sometime later. Maybe when your application is under load or maybe when clock on the server is moved back by an hour or maybe when the connection breaks in a certain way.
Base your work on knowing how something works and not assuming.
Best way to limit the risk of your application failing due to broken assumption is to limit your reliance on assumptions in the first place.
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.
But you can say the same for Java. IntelliJ IDEA internally does equivalent of compilation and tells me exactly where my code would fail to compile.
So in a sense I am not strictly practicing my approach, but I also don't see reason to do so if the tools are reliably giving me hints when I made mistake writing something that will not compile.
I’m looking forward to someone making a legit IDE/suite with support, no indication of it yet but I assume some day!
Rust, well, "works". But there is still a bunch of issues so I keep developing using C until I get the kinks ironed out.
Developing in an IDE that compiles almost continuously is about as far from the development philosophy you're advocating for here as one could get :P
This isn't about throwing away tools for some idealized goal. It is about using the tools that are available to achieve best results without making you reliant on the tools to the point you don't know what your program is going to do without compiling and running.
IDE helps catch a lot of stupid simple mistakes and that helps save time. Why would that be bad?
> 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.
Explain to me how this statement doesn't apply to your use of an IDE, but the other engineers you've observed don't understand what they're doing.
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.
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.
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.
For debug builds, where incremental is usually on by default, it was disabled for 1.52.1 due to bugs, and then kept off in 1.53 out of an abundance of caution. It should be back on in 1.54.
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.
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).
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.
initial compile has to download and compile all dependencies. after that compiling is incremental. still slower than go though
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.
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.
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).
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
(Not saying that that's acceptable...)
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.
It's not just not optimized, it's wrong.
You can't just go "Eh, shrug emoji" without deciding what happens when you don't match.
Suppose you silently treat the first (or last) handled case as the default, so I can write code that only handles Cubes and unlike the real Rust compiler your naive compiler spits out a program. But wait, now what happens for a Tetrahedron? I defined Cubes to have a 32-bit floating point size, but for whatever reason Tetrahedrons have a 16-bit integer length instead. Does your compiler just try to treat the 16-bit integer as a 32-bit floating point number since it assumes this was a Cube?
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.
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.
https://github.com/rust-lang/rust/blob/master/compiler/rustc...
A and B and (A or B) and (!A or !B)
The catch is that taking a logical formula, and placing it in Disjunctive normal form is actually a rather arduous, non polynomial process.
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.
That may not count as a correct Rust compiler though, I'm not 100% sure how that's defined, or if it is.
A is of type T <=> B is not of type T
B is of type T <=> A is not of type T
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.
That said, it's not clear to me what part of "you can write uninstantiable templates" is surprising, so I'm probably not understanding correctly. Maybe you could find the C++ code you're talking about? I would be interested.
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 ?
If nothing else, it does demonstrate that you can do a lot more in the preprocessor than you might think, and this is at least a significant subset of what true MP macros are used for in Lisp most of the time. Except much gnarlier...
Correction: you can't do well in the worst case, assuming P ≠ NP (where "well" means "in polynomial runtime").
As an aside, I find it a bit ironic that you're complaining about pedantry while interpreting the "you" word literally.
“Can’t” can mean impossible, or it can mean nobody can do it. Compare “you can’t go back in time” with “you can’t lift a horse”.
To say that a solver is not in P is a type error.
Yet another pedantic fallacy.
I give you until the end of today to show me someone (anyone!) step on Mars
It was just someone being cheeky about someone being cheeky. Now I'm being cheeky about you being cheeky over someone being cheeky about someone being cheeky
[1]: https://github.com/rust-lang/cargo/blob/master/src/cargo/cor...
[2]: https://doc.rust-lang.org/cargo/reference/specifying-depende...
> 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.
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.
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.
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").
(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.)