Implementing heap-object behavior prediction efficiently and effectively

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.