Allocators in Rust

http://smallcultfollowing.com/babysteps/blog/2014/11/14/allocators-in-rust/

by adamnemecek • 12 years ago

129 19 12 years ago

wyager2• 12 years ago

Why does the default glibc allocator have relatively poor performance? (What makes it slower, and why hasn't it been changed?)

dmix• 12 years ago

This stuff is out of the scope of my knowledge, but I do know libraries such as OpenBSD's memory allocator are slower due to security optimizations. jemalloc is not known for it's security, instead it seems to be focused on performance. Security features such as ASLR, not leaving old memory around, zeroing out memory on release, etc, are not things that improve an allocators performance.

wyager2• 12 years ago

Good point. I wonder if Rust's allocator needs fewer security features because of heavy compile-time heap safety checking. For example, I don't believe use-after-free or double-free is possible in Rust due to Rust's lifetime system (barring use of unsafe code blocks).

db48x3• 12 years ago

I'm not sure the point about ASLR is entirely correct; ASLR does randomize the addresses returned by mmap (slightly), and jemalloc primarily uses mmap to allocate its arenas.

db48x3• 12 years ago

The man page explains several of the differences (http://www.canonware.com/download/jemalloc/jemalloc-latest/d...). These include a different API (you can pass in some flags that explicitly direct it how to do alignment, initialization, etc), reduced use of sbrk in favor of mmap, multiple arenas for allocations of different sizes, per-cpu arenas to eliminate lock contention, etc.

Mozilla has been using jemalloc since the release of Firefox 3 in 2008, primarily because having multiple arenas for allocations of different sizes means that you end up with less fragmentation over time. Fragmentation happens when you deallocate ten 100-byte objects that are scattered around in memory, then need to allocate one thousand-byte object. You can't reuse those 10-byte empty spots in memory, because that 1000-byte allocation has to be contiguous. This means that your total memory usage has to grow. Jemalloc puts small allocations into buckets where they'll be closer together, making it more likely that new allocations will be able to fill the holes left by deallocations, and that freeing small objects will eventually empty a memory page, allowing you to return the page to the OS.

I remember that we were all pretty chuffed at the improvements in Firefox's memory usage; it was quite significant and would surely reduce the general perception that Firefox was a memory hog. Just using jemalloc reduced memory usage by 22% (http://blog.pavlov.net/2008/03/11/firefox-3-memory-usage/ has a really amazing graph comparing FF2 and FF3 to IE7).

Rust uses jemalloc for the same reasons; there's just no technical reason not to use it.

azakai• 12 years ago

Rust uses jemalloc for the same reasons; there's just no technical reason not to use it.

If so, I wonder if this is true for every language, then? For example, for C++, should gcc and clang emit binaries with jemalloc linked in?

pcwalton• 12 years ago

It tends to take more locks in multithreaded scenarios instead of making heavy use of per-thread arenas.

nteon2• 12 years ago

the glibc allocator is based off of Doug Lea's malloc that was developed before multithreading was common. Optimizations for multiple threads + arenas were retrofitted on top of the existing code, whereas jemalloc was designed more recently from scratch for multi-threaded workloads, and was able to take advantage of recent research.

gosu• 12 years ago

Probably the fact that it eagerly coalesces newly freed blocks where high performance allocators like tcmalloc and jemalloc use slabs of fixed-sized blocks which are never coalesced. Coalescing will load adjacent blocks into cache, and it probably implies doubly linked lists where slab allocators can get away with cache-friendlier single links or bitmaps etc. (Because you probably have to remove a block from the middle of a free list if you've just coalesced it with a newly freed block). It turns out cache footprint is key for speed and scalability in allocators, so that's a big problem.

I'm embarassed to link this twice in a row now, but at one point I played around with the perf of a couple allocators, including glibc's ptmalloc. I wound up answering exactly this question, at least for some simple use cases: http://www.andrew.cmu.edu/user/apodolsk/418/finalreport.html.

Comments in ptmalloc sources say they basically stick to the algorithm described here: http://gee.cs.oswego.edu/dl/html/malloc.html.

ExpiredLink• 12 years ago

glibc allocator have relatively poor performance

Famous last words before someone creates a bug-ridden, slow replacement. See also the papers of Emery Berger et al.

lgeek• 12 years ago

I would suggest reading the jemalloc paper [0]. The main improvements compared to phkmalloc are:

* improved cache locality

* reduced false sharing

* use of multiple arenas for reduced lock contention

[O] http://people.freebsd.org/~jasone/jemalloc/bsdcan2006/jemall...

emeryberger• 12 years ago

No good reason for why it hasn't changed, except that the underlying single-threaded allocator (Doug Lea's malloc) is really good. The multithreaded version, which is a "per-thread" (not really) wrapper around the Lea allocator has serious problems that have been known for a long time. I wrote a paper outlining and demonstrating the problems in 2000. The inertia is difficult to explain.

Paper here: http://people.cs.umass.edu/~emery/pubs/berger-asplos2000.pdf

Hoard replacement allocator here: http://www.hoard.org/

(Note that Hoard's design has evolved considerably since 2000; the Mac OS X allocator is based on an older version.)

rdw• 12 years ago

I was curious about Rust's support for within-application custom allocators, it looks like this is still under discussion: https://github.com/rust-lang/rfcs/pull/244

rdc12• 12 years ago

"How much allocation takes place in Rust vs in the other language?"

Wouldn't the distribution of the allocations matter too, switching between the two allocators frequently showing the worst case and reuse of one of two minimising the effect.

Allocators in Rust

Related Stories