Homework 2: a high-performance malloc (DRAFT)

In this homework, we take a naive malloc implementation and add optimizations to significantly improve the performance of a sample application.

The homework template in svn://bits.cs.uic.edu/cs361/pub/homeworks/hw2 holds the application, as well as a basic malloc implementation in basic.c, and a libc malloc wrapper in libcmalloc.c. export this template to your turn-in directory, then svn add it.

The Makefile includes targets for both the original basic.c malloc, your improved hw2.c malloc, and a wrapper for the libc malloc. Running make test on the command line executes the target program compiled with all three mallocs, to compare their relative performance.

The basic solution takes about 25-30 seconds to run, whereas the libc malloc wrapper takes about 1-1.5 seconds, or a 20x speedup. For full points on this homework, get to below 2 seconds on Amazon, or a 15x speedup over the basic solution. exact cutoff liable to change until Wednesday Sept 4.

Turn-in instructions

As in hw1, turn in your homework by committing your latest version to your turn-in repository before the turn-in deadline. Your hw2 turn-in should be in a folder called hw2 directly under the root folder of your repository. Simply committing the hw2 template is a good start, and highly recommended to do early on.

Put all of your solution code in the file hw2.c, and do not modify the other files.

Libc Malloc Reference

In contrast with most homework, this time you're allowed to look at the solution ahead of time! The link below leads to the source code for malloc in libc, which is very fast. Feel free to read as much or as little of this code as you want, it is very well written and documented. Just don't copy-paste anything.

libc malloc link

This nice malloc presentation describes some of the standard features implemented in malloc, such as boundary tags, coalescing free chunks, and multiple free-lists. It might be a good complement to Section 9.9 in the textbook.

Competition Aspect

To make things a little more interesting, we periodically check for committed solutions, run them, and publish the results here.