Dynamic Memory Management

Dynamic Memory Management (DM) is essential to the implementation of functional languages and many other modern programming languages. Prior to Clack's research, DMM could either be fast or small (i.e. have low fragmentation) but not both. DMM is a very mature research area, and to identify a new algorithm is a considerable challenge. By using a tree bitmap representation and altering the search semantics, a best-fit free-list memory allocator was created that provides both a ten times improvement in worst-case performance and excellent best-case performance. The allocator was patented:

  • A Data Structure, Memory Allocator and Memory Management System (Clack, UK Patent Application number 9924061.6, filing date 11th October 1999. PCT application number WO0231660, filing date 10th October 2001. UK and EU Patent Offices.

Christopher D. Clack
Department of Computer Science
UCL
Gower Street
London
WC1E 6BT

 clack@cs.ucl.ac.uk