Custom Allocators, Memory Pools & Runtime Polymorphism

Week 3 taught you to own a lifetime. This week you own the memory itself. malloc is a correct, thread-safe, general-purpose service and it is the single largest source of unbounded jitter in a tick-to-trade path — so you take it out and put a pointer swap in its place. Then you put polymorphic objects in those pools and price the one thing that makes them polymorphic: the virtual call.

• Explain, with numbers, why the same new call is 22 ns on one tick and 18 µs on the next — and which of those two numbers your deadline actually sees.
• Build a fixed-size Pool with an intrusive free-list: O(1) allocate, O(1) free, zero fragmentation, and a documented answer for what happens when it runs dry.
• Choose correctly between a pool, an arena, std::pmr and plain new — including the cases where pooling is the wrong answer.
• Say why alignas(64) is a latency decision and not a cosmetic one.
• Explain how virtual works — vptr, vtable, virtual destructor — put a polymorphic object in a pool without leaking, and say what a virtual call costs (Part 4).

1What is it? An allocator you sized before the session opened

A custom allocator is not a faster malloc. It is a different contract: you give up generality — arbitrary sizes, unbounded growth, thread safety you did not ask for — and in exchange you get a cost that is the same on every single call. In a system graded on p99.9, a predictable 4 ns beats an average of 22 ns every time.

Interactive · the malloc latency distribution

20,000 simulated malloc calls, drawn on a logarithmic axis. Move the fragmentation slider and watch the mean barely move while p99.9 walks two decades to the right. The violet marker is the pool you build in lab — it does not have a tail to walk.

2How does it work? A free-list threaded through the free slots

The fixed-size pool is the cheapest allocator that exists, and it is about twelve lines of real code. One slab, owned once. Every slot is the same size. A free slot has no live object in it, so you store the address of the next free slot inside the slot itself — an intrusive free-list that costs zero extra memory. Allocate is a pop; free is a push.

// include/pool.hpp — HW4. Slot is at least sizeof(void*)
// because a FREE slot stores the next free slot in itself.
template <class T, std::size_t N>
class ObjectPool {
  union Slot { Slot* next; alignas(T) unsigned char buf[sizeof(T)]; };
  Slot  slots_[N];
  Slot* free_ = nullptr;
 public:
  ObjectPool() {                          // thread the list once
    for (std::size_t i = N; i-- > 0;) { slots_[i].next = free_; free_ = &slots_[i]; }
  }
  template <class... A> T* alloc(A&&... a) {
    if (!free_) return nullptr;           // exhausted: caller must cope
    Slot* s = free_; free_ = s->next;     // O(1) pop
    return new (s->buf) T{std::forward<A>(a)...};   // placement new
  }
  void release(T* p) {                    // O(1) push
    if (!p) return;
    p->~T();                              // YOU call the dtor. The pool never does.
    Slot* s = reinterpret_cast<Slot*>(p);
    s->next = free_; free_ = s;
  }
};

Interactive · the arena, and what alignment costs you

A pool needs one fixed size. An arena (bump allocator) does not care about size at all — it keeps one offset, rounds it up to the requested alignment, hands it back, and advances. There is no per-object free; there is only reset(), which reclaims everything in one instruction. Perfect for per-tick scratch. Notice the padding wasted counter as you raise the alignment.

class Arena {
  unsigned char* base_;
  std::size_t    cap_, off_ = 0;
 public:
  Arena(unsigned char* base, std::size_t cap) : base_(base), cap_(cap) {}
  void* alloc(std::size_t n, std::size_t align) {
    std::size_t p = (off_ + align - 1) & ~(align - 1);   // round up
    if (p + n > cap_) return nullptr;
    off_ = p + n;
    return base_ + p;                                    // one add: O(1)
  }
  void reset() { off_ = 0; }              // free EVERYTHING, O(1)
};

Interactive · four allocators, one hot path

The same on_book written four ways. Read the code, then read the contract underneath it — that table is what you are actually choosing between.

3Why it matters: cache lines, and knowing when not to pool

Owning the memory buys you a second thing beyond determinism: you get to decide where objects sit. A cache line is 64 bytes on every x86-64 core you will run on, and the hardware moves memory in exactly that unit. A struct that straddles a line boundary is not slightly slower — it costs an extra line fetch and a split-load penalty on every access, forever.

Interactive · aligned vs unaligned access

Place a Quote at a byte offset inside the slab and watch how many 64-byte lines the hardware has to touch. Then tick alignas(64) and watch the split loads go to zero. The right-hand column is the same struct, cache-line aligned, for comparison.

