News for hackers. Stuff that matters.
Re:How to speed up the Rust compiler some more by ronjouch on Wednesday November 23, 2016 @08:10AM (#13022356)
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).

Re:How to speed up the Rust compiler some more by valarauca1 on Wednesday November 23, 2016 @08:58AM (#13022644)

    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.

Re:How to speed up the Rust compiler some more by marcosdumay on Wednesday November 23, 2016 @11:01AM (#13023479)
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.
Re:How to speed up the Rust compiler some more by valarauca1 on Wednesday November 23, 2016 @11:34AM (#13023723)
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...

Re:How to speed up the Rust compiler some more by unwind on Wednesday November 23, 2016 @08:16AM (#13022395)
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.

Re:How to speed up the Rust compiler some more by twoodfin on Wednesday November 23, 2016 @10:09AM (#13023125)
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.
Re:How to speed up the Rust compiler some more by ronjouch on Wednesday November 23, 2016 @10:28AM (#13023244)
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

Re:How to speed up the Rust compiler some more by kibwen on Wednesday November 23, 2016 @10:51AM (#13023401)
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...
Re:How to speed up the Rust compiler some more by hrydgard on Wednesday November 23, 2016 @10:43AM (#13023343)
I-cache and D-cache means instruction cache and data cache.
Re:How to speed up the Rust compiler some more by vvanders on Wednesday November 23, 2016 @12:08PM (#13023959)
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.

Re:How to speed up the Rust compiler some more by nnethercote on Wednesday November 23, 2016 @05:18PM (#13026243)
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.
Re:How to speed up the Rust compiler some more by gcp on Wednesday November 23, 2016 @09:03AM (#13022672)
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.
Re:How to speed up the Rust compiler some more by Rusky on Wednesday November 23, 2016 @05:03PM (#13026130)
Further, all stack allocations for a frame can be coalesced into a single add/sub.
Re:How to speed up the Rust compiler some more by stevedonovan on Wednesday November 23, 2016 @04:37AM (#13021326)
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.
Re:How to speed up the Rust compiler some more by barrkel on Wednesday November 23, 2016 @06:31AM (#13021787)
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.)

Re:How to speed up the Rust compiler some more by pjmlp on Wednesday November 23, 2016 @07:04AM (#13021963)
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.

Re:How to speed up the Rust compiler some more by jerf on Wednesday November 23, 2016 @09:14AM (#13022744)
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.)

Re:How to speed up the Rust compiler some more by stevedonovan on Wednesday November 23, 2016 @09:50AM (#13022988)
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.”
Re:How to speed up the Rust compiler some more by marcosdumay on Wednesday November 23, 2016 @11:04AM (#13023502)
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).

Re:How to speed up the Rust compiler some more by paulddraper on Wednesday November 23, 2016 @09:07PM (#13027458)
C++/Boost does that
Re:How to speed up the Rust compiler some more by marcosdumay on Thursday November 24, 2016 @06:56AM (#13029857)
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.

Re:How to speed up the Rust compiler some more by pjmlp on Wednesday November 23, 2016 @11:16AM (#13023605)
Go's minimum bar is well below Active Oberon, Delphi, Eiffel, Java and .NET ones.
Re:How to speed up the Rust compiler some more by jerf on Wednesday November 23, 2016 @02:49PM (#13025294)
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.
Re:How to speed up the Rust compiler some more by pjmlp on Wednesday November 23, 2016 @03:56PM (#13025779)
> 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.

Re:How to speed up the Rust compiler some more by jerf on Wednesday November 23, 2016 @09:40PM (#13027588)
"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.

Re:How to speed up the Rust compiler some more by pjmlp on Wednesday November 23, 2016 @11:30AM (#13023698)
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.

Re:How to speed up the Rust compiler some more by neikos on Wednesday November 23, 2016 @09:40AM (#13022920)
python has a http server coming with the standard installation
Re:How to speed up the Rust compiler some more by adrianN on Wednesday November 23, 2016 @07:09AM (#13021986)
Especially given the CPUs used in the computers back when Delphi was popular.
Re:How to speed up the Rust compiler some more by pjmlp on Wednesday November 23, 2016 @07:50AM (#13022239)
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).
Re:How to speed up the Rust compiler some more by noir_lord on Wednesday November 23, 2016 @09:10AM (#13022711)
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.

Re:How to speed up the Rust compiler some more by mickronome on Wednesday November 23, 2016 @10:04AM (#13023089)
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.
Re:How to speed up the Rust compiler some more by noir_lord on Wednesday November 23, 2016 @10:45AM (#13023351)
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 :)

Re:How to speed up the Rust compiler some more by pjmlp on Wednesday November 23, 2016 @11:32AM (#13023712)
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.

Re:How to speed up the Rust compiler some more by noir_lord on Wednesday November 23, 2016 @01:19PM (#13024521)
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.
Re:How to speed up the Rust compiler some more by grokys on Wednesday November 23, 2016 @04:52AM (#13021394)
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!

Re:How to speed up the Rust compiler some more by stevedonovan on Wednesday November 23, 2016 @05:15AM (#13021486)
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...

Re:How to speed up the Rust compiler some more by pas on Wednesday November 23, 2016 @05:57AM (#13021636)
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

Re:How to speed up the Rust compiler some more by pjmlp on Wednesday November 23, 2016 @07:02AM (#13021949)
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

Re:How to speed up the Rust compiler some more by amelius on Wednesday November 23, 2016 @04:44AM (#13021357)
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.
Re:How to speed up the Rust compiler some more by pjmlp on Wednesday November 23, 2016 @06:59AM (#13021938)
You mean like Lisp, Smalltalk?
Re:How to speed up the Rust compiler some more by adamrezich on Wednesday November 23, 2016 @09:11AM (#13022726)
Also that language Jonathan Blow is working on https://www.youtube.com/watch?v=HLk4eiGUic8
Re:How to speed up the Rust compiler some more by vanderZwan on Wednesday November 23, 2016 @08:21AM (#13022425)
The new kid on the Smalltalk block is Pharo:

http://pharo.org/

Re:How to speed up the Rust compiler some more by flukus on Wednesday November 23, 2016 @09:55PM (#13027656)
Traditional as in c? Object files would maintain state and build incrementally.
Re:How to speed up the Rust compiler some more by wyldfire on Wednesday November 23, 2016 @01:33AM (#13020570)
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%.

Re:How to speed up the Rust compiler some more by corndoge on Wednesday November 23, 2016 @03:30AM (#13021070)
we should just make computers faster, intel is failing, moores law
Re:How to speed up the Rust compiler some more by thecopy on Wednesday November 23, 2016 @03:33AM (#13021080)
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.
Re:How to speed up the Rust compiler some more by jabl on Wednesday November 23, 2016 @02:27PM (#13025085)
> 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.

Re:How to speed up the Rust compiler some more by RX14 on Wednesday November 23, 2016 @03:42AM (#13021131)
Intel essentially has a monopoly on the market for desktop cpus, which can't help.
Re:How to speed up the Rust compiler some more by jabl on Wednesday November 23, 2016 @02:36PM (#13025179)
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.

Re:How to speed up the Rust compiler some more by thecopy on Wednesday November 23, 2016 @03:46AM (#13021149)
Affordable air-cooled x86-CPUs at > 4GHz will disrupt that very quickly.
Re:How to speed up the Rust compiler some more by k__ on Wednesday November 23, 2016 @06:42AM (#13021843)
Is x86 still needed?

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

Re:How to speed up the Rust compiler some more by wbl on Wednesday November 23, 2016 @02:09PM (#13024941)
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.
Re:How to speed up the Rust compiler some more by vanderZwan on Wednesday November 23, 2016 @08:24AM (#13022440)
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.
Re:How to speed up the Rust compiler some more by snovv_crash on Wednesday November 23, 2016 @09:15AM (#13022751)
You can find roughly that here, unfortunately mixed in with everything else though:

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

Re:How to speed up the Rust compiler some more by nnethercote on Wednesday November 23, 2016 @05:21PM (#13026257)
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.
Re:How to speed up the Rust compiler some more by TazeTSchnitzel on Wednesday November 23, 2016 @09:31AM (#13022858)
Is heap allocation actually unavoidable? PHP uses an arena allocator for its AST. I don't know how applicable that could be to Rust.
Re:How to speed up the Rust compiler some more by rkangel on Wednesday November 23, 2016 @11:26AM (#13023674)
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).

Re:How to speed up the Rust compiler some more by Manishearth on Wednesday November 23, 2016 @11:46AM (#13023809)
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.
Re:How to speed up the Rust compiler some more by hackcrafter on Wednesday November 23, 2016 @11:04AM (#13023510)
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.

Re:How to speed up the Rust compiler some more by TazeTSchnitzel on Thursday November 24, 2016 @09:27AM (#13030449)
PHP's compiler is written in C, and its AST isn't garbage-collected. I think we just throw out the entire arena, actually.
Re:How to speed up the Rust compiler some more by slededit on Friday November 25, 2016 @01:13AM (#13034680)
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.
Re:How to speed up the Rust compiler some more by TazeTSchnitzel on Friday November 25, 2016 @06:59PM (#13040829)
I believe it's manually freed.