pcp-allocator

A user-space slab allocator in C++17 with per-CPU caches — the same per-CPU pageset design pattern used by the Linux kernel's page allocator. Build, benchmark, learn what jemalloc and tcmalloc do under the hood.

┌──────────┐    ┌──────────┐    ┌──────────┐
│ PcpCache │    │ PcpCache │    │ PcpCache │   ← fast path, per-CPU
│  CPU 0   │    │  CPU 1   │    │   ...    │     (one mutex each)
└────┬─────┘    └────┬─────┘    └────┬─────┘
     └────────────────┼────────────────┘
                     ▼
            ┌──────────────────┐
            │ CentralFreelist  │              ← slow path: refill/drain
            │  (per size class)│                 of per-CPU caches
            └────────┬─────────┘
                     ▼
            ┌──────────────────┐
            │  ChunkAllocator  │              ← mmap-backed 2 MiB chunks
            └──────────────────┘

Why this exists

If you've ever wondered why jemalloc and tcmalloc exist at all — why glibc malloc isn't just "good enough" — the answer is that on modern multi-core hardware a single contended lock around the heap becomes a bottleneck before anything else. The whole game in modern allocators is reducing contention between threads while keeping the per-allocation cost low. This repo is the smallest plausible implementation of the techniques those production allocators use, with measurements.

The headline data structure is the per-CPU cache (PcpCache). The Linux kernel calls this same idea a "per-CPU pageset" in mm/page_alloc.c; the kernel patch from which this allocator's name inherits fixed an accounting bug in that exact structure.

The repository is intentionally small enough to read in an afternoon. The docs/design.md walks through every layer with the rationale, and is meant as the takeaway artifact.

Benchmark results

Measured on this benchmarking workload set (benchmarks/bench_allocator.cpp), comparing pcp::Allocator against glibc malloc:

workload                                 alloc     ns/op    ops/sec
bulk-small (size=64, n=200k)             glibc      50.4   19.8 M/s
bulk-small (size=64, n=200k)             pcp        44.8   22.3 M/s   (-11%)
mixed-random (8..2048, n=100k)           glibc     244.7    4.1 M/s
mixed-random (8..2048, n=100k)           pcp       210.5    4.8 M/s   (-14%)
producer-consumer (size=128, n=50k)      glibc      61.2   16.3 M/s
producer-consumer (size=128, n=50k)      pcp        61.9   16.2 M/s   (≈)

(Run ./build/pcp_bench on your hardware for fresh numbers — they'll differ by absolute value but the shape should hold.)

Reading the numbers:

• On bulk small and mixed-random, the per-CPU cache fast path beats glibc by 10-15%. This is the steady-state case the design targets.
• On producer-consumer, where one thread allocates and another frees, the per-CPU caches cross-pollinate: the producer's cache drains, the consumer's cache fills with returned objects. Steady state ends up routing through the central freelist, so the gain collapses to roughly even with glibc on a single-socket machine. On a multi-socket NUMA box the picture changes — different story.
• glibc isn't slow; it's just designed for a different workload mix.

The interesting story is the docs/design.md explaining why these numbers come out the way they do.

Build and run

Requires Linux x86-64, CMake 3.16+, a C++17 compiler (gcc 9+ or clang 10+), and pthreads. GoogleTest is fetched automatically by CMake.

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build -j

# Run unit tests
./build/pcp_tests

# Run benchmarks (compares against glibc malloc)
./build/pcp_bench

# Build with sanitizers for debugging
cmake -S . -B build-asan -DCMAKE_BUILD_TYPE=Debug -DPCP_ENABLE_ASAN=ON
cmake --build build-asan -j
./build-asan/pcp_tests

Usage

#include <pcp/allocator.hpp>

pcp::Allocator a;

void* p = a.allocate(64);     // get 64 bytes
// ... use p ...
a.deallocate(p, 64);          // sized free (size class lookup needs the size)

// Introspection
auto stats = a.stats();
std::cout << "live chunks: " << stats.live_chunks << "\n";
for (auto& sc : stats.per_class) {
    std::cout << "  size " << sc.object_size
              << ": " << sc.total_allocs << " allocs, "
              << sc.refills << " refills, "
              << sc.drains  << " drains\n";
}

pcp::Allocator::instance() returns a process-wide singleton if you want a shared allocator instead of constructing your own.

Project layout

include/pcp/
  size_class.hpp        size-class table and lookup
  chunk_allocator.hpp   mmap-backed bottom layer
  central_freelist.hpp  per-size-class freelist with mutex
  pcp_cache.hpp         per-CPU cache (the headline)
  allocator.hpp         public Allocator + Stats API
src/                    matching .cpp files
tests/                  GoogleTest unit + multithread tests (22 tests)
benchmarks/             head-to-head vs glibc malloc
docs/design.md          design walkthrough — the takeaway artifact

What this is and isn't

It is a clean, readable, correct implementation of the per-CPU cache + size-class + central-freelist pattern, with tests and benchmarks proving it works.

It isn't a drop-in replacement for glibc malloc. Things it doesn't do:

• No realloc beyond trivial cases.
• No MAP_HUGETLB request.
• No multi-arena tuning (jemalloc has 8 arenas per CPU; we have 1).
• Only Linux x86-64.
• Per-CPU cache uses a mutex instead of the rseq() syscall, so contention is bounded but not zero.

For production use, take jemalloc, tcmalloc, or mimalloc. The point of this repo is to show how those work.

Roadmap

• Size-class table with O(log N) lookup
• 2 MiB chunk allocator
• Per-class central freelist
• Per-CPU caches with refill/drain watermarks
• Public Allocator API + introspection Stats
• GoogleTest unit + multithread tests, 22 cases
• Benchmark suite vs glibc malloc, 3 workloads
• ASAN/UBSAN build (-DPCP_ENABLE_ASAN=ON)
• CI: gcc + clang × Debug + Release matrix
• rseq() per-CPU sections to eliminate the per-cache mutex
• Return entirely-empty chunks to the kernel
• Multi-arena tuning
• 256-byte direct lookup table for class lookup
• Memory-pressure-aware drain policy

License

MIT.

Acknowledgements

Design lineage:

• The Slab Allocator: An Object-Caching Kernel Memory Allocator, Jeff Bonwick (1994).
• The Linux kernel's per_cpu_pages in mm/page_alloc.c.
• jemalloc's arenas + tcaches design.
• tcmalloc's design doc.