Abstract Heap‐allocated objects play an important role in many modern programs. Various results have shown the overall performance of these programs can be improved by increasing the reference locality of heap‐allocated objects. In this paper we describe an approach that improves the virtual memory performance of allocation‐intensive C programs by predicting the reference behavior and lifetime of heap objects as they are allocated. We further describe an implementation of our prediction algorithm and evaluate its performance on real programs. As part of our implementation, we present a low‐overhead algorithm to minimize the cost of gathering run‐time stack information. Finally, we show that an implementation of these algorithms has little overhead and can improve the virtual memory and TLB performance of programs substantially. Copyright © 2001 John Wiley & Sons, Ltd.

Dynamic storage allocation has become increasingly important in many applications, in part due to the use of the object-oriented paradigm. At the same time, processor speeds are increasing faster than memory speeds and programs are increasing in size faster than memories. In this paper, we investigate efforts to predict heap object reference and lifetime behavior at the time objects are allocated. Our approach uses profile-based optimization, and considers a variety of different information sources present at the time of object allocation to predict the object's reference frequency and lifetime. Our results, based on measurements of six allocation intensive programs, show that program references to heap objects are highly predictable and that our prediction methods can successfully predict the behavior of these heap objects. We show that our methods can decrease the page fault rate of the programs measured, sometimes dramatically, in cases where the physical memory available to the program is constrained.