I interviewed at Microsoft recently and one of the questions was to implement malloc and free from scratch in pseudocode. Of course, there were some assumptions that were made:

In addition to these assumptions, I was given the method stubs and a description of both malloc and free.

Malloc: This takes the required length in bytes as an argument and returns the address to a contiguous, free block of the required size.

Free: This takes an address that points to the first location of a block of allocated memory and adds this block back to the pool of free memory.

The Interview Solution

Almost immediately, I decided that a bit array with each bit representing one 128 byte chunk would be a relatively efficient way to track the status of each block. I also thought about using a linked list or some similar structure to store pointer to each of the free blocks. I know at one point, I thought that at least maintaining a pointer to the first free block could save some time, but honestly can't remember if I mentioned it due to the surrounding flood of thoughts.

Preventing Fragmentation and Binning

I also realized that fragmentation would be an issue, so suggested that allocating memory in the smallest available space that it still fits in would help to reduce that. I didn't think to call it fragmentation, so I just gave an example where it would occur to illustrate my point. In order to solve this issue, I suggested a form of binning where there are several bit arrays, where each one would represent a set of chunks that were of different sizes. One array would represent 128 byte chunks and the next would represent 256 bit chunks and the next would be 512 bit chunks. The bit representing a chunk would be set to false if any of the smaller chunks that occurred over the same space were occupied. I had never heard of this, so I gave another example and compared the structure to that of a skip list (yeah, not really the same, but it visually matches my mental picture).

Keeping track of chunk length

At this point, it was suggested that I go with just the single bit array. Then, I had to decide how to keep track of the length of each allocated chunk, so that the correct number of blocks could be freed. I mentioned that an integer array could be used, but could waste a large amount of space especially as the size of the chunks being allocated increases. The other solution that I suggested was simply including a length field at the beginning of each chunk that was allocated.

Adapting a string search algorithm

When trying to think of a way to improve the efficiency of the chunk finding algorithm for malloc, I remembered a string matching algorithm that was briefly discussed in one of my classes last year. This algorithm can be found here. Luckily, for chunk finding, this algorithm could be further simplified. When iterating through the bit array, start n (where n is the length of the desired chunk) places past the beginning and work backward. Any time a 1 is encountered, skip ahead n spaces and check the n preceding values. If you encounter n consecutive values that are set to 0, return the last index that was checked.

A few tricks

I needed to find the ceiling of a division since integer division truncates in all of the languages I've ever used. I wrote something similar to the following on the board:

	numBlocks = numBytes / 128;
	If(numBytes % 128) numBlocks++;

I just sort of blurted out that there had to be a more concise way to do this. The interviewer then showed me a little trick.

	numBlocks = (numBytes + 127)/128;

Things I realized after the interview

Later on the day of the interview, I explored Seattle, but the following two days, my mind kept wandering onto the subject of this problem. I ended up thinking of a few other optimizations.

Store data about the free blocks within the free blocks

If a block is unallocated, then it doesn't really matter what data is located within it. This means that the storage overhead from maintaining a linked list pointing between free blocks can be mitigated. Just store a pointer to the next block, a pointer to the previous block, and the length of the current block at the beginning of each free chunk.

Following up with some research

It seems like these options cover the majority of the cases that don't account for threading, an expandable heap, or caching. This should be interesting!