$ show mtrebi/memory-allocators
This repository provides a set of custom memory allocator implementations in C++ (Linear, Stack, Pool, FreeList, and a wrapper for malloc). The allocators are designed for educational purposes, demonstrating how to replace general-purpose malloc with more efficient, specialized allocators. The code is structured around a common base class (`Allocator`) and uses generic linked list data structures (singly and doubly linked, plus a stack-based linked list) to manage free memory blocks. A benchmarking framework (`Benchmark`) measures allocation/free throughput and memory usage. The project is a library/example, not a production service, and is intended to illustrate trade-offs between allocator types. The implementation is clean and well-organized, but lacks tests and modern C++ features, and has not been actively maintained.
The LLM identified 6 files worth highlighting for reuse:
Implements a general-purpose free list allocator supporting first-fit and best-fit placement policies. It uses a singly linked list of free blocks stored inline, allocation headers, and coalescence of adjacent free blocks. The allocation algorithm searches for a suitable block, splits it if necessary, and manages an allocation header for metadata. The free operation inserts the block in sorted order by address and merges contiguous free blocks. This component is self-contained, reusable, and demonstrates non-obvious memory management techniques.
Implements a stack (LIFO) allocator that supports allocation of variable sizes, free in LIFO order, and checkpoint/rollback via markers. Uses a vector of markers to track allocation history and enables partial rollback through push/pop of checkpoints. The allocator stores no metadata in the allocated memory itself, keeping the user-facing memory contiguous. This pattern is reusable for any system requiring stack-like allocation and deallocation.
Implements a fixed-size chunk pool allocator. It uses a stack-linked list (LIFO) of free chunks stored inline within the free blocks themselves. On allocation, it pops from the free list or falls back to the next unused chunk from the pool memory. On free, it pushes the chunk back onto the free list. This component is self-contained and demonstrates a classic pool allocator pattern with O(1) allocation and deallocation.
Provides a generic benchmarking framework for memory allocators. It measures time and memory usage for single/multiple/random allocation and free patterns. Uses high-resolution clock and calculates operations per second, time per operation, and peak memory usage. The class is reusable with any allocator deriving from the base `Allocator` class, making it suitable for evaluating custom allocators in other projects.
A generic singly linked list template class with insert and remove operations. The data structure is stored separately from the nodes, allowing the list to be used for various purposes. The implementation is self-contained, template-based, and can be extracted and reused in any C++ project needing a simple singly linked list.
A generic stack (LIFO) linked list template class with push and pop operations. The nodes are stored as a singly linked list but only the head is accessible. This is used by the PoolAllocator to manage free chunks. The implementation is minimal, efficient, and reusable in any C++ project requiring a stack-like linked list.