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.

(More on arenas)

Test your arena allocator by running ./membench-arena with different arguments. The arguments are:

• -n N: Run N operations (default 50,000,000).
• -k K: Allocate at most K chunks at a time (default 4096). (The handout code only works when K=1.)
• -j J: Run with J 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 ints).

Survey

When you’re done, complete the survey!

Solution video

This solution video starts from the fundamentals4x code.