The cost of reclaiming space with traversal-based garbage collection is inversely proportional to the amount of free memory, i.e., O(1/(1-f)), where f is the fraction of memory that is live. Consequently, the cost of garbage collection can be very high when the size of the live data remains large relative to the available free space. Intuitively, this is because allocating a small amount of memory space will require the garbage collector to traverse a significant fraction of the memory only to discover little garbage. This is unfortunate because in some application domains the size of the memory-resident data can be generally high. This can cause high GC overheads, especially when generational assumptions do not hold. One such application domain is self-adjusting computation, where computations use memory-resident execution traces in order to respond to changes to their state (e.g., inputs) efficiently.
This paper proposes memory-management techniques for self-adjusting computation that remain efficient even when the size of the live data is large. More precisely, the proposed techniques guarantee O(1) amortized cost for each reclaimed memory object. We propose a set of primitives for self-adjusting computation that support the proposed memory management techniques. The primitives provide an operation for allocating memory; we reclaim unused memory automatically.
We implement a library for supporting the primitives in the C language and perform an experimental evaluation. Our experiments show that the approach can be implemented with reasonably small constant-factor overheads and that the programs written using the library behave optimally. Compared to previous implementations, we measure up to an order of magnitude improvement in performance and up to a 75% reduction in space usage.
@inproceedings{HammerAc08,
author = {Matthew A. Hammer and Umut A. Acar},
title = {Memory management for self-adjusting computation},
booktitle = {International Symposium on Memory Management},
year = {2008},
pages = {51-60}
}
Available as PDF.
It was presented at the International Symposium for Memory Management (ISMM) 2008 on June 7th in Tuscon Arizona. The slides from the talk are also available.
The paper describes an implementation that we call ACTK (Self-Adjusting Computation ToolKit), for lack of a better name. ACTK is a C library that allows users to embed self-adjusting computations within their C programs. It features efficient memory management techniques for these computations including automatic reuse and reclamation.
ACTK is available for download. The code is licensed under the GPL.