Arena allocation
The 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
malloc
and free
do. But we can obtain performance benefits, and
some neat features, by allocating and freeing related objects in groups.
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 malloc
and
free
.
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 allocator should:
- 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
: RunN
operations (default 50,000,000).-k K
: Allocate at mostK
chunks at a time (default 4096). (The handout code only works whenK
=1.)-j J
: Run withJ
threads (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
The 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
Skills
- 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 sz
.
(2) Implement an arena allocator that can efficiently allocate objects
smaller than a pointer (for instance, an allocator for single int
s).
Survey
When you’re done, complete the survey!
Solution video
This solution video starts from the fundamentals4x
code.