Building a Simple Memory Allocator
- Demonstrate the impact that the quality of a dynamic memory allocation library can have on application performance.
- Implement a simple fixed-size allocator
- Explain how your allocator could be a piece of a more comprehensive allocator
A Simple Fixed Sized Allocator
Pull today's code from the
cs61-exercises repository. It is in the l05 directory. As explained in the README.txt file:
membench.c A program for benchmarking different malloc implementations. We allocate 4096
memnodeobjects, then, NOPERATIONS times (which defaults to 10,000,000), free one object and allocate another.
memnodeis declared in
membench.h. membench uses an "arena" for its allocations. An arena is an object that encapsulates a set of allocations and frees. You can use arenas just to capture statistics or to encapsulate state for a specialized allocator. membench links with different allocator libraries. The simplest is mb-malloc.c, which implements the
memnode_alloc()functions with malloc and free. Run this with
./membench-malloc. Run a different number of allocations and/or simultaneous threads with
./membench-malloc NOPERATIONS NTHREADS. But it's more interesting to see how much time a run takes. For this, use the
timeprogram: time ./membench-malloc
A memnode allocator
In today's exercise, you will develop an allocator for
memnode structures, described in
membench.h. Since your allocator is always going to be called upon to allocate objects of the same size, one would expect that you can build something much faster than the general purpose allocator that malloc uses.
Given the declaration in
membench.h, how large are
Read the comments at the beginning of
mb-arena.h describing how we are going to represent the arena (the storage in which we'll store our
memnodes). Before we get into the details of your allocator design, we ought to be able to write several of the functions you need to complete.
You will build your implementation by typing
Creating the Arena
Fill in the function
memnode_arena_new. It need not actually allocate space for the
memnodes. It simply needs to set up the arena so that the first time
memnode_alloc is called, the right thing happens. You may use
malloc to create space for your
Once you have written
memnode_arena_new, you should also be able to write
Tip: Compile early and often! Make sure your code compiles with the new functions you've written.
Tip: Test early and often!
membench requires a fully working implementation to run completely, there are a number of ways you might test your code right now. You can write a separate program. You can add a call to
memnode_arena_free right after you allocate the arena and then exit. You can run things in the debugger. Try a variety of these techniques, but whatever you do, test each piece as you develop it. (Note: the tests in assignment 1 were designed to provide incremental testing to your debugging malloc implementation so that you didn't need to have everything fully functional at once. This "test early; test often" philosophy is critical to building good software.)
Designing Free Space Management
You now have one major design decision to make -- how will you keep track of which
memnodes are in use (e.g., have been allocated) and which are available for allocation. Here are some questions to think about when you design this.
1. When will you need to allocate a new
memnode_group ? (You need not worry about freeing
memnode_group structures until you free the arena.)
2. Is there a way to design management of the free/allocated space so that it will take you constant time to allocate/free a node?
3. How much space will you require to manage your free/allocated space? What fields will you need to add to your existing structures?
Use scratch paper or your whiteboards to illustrate your design. When you think you've got a good method for tracking your free/allocated
memnodes, raise your hand and run your design past a member of the course staff.
Go ahead and code it up
Once a staff member has checked your design, go ahead and complete your implementation. You will probably need to:
1. Modify new and free to initialize and clean up any new fields you added. (And then test this.)
memnode_alloc. You can test this before moving on to
memnode_free. You may not be able to run the test to completion, but you should be able to get through the set of initial allocations.
3. Now implement
At this point, you'll need to spend some time testing. Try running
membench with different parameters. When everything is working, you can compare your fixed-size allocator to malloc by comparing the timed output of
membench-malloc. Run each one multiple times.
Should you finish early
If you have extra time, design a second, completely different method to track free and allocated
memnodes. Be sure to save your original so that you can compare your two implementations.
Before you Leave
Shockingly, we have another survey for you to complete!