5 ms·

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

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 10y 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 10y 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.
  - ronjouch 10y ago
    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/tutorial.html 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.00897.x/abstract 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://news.ycombinator.com/item?id=12245458 , https://fgiesen.wordpress.com/2016/08/07/why-do-cpus-have-multiple-cache-levels/ 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 https://www.youtube.com/watch?v=rX0ItVEVjHc
    - hrydgard 10y ago
      I-cache and D-cache means instruction cache and data cache.
    - kibwen 10y ago
      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-data-cache-and-instruction-cache http://stackoverflow.com/questions/22394750/what-is-meant-by...
  - vvanders 10y ago
    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.
valarauca1 10y 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.
- marcosdumay 10y 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.
  - valarauca1 10y ago
    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/jemalloc.pdf https://people.freebsd.org/~jasone/jemalloc/bsdcan2006/jemal...
gcp 10y 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 10y ago
  Further, all stack allocations for a frame can be coalesced into a single add/sub.
nnethercote 10y 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.

unwind 10y 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 10y 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.
- ronjouch 10y ago
  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/tutorial.html 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.00897.x/abstract 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://news.ycombinator.com/item?id=12245458 , https://fgiesen.wordpress.com/2016/08/07/why-do-cpus-have-multiple-cache-levels/ 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 https://www.youtube.com/watch?v=rX0ItVEVjHc
  - hrydgard 10y ago
    I-cache and D-cache means instruction cache and data cache.
  - kibwen 10y ago
    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-data-cache-and-instruction-cache http://stackoverflow.com/questions/22394750/what-is-meant-by...
- vvanders 10y ago
  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.

valarauca1 10y 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.

marcosdumay 10y 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.
- valarauca1 10y ago
  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/jemalloc.pdf https://people.freebsd.org/~jasone/jemalloc/bsdcan2006/jemal...

gcp 10y 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 10y ago
Further, all stack allocations for a frame can be coalesced into a single add/sub.

nnethercote 10y 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.