struct alignas(64) Quote {            // one line, never straddles
  std::int64_t  bid_ticks;
  std::int64_t  ask_ticks;
  std::uint32_t bid_qty;
  std::uint32_t ask_qty;
  std::uint64_t seq;
};
static_assert(sizeof(Quote)  == 64, "Quote must be exactly one cache line");
static_assert(alignof(Quote) == 64, "Quote must be cache-line aligned");

Interactive · should you pool this?

The honest answer is often no. Describe the allocation and get a recommendation — plus the one line of code that implements it.

4Runtime polymorphism — what a virtual call costs

Pools give you objects of one type. The moment those objects sit behind a common interface — an Order, a Quoter, a Strategy — you are using runtime polymorphism: one call site, several bodies, chosen by a hidden pointer in the object. It is the right tool for an open set of types and a real cost for a closed one. This part builds the mechanism, prices it, and shows how a virtual object lives inside a pool.

struct Quoter {
  virtual ~Quoter() = default;      // see the rule opposite
  virtual std::int64_t price(std::int64_t mid) const = 0;  // pure
  virtual void on_fill(std::uint32_t) {}  // hook
  std::uint32_t id = 0;
};
struct Passive final : Quoter {
  std::int64_t price(std::int64_t mid) const override { return mid - 1; }
};
struct Aggressive : Quoter {
  std::int64_t price(std::int64_t mid) const override { return mid + 1; }
  void on_fill(std::uint32_t q) override { filled += q; }
  std::uint32_t filled = 0;
};
std::int64_t quote(const Quoter& q, std::int64_t mid) {
  return q.price(mid);   // one call site, any Quoter
}

struct Bad  { ~Bad() {} virtual void f() {} };   // dtor NOT virtual
struct Sub : Bad { std::string tag = std::string(64, 'x'); };
Bad* p = new Sub;
delete p;          // UB: ~Bad only; Sub::tag never destroyed
                       // (clang warns: -Wdelete-non-abstract-non-virtual-dtor)

struct Good { virtual ~Good() = default; };   // the fix

Interactive · the vptr and the vtable

Every polymorphic object carries one hidden pointer, the vptr, to a per-class table of function addresses that lives in read-only memory. Pick a derived class and a method, then step through the call: Base* → object → vptr → vtable slot → function. Layout shown is the Itanium ABI (GCC and Clang on x86-64, 8-byte pointers); the two destructor slots are the complete-object and deleting variants.

// p->price(mid) compiles to roughly:
mov  rax, [rdi]        ; 1. vptr out of the object
mov  rax, [rax + 16]   ; 2. slot [2] out of the vtable
call rax               ; 3. indirect call: target unknown

Interactive · what one virtual call costs on the hot path

The vtable loads are not the bill. The bill is the indirect branch when the predictor cannot learn the target, and the inlining you lose because the optimiser cannot see through the call. Numbers are the ones measured in class — one laptop, -O2, 10 M calls — and are order-of-magnitude only: direct/inlined ≈ 0.4 ns, virtual with one hot target ≈ 2.2 ns, virtual with four unpredictable targets ≈ 7 ns, and final with an exact type is back to direct. Measure yours.

The alternatives map

Dynamic dispatch answers one question: how do I call code I do not know yet? If you do know the type set at build time, there are cheaper answers. Open set = plugins and boundaries; closed set = the handful of message and strategy types you actually ship.

using Msg = std::variant<Add, Cancel>;      // closed set, no vptr
struct Handler {
  long operator()(const Add& a)    const { return a.px; }
  long operator()(const Cancel& c) const { return (long)c.id; }
};
long h(const Msg& m) { return std::visit(Handler{}, m); }

Interactive · a polymorphic object living in a pool

Putting the two halves of the week together. The pool hands out raw bytes; placement new builds a Limit in them; you talk to it through an Order*; and reclaiming it means calling p->~Order() — which is only correct if that destructor is virtual. Step through the lifecycle, then flip the switch and watch what leaks.

struct Order {
  virtual ~Order() = default;      // the switch above
  int id = 0;
};
struct Limit : Order {
  std::string tag = std::string(64, 'x');   // owns a heap buffer
  ~Limit() override { std::puts("~Limit"); }
};
struct Pool {
  alignas(std::max_align_t) unsigned char slab[sizeof(Limit)];
  Order* alloc()          { return new (slab) Limit{}; }  // placement new
  void   release(Order* p) { p->~Order(); }              // virtual: ~Limit, then ~Order
};
int main() { Pool pl; Order* o = pl.alloc(); pl.release(o); }   // prints ~Limit

5Five ways this goes wrong

These are the five that cost marks on HW4, every time. Open them.

6Check yourself

Four questions, instant feedback, nothing recorded.

7Do the work