Technical Report MSC-2011-03

Title: On the Limits of Partial Compaction
Authors: Anna Bendersky
Supervisors: Erez Petrank
Abstract: Dynamic memory allocation is ubiquitous in today's runtime environments. Allocation and de-allocation of objects during program execution may cause fragmentation and foil the program's ability to allocate objects. Robson has shown that a worst case scenario can create a space overhead within a factor of log n of the space that is actually required by the program, where n is the size of the largest possible object. Compaction can eliminate fragmentation, but is too costly to be run frequently. Therefore, some memory managers choose to run the compaction method seldom. Many runtime systems employ partial compaction, in which only a small fraction of the allocated objects are moved. Partial compaction reduces some of the existing fragmentation at an acceptable cost. In this work we limit the memory that can be compacted, and study the effects of the compaction use on the required heap size. We provide lower and upper bounds on the heap size requirement, for any program and any memory manager that employs compaction. In another part of our work, we show tighter bounds for a specific popular memory management method - the segregated free list. This work provides the first rigorous lower and upper bounds on the partial compaction effectiveness in reducing fragmentation at a low cost.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2011
To the main CS technical reports page

Computer science department, Technion