Discussion

We did not study the internal algorithm of any of the mallocs we measured, except for the modified binary buddy algorithm. We treated them as ``black boxes'', since this is the way most application developers use them. Thus we can not explain why some mallocs consumed much more heap space than others.

One could argue that we can resolve the memory fragmentation problem in Hummingbird by rounding the sizes of all memory blocks to the next power of two, and then use an existing malloc. In this way, splitting memory blocks and coalescing memory blocks will not cause fragmentation. However, as Table 3 shows, the modified binary buddy allocator caused 50.7% fragmentation, which is much worse than the best allocator, which caused only 30.5% fragmentation. Remember that the binary buddy actually allocates memory only in chunk sizes which are a power of two. Moreover, some implementation of malloc append a header to all memory blocks. Thus coalescing two blocks of the same size will generate a block whose size is slightly larger than twice the size of each original block. Thus this method will not eliminate fragmentation.

The large increase of the heap size experienced with Solaris 3X malloc when used with the Hummingbird trace is within the theoretical bounds for worst case fragmentation of first fit and best fit allocation algorithms [6]. The maximal memory needed for first fit is about $M \log_2 n$, where $M$ is the total size of live memory, and $n$ is the size of the largest object. The maximal memory needed for best fit is about $M n$, which is much larger. In our case, $M$ is 217.4 MB and $n$ is 39.9 MB. Considering the above worst case analysis, most mallocs (except Solaris 3X) required a much smaller amount of memory than the worst case.

The Emacs measurements showed that even when the object distribution is ``more typical'', some mallocs are better than others. In particular, the GNU malloc caused 21.4% fragmentation, while the better mallocs caused about 3% fragmentation.