Summary and Conclusions

We studied the behavior of Hummingbird, a long-running program with dynamic memory allocation and deallocation patterns which do not conform to the typical pattern for which dynamic memory allocators are optimized. We also studied the dynamic memory activity of GNU Emacs when it was used to edit files in a large source hierarchy. We studied the fragmentation caused by the different implementations of malloc when used with the same Hummingbird and Emacs dynamic memory activity traces. We found that most mallocs caused extensive fragmentation for the Hummingbird trace. However we also found that some of them performed well. This is in contrast with the Emacs trace, which caused little fragmentation for most mallocs. However, there was a noticeable difference between the best mallocs and the rest. No malloc performed the best for both traces, while one malloc was consistently the worst.

While dynamic memory management for programs that allocate a small number of object sizes has been studied extensively, further research is needed to understand the dynamic memory management for long-running programs which allocate a large number of memory object sizes with varying sizes and lifetimes. Moreover, the low memory fragmentation of the best malloc for Hummingbird, PhK/BSD malloc [3], is purely serendipitous based on a correspondence with its author, Poul-Henning Kamp. Moreover, P-H Kamp did not claim to have tried to reduce fragmentation in case of a very large number of object sizes. In other words, he does not know why it performed so well on our workload.

We hope that this paper will spur renewed interest in dynamic memory allocation, and would lead to better understanding why particular dynamic memory allocation schemes work better for the kind of dynamic memory activity described in this paper. Future malloc implementors should consider a dynamic memory activity pattern similar to Hummingbird's when updating their code. At the minimum, application developers should become aware of the excessive memory fragmentation problem described in this paper, and if they encounter one, they should try to alleviate it by picking a different malloc package.