How to speed up the Rust compiler some more

https://blog.mozilla.org/nnethercote/2016/11/23/how-to-speed-up-the-rust-compiler-some-more/

by nnethercote • 10 years ago

170 62 10 years ago

blog.mozilla.org

wyldfire• 10 years ago

Can rust capitalize on LTO/PGO? Even if that's not quite ready for primetime, if we're spending 50% or more time in the LLVM backend, that certainly can be built with LTO/PGO.

Seems like it might be worth the trouble/bootstrapping challenge if it yields another ~5%.

corndoge• 10 years ago

we should just make computers faster, intel is failing, moores law

thecopy2• 10 years ago

We know how to make them faster. How to make faster CPUs viable & affordable to the public though, that's a hard problem to solve.

stevedonovan3• 10 years ago

Here's some thinking outside the box. Traditional compilers are focused on building an executable as fast as possible, throwing away an enormous amount of state each time. The new rustc incremental compilation attempts to re-use some of that computed state, although still early days. If however the compiler's state remains persistent (it is running as a daemon) then small code changes should usually be pretty fast - it's analogous to the code scanners of Eclipse. If the target of the compiler isn't a native executable, but a continuously updated image containing code, then the link gets pretty fast as well. The result will not be fast, but it will be _fast enough_ to test changes.

amelius• 10 years ago

Yes, and it would be even nicer if such techniques would be available outside the compiler community. In fact, it could perhaps even be a language feature.

pjmlp8• 10 years ago

You mean like Lisp, Smalltalk?

grokys• 10 years ago

I think the Roslyn compiler does something similar to what you're suggesting.

http://www.dotnetcurry.com/csharp/1258/dotnet-platform-compi...

Every time a developer changes a single character in any of the files, a new copy of all the data structures is created, leaving the previous version unchanged. This allows a high level of parallelism and concurrency in the Roslyn engine, as well as in its consumers, thereby preventing any race conditions to occur. Of course, in the interest of performance, these operations are highly optimized and reuse as much of the existing data structures as possible. Again, those being immutable makes this possible!

stevedonovan3• 10 years ago

Right! That's a compiler designed to be used as a service! Most compilers are usually in a terrible hurry to build that executable before people start playing with light sabers or thinking about new programming languages [1].

I first thought about this when working on UnderC, a hopelessly over-ambitious C++ interpreter. Functions could be recompiled, because there was an indirect reference to the actual code. And this is of course exactly how Lisp people used their compiler. (The 'image' reference of course is to Smalltalk)

[1] https://commandcenter.blogspot.co.za/2012/06/less-is-exponen...

pas• 10 years ago

Scala's new compiler (dotty) also tries to go that way (first of all using streaming AST-s for better cache locality).

The problem is, that usually this "keep state and just percolate changes" is easier said than done. But we're getting there.

See also:

https://www.youtube.com/watch?v=TS1lpKBMkgg#t=23m38s (scalac performance) https://www.youtube.com/watch?v=TS1lpKBMkgg#t=37m53s (what do we really need from "computing science" to do programming)

https://d-d.me/talks/scalaworld2015/#/49

barrkel• 10 years ago

The Delphi compiler, when hosted in the IDE, has done this since 1996 or so.

The symbol table, generated code etc. for every compilation unit is kept in memory and only discarded if the source is modified. All imports across compilation units are done via a double indirection, so the symbols can be unlinked and relinked more easily.

(Sub-second recompiles in Delphi are the norm, not the exception. In large projects, most of the time during dev builds is linking, and that's usually only a few seconds.)

pjmlp8• 10 years ago

Which is why I kind of think that it is a bit sad when millennials think Go compilation speed is some kind of achievement.

Specially given Delphi features vs Go ones.

noir_lord3• 10 years ago

Delphi is still my favourite ever development environment even though I haven't touched it for over a decade.

IDE power, the VCL, amazing documentation, rapid builds, clean OO language, it had it all.

pjmlp8• 10 years ago

Besides the sibling comments, this is how Lisp, Smalltalk, Ada and Eiffel environments work.

Even C++ had such tools in the past via Energize C++ and VisualAge for C++ v.40.

Microsoft is now kind of following this path with /fastlink and improved database backend for code metadata.

EDIT: Typo

flukus• 10 years ago

Traditional as in c? Object files would maintain state and build incrementally.

ronjouch2• 10 years ago

The post goes directly from "heap allocations were frequent within rustc" to "effort to minimize heap allocations", and proceeds to detailing speedups.

→ Systems programming newbie question: why are heap allocations bad for performance? Is it the additional level of indirection? The cost of calling your memory allocator? Something else?

My background, if that helps focusing answers: python/js programmer, did a tiny bit of C/C++, am ~approximately~ familiar with the stack (call frames, each with its context) vs. the heap (where to allocate memory for big/long-lived objects e.g. arrays and trees).

unwind• 10 years ago

I think it's mainly cache effects; things in heap memory tend to be more spread out, and that hurts spatial locality which is the basis of caching. The indirection is part of this too, since "jumping around" following pointers can pollute the cache which in turn can make subsequent accesses slower.

Sure, the allocator itself can be expensive, and that's certainly important if you're doing "too many" allocations, but in general I think it's worse caching that matters the most.

twoodfin• 10 years ago

This is important to keep in mind when looking at profiling reports: The cost of cache effects (both I and D!) can be spread throughout the critical path. Even if your profile shows your allocator being executed only in (say) 2% of the samples, if what it's doing during that time is pushing lots of useful instructions or data out of the fastest caches into which they otherwise would fit, the total cost of that allocation is likely much greater, but hard to pinpoint.

valarauca12• 10 years ago

    why are heap allocations bad for performance?

1. You have to call to your allocator. Then do some type of search for free memory, of the approximate size. Then flag this memory as used. Then mark the remaining memory in that block as unused. Then mark the internal books to match the new layout.

This is done efficiently, but modifying these collections take time. AND IT STILL FASTER THEN:

2. Calling the kernel to MMAP in new virtual memory, adding that to the pool, and well restarting this process all over again.

Allocation time is a big cost, and there is work to make allocation lazy by default in the Rust Compiler at the minute.

marcosdumay3• 10 years ago

Also, make sure #1 is done atomically. Your request will either get in a queue, wait for a mutex, or create many more of #2 than needed because the pool isn't shared between threads.

gcp• 10 years ago

Aside from what the other reply said: heap allocations do incur management overhead and are prone to things like fragmentation. Stack allocation is literally a single add/sub micro-op.

Rusky• 10 years ago

Further, all stack allocations for a frame can be coalesced into a single add/sub.

nnethercote2• 10 years ago

Author of the post here. A lot of the heap allocations I removed were small and short-lived. So I believe just the malloc/free calls themselves -- and whatever synchronization and data structure manipulation they entail -- are most of the cost, more so than the cache effects that others have mentioned.

vanderZwan2• 10 years ago

Nice article, although I would have liked to see a before/after summary bar chart of the benchmarks for all PRs as a whole; I'm curious how all these incremental improvements add up together.

snovv_crash• 10 years ago

You can find roughly that here, unfortunately mixed in with everything else though:

http://perf.rust-lang.org/

nnethercote2• 10 years ago

I too would like that! But lots of other changes have been landing concurrently, so it's hard to isolate the effect of my changes.

TazeTSchnitzel3• 10 years ago

Is heap allocation actually unavoidable? PHP uses an arena allocator for its AST. I don't know how applicable that could be to Rust.

hackcrafter• 10 years ago

Not that applicable.

Rust memory model around strong ownership and borrow-checking differs from the GC languages that can use generational strategies and lots of heap allocation re-use.

All languages are doing allocations to the OS, rust just doesn't have a GC like PHP does to intermediate.

TazeTSchnitzel3• 10 years ago

PHP's compiler is written in C, and its AST isn't garbage-collected. I think we just throw out the entire arena, actually.

rkangel• 10 years ago

There are plenty of things that could be used to speed up particular hotspots - arena allocators are one option.

Better than that is to not allocate at all, which is the focus of the effort here.

A step further down the line of optimisation may identify allocation hotspots and use custom allocation strategies rather than using the language default (the heap).

Manishearth• 10 years ago

Rust uses an arena for the type graph as well. Note that jemalloc gets you a lot of the benefits of using an arena for free.

How to speed up the Rust compiler some more

Related Stories