Low Cost Methods for Predicting Heap Object Behavior

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. Many researchers have used the call stack as a way of naming objects and predicting their behavior, but gathering call stack information at runtime can be very expensive. In this paper, we describe a lowoverhead algorithm for identifying which allocation sites are necessary to implement one version of a call stack based object predictor. In addition to the algorithms we include performance data on how the program's execution is aected by the added instrumentation. Finally, we present some brief results of using these algorithms to implement our previous heap object allocation optimization. 1 Introduction The reference locality of heap-allocated objects is important in many applications. As we have documented in previous work, object-oriented languages, such as Java an..