Alexandrescu Replaces std::allocator With Composable Memory Model
CppCon
Standard C++ memory allocation fails because std::allocator couples typed object construction with raw byte management, requiring a replacement built on untyped blocks and composable primitives.
AI-assisted summary of CppCon 2015: Andrei Alexandrescu “std::allocator...” — original source. Check the original for full context.
Source published:
Key ideas
- std::allocator has fundamentally failed modern C++ because it was historically engineered to abstract 16-bit segmented x86 architectures rather than serve as a generic, composable memory allocation framework. (14:09)
- True composability in allocator design requires operating on raw untyped memory blocks (void* and size_t) rather than strongly typed objects, separating object lifecycle management from storage acquisition. (18:03)
- Deallocation in layered or fallback allocators is mathematically impossible without either storing block sizes or exposing an owns(Block) query to verify block provenance across tiers. (30:45)
- Production-grade general allocators can be constructed entirely from orthogonal, composable building blocks—such as Segregators, FallbackAllocators, FreeLists, and Bitmapped Arenas—nested in compile-time search trees. (63:42)
Detailed notes
## Background This talk was delivered by Andrei Alexandrescu and published on YouTube by the CppCon channel on October 13, 2015. According to the page description, the presentation critiques the historical design failures of std::allocator and introduces a generic, componentized, and composable memory allocator architecture designed from first principles for modern, high-performance C++ applications.
## TL;DR Alexandrescu argues that std::allocator fundamentally failed because it was built around obsolete segmented-memory pointer models, tightly coupled object construction with untyped byte allocation, and completely lacked composability. He outlines the core requirements for an effective memory allocator, demonstrating that allocators must trade in raw memory blocks containing both a pointer and a size rather than typed elements. By introducing foundational building blocks—including NullAllocator, FallbackAllocator, FreeList, Affix Allocator, BitmappedBlock, and Segregator—he shows how developers can assemble industrial-strength, custom allocators tailored to exact application workloads. The proposed composable API incorporates crucial operational primitives such as owns(), good_size(), expand(), and scoped batch deallocation to deliver maximum runtime efficiency without manual heap chaos.
## Atmosphere & style The presentation is energetic, irreverent, and intellectually combat-ready, driven by Alexandrescu's sharp wit and theatrical declarations that he has arrived on a 'war path' to dismantle sacred cows. He commands the room with spontaneous audience banter, sharp comedic analogies comparing allocators to Crocs, and self-deprecating commentary on slide syntax highlighting bugs. Watching the talk feels like an intense, fast-paced masterclass that shifts fluidly from historical software post-mortems to live architectural design, blending technical rigor with genuine showmanship.
## Bulletin - [14:09](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=849s) std::allocator has fundamentally failed modern C++ because it was historically engineered to abstract 16-bit segmented x86 architectures rather than serve as a generic, composable memory allocation framework. - [18:03](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=1083s) True composability in allocator design requires operating on raw untyped memory blocks (void* and size_t) rather than strongly typed objects, separating object lifecycle management from storage acquisition. - [30:45](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=1845s) Deallocation in layered or fallback allocators is mathematically impossible without either storing block sizes or exposing an owns(Block) query to verify block provenance across tiers. - [01:03:42](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=3822s) Production-grade general allocators can be constructed entirely from orthogonal, composable building blocks—such as Segregators, FallbackAllocators, FreeLists, and Bitmapped Arenas—nested in compile-time search trees.
## Key takeaways - [05:18](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=318s) The classic C memory API exhibits a structural asymmetry where malloc takes a size but free takes only a bare pointer, forcing runtimes to manage hidden metadata or page tables. - [11:56](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=716s) Class-level operator new and operator new[] introduce severe language quirks and should be avoided in favor of dedicated memory allocation abstractions. - [18:03](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=1083s) std::allocator conflated raw memory allocation with object construction and destruction, unnecessarily binding allocation policies to C++ object types. - [21:44](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=1304s) Realistic allocators are inherently stateful, meaning stateless allocator models force undesirable reliance on global state or hidden monostates. - [24:10](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=1450s) Composability is the essential first principle of allocator design, matching the tiered architectures of industrial allocators like jemalloc and dlmalloc. - [25:25](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=1525s) NullAllocator acts as an immutable compositional terminator, safely terminating fallback allocation chains and asserting on invalid deallocations. - [30:45](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=1845s) A fallback allocator cannot safely implement deallocate without an owns() primitive that checks whether a given block originated from the primary allocator. - [35:44](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=2144s) Combining a fast stack bump allocator with a general-purpose heap fallback provides small-buffer optimization that can satisfy up to 95% of throughput locally. - [41:00](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=2460s) Compulsive alignment rounds every requested allocation size immediately to the boundary constraint, preventing cascading alignment drift across consecutive bump allocations. - [43:20](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=2600s) Free lists achieve near-zero runtime space overhead by reusing the payload memory of deallocated blocks for intrusive next-pointers, though they risk retaining memory indefinitely. - [45:28](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=2728s) Reused blocks in free lists are often cold in CPU cache, making writes to intrusive pointers during deallocation a hidden source of cache line misses. - [56:00](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=3360s) Affix allocators enclose payload allocations in compile-time prefixes and suffixes to provide canary guard bands, dynamic profiling, and leak tracking with zero overhead when disabled. - [59:08](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=3548s) Static registration structures embedded in allocation call sites allow tracking caller origins and invocation counts at runtime without triggering secondary dynamic heap allocations. - [01:01:48](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=3708s) BitmapBlock allocators isolate allocation metadata away from user data into dedicated bit arrays, keeping allocator bookkeeping hot in cache without polluting payload memory. - [01:03:42](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=3822s) Segregators split allocation routing strictly by size thresholds at compile time, enabling deep binary trees of specialized sub-allocators without requiring owns() checks. - [01:07:03](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=4023s) A comprehensive minimal allocator API should provide primitives like good_size(n) to allow containers such as std::vector to consume slack capacity without extra allocations.
## Detailed walkthrough ### [00:00](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=0s) Working Titles and the War Path Against `std::allocator`
Andrei Alexandrescu opens the session early, joking that starting early is necessary because they are bound to finish late. He explains the evolution of his working titles. Initially, he floated a cryptic title that left people baffled, leading him to consider a playful pun: an allegation about an alligator that ate someone's Crocs. The joke illustrates his core thesis: just as an alligator has virtually nothing to do with casual footwear, there is minimal connection between `std::allocator` and actual, practical memory allocation.
He then considered the title *"Design allocators that don't (not work)."* While grammatically malicious in English, it is logically sound to a programmer if one treats `"not work"` as a grouped verb expression inside parentheses. Alexandrescu makes his stance toward the standard library's allocator design unmistakably hostile, declaring to the audience:
> “I’m here to destroy, okay, I’m on a war path right now.”
The goal, however, is constructive. He notes that taking cheap shots at `std::allocator` is far too easy; the real objective of the talk is to understand how to design high-performance, composable memory allocators from first principles. Invoking Bjarne Stroustrup, he reminds the audience that this is C++, where runtime efficiency and layout control are paramount.
```mermaid flowchart LR accTitle: Evolution of Talk Titles accDescr: Andrei Alexandrescu's transition from humorous working titles to his serious thesis on allocators. A["Allegation about an alligator"] --> B["Design allocators that don't (not work)"] B --> C["Core Mission: Build allocator APIs that actually work"] ```
---
[02:05](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=125s) The Cyclical History of Memory Allocation (1983–Present)
Memory allocation has followed an intriguing historical cycle. Alexandrescu reflects on how the fortunes of memory allocator implementers have swung back and forth over several decades:
- **1983 (The K&R Era):** When Brian Kernighan and Dennis Ritchie published the second edition material featuring their minimal storage allocator, it was a revelation. For the first time, programmers could implement custom memory management entirely in a high-level systems language using `void*`, casts, and layout manipulation—without dropping into raw assembly language. Compared to contemporary languages like Pascal, Fortran, or Lisp, C offered unprecedented power to put bits precisely where the programmer wanted. Dynamic memory allocation, once an exotic feature, suddenly became the default hammer for every programming nail. - **1993 (The Custom Allocator Boom):** A decade later, the naive global `malloc` implementations shipped by standard libraries had become severe performance bottlenecks. Application developers realized that almost any hand-rolled custom allocator tailored to specific data structures outperformed the general-purpose system `malloc`. - **2003 (The Modern Allocator Renaissance):** General-purpose allocators fought back. Advanced multi-threaded designs—such as Hoard, jemalloc, and TCMalloc—reclaimed performance ground through thread caching and sophisticated binning, matching or beating naive custom allocators. - **Present Day:** The industry sits in a balanced, pragmatic middle ground. Modern general-purpose allocators are very capable, but high-performance applications still routinely require domain-specific allocation patterns to minimize overhead and fragmentation.
---
[05:18](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=318s) The Fundamental Asymmetry of `malloc` and `free`
Examining the classic C memory API reveals a long-standing architectural flaw. When allocating memory via `malloc(size)`, the caller specifies the requested byte count; but when releasing it via `free(ptr)`, the caller passes only the bare pointer:
```c void* malloc(size_t size); void free(void* ptr); ```
When asked why this signature is problematic, the audience immediately identifies performance. Because `free` receives no size parameter, the allocator itself is forced to record and look up the metadata for every allocated chunk—typically by prepending hidden header prefixes or maintaining out-of-band page-run tables. The caller frequently already knows the exact size of the buffer being destroyed (for instance, inside a typed object destructor or container), yet the API prevents that size from being communicated back down to the memory subsystem.
Alexandrescu highlights ongoing standards efforts—referencing a formal C++ proposal number (N3778 / sized deallocation)—aimed at fixing the performance penalties incurred by global `operator delete` lacking size information. Pointing out Howard Hinnant in the audience, he jokes about the exhausting grind required to get memory allocation proposals altered in standard committees:
> “I was talking to this fine gentleman Howard Hinnant, and he says, I’m like, 'Been there, done that, and I would hate trying to do it again—doing anything, exacting any change about memory allocation in the respective standards.'”
Had C started from a clean slate, the primitive unit of currency would be a self-contained block structure rather than a raw address:
```cpp struct Block { void* ptr; size_t length; }; ```
Under this model, allocation returns a `Block`, and deallocation accepts that same `Block` back, freeing the underlying engine from redundant size management and header tracking.
---
[08:48](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=528s) Operator `new`, Type Information, and Syntactic Quirks
Alexandrescu turns to the next historical step: C++'s `operator new`. While `new` introduces strong typing, it quickly throws that advantage away under the hood because the default implementations simply delegate directly down to `malloc`. This inheritance also explains the conspicuous absence of an `operator renew` to pair with C's powerful, if notoriously misused, `realloc`.
Beyond deallocation metadata loss, operator `new` introduces bizarre syntactic ambiguities in the language grammar itself. For example: - `int` is a distinct type. - `int[100]` is equally a well-formed type representing a fixed-size array of 100 integers.
Yet evaluating `new int[100]` does not return a pointer to a fixed-size array of 100 integers (`int(*)[100]`). Instead, the language hijacks the syntax, treating the bracketed expression as a request to dynamically allocate a variable runtime count of integers, degrading the return type to a raw `int*`.
Alexandrescu registers his vigorous disagreement with how the language evolved:
> “Operator `new` was designed to work with `malloc`, but you know, it didn't—I have, you know, like in that movie, like: I protest!”
Furthermore, native C++ operators impose a complete communication firewall between memory allocation and object construction: `operator new` runs in isolation without knowing which constructor arguments will be evaluated, severely hampering class-specific memory placement strategies.
[11:56](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=716s) "The Great Array Distraction" and Operator New
Andrei warns the audience against clever class-level allocation tricks, quipping that anyone struggling with it should consider attending "Operator New Anonymous" (OA) meetings. In his view, the healthiest choice a programmer can make regarding class-level `operator new` is complete avoidance: “I think the best trick you can do with class level operator new is to forget all about it and never use it and like really pretend it doesn't exist in the language and then you'll be happy you you lead a better life.” He then introduces what he dubs the "Great Array Distraction" (TGAD). The language already had the idiosyncratic `operator new`, but then language designers felt compelled to invent a bracketed variant, `operator new[]`, strictly for allocating arrays, alongside a rigid ritual: matching scalar `new` with scalar `delete`, and array `new[]` with array `delete[]`.
To demonstrate the absurdity of this rule, Andrei polls the room on why the distinction even needs to exist. An audience member points out that calling single-object `delete` on an array will simply invoke the first destructor it encounters and fail to tear down the rest. Andrei concedes this mechanical explanation, but argues that from an architectural perspective, there is no legitimate reason for this dual-syntax machinery to exist in the first place—it serves only to make life miserable for developers. Turning directly to the camera operator tracking his movements across the stage, Andrei jokes that if he were trying to escape from a prison, having this camera following his every step would make it impossible. He then leaves no doubt about his stance: “I unrecommend operator new for any serious use of memory allocation.”
- Class-level `operator new` is dismissed as an anti-pattern best purged entirely from one's coding habits. - The Great Array Distraction (TGAD) introduced `new[]` and `delete[]` to handle array destructions, complicating memory management without fundamentally improving allocation. - Andrei rejects `operator new` as unsuitable for serious, high-performance systems programming.
---
[14:09](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=849s) The Real Origin of `std::allocator` and the 20-Year Problem
Andrei pivots to the historical reality of `std::allocator`, asserting that the single funniest fact about it is that it was never genuinely designed for general-purpose memory allocation. When he asks the audience what its true purpose was, Pablo Halpern calls out pointer types, confirming Andrei's point: it was conceived to abstract away the segmented memory architectures of 16-bit systems—specifically 20-bit pointers broken into segment and offset pairs ("near" and "far" pointers). Andrei jokes that anyone old enough to remember segment/offset gymnastics should turn to the younger attendees to explain the horror, before advising that the younger generation is honestly better off not knowing. Despite the disappearance of segmented architectures, `std::allocator` lingered in the standard all the way through C++17, functioning like a single, stubborn square wheel on a multi-wheeled transport truck.
```mermaid flowchart TD accTitle: Historical Evolution of std::allocator accDescr: Diagram tracing std::allocator from 1990s segmented memory models to modern C++ where its original purpose was removed.
subgraph Origin["1990s Design: Segmented Architecture"] A["16-bit Systems / 20-bit Pointers"] --> B["Near & Far Pointer Abstractions"] B --> C["std::allocator finalized (pre-1994)"] end
subgraph Subsided["Hardware Evolution"] C --> D["Segmented memory models disappear"] D --> E["C++ Committee strips near/far pointer machinery"] end
subgraph Present["Modern C++ Reality"] E --> F["std::allocator remains: square wheel on the truck"] F --> G["Lacks native allocation algorithms"] end ```
To illustrate just how broken the abstraction remains, Andrei highlights Alisdair Meredith's presentation from CppCon 2014, titled "Making Allocators Work." Andrei performs a linguistic critique of that title: `std::allocator` had been standardized twenty years earlier (prior to 1994), yet two decades later, the community was still attending a grueling, 180-minute two-part marathon session just trying to get allocators to function properly. As Andrei puts it: “There's no talk like making sort work.” Furthermore, having sat through most of those three hours, Andrei noticed there was not a single slide dedicated to actual memory allocation algorithms. He emailed Alisdair asking for the slide deck so he could cite it, but received total silence in return because, Andrei jokes, Alisdair knew he was going to make fun of it.
- `std::allocator` originated as a stopgap abstraction for 16-bit segmented x86 architectures handling 20-bit near and far pointers, not as an engine for memory management. - The C++ standards committee eventually stripped the near/far pointer support from the allocator specification, thereby dismantling the exact problem it had originally been created to solve. - Alisdair Meredith's 2014 CppCon presentation ("Making Allocators Work") ran for 180 minutes across two back-to-back 90-minute slots without dedicating a single slide to allocation mechanics.
---
[18:03](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=1083s) Flaws in `std::allocator`: Types, Factories, and Void Stars
Andrei unpacks why `std::allocator` fails as an allocation mechanism from first principles, declaring: “The short story here is that std::allocator is not a great allocator because it was not designed for that purpose; it was designed for near and far pointers.” The most fundamental design error is parameterizing the allocator on a specific type `T`. Memory allocators do not need to care about object types; they care exclusively about size and alignment. Andrei asks the room whether anyone needs to allocate an `int` differently than an `unsigned int`—they share identical byte layouts and sizes. Even across completely unrelated types `T1` and `T2` that both happen to require 128 bytes, an optimal allocator configured for that size and alignment handles both equally well. Tying an allocator's identity to a data type was sensible only when pointer representations differed across types, but for modern allocation it is an active hindrance.
This conceptual confusion led directly to conflating an allocator with an object factory. Instead of merely handling memory buffers, `std::allocator` was saddled with `construct` and `destroy` member functions. Andrei playfully calls out Howard Hinnant in the audience, joking that the committee still had not excised these extraneous methods: “They didn't remove them, those bastards!” Adding insult to injury, despite claiming these high-level object-construction factory powers, the allocator still trades underneath in raw `void*` pointers. This architectural mismatch produced notorious crutches like `rebind`, which containers must use simply to allocate internal bookkeeping nodes of a different type than the stored value. Andrei summarizes the proper conceptual contract cleanly: “So what I'm seeing here is allocators should trade in memory blocks, void* and size_t, that's it.”
- Allocation strategies depend strictly on request size and alignment constraints, not semantic object types. - Allocators were mistakenly turned into factories by coupling memory acquisition with object lifecycle operations (`construct` and `destroy`). - The type-parameterized model necessitated awkward template metaprogramming workarounds, most prominently template `rebind`. - A clean memory allocator interface should operate entirely on memory blocks characterized by a base pointer (`void*`) and an extent (`size_t`).
---
[21:44](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=1304s) The Myth of Statelessness and the Need for Composition
Another foundational flaw Andrei attacks is the historical assumption that allocators are stateless. He ridicules the notion that an object dispensing finite physical resources could somehow carry no state: “A memory allocator that giving me memory has no state, right? This is very interesting, it's like the empty bottle that you keep on drinking water from and it's just you know, it's like Sinbad, you know the, it's the story, it's like magic, you know it's empty but I'm pouring from it.” In reality, every allocator has state; if it appears stateless, it is simply hiding its state behind a global heap or a monostate pattern ("a global except it has a great name"). Andrei acknowledges that C++14 finally permitted stateful allocators, pointing out committee members John Lakos and Pablo Halpern sitting in the front row and joking that the audience should either thank them or throw tomatoes at them depending on their perspective.
However, Andrei argues that even modern standard revisions missed the single most critical structural requirement of allocator design: composability. When building industrial memory allocators, one cannot rely on a single monolithic strategy. Looking at proven allocators like Doug Lea's `dlmalloc`, the implementation immediately branches into different sub-allocators based on request thresholds (for instance, applying small-object strategies below one kilobyte and completely different mechanisms above it). Andrei emphasizes that modularity is non-negotiable: “If you want to write an allocator, you got to make it composable.” An effective allocator architecture must consist of small, focused building blocks that can be stacked, cascaded, and composed to fit application-specific memory consumption patterns.
- Classical standard allocators enforced an unrealistic stateless model, forcing implementations to rely on hidden global state. - C++14 introduced stateful allocators thanks to proposals championed by committee members including Pablo Halpern and John Lakos. - High-performance memory allocators cannot be monolithic; they inherently require composition across distinct allocation strategies tuned to different size classes.
[24:10](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=1450s) Composition as the First Principle of Allocator Design
Every realistic general-purpose allocator relies on a tiered composition of allocation strategies driven by request size. A typical design might allocate anything under 1 kilobyte using an array of highly specialized bucket allocators, apply a completely different strategy between 1 kilobyte and 64 kilobytes, and for requests larger than that, simply bail out to an operating system call like `mmap`. The Windows heap allocator follows this exact architecture: small objects follow one specialized code path, medium objects follow an entirely different path, and enormous requests trigger out-of-memory or map calls. Under the hood, a sub-64 KB small-object allocator is itself composed of an entire array of smaller allocators, each tailored to a specific size class with its own discrete buckets.
Because production memory allocators are fundamentally aggregates of specialized strategies, composability cannot be an afterthought or an accidental feature. It must be the primary design constraint from day one. When composition is solved first, the underlying allocator abstractions and APIs fall into place naturally.
```mermaid flowchart TD accTitle: Tiered Allocation Strategies by Size accDescr: Incoming allocation requests are partitioned across specialized allocators based on size thresholds.
Req["Allocation Request (Size N)"] --> Check{"Size Range?"}
subgraph Small ["Small Objects"] Check -->|"< 1 KB"| Buckets["Bucket Allocators<br>(Array of size classes)"] end
subgraph Medium ["Medium Objects"] Check -->|"1 KB – 64 KB"| MedStrategy["Specialized Medium<br>Pool Strategy"] end
subgraph Large ["Large Objects"] Check -->|"> 64 KB"| OSMap["Direct OS Mapping<br>(mmap / VirtualAlloc)"] end ```
- High-performance allocators cannot use a single monolithic algorithm; they partition requests by size classes (e.g., `< 1 KB`, `1–64 KB`, `> 64 KB`). - Small-object allocators internally host an array of micro-allocators, each tuned to tight bucket intervals. - Andrei emphasizes: “Getting composition right is getting the allocators right.”
---
[25:25](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=1525s) The Null Allocator as a Compositional Terminator
To establish a design based on composition, Andrei asks the audience to identify the simplest possible composable allocator. The answer is the `NullAllocator`. Borrowing a comparison from *Seinfeld*, Andrei calls it “a show about nothing”: it does absolutely nothing, but it does so in style. Every request to `allocate()` immediately returns null. For `deallocate()`, the allocator asserts that the passed pointer is null, since a consumer must only pass back memory that the allocator itself previously handed out.
```mermaid flowchart LR accTitle: Allocation Strategy Pipeline with NullAllocator Terminator accDescr: Requests pass down an allocation chain and are terminated by a NullAllocator if all prior attempts fail.
Req["Allocate Request"] --> Alloc1["Primary Strategy"] Alloc1 -->|"Fails (null)"| Alloc2["Secondary Strategy"] Alloc2 -->|"Fails (null)"| NullTerm["NullAllocator<br>(Always returns null)"] NullTerm --> RetFail["Return Out-of-Memory"] ```
Though trivial, the null allocator serves an indispensable role as a sentinel or terminator in composite designs, analogous to wave terminators in electrical engineering waveguides. Placing a null allocator at the end of an allocation chain provides an explicit, well-defined terminal boundary when all previous allocation attempts have been exhausted.
- `NullAllocator::allocate(size_t)` always returns `null`. - `NullAllocator::deallocate(void* p)` asserts that `p == nullptr`. - Its total capacity can conceptually be modeled as either zero or infinite; the critical property is that it serves as an immutable terminator in layered pipelines.
---
[27:10](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=1630s) Fallback Allocator and the Derivation of API Primitives
Moving past the null allocator, Andrei introduces `FallbackAllocator<Primary, Fallback>`, the simplest non-trivial composite allocator. It holds two allocators: it attempts to satisfy an allocation using `Primary`, and if that returns null, it falls back to `Fallback`. Andrei implements this using private inheritance to take advantage of the Empty Base Optimization (EBO), keeping stateless sub-allocators at zero overhead.
Implementing `allocate(size)` in `FallbackAllocator` requires only three lines:
```cpp Block allocate(size_t n) { Block b = Primary::allocate(n); if (!b.ptr) b = Fallback::allocate(n); return b; } ```
However, when considering `deallocate(Block)`, the interface hits an immediate structural roadblock. The allocator receives a block of memory, but with only `allocate` and `deallocate` defined, it is impossible to know whether that block originally came from `Primary` or `Fallback`. Passing a foreign pointer into the wrong allocator is a fatal error. Andrei notes that designing strictly for composability forces the discovery of necessary primitives without relying on guesswork: “And that's a good sign right I'm not kidding actually to not have to be smart is a great thing in software engineering right because it means you you have the right frame of thinking and the right frame of reference and there's only one way to follow the tunnel.”
- Private inheritance allows the composite allocator to inherit state from base allocators while benefiting from the Empty Base Optimization (EBO). - `allocate()` requires a trivial check: if `Primary::allocate()` returns an empty/null block, forward the request to `Fallback::allocate()`. - The existing two-method interface (`allocate`/`deallocate`) is provably insufficient for composability because the deallocation path cannot deduce provenance.
---
[30:45](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=1845s) The `owns()` Primitive and Conditional Interfaces
To resolve the provenance dilemma in deallocation, the allocator interface must introduce a new fundamental primitive: `owns(Block)`. Using `owns()`, an allocator can inspect a block (via pointer range checks, pool address boundaries, or lookup tables) and report whether it allocated that memory. With this primitive, deallocation in `FallbackAllocator` becomes clean and robust:
```cpp void deallocate(Block b) { if (Primary::owns(b)) Primary::deallocate(b); else Fallback::deallocate(b); } ```
This requirement raises two questions about interface design: 1. Does `Fallback` also need to implement `owns()`? Not necessarily. It is common for the fallback allocator to be a blunt catch-all like standard `malloc`, which often cannot efficiently report address ownership. 2. When can `FallbackAllocator` itself implement `owns()`? Only when both `Primary` and `Fallback` implement it, returning `Primary::owns(b) || Fallback::owns(b)`.
```mermaid flowchart TD accTitle: Deallocation Flow in FallbackAllocator accDescr: Demonstrates how ownership checks route deallocation between primary and fallback allocators.
BlockIn["deallocate(Block b)"] --> OwnCheck{"Primary::owns(b)?"} OwnCheck -->|"Yes"| PrimaryDealloc["Primary::deallocate(b)"] OwnCheck -->|"No"| FallbackDealloc["Fallback::deallocate(b)"] ```
In C++, member templates take advantage of what Andrei playfully terms "MEDF" (Method Definition Failure Is Not An Error, riffing on SFINAE). If a method in a class template is never called by user code, it is not instantiated, allowing allocators to omit `owns()` unless a composite wrapper specifically queries it.
When an audience member asks whether `FallbackAllocator` could simply prepend a hidden boolean tag to every allocation to record which sub-allocator served it, Andrei explains that doing so burns time and memory on metadata overhead. For high-speed allocators, `owns()` is often a fast range check (e.g., checking whether a pointer falls within a pre-allocated stack buffer), making metadata tagging wasteful.
- `owns(Block)` returns `true` if the block originated from this allocator. - Andrei's dictum: “The primary allocator must be able to tell whether a block came from it or not and only with that knowledge I'm able to implement deallocate.” - The composite `FallbackAllocator` exposes `owns()` conditionally via logical OR if both sub-allocators support it. - Storing dynamic discriminator tags alongside allocations wastes both space and time compared to intrinsic address-range checks.
---
[35:44](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=2144s) Composing a Fast Stack-and-Heap Allocator
With just `allocate`, `deallocate`, and `owns`, fully functional and performant allocators can already be composed. Andrei demonstrates this by combining a fast, lightweight `StackAllocator` with a general-purpose heap allocator. The stack allocator manages a fixed contiguous buffer (e.g., 16 KB) directly on the execution stack, satisfying allocations by bumping an internal offset pointer.
By assembling a `FallbackAllocator<StackAllocator<16384>, Mallocator>`, small allocations are fulfilled on the stack with zero system overhead. Once that 16 KB buffer is exhausted, subsequent allocations seamlessly fall back to `malloc`.
```mermaid flowchart TD accTitle: Composition of StackAllocator and Mallocator accDescr: Requests attempt allocation from a 16 KB stack buffer, falling back to malloc if exhausted.
AllocCall["allocate(size)"] --> TryStack["StackAllocator<16384><br>(Pointer bump)"] TryStack -->|"Success"| StackReturn["Return Stack Block"] TryStack -->|"Exhausted (null)"| TryMalloc["Mallocator<br>(Calls malloc)"] TryMalloc --> HeapReturn["Return Heap Block"] ```
Andrei then poses a question to the audience: Can a stack allocator support deallocation? The room debates whether the answer is a strict "yes," "no," or a "qualified yes." Andrei jokingly asks whether the qualifier is "const or volatile," before exploring what conditions must be met for a bump allocator to safely unwind or reclaim memory.
- `StackAllocator<N>` satisfies allocation requests via rapid pointer-bumping within a local array of size `N`. - Composition via `FallbackAllocator<StackAllocator<16384>, Mallocator>` yields an optimal small-buffer optimization pattern in just a few lines of code. - Whether a bump-pointer stack allocator can deallocate depends entirely on the order of deallocations (LIFO unwinding versus arbitrary free order).
[37:10](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=2230s) Conditional Deallocation and Stack Allocator Mechanics
Alexandrescu dives into the mechanics of `deallocate` in a stack-based allocator. In a stack allocator, allocation simply moves an offset pointer forward through a preallocated buffer; everything behind that pointer is live allocated space, while everything in front is available memory. As a direct consequence, arbitrary deallocation is impossible if the target happens to sit somewhere in the middle of live blocks. Alexandrescu explains that deallocation can only proceed if the pointer to the beginning of the block, plus the size of the block rounded up to alignment, lands exactly at the current allocation frontier. As he puts it in plain terms: “if this deallocation is the deallocation of the last allocation that happened then I can deallocate because I can't roll back the pointer but if it's somewhere in the middle I can't.”
This leads to a conditional deallocation design. If the caller happens to free objects in strict LIFO (last-in, first-out) order, the allocator can step its pointer backward cleanly without causing any harm. In addition, checking whether a block is managed by this allocator via an `owns` member function is trivial and cheap, requiring only a simple range test against the buffer bounds. The interface also supports a `deallocate_all` primitive, which Alexandrescu describes as very cheap but very risky, as it unconditionally resets the allocation pointer back to the beginning, instantly wiping the state and making the entire buffer reusable.
```mermaid flowchart LR accTitle: Stack Allocator Layout and Rollback Condition accDescr: Diagram showing the buffer split into previously allocated space, the last allocated block, and free space, demonstrating where rollback is allowed.
subgraph Buffer["Stack Allocator Buffer"] A["Previously Allocated<br/>(Cannot roll back)"] B["Last Allocation<br/>(Pointer + rounded size)"] C["Free Available Space"] end
A --> B B --> C D["deallocate(p, s)"] -->|"p + roundUp(s) == frontier"| E["Roll back frontier<br/>(Success)"] D -->|"p + roundUp(s) < frontier"| F["No-op / Cannot deallocate"] ```
[39:15](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=2355s) Untyped Allocators and the Stack-Backed Pattern
Responding to an audience question about type qualifications, Alexandrescu emphasizes a fundamental philosophical separation in his design: memory allocators should deal solely with raw memory, operating strictly on untyped `void*` and byte sizes. While many C++ developers intuitively view allocation as tightly coupled to typed objects, Alexandrescu argues that separating the two creates a much cleaner architecture: “many people approach allocation as a kind of object and everything matter but actually can isolate the two quite cleanly it turns out and then you can build a type allocators on on top of untyped allocators.”
With this clean separation, stack allocators can be composed smoothly with system allocators. Combining a stack allocator with a general fallback like `malloc` yields a tremendous performance optimization. In typical workloads, such as a high-throughput web server handling incoming requests, around 95% of allocation requests are small enough to fit completely within a fixed, fast, cache-hot stack buffer. If an unusually large request arrives, the allocator simply delegates it to `malloc`. By pairing this pattern with RAII cleanup tools like `SCOPE_EXIT`, developers get maximum performance on the happy path while preserving total correctness under edge cases.
- Stack-backed allocation handles the vast majority of small, short-lived allocations directly on the stack without heap overhead. - When an allocation exceeds the available capacity of the local stack buffer, it cleanly delegates to a fallback allocator like `malloc`. - Scope guards (such as `SCOPE_EXIT`) provide a convenient and safe idiom for releasing stack resources in proper reverse order.
[41:00](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=2460s) Alignment Hazards and the "Compulsive" Strategy
Alexandrescu moves on to the alignment requirements inside the stack allocator's `allocate` function, posing a question to the room about the necessity of rounding allocation sizes. If an allocator begins with a 16-kilobyte buffer nicely aligned to a CPU word boundary, and the user asks for a single byte, simply advancing the allocation pointer by one byte leaves the remaining buffer misaligned. As Alexandrescu warns the audience about the cascading effect: “Do you see the tsunami that's being initiated here what is it please the next allocation is going to be unaligned right how do you fix that.”
An audience member asks why one cannot be lazy and align addresses on demand only when a typed request specifically requires it. Alexandrescu concedes that lazy alignment is a completely valid technique provided type alignment metadata is carried through, but explains that his implementation opts for a simpler, "compulsive" alignment strategy: every requested size is immediately rounded up to the required alignment boundary prior to adjusting the frontier. The method checks if the rounded request fits within the remaining space, returning `nullptr` if it exceeds bounds. On reviewing his slide, he jokes about modern C++ conventions: “notice that my code is like nullptr compliant I use nullptr and actually I'm using also like the brace initializers and everything but I do see a bug in the slide which is nullptr is not blue which bothers me to no end.”
[43:20](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=2600s) Anatomy and Mechanics of a Free List
Alexandrescu shifts focus to another indispensable building block in memory management: the free list. Clarifying that a generic fixed-size list is not necessarily a *free* list, he points out that the true defining characteristic of a free list is its intrusive nature: it incurs almost zero memory overhead because it repurposes the dead payload memory of previously deallocated blocks to store its internal linked-list node pointers.
The lifecycle of a free list involves lazy initialization and opportunistic recycling. A free list starts completely empty, relying on a backing allocator for initial requests. The free list only springs to life during deallocation:
```mermaid flowchart TD accTitle: Free List Allocation and Deallocation Flow accDescr: Flowchart illustrating how free list intercepts matching size deallocations and satisfies subsequent allocations in O(1).
subgraph AllocFlow["Allocation Request"] Req["Request size S"] --> CheckList{"Free list has<br/>node for S?"} CheckList -- "Yes" --> PopHead["Pop node from head<br/>O(1) Return"] CheckList -- "No" --> BackingAlloc["Forward to<br/>Backing Allocator"] end
subgraph DeallocFlow["Deallocation Request"] FreeReq["Free block of size S"] --> CheckSize{"Size matches<br/>free list S?"} CheckSize -- "Yes" --> PushHead["Write next pointer into block<br/>Push to intrusive head"] CheckSize -- "No" --> BackingFree["Pass to Backing Allocator"] end ```
When an allocation request matches the exact chunk size managed by the free list, the allocator checks its single head pointer; if non-null, it pops and returns the node in $O(1)$ time without touching the parent allocator.
[45:28](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=2728s) The Hidden Pitfalls of Free Lists: Retention, Contention, and Cache
Despite their raw speed and $O(1)$ efficiency, free lists suffer from substantial trade-offs. The first flaw is unconstrained memory retention: free lists hold onto memory indefinitely. If an application suddenly allocates and frees one million 64-byte objects, the free list retains all one million chunks, refusing to return that capacity to the operating system or backing storage and causing severe memory fragmentation.
Fedor and other audience members raise concurrency and threading costs. Alexandrescu observes that basic free lists have terrible thread affinity: if thread $A$ allocates memory and drops it onto a shared global free list, and thread $B$ subsequently picks it up, thread $B$ inherits a cold cache and suffers multithreaded synchronization bottlenecks. When John asks why cross-thread recycling matters so much, a spirited room discussion breaks out regarding contention. Alexandrescu clarifies the industry standard defense: “anybody who defines a freelist allocator the first thing they do they make a thread local free list and that's the first line of defense there.” Each thread gets a private, contention-free mini-pool before ever falling back to a shared global list.
Beyond fragmentation and multithreading contention, Alexandrescu reveals the most non-intuitive drawback of free lists: their hostility toward the CPU hardware cache. While programmers assume reusing recently freed chunks leads to "hot" cache hits, reality often behaves in reverse. Memory being released by applications is very frequently cold because the application finished working with it some time ago. Threading a linked list through that block forces an explicit write of a `next` pointer directly into cold memory, causing avoidable cache line fills. Alexandrescu notes that “a good allocator tries to not write to cold memory it turns out memory that's being freed is very often cold.” In spite of these subtle complexities, he concludes that when sized properly for small objects, free lists remain exceptionally fast tools.
[50:43](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=3043s) Generic FreeList Allocator Mechanics and Optimizations
Andrei Alexandrescu walks through the implementation of a generic `FreeList` allocator template. The class takes a template parameter `A`, which represents the parent allocator sitting underneath the free list. Because the design is generic, this parent can be any conforming allocator—`malloc`, a stack-based allocator, or another custom design. The free list targets a specific allocation size. Pointing his cursor to the `allocate` function on the slide, he explains that if a requested size matches the targeted size and the list's root pointer is not null, the allocator simply pops the next item off the list in an $O(1)$ constant-time operation. If either condition fails, the request falls back and delegates directly to the parent allocator. Deallocation behaves symmetrically: if a freed block matches the designated size, the allocator writes the pointer to the next free node directly into the first word of the returned memory buffer to maintain an intrusive singly linked list in-place without auxiliary memory overhead; otherwise, it passes the block back to the parent allocator to free.
```mermaid flowchart TD accTitle: FreeList Allocation Logic accDescr: Flowchart demonstrating how FreeList satisfies an allocation request by checking target size and root availability, falling back to parent allocator. subgraph RequestCheck["Evaluate Request"] REQ["allocate(n)"] --> COND{"n == targetSize and root!= nullptr?"} end subgraph FastPath["FreeList Fast Path"] COND -- "Yes" --> POP["Pop node from intrusive free list (O(1))"] POP --> RET["Return pointer to memory"] end subgraph FallbackPath["Parent Delegation"] COND -- "No" --> FALLBACK["Delegate allocation to Parent Allocator A"] FALLBACK --> RET end ```
Alexandrescu highlights several practical improvements needed to transform this basic structure into a production-grade free list: - **Size tolerance (Min/Max range):** Allocators often introduce a range (for example, between 512 bytes and 1 kilobyte) where any request within the band is satisfied using fixed 1-kilobyte chunks rather than enforcing strict equality. - **Batch allocation:** Instead of requesting individual blocks from the parent allocator one at a time, the free list can allocate large multi-object blocks and thread the intrusive list through them. However, Alexandrescu cautions: “What's the problem there? It's hard to detect when you can deallocate that big block, right? So that's it's kind of more difficult.” - **Upper-bound capping:** To prevent unbounded memory consumption from freed objects accumulating indefinitely, a cap (such as 1,024 items) can be placed on the free list length; once saturated, excess deallocations bypass the list and return to the parent.
---
[54:02](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=3242s) Realistic FreeList Parameters and Composition
Alexandrescu presents a complete, realistic declaration for a `FreeList` allocator: it parameterizes the underlying allocator, a minimum size (17 bytes), a maximum size (32 bytes), an allocation batch size (8 objects at a time), and an upper capacity limit (1,024 elements). When an audience member asks how individual elements inside a batch are freed, Alexandrescu clarifies that freed elements are recycled into the intrusive list rather than returned individually to the system: “You put it back in the list, you never free it.” An upper bound of 32 means that every request between 17 and 32 bytes receives a 32-byte chunk, while the 1,024 limit caps the maximum number of idle recycled blocks held in cache.
He emphasizes the architectural power of composability: - A `FreeList` can be layered directly on top of a stack allocator. - Stack allocators normally demand strict LIFO (last-in, first-out) deallocation and cannot free arbitrary allocations made in the middle of their buffer. - Layering a free list over the stack allocator allows intermediate allocations of matching size to be recycled and reused out-of-order, bypassing the stack's strict lifetime limitations. - Alexandrescu observes: “I'm gaining composition strength here, right?”
---
[56:00](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=3360s) The Affix Allocator: Bookends, Guard Bands, and Debugging
Alexandrescu introduces the affix allocator, a design pattern where an allocator wraps a parent allocator by prepending a prefix object and appending a suffix object to each allocated block. By default, the suffix can be `void` (occupying zero bytes). The pattern provides a generic composition device with numerous applications, most notably memory safety and debugging:
```mermaid flowchart LR accTitle: Affix Allocator Memory Layout accDescr: Memory block layout showing the prefix metadata, the usable memory block payload, and the trailing suffix guard. subgraph MemoryChunk["Composite Allocated Block"] P["Prefix Metadata\n(File/Line, Size, Guard)"] U["Usable Payload\n(Returned to Caller)"] S["Suffix Metadata\n(Electric Fence / Void)"] end P --> U U --> S ```
Prefixes and suffixes act as "electric fences" or guard signatures: a known signature or canary is written before and after the client payload, and verified upon deallocation to catch buffer overruns and memory corruptions. Beyond guard bands, affix allocators are useful for tracking allocation origins by embedding the caller's source file and line number in the prefix. Referring to a plenary performance talk given that morning by Chandelle, Alexandrescu remarks on system profiling tools: Linux has the powerful `perf` tool, Windows has comprehensive visual profiling utilities, while OS X lacks equivalent built-in facilities. However, even with `perf`, tracking down memory allocation provenance remains elusive:
> “All of these great things you can see with `perf`, you can't see who's asking for memory in `perf`. You can't. It's dark matter; you can't see it. With this kind of stuff you can.”
By wrapping allocations with file and line metadata, a program can pinpoint exactly which lines of code in a massive multi-million-line codebase consume the most dynamic memory. Furthermore, an affix allocator can collect global or per-allocation statistics—such as total allocate and deallocate invocations—by configuring capacity flags and slicing the metrics after program termination.
---
[59:08](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=3548s) Static Registration Trick for Zero-Allocation Profiling
Facing a sudden time warning from the session monitors indicating only five minutes remain, Alexandrescu bargains with the room to borrow five minutes from the upcoming break, joking about attendees dozing off in their seats. Rather than skipping past tracking techniques, he shares a clever C++ implementation trick for collecting memory allocation statistics without incurring any secondary dynamic memory allocations.
The technique relies on an allocation macro (such as `ALLOCATE(...)`) that defines an internal static structure at every call site:
```cpp // Conceptual pattern explained by Alexandrescu #define ALLOCATE(size) ([] { \ struct AllocSite { \ const char* file; \ unsigned long line; \ size_t count; \ AllocSite* next; \ }; \ static AllocSite info = { __FILE__, __LINE__, 0, globalHead }; \ globalHead = &info; \ info.count++; \ return do_allocate(size); \ }()) ```
- Every allocation macro invocation instantiates a local `static` struct containing `__FILE__`, `__LINE__`, call counters, and a pointer to the `next` record. - Because these records reside entirely in static program storage, linking them into an intrusive singly linked list requires zero dynamic allocations. - At application termination, the runtime traverses the linked list from the head pointer to dump fine-grained allocation diagnostics across the entire binary without perturbation from tracking overhead.
---
[01:01:48](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=3708s) Introduction to Bitmap Block Allocators
As the session timer is extended to ten minutes, Alexandrescu introduces the `BitmapBlock` allocator. This allocator divides a contiguous memory arena into fixed-size blocks (for instance, 64-byte blocks) and tracks occupancy using a compact bitmap that uses exactly one bit of metadata per block to indicate whether it is free or in use. This produces minimal metadata overhead while offering fast bitwise scanning for available chunks.
[01:02:14](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=3734s) The Bitmapped Block and Metadata Separation
Andrei Alexandrescu details the architecture of the bitmapped block allocator, contrasting it with free lists. By assigning a single bit per contiguous block, this scheme eliminates nearly all the disadvantages associated with free lists. Allocating an arbitrary size is straightforward because one can simply claim multiple consecutive blocks. Most importantly, metadata is stored completely separate from user data, meaning the metadata stays hot in cache. Alexandrescu emphasizes this design rule: “This is a recipe for great things in memory allocation: store metadata elsewhere than the data.” Modern CPU manufacturers have heavily optimized bitwise operations, enabling high-performance scans using SIMD and dedicated instructions.
However, no allocator design comes without trade-offs. The fixed block granularity leads directly to internal fragmentation whenever a request does not perfectly align with block boundaries. Additionally, multithreaded environments introduce concurrency headaches; bit manipulation across shared memory words causes false sharing and race conditions. Despite these limitations, Alexandrescu strongly recommends bitmapped blocks as a core building block.
```mermaid flowchart TD accTitle: Bitmapped Block Layout accDescr: Separates bit metadata from contiguous payload memory blocks.
subgraph Meta ["Hot Metadata (Cache Friendly)"] BM["Bit Vector / Words<br/>(SIMD & Bitwise Scans)"] end
subgraph Data ["Contiguous Payload Storage"] B0["Block 0"] B1["Block 1"] B2["Block 2"] B3["Block..."] end
BM -.->|"tracks status of"| B0 BM -.->|"tracks status of"| B1 BM -.->|"tracks status of"| B2 BM -.->|"tracks status of"| B3 ```
- Bit manipulation benefits directly from SIMD primitives and dedicated CPU bitwise instructions. - Storing metadata away from data payloads ensures allocator bookkeeping stays hot in cache without cache-polluting client memory. - The primary disadvantage is internal fragmentation caused by fixed-size block rounding. - Multithreading introduces complications due to bit-sharing across adjacent allocation tracking words.
[01:03:42](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=3822s) Cascading Allocators, Segregators, and Composition
Alexandrescu moves on to more advanced, composable designs, beginning with the cascading allocator. Imagine placing a bitmapped block allocator atop a 1-megabyte buffer; once that megabyte is exhausted, the cascading allocator lazily allocates a second megabyte, organizes it with another bitmapped block, and chains them together. When blocks are vacated, it deallocates them cleanly.
He then introduces the segregator, teasing the audience when Marshall Clow immediately shouts out the answer: “You guys can't have Marshall answer every question here.” A segregator divides requests according to a size threshold: requests less than or equal to the threshold route to a small-object allocator, while those exceeding it go to a large-object allocator. Crucially, segregators do not need an `owns()` member function because the requested byte size alone dictates routing. Segregators can nest recursively: a primary segregator can branch requests at 4 KB, routing larger allocations to a system fallback, while sub-4 KB allocations pass to an inner segregator that splits at 128 bytes between a free list and a medium allocator. Alexandrescu notes that chaining roughly 16 segregators into a compile-time binary search tree yields an industrial-strength allocator, though a linear search can sometimes be preferable because tiny allocations are far more frequent and large allocations can afford slight routing overhead.
```mermaid flowchart TD accTitle: Segregator Allocation Hierarchy accDescr: Hierarchical tree showing request routing by allocation size.
Req["Allocate(n bytes)"] --> S1{"n <= 4 KB?"} S1 -->|"Yes"| S2{"n <= 128 B?"} S1 -->|"No"| Fallback["Large / System Allocator"] S2 -->|"Yes"| FL["FreeList Allocator"] S2 -->|"No"| Med["Medium Allocator"] ```
- Segregators route solely by size: `size <= Threshold? SmallAlloc: LargeAlloc`. - Segregator implementations take at most around 50 lines of code. - Compositions of ~16 segregators can be organized as compile-time binary search trees or linear cascades based on profile frequencies.
[01:07:03](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=4023s) The Bucketizer and the Complete Minimal Allocator API
The final structural component presented is the bucketizer. Operating across a range between a minimum and maximum size with a defined step size (or powers-of-two for logarithmic growth), the bucketizer maps size classes directly to dedicated allocators. Alexandrescu asserts that between bitmapped blocks, cascading wrappers, segregators, and bucketizers, almost every known memory allocation architecture can be expressed with minimal code.
```mermaid flowchart LR accTitle: High-Level Allocator API Map accDescr: Categorization of core allocator methods into allocation, sizing, and management.
subgraph Sizing ["Size & Alignment"] A1["alignment"] A2["good_size(n)"] end
subgraph Lifecycle ["Allocation Lifecycle"] B1["allocate(n)"] B2["allocate_all()"] B3["deallocate(b)"] B4["deallocate_all()"] end
subgraph InPlace ["In-Place Growth & Query"] C1["expand(b, delta)"] C2["reallocate(b, new_size)"] C3["owns(b)"] C4["aligned_allocate(n, align)"] end ```
He then summarizes the universal, clean allocator API discovered through this composable framework: - `alignment`: A `static constexpr` value advertising alignment guarantees. - `good_size(n)`: Returns the rounded-up capacity the allocator will actually provision for a request of size $n$, enabling containers like `std::vector` to exploit slack memory without reallocating. - `allocate(n)`: Standard allocation returning an untyped memory block. - `allocate_all()`: Captures all remaining storage in a single operation, ideal for nesting arena or stack allocators within pre-reserved memory chunks. - `expand(b, delta)`: Expands an existing allocation in place without relocating pointers. - `reallocate(b, new_size)`: Mimics C `realloc` behavior. - `owns(b)`: Identifies whether a given memory block originated from this specific allocator instance. - `deallocate(b)` and `deallocate_all()`: Reclaims individual blocks or drops all allocations at once. - `aligned_allocate(n, a)`: Supports over-aligned allocations, an unavoidable requirement in performance-critical domains like game development.
[01:10:47](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=4247s) Conclusion: Why std::allocator Failed and How Composition Wins
Alexandrescu concludes by reflecting on the core lesson of the talk: `std::allocator` failed because it lacked composability. Trapped by its historical baggage as a 1990s segmented-memory workaround, `std::allocator` conflated object construction with memory sourcing, omitted block sizing, and offered no mechanism for layering strategies. Alexandrescu admits that shedding that legacy was mentally challenging: “And it was difficult for me to get away from the frame of mind in which it exists, therefore it must be good, to the point where, you know, this may be a mistake and let me see if I kind of clean my mind off of everything, let me see if I can do better right, and better means composable.”
By discarding existing patterns and building from first principles around raw byte blocks, compile-time metadata queries, and composable structural components, developers can assemble custom, optimal memory allocators for any platform or application pattern. With the session time elapsed, Alexandrescu closes to audience applause and remains on stage for informal follow-up questions.
## Notable quotes > [01:02:14](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=3734s) This is a recipe for great things in memory allocation: store metadata elsewhere than the data. — Andrei Alexandrescu
> [11:56](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=716s) I unrecommend operator new for any serious use of memory allocation. — Andrei Alexandrescu
> [24:10](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=1450s) Getting composition right is getting the allocators right. — Andrei Alexandrescu
> [18:03](https://www.youtube.com/watch?v=LIb3L4vKZ7U&t=1083s) std::allocator is not a great allocator because it was not designed for that purpose; it was designed for near and far pointers. — Andrei Alexandrescu
## Mentioned Andrei Alexandrescu, Bjarne Stroustrup, Brian Kernighan, Dennis Ritchie, Hoard, jemalloc, TCMalloc, Howard Hinnant, Pablo Halpern, Alisdair Meredith, John Lakos, Doug Lea, dlmalloc, StackAllocator, FallbackAllocator, NullAllocator, Mallocator, FreeList, Affix Allocator, BitmapBlock, Marshall Clow, SCOPE_EXIT, std::allocator, std::vector, perf, Linux, Windows, OS X
## Video description http://www.Cppcon.org — std::allocator Is to Allocation what std::vector Is to Vexation -- Presentation Slides, PDFs, Source Code and other presenter materials are available at: https://github.com/cppcon/cppcon2015 — std::allocator has an inglorious past, murky present, and cheerless future. STL introduced allocators as a stop gap for the now antiquated segmented memory models of the 1990s. Their design was limited and in many ways wasn't even aiming at helping allocation that much. Because allocators were there, they simply continued being there, up to the point they became impossible to either uproot or make work, in spite of valiant effort spent by the community.
But this talk aims at spending less time on poking criticism at std::allocator and more on actually defining allocator APIs that work.
Scalable, high-performance memory allocation is a topic of increasing importance in today's demanding applications. For such, std::allocator simply doesn't work. This talk discusses the full design of a memory allocator created from first principles. It is generic, componentized, and composable for supporting application-specific allocation patterns. — Andrei Alexandrescu is a researcher, software engineer, and author. He wrote three best-selling books on programming (Modern C++ Design, C++ Coding Standards, and The D Programming Language) and numerous articles and papers on wide-ranging topics from programming to language design to Machine Learning to Natural Language Processing. Andrei holds a PhD in Computer Science from the University of Washington and a BSc in Electrical Engineering from University "Politehnica" Bucharest. He works as a Research Scientist for Facebook.Website: http://erdani.comTwitter handle: @incomputable — Videos Filmed & Edited by Bash Films: http://www.BashFilms.com
Work at Hudson River Trading (HRT): https://tinyurl.com/safxfctf
[Source](https://www.youtube.com/watch?v=LIb3L4vKZ7U)