Given the efficiency of using red-black binary trees, is it possible that the
malloc() implementation itself is coded to use them? After all, the memory allocation functionality must somehow maintain the set of allocated regions so they can be safely deallocated. Also, note that each of the programs listed previously make allocation requests for 32 bytes. Does the size of the request affect the performance of
free() requests? To investigate the behavior of
malloc(), we ran a set of experiments. First, we timed how long it took to allocate 4,096 chunks of n bytes, with n ranging from 1 to 2,048. Then, we timed how long it took to deallocate the same memory using three strategies:
In the order in which it was allocated; this is identical to ProgramC
In the reverse order in which it was allocated
In a scattered order that ultimately frees all memory
For each value of n we ran the experiment 100 times and discarded the best and worst performing runs. Figure 1-3 contains the average results of the remaining 98 trials. As one might expect, the performance of the allocation follows a linear trend—as the size of n increases, so does the performance, proportional to n. Surprisingly, the way in which the memory is deallocated changes the performance.
freeUp has the best performance, for example, while
freeDown executes about four times as slowly.
The empirical evidence does not answer whether
free() use binary trees (balanced or not!) to store information; without inspecting the source for
free(), there is no easy explanation for the different performance based upon the order in which the memory is deallocated.
Showing this example serves two purposes. First, the algorithm(s) behind memory allocation and deallocation are surprisingly complex, often highly tuned based upon the specific capabilities of the operating system (in this case a high-end computer). As we will learn throughout this book, various algorithms have "sweet spots" in which their performance has no equal and designers can take advantage of specific information about a problem to improve performance. Second, we also describe throughout the book different algorithms and explain why one algorithm outperforms another. We return again and again to empirically support these mathematical claims.