Project 7: Cache-Line Aware Memory Allocator

A simple, special-purpose memory allocator that is aware of cache lines. It will provide a function like alloc_on_new_line(size_t size) which guarantees the returned memory block starts on a new 64-byte cache line boundary.

Quick Reference

Attribute Value
Primary Language C
Alternative Languages C++
Difficulty Level 4: Expert
Time Estimate 2-3 weeks
Knowledge Area Memory Management / Systems Programming / CPU Caches
Tooling GCC/Clang
Prerequisites Strong C skills, including pointer arithmetic and bitwise operations.

What You Will Build

A simple, special-purpose memory allocator that is aware of cache lines. It will provide a function like alloc_on_new_line(size_t size) which guarantees the returned memory block starts on a new 64-byte cache line boundary.

Why It Matters

This project builds core skills that appear repeatedly in real-world systems and tooling.

Core Challenges

  • Requesting a large block of memory from the OS → maps to using mmap (on Linux/macOS) or VirtualAlloc (on Windows)
  • Managing your own memory pool → maps to writing a simple slab or bump allocator
  • Calculating aligned memory addresses → maps to bitwise operations and pointer arithmetic
  • Returning memory that satisfies alignment requests → maps to the core logic of the allocator

Key Concepts

  • Data Alignment: “Write Great Code, Volume 1” Ch. 4 - Randall Hyde
  • Pointer Arithmetic: “Understanding and Using C Pointers” by Richard M Reese
  • Memory Pool / Slab Allocation: Wikipedia provides a good high-level overview.

Real-World Outcome

#include "cache_allocator.h"

// In another project (like the False Sharing Detector)
int main() {
    pool_t* my_pool = pool_create(1024 * 1024); // 1MB pool

    // These two variables are guaranteed to be on different cache lines
    long long* counterA = alloc_on_new_line(my_pool, sizeof(long long));
    long long* counterB = alloc_on_new_line(my_pool, sizeof(long long));

    // ... run false sharing benchmark ...
    // The benchmark will show no false sharing, proving your allocator works.

    pool_destroy(my_pool);
    return 0;
}

Implementation Guide

  1. Reproduce the simplest happy-path scenario.
  2. Build the smallest working version of the core feature.
  3. Add input validation and error handling.
  4. Add instrumentation/logging to confirm behavior.
  5. Refactor into clean modules with tests.

Milestones

  • Milestone 1: Minimal working program that runs end-to-end.
  • Milestone 2: Correct outputs for typical inputs.
  • Milestone 3: Robust handling of edge cases.
  • Milestone 4: Clean structure and documented usage.

Validation Checklist

  • Output matches the real-world outcome example
  • Handles invalid inputs safely
  • Provides clear errors and exit codes
  • Repeatable results across runs

References

  • Main guide: LEARN_C_PERFORMANCE_DEEP_DIVE.md
  • “C Interfaces and Implementations: Techniques for Creating Reusable Software” by David R. Hanson