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.