The build command points at a directory the clone does not create

The clone name and the configure path differ

The build instructions are three commands, and the middle one does not match the first:

git clone https://github.com/mtrebi/memory-allocators.git
cmake -S memory-allocator -B build
cmake --build build

The clone URL ends in memory-allocators and creates a directory of that name, while the configure step points CMake at memory-allocator, singular. Following the three lines exactly gives you a configure step that cannot find the source directory. It is a small typo with a real cost, because it is the kind of error that looks like a missing CMakeLists.txt rather than a name mismatch, and the repository does contain a CMakeLists.txt at its root. The top-level layout explains why a fix is easy: .gitignore, a CMakeLists.txt, a legal file, this README and three directories, docs/, includes/ and src/, which is a conventional shape for a small C++ library where headers and sources are separated. The README also carries a Made with love at the Recurse Center badge, which places the project in a batch-style educational setting rather than a production codebase.

The stack allocator describes headers two different ways

This is the passage to read twice, because the data structure subsection and the allocate subsection disagree. The data structure subsection says the allocator only needs a pointer or offset to track the top of the stack, that rollback points are stored outside the managed block, and that this avoids per-allocation headers, avoids wasting padding space and keeps the user-facing memory contiguous. Then the allocate subsection says to move the pointer forward and place a header right before the memory block indicating its size. Those cannot both hold. The complexity figure is given as O(N*H) improving to O(N), where H is the header size and N is the number of allocations, and the free subsection then says free is a LIFO rollback that restores the last saved offset and does not need to inspect any header stored in the allocation itself. So the free path matches the first description and the allocate path matches the second. Whichever is intended, the free path is the cheaper design, and the discrepancy is worth resolving in the code before you copy the pattern.

Linear is a pointer, and it never frees

The linear allocator is the baseline and the simplest thing in the repository. A pointer, or an offset, is kept at the first memory address of the chunk and moved forward on every allocation, which is O(1) for both the data structure and the allocate operation. The stated benefit is minimal internal fragmentation, because elements are inserted sequentially with spatial locality and the only fragmentation between them is alignment. The stated cost is the important one: due to its simplicity, this allocator does not allow specific positions of memory to be freed, and usually all memory is freed together. That is the whole trade in one sentence, and it is why a linear allocator suits a frame, a request, or any phase where objects share a lifetime. It also explains why the pool allocator, which comes later, needs a different strategy entirely.

Pool and free list both divide the chunk, in opposite ways

The pool allocator splits the big chunk into smaller chunks of the same size and keeps track of which of them are free, returning a free chunk when an allocation is requested. Fixed size and a free list are what make it work, and it is the natural fit for a workload whose objects are all the same shape, where a linear allocator would waste the tail of every allocation on alignment. The free list allocator occupies the fourth slot in the table of contents, sitting alongside the linear, stack and pool sections and between the custom allocators and the benchmarks, though its description lies beyond the portion of the text reproduced here. All four share the three traits listed before them, and those traits are the real content: a low number of mallocs, because any custom allocator takes big chunks and manages them internally; secondary data structures such as linked lists, trees or stacks to track allocated and free portions; and constraints, which are what buy the performance and also what limit where the allocator can be used.

The malloc critique is two sentences long

The section on what is wrong with malloc makes exactly two arguments, and both are about generality rather than about the algorithm. The first is that malloc is general purpose, meaning it must work in every case from one byte to a gigabyte or more, and an implementation that must handle all of that is not as efficient as one written for a specific need. The second is speed: sometimes, when allocating, malloc needs to change from user mode to kernel mode to get more memory from the system, and when that happens it turns out to be very slow. That second point is the one that shapes the whole project, because it is why custom allocators take large chunks up front. A program that allocates a small number of large blocks pays the mode transition once instead of many times. The rest of the introduction frames the goal as understanding how the most common allocators work, what they offer, and comparing them to see which performs better, which is a study goal rather than a library goal.

Benchmarks and complexity follow the allocators, not the use cases

The table of contents puts benchmarks, then time complexity, then space complexity, then a summary and last thoughts, so the evaluation material comes after the four implementations rather than being interleaved with them. Each allocator section carries its own complexity annotations inline, which is the part that survives translation from the article into a decision: linear is O(1) for the structure and O(1) to allocate; stack is O(1) to allocate and O(1) to free, with the data structure at O(N*H) improving to O(N); pool splits by size and tracks free chunks. What the numbers do not cover is your workload. A complexity class tells you how an operation scales with N, not how many operations your program performs, and an allocator wins or loses on the ratio of allocation to computation. The last push to master was on 2026-09-21, and there are no tagged builds, so there is no versioned artifact to pin if you decide to depend on the code.

Where custom allocators are the wrong tool

Four cases. The first is code whose lifetimes are not uniform. A linear allocator cannot free individual objects, and a stack allocator frees in reverse order, so a program that allocates and releases in an arbitrary pattern needs a pool or a free list, which means accepting fixed sizes or the bookkeeping cost. The second is a team without someone who will own the allocator. The listed constraint on custom allocators is that they impose restrictions on what data can be stored and which operations are allowed, which is what makes them fast and also what makes a subtle misuse a memory bug rather than an exception. Third is allocation that is not actually your bottleneck. The cost being optimized here is a user to kernel transition on large allocations, and in many programs that happens rarely enough that the complexity lives elsewhere. Fourth is anything where you would be replacing malloc wholesale. This is a set of focused allocators studied in isolation, with the stated purpose of understanding them, so reaching for it in place of a general-purpose allocator in production is a different project from the one in the repository.

Editorial conclusion

This repository suits a C++ developer who wants to understand what malloc does before trusting a custom allocator, and who reads diagrams and code alongside prose. It does not suit anyone planning to ship it as a dependency: there is no versioned package, and the configure command needs its source path corrected first. Before adopting, read the complexity annotations on each allocator, resolve the contradiction in the stack allocator description, and treat the benchmark section as a teaching example rather than as a measurement of your own workload.

Frequently asked questions

Official sources

1. Issues
2. License: MIT
3. mtrebi/memory-allocators on GitHub
4. README