Heap-allocated objects play an important role in many modern programs. Vari
ous results have shown the overall performance of these programs can be imp
roved by increasing the reference locality of heap-allocated objects. In th
is paper we describe an approach that improves the virtual memory performan
ce 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 alg
orithm to minimize the cost of gathering run-time stack information, Finall
y, we show that an implementation of these algorithms has little overhead a
nd can improve the virtual memory and TLB performance of programs substanti
ally. Copyright (C) 2001 John Wiley & Sons, Ltd.