How to speed up the Rust compiler

https://blog.mozilla.org/nnethercote/2016/10/14/how-to-speed-up-the-rust-compiler/

by nnethercote • 10 years ago

185 123 10 years ago

blog.mozilla.org

keyle• 10 years ago

I've never used rust but seeing it's so oriented towards correctness and type checking, I'm not surprised it's a little slow to compile!

From someone stuck with dynamic languages, mark my words, it's best for your compiler to be a bit slow, than your brain being the compiler! :-)

ekr• 10 years ago

Never underestimate the edit-compile-test loop. It has an huge impact on productivity.

arunc• 10 years ago

AKA, REPL: Read Evaluate Print Loop.

amelius• 10 years ago

Can we have the best of both worlds?

aninhumer• 10 years ago

Well with stronger type guarantees, a lot of the "test" part of that loop gets pushed into "compile".

Indeed the core loop becomes edit-typecheck, and while the compiler can be slow, the type checker tends to be a lot faster than the test suite.

openasocket• 10 years ago

The biggest win for that is going to be incremental compilation. I can't wait for that to stabilize.

pjmlp14• 10 years ago

Still it can be improved and it is nice to see work being done there.

For me, the sweet spot would be the compilation speed of Delphi, .NET Native and similar languages.

k__2• 10 years ago

From someone stuck with dynamic languages, mark my words, it's best for your compiler to be a bit slow, than your brain being the compiler!

lol, I'm on a project right now that uses ES2016 (dynamic) and I'm still stuck on a slow compiler.

patates• 10 years ago

Switch to TypeScript or Flow. Then at least it's worth the wait (in terms of correctness).

jnbiche• 10 years ago

If you're only using standard ES6 features, you may be able to switch to Buble. I got a pretty significant speedup after switching one project to Buble ES6 compiler.

https://buble.surge.sh/guide/

nostrademons• 10 years ago

If you're targeting modern browsers you may want to look into disabling all plugins except for modules. The latest version of every major browser supports ES2015 natively (as well as much of ES2016 and ES2017). There are various Babel presets (eg. babel-preset-modern) available on NPM that do this.

Even if you're not targeting modern browsers, you might consider developing on Chrome with a very minimal, modules-only Babel config, and then running the full transform only when you're ready to QA & deploy.

vintagedave• 10 years ago

Why? You can have both fast compilers and safe languages.

Take Delphi for example: statically typed, strong type correctness, you have to work to avoid type safety. Compiles a million lines of code in 4 seconds (including linking.)

* https://www.youtube.com/watch?v=Yq2mNUzcpE0 (1 million lines, 4 seconds)

* https://www.youtube.com/watch?v=kvuxeaMDmMc (277,000 lines of much more complex code (the most complex, compiler-stressing library Delphi has) in 16 seconds counting linking.

adrianN• 10 years ago

I think the correctness guarantees that Rust provides are a little stronger than what Delphi provides.

krylon2• 10 years ago

At work, I am stuck doin maintenance on an in-house application our accounting department uses, which is written in Delphi. It's small (~10k lines of code), but it compiles so fast I sometimes wonder if I clicked the wrong button / hit the wrong key.

userbinator• 10 years ago

I don't know about the latest versions, but I remember looking at Delphi compiler output and it seemed like it did not optimise at all. That would certainly explain its speed.

chamakits2• 10 years ago

I'm not familiar enough to comment on what different feature set and different type of work each compiler does to compare the speed, but WOW, that's an INSANE quick build speed.

Was it always an explicit goal of theirs compilation speed? Is there any documentation of specific things they did to achieve that build speed?

pcwalton3• 10 years ago

Delphi didn't have anywhere near the level of optimization that modern backends like LLVM have.

duaneb• 10 years ago

Delphi is not much safer than C; it's not surprising it compiles quickly.

It's also not competitive speed-wise with either clang/gcc OR rust.

whyever2• 10 years ago

If you forego optimizations, you can compile the Linux kernel in seconds (see tcc).

mmargerum• 10 years ago

Start using lots of generics and see how fast Delphi compiles.

pjmlp14• 10 years ago

In conclusion, allocating memory is expensive, regardless how it is done. :)

kzrdude2• 10 years ago

The allocation fixes are scratching on the surface of the compiler. It must be something more fundamental underlying the long compilation time.

qznc2• 10 years ago

Apart from the borrow checker there is nothing fundamentally different to other compilers. I doubt that borrow checking is fundamentally more expensive than other type checks.

My guess is: Large compilation units and LLVM optimizations.

Manishearth5• 10 years ago

One of the main slow bits is just LLVM. Rust produces LLVM IR which LLVM takes a long time to optimize.

Since MIR has landed, IIRC work on doing MIR optimizations and LLVM IR simplifications is the next step here.

gribbly4• 10 years ago

Not sure how much is due to this, but LLVM has gotten much slower in recent releases, probably due to improved optimizations.

I would not be surprised if down the line, the Rust devs decided to write their own Rust backend rather than relying on LLVM.

zigzigzag2• 10 years ago

It sounds like a lot of the allocations in the Rust compiler follow the generational hypothesis, even though Rust isn't GCd. If the Rust compiler was using a parallel generational GC then it's possible it'd be a lot faster, as the hard work of the allocation would be done on separate cores and all those tiny unused TypedArenas would die young which makes them rather cheap.

lucozade• 10 years ago

I'm not sure that this follows from the analysis. Why would a GC remove allocations from the hot path? I could see that it may take deallocations off and may be faster if it's a very good GC.

But you'll also get into the territory of what you're GCing. I take it from the fact that there are a lot of arenas that there are an awful lot of small allocations. Unless your GC lets you choose the level of allocation i.e. it doesn't necessarily allocate at the object level, your GC'd language is likely to be much, much slower. There may be GCs like this but I think they are relatively unusual (I'm not aware of them but I'm no expert).

It seems to me that the issue here is actually the same as you get when you try to improve performance of GC'd languages i.e. you want to try to avoid any allocation wherever possible.

I must say I was a little surprised by how much allocation is going on. Does it imply that idiomatic rust may lend itself to somewhat excessive memory use? Or maybe the rust code in the compiler is sufficiently old to not be considered idiomatic. Would be interested in the views of those more knowledgeable than me.

Manishearth5• 10 years ago

Rust used to be GCd and the compiler made extensive use of this. It was slowly migrated off this, but I suspect the code is still structured that way.

mrottenkolber• 10 years ago

In conclusion, allocating memory is expensive, regardless how it is done. :)

My experience goes contrary to that statement. How allocation is done makes all the difference. Between what the language implementations memory model is good or bad at, and what allocations/usage patterns the CPU is good or bad at, there are worlds of possibilities and trade-offs. Especially the “increased allocation equals decreased performance” myth doesn’t hold true. See http://mr.gy/blog/maxpc.html#section-3-2 for my own ragtag exploration of this phenomenon.

notriddle• 10 years ago

Allocating memory can be as cheap as adding to a number. Even if you want a concurrent allocator, atomic increments are pretty fast compared to any typical malloc. It's allocating and then freeing that's slow.

A copying-compacting GC has very fast allocation at the cost of very slow freeing (you have to walk memory).

DMD has very fast allocation and never frees memory.

acqq3• 10 years ago

As far as I know, the Rust compiler is written in Rust? That should mean that if the features of the language are used, a lot of "small" allocations shouldn't happen at all, instead, the language is supposed to allow that the short lived variables (and objects) exist only on the stack, costing effectively nothing to allocate them?

Moreover, the compilers in general have an advantage to know that most of the objects are needed only during specific times, allowing optimized allocation and bundled deallocation. I see "a lot" of "arena" allocators are mentioned, so it seems there is something like that, just maybe too fine grained?

In short, there's no need for the Rust compiler to have any measurable overhead due to the allocations.

Then only the changes in the compiling algorithms and the underlying data structures (how often is what traversed and why, is something kept or recalculated, sometimes it's even more expensive to produce too much data to be kept in memory, and sometimes the data structures aren't optimal for the most of the uses) should have the potential of changing the compilation speed.

Chirono• 10 years ago

Don't know why you are being down voted. Even if you are incorrect, it would be interesting to hear why. Anyone care to comment?

__s• 10 years ago

Compilers spend a lot of time with hashtables, which exist on the heap. Rust isn't some magical language that makes the heap some unnecessary entity. One still has objects whose lifetime do not fit the stack model or whose size is dynamic

Their comment went on to claim that given their hypothesis, allocation optimization shouldn't be impactful. Yet this post demonstrates otherwise, perhaps showing that therefore their hypothesis is false (if a then b, b is false, therefore a is false)

One of the post's optimizations was to use Cow<str> over String tho, which is an example of reducing allocations with borrows

Additionally it's oft mentioned that a weak point in Rust's compile time is LLVM. This has to do with various things, some of which are Rust's fault (it could generate less IR), but it points out that there's a lot of time being spent in C++ code. LLVM's great, but it's guidelines essentially suggest 'if you want to make llvm play nice, generate IR like clang'

valarauca12• 10 years ago

Because the parent poster's thesis

>Moreover, the compilers in general have an advantage to know that most of the objects are needed only during specific times, allowing optimized allocation and bundled deallocation

Is flawed.

Compiler can know this. Most the time they don't. In Turing complete languages you can't reason about how much space/time a program will need to run.

When you do know that and object, or objects will be determanstically allocated/de-allocated together. Then you need to know how large they'll grow too over their their lifetimes. Which again may hit a Turing Tarpit, and you lose this ability.

Here is an incredibly simple example

        fn read_file(path: &str) -> String;
        fn get_tokens<'a>(s: &'a str, r: &Regex) -> HashMap<&'a str, &'str>
        fn main() {
            let my_regex = //something
            let file_data = read_file(&arg[1]);
            let tokens = get_tokens( &file_data, &my_regex);
        }

On can see the String that will contain the file's data, and Hashmap can be allocated together. But one cannot reason about how large either will be head of time to pre-size these on the heap.

Lastly, address randomization is a good thing. Knowing ahead of time which allocations will determanstically be in relation to each other is a security vulnerability.

Zarathustra30• 10 years ago

...if the features of the language are used...

The Rust compiler uses Rust's features terribly, just because Rust's features were a moving target for the majority of the compiler's lifetime.

nickpsecurity7• 10 years ago

I still think they should investigate doing the LISP solution to the problem where you combine several options:

1. Interpreter (eg REPL) that executes it instantly with dynamic checks for rapid prototyping of logic.

2. Fast, non-optimizing compile that at least does the safety checks.

3. Fully-optimizing compile that can be done in background or overnight while programmer works on other things like tests or documentation.

4. Incremental, per-function version of 2 or 3 for added boost. Rust is already adding something like that.

This combo maximizes mental flow of programmer, lets them tinker around with algorithms, quickly produces executables for test deployments, and will often do full compiles without interrupting flow with wait times. It's the workflow available in a good LISP. It doesn't have to be exclusive to LISP. Other languages should copy it. I'll go further to say they should even design the language and compiler to make it easy to pull that off.

qwertyuiop9249• 10 years ago

In CLs, anyways. In Schemes, we usually only have 1 and 3. Maybe 2 and four, but only sometimes.

nickpsecurity7• 10 years ago

The Scheme I was thinking of using to re-learn LISP and Scheme was Racket. Its environment + How to Design Programs looked like a strong combo. Do you know how it fares on this list?

dleslie5• 10 years ago

Chicken can be configured for the different levels of optimization it will do; now I wouldn't call it fast...

whyever2• 10 years ago

If you are only interested in whether your Rust program typechecks, you can use cargo check, it is quite fast, because it does not generate any code.

eridius3• 10 years ago

malloc and free are still the two hottest functions in most benchmarks. Avoiding heap allocations can be a win.

This is a non-sequitur. If you see a hot function in a profile, that is an indication that you should optimize that function if you can. But it does not mean that you should try to reduce calls to that function elsewhere (unless you can cut out a lot in one go). As a trivial example, if you have a super-fast function that cannot be optimized any further, but it's called millions of times, that function may appear hot, but any individual invocation of the function might be taking just a few microseconds. Getting rid of a handful of calls to this function (or even a few hundred) isn't going to make an appreciable difference. Of course, if you can cut the number of calls in half, then that would be good.

I guess another way of saying this is, if you're trying to optimize a hot function by reducing the number of times it's called, you need to reduce it by a significant percentage of the total calls rather than reducing it by a specific number of times. No matter how many times it's called, if you reduce the number of calls by 50%, the overall time taken by the function drops by 50%. But if you reduce the number of calls by 50, then whether that's meaningful or not depends entirely on how long each individual call to the function takes.

Edit: Why am I being downvoted for this? I'm speaking a factually correct statement. It's not like this is some sort of controversial opinion. If I'm wrong, please tell me why.

elihu• 10 years ago

The original statement isn't a non-sequitur. If the compiler is spending a lot of time in malloc, it makes sense to replace those heap allocations with stack allocations where possible.

You are also correct that removing mallocs might not be much of a low-hanging fruit, since it might entail changing a lot of malloc calls rather than just a few, but that doesn't mean the original statement was wrong.

eridius3• 10 years ago

Fair enough, but it's a good bet that most of those mallocs cannot be replaced with stack allocations.

MaulingMonkey3• 10 years ago

Edit: Why am I being downvoted for this? I'm speaking a factually correct statement. It's not like this is some sort of controversial opinion. If I'm wrong, please tell me why.

Didn't downvote you, and considering you're currently on the top of the replies list, I wouldn't worry about potential misclicks. But I'll bite.

This is a non-sequitur. If you see a hot function in a profile, that is an indication that you should optimize that function if you can.

This is just as much of a "non-sequitur" - maybe you can optimize that function further, but if it's reached the point of diminishing returns it may not be worth it even if it's technically possible. In-context, there has already been a lot of optimization work put into malloc and free, lots of low hanging fruit is gone.

Further, malloc and free are very generic allocation strategies that generally do a lot of work to try and handle many different cases with OK efficiency. I challenge you to make them as fast as, say, stack allocation - go ahead, I'll wait. Sure, you can't replace all use of a heap with a stack, but most programs I've seen have at least some cases where you could.

And there is actually a way to make malloc and free as fast as a stack - turn your malloc implementation into a pointer increment, and free into a noop. Not appropriate for all tools, but a short lived compiler pass might be able to get away with it! Although it'd possibly cause problems for large 32-bit builds. Regardless - this is also technically no longer a heap.

As such, "Avoiding heap allocations can be a win" seems to be a very true and straightforward reply. Confusingly, you seem to agree with this in your next paragraph despite labeling it a "non-sequitur"? Perhaps you're interpreting this as claiming that avoiding a single heap allocation call site is going to be a significant win? Because that's reading far too much into the statement, IMO.

Getting rid of a handful of calls to this function (or even a few hundred) isn't going to make an appreciable difference. Of course, if you can cut the number of calls in half, then that would be good.

An important note here:

Cutting the number of calls in half could, in theory, involve eliminating one call site (because e.g. the calling code itself is very hot) although this probably isn't the case in the Rust codebase or it'd have been optimized already. Even if we pessimistically assume that we need to eliminate N% of call sites to eliminate N% of calls, the first step to eliminating N% of call sites is to eliminate one call site. The second step is to eliminate a second call site.

eridius3• 10 years ago

Didn't downvote you, and considering you're currently on the top of the replies list, I wouldn't worry about potential misclicks. But I'll bite.

Thank you for your reply. At the time I added that edit, I was at -2 points. And I'm only at 1 point right now (and aren't showing up at the top of the stack when I look at the comments page). In any case, the edit did seem to do what I wanted, which was to get replies.

As such, "Avoiding heap allocations can be a win" seems to be a very true and straightforward reply. Confusingly, you seem to agree with this in your next paragraph despite labeling it a "non-sequitur"? Perhaps you're interpreting this as claiming that avoiding a single heap allocation call site is going to be a significant win? Because that's reading far too much into the statement, IMO.

The way I read it was "malloc is a hot function, therefore you should try to avoid using it". And that's a non-sequitur because the conclusion does not follow from the premise. Whether or not it's a hot function has no bearing on what the cost of an individual call is. And when you identify a hot function in a profile, that doesn't mean you should remove calls to it, that means you should optimize it. If you can't optimize it, then you should charge it to its parent frame. If you take all your un-optimizable hot functions and charge them to their parent frame, then you can see if any new hot functions pop up that can be optimized. e.g. you can't optimize malloc, but if you find one function is calling malloc hundreds or thousands of times, and it doesn't have to, then you can optimize that function (or if it does need all those allocations, you can investigate using alternatives to malloc).

Even if we pessimistically assume that we need to eliminate N% of call sites to eliminate N% of calls, the first step to eliminating N% of call sites is to eliminate one call site. The second step is to eliminate a second call site.

When talking about a function with many thousands of individual call sites, eliminating them one at a time isn't practical. You need to come with some way to systematically eliminate a lot of them. Of course, if you do the above and charge malloc to its callers then maybe you can identify a small number of call sites that are responsible for a high percentage of calls to malloc.

How to speed up the Rust compiler

Related Stories