cs61-exercises/fundamentals3x directory contains a program called
membench that benchmarks dynamic memory allocators. Your task is to build a simple arena allocator that can beat the performance of
malloc. We’ve started the code for you in
mb-arena.c. Complete that file and evaluate your allocator’s performance.
Normally, we allocate and free dynamic objects independently, as
free do. But we can obtain performance benefits, and
some neat features, by allocating and freeing related objects in
An arena (also called a zone, area, pool, memory context, etc.)
formalizes this concept. An arena is a type that represents a group of
allocated objects. Special functions are used to allocate and free
objects from this arena. Those special functions can be faster, more
convenient, and sometimes safer than general-purpose
mb-arena.c contains the start of an arena allocator for
chunk objects—but it
only knows how to allocate one chunk. Finish the allocator! Your
- Allocate a chunk in O(1) time.
- Free a chunk in O(1) time.
- Use memory proportional to the peak number of actively allocated chunks (rather than, say, the total number of allocated chunks).
- Run out of memory only if the system has no more memory available.
Test your arena allocator by running
./membench-arena with different arguments. The arguments are:
-n N: Run
Noperations (default 50,000,000).
-k K: Allocate at most
Kchunks at a time (default 4096). (The handout code only works when
-j J: Run with
Jthreads (default 1).
And use command-line tools to test your allocator’s performance and memory usage. A particularly useful command is
time, which comes in two varieties. Simply running
time COMMAND reports the amount of time it took to run a command. (The
real number is what you want; we’ll hear more about the others later). Running
/usr/bin/time COMMAND reports more information, including memory usage. On my laptop:
$ /usr/bin/time ./membench-malloc -k1 1.72user 0.00system 0:01.72elapsed 99%CPU (0avgtext+0avgdata 5932maxresident)k 0inputs+0outputs (0major+90minor)pagefaults 0swaps
maxresident number is the maximum amount of memory used in kilobytes; this program used about 6MB. And use
valgrind --tool=memcheck to check for memory leaks; how sweet it is to see
==92996== All heap blocks were freed -- no leaks are possible
- Demonstrate the impact of a dynamic memory allocators on application performance.
- Implement a simple arena allocator.
- Use unions and pointers.
Advanced features for optional after-class work
(1) Change the interface of
membench_arena_new to take a
size_t sz argument. An arena of size
sz should allocate objects of size
sz, meaning every object returned by
membench_alloc(arena) should have size
(2) Implement an arena allocator that can efficiently allocate objects smaller than a pointer (for instance, an allocator for single
When you’re done, complete the survey!
This solution video starts from the