Algorithms in a Nutshell

Side Story

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 malloc() and 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:

freeUp

In the order in which it was allocated; this is identical to ProgramC

freeDown

In the reverse order in which it was allocated

freeScattered

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 malloc() and free() use binary trees (balanced ...