Increasing the reference locality of dynamically allocated objects

Heap-allocated objects play an important role in many modern programs. Our investigations of dynamically allocated objects show that there is a strong skew in object reference behavior: a small percentage of the objects receive a large percentage of the references. In this thesis, we describe A VON a memory allocation system that uses the skew in reference density between objects to improve program performance.;The AVON system is designed to increase the reference density of large programs that make heavy use of dynamically allocated memory by segregating objects into Avon heap areas based on their reference behavior and lifetime. All programs we have studied appear to have very non-uniform reference patterns across their dynamically allocated memory. We found that it is possible to predict object reference behavior at allocation time. Our system does this by using profile data to observe both the information available to the allocator when it creates an object and the resulting behavior of that object.;With an accurate predictor, we are able to build a customized allocator to use the skew in references between dynamic objects to improve program performance. In implementing the AVON allocator, we discovered that a naive solution to the allocator runtime had a substantial overhead and reduced program performance. To alleviate this overhead, we developed two algorithms that together reduced the runtime overhead of the AVON allocator by an average of 80%.;By reducing the runtime overhead, we were able to build optimized binaries with the AVON allocator and evaluate them side-by-side against binaries with a more traditional allocator. We found that object segregation can result in a reduction of virtual memory paging activity and data TLB miss rates. The combination of these two effects improves performance, and reduces execution time, in applications that use a large amount of dynamic data.