How to speed up the Rust compiler some more | Hacker News Reader

How to speed up the Rust compiler some more

blog.mozilla.org

170 pointsnnethercote62 comments

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).

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.

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.

Thanks unwind/twoodfin! @twoodfin, can you precise what you mean by "cache effects (both I and D!)" ? (Indirect and Direct? By Indirect you mean Associative and by Direct you mean Direct Mapped as defined in http://www.ecs.umass.edu/ece/koren/architecture/Cache/tutori... ?). Also, googling "direct indirect cache" yielded the hilarious http://onlinelibrary.wiley.com/doi/10.1046/j.1439-0310.2003....

To other programmers not so familiar with CPU caching, resharing two blurbs that helped me get a start of a grasp on it:

- Why do CPUs have multiple cache levels? https://news.ycombinator.com/item?id=12245458 , https://fgiesen.wordpress.com/2016/08/07/why-do-cpus-have-mu...

- CppCon 2014 - Mike Acton: Data-oriented design and C++ , https://www.youtube.com/watch?v=rX0ItVEVjHc

I-cache and D-cache means instruction cache and data cache.

I believe by "I and D" the parent is referring to instruction cache and data cache: http://stackoverflow.com/questions/22394750/what-is-meant-by...

We used to call that a "flat profile" where everything looks slow due to cache thrashing but there's no inner loop that's a smoking gun.

It's really a shame more platforms don't show cache/icache misses in an easy to access manner.

    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.

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.

Rust uses jemalloc which has per-thread-pooling (sort of). There is very little lock contention as there are multiple pools per-thread.

Also per thread pooling doesn't use more memory then not. In some cases it actually uses less. Citation: https://people.freebsd.org/~jasone/jemalloc/bsdcan2006/jemal...

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.

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

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.

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.

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.

You mean like Lisp, Smalltalk?

The new kid on the Smalltalk block is Pharo:

http://pharo.org/

Also that language Jonathan Blow is working on https://www.youtube.com/watch?v=HLk4eiGUic8

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!

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...

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

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.)

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.

Especially given the CPUs used in the computers back when Delphi was popular.

Yeah that as well, and even Turbo Pascal was already quite fast on MS-DOS systems (I was using it with MS-DOS 5.0).

I've said a couple of times that new language designers should thank their lucky stars that C++ has set the bar for "fast compilation" so low. Coming out of the gate with a compiler that's "faster than C++!" is pretty doable even for a relatively compile-time heavy language. If you had to come out of the gate with something as fast as Delphi to be taken seriously, we wouldn't get very many new languages.

(I mention this in the context of my observation that the minimum bar to be taken seriously for a language is going steadily up. You certainly need a standard library that is powerful out of the gate, whether or not it is necessarily "part" of the language, and we're getting perilously close to the language being required to ship some heavy-duty HTTP stuff, possibly a server implemented in the language, before it stands a chance. Rust may have snuck in under the wire on that, though of course that stack is developing apace even so.)

python has a http server coming with the standard installation

Go (despite its faults) definitely raised that minimum bar; a language needs to arrive with a package manager and doc tools, as well as enough standard library to get non-trivial things going. Rust made the right decision on HTTP - let the ecosystem provide. Of course, the result of that is summarized in the quote by Grace Hopper: “The wonderful thing about standards is that there are so many of them to choose from.”

There's always the Python way:

Let the ecosystem provide, then, once there's a few clean winners, pick one as the official (while keeping the others there, obviously).

C++/Boost does that

Yes (what is quite inline with the C tradition).

What is interesting is that I can't think of a lot languages that do it. It should be the default, as it's easy, safe, and gets good results. Somehow, it isn't.

And then there's the Haskell's way of: let the community informally choose the one best option, and when somebody uses any of the other ones, just get somebody near him telling "nobody goes there anymore, come to this other place". It works very well, but is a bit confusing for newbies.

Go's minimum bar is well below Active Oberon, Delphi, Eiffel, Java and .NET ones.

Remember I'm not discussing what they have now, though; the question is what they came out of the gate with in their 1.0. I'm fairly confident Go 1.0 was much more useful than Java 1.0. Java 1.0 certainly didn't ship with a built-in web server and routing stack, or even anything close to that high-level functionality, even if it did ship with more data structures that Go has even now. .Net was a closer call, but, then, .Net came later, the bar had raised. Can't speak to the other ones but I would imagine their first releases were also less useful than Go.

> Java 1.0 certainly didn't ship with a built-in web server and routing stack

Kind of, it supported distributed computing via CORBA and RMI.

A built in web server was released as part of Java 6, 2006.

> Can't speak to the other ones but I would imagine their first releases were also less useful than Go.

The fact is that Go, released in 2009, was a pretty bare bones compared to the state of those programming languages in 2009.

Also while Go might had an HTTP package on version 1.0, it surely still doesn't have a GUI framework on 1.8, which those languages had on 1.0.

EDIT: Rephrased a bit the answer.

"A built in web server was released as part of Java 6, 2006."

Go isn't even that old yet. You're welcome to discuss what you like but I'm talking about what thing came with at first release.

"Also while Go might had an HTTP package on version 1.0, it surely still doesn't have a GUI framework on 1.8, which those languages had on 1.0."

Point. And even by 1.0 Java's was at least modestly capable by the standards of the time, as I recall. It didn't have everything, certainly couldn't compete with all the custom widgets you could buy for Windows, but usable.

I believe if Sun and MS had provided optimized AOT native compilers as part of Java and .NET, instead of waiting 20 years to do so or relying on third parties, C++ use cases would be even less than they are nowadays.

Just in cases someone mentions NGEN, it is just intended to enable fast startups.

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.

For building GUI small/medium applications on windows I don't think there have never existed anything more convenient. Not to mention that usually your only deliverable was a single executable file.

Agreed and it was fast at runtime as well, not far off the same speed as C++ for a lot of things, I remember using it for some pretty performance intensive stuff and you could easily drop to assembly if needed.

It was a fantastic development environment even by modern standards but for its time it was well ahead of the curve.

I still try out Lazarus once in a while just for nostalgia :)

It IS fast.

We are doing a project with a company that uses it for all their Windows applications.

Delphi conferences are still a thing in Germany.

It was pretty big over here as well, the last version I used in anger was 7 but I still see the odd job posted for Delphi devs.

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

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

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%.

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

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.

Intel essentially has a monopoly on the market for desktop cpus, which can't help.

Affordable air-cooled x86-CPUs at > 4GHz will disrupt that very quickly.

Is x86 still needed?

I mean the ARM stuff is getting more traction and maybe it will run around x86 in the next years.

POWER already did by sucking vast amounts of electricity and dumping heat. Getting a high IPC isn't easy and leads to lots of thermal dissapation. Odd arches might make a comeback but don't help much.

If we assume that the economic model of CPU manufacturing is essentially

- very large upfront costs in R&D and improved fabs

- The marginal cost for each additional CPU manufactured is, in fact, very low

Then, isn't this pretty much the textbook example of a natural monopoly?

I.e. in such a case, if the market was spread out over more suppliers, would the customer in the end pay more due to the vendors amortizing the R&D costs over fewer units sold? Vs. the current situation where customers are paying monopoly prices to the incumbent vendor.

> We know how to make them faster.

Well... Seems the reason for the "multicore revolution" that started around 2005-ish(?) for desktop/x86 server CPU's was largely that CPU designers ran out of ways to make cpu's faster. Previously, there was always some micro-architectural feature waiting to be exploited (say, caches, pipelining, superscalar, OoOE, branch prediction, etc.) that enabled processor designers to utilize the transistors Moore's law gave us in order to increase single-threaded performance. However, it seems that at about the same time we ran into a triple whammy;

1) at about the same time that processor designers ran out of new tricks (with massive payoffs) to pull from their sleeves.

2) existing tricks ran far into diminishing returns

3) transistor scaling wasn't as good as before (the "power wall")

tl;dr: We seem to know a lot of tricks that can increase performance a bit, albeit at a heavy cost in power consumption.

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.

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

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

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.

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

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.

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

Technically its a very limited form of garbage collection... Then again with this definition so is just not free-ing anything and letting the OS cleanup after process exit.

I believe it's manually freed.

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).

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.

Reply on news.ycombinator.com