Allocators

An "allocator" is a library that sets aside an area in computer memory -- called the "heap" as opposed to the "stack" and "static" memory -- for use by some other program. An allocator may or may not keep track of these "allocations" in its private mechanism and it may or may not allow for callers to "return" allocations to the allocator, thus freeing up that memory for us by another caller. If you've ever called malloc, free et all in C you've interacted with an allocator. If you've used a language with a runtime that manages memory you have done so indirectly. If you've only programmed for embedded devices that manage memory themselves and allocate only at startup then, well, kudos.

The third chapter of my new book introduces the memory heirarchy of a computer, starting with static memory, working into the stack and out to the heap. By the end of the chapter the reader's got the ability to swap in new allocators but no ability to write them, on account of the book hasn't built up any expertise in thread-safe programming. Next chapter aims to teach that very thing and, in so doing, will build up several allocators. We'll see how successful I am. Anyhow, I've been going back through the literature on allocators. Here's what's interesting I've turned up so far, in no particular order:

Andrei Alexandrescu: Policy–Based Memory Allocation
David Gay et al: Memory Management with Explicit Regions
Emery Berger et al: Composing High-Performance Memory Allocators
Jason Evans: A Scalable Concurrent malloc(3) Implementation for FreeBSD
Jeff Bonwick: Magazines and Vmem: Extending the Slab Allocator to Many CPUs and Arbitrary Resources
Jeff Bonwick: The Slab Allocator: An Object-Caching Kernel Memory Allocator
Maged Michael: Scalable Lock-Free Dynamic Memory Allocation
Paul Lietar et al: snmalloc: A Message Passing Allocator
Trishul M. Chilimbi et al: Cache-Conscious Structure Definition

Rust Allocators

These are interesting Rust allocators that I'm aware of: