An efficient data structure for dynamic memory management

Advances in software engineering, such as graphical user interface and obje ct-oriented programming, have caused applications to become more memory int ensive. The growing popularity of these applications increases the importan ce of high-performance dynamic memory management. This paper introduces a n ew data structure intended to increase the emciency of implementations of c ommon dynamic memory allocation and deallocation algorithms, including Firs t Fit. The data structure, called the Common List, establishes a relationsh ip between the allocated and free list. This strategy increases significant ly the deallocation performance. Simulation results based on the traces fro m publicly available software applications are presented. (C) 2000 Elsevier Science Inc. All rights reserved.