Access Restriction

Author Grunwald, Dirk ♦ Zorn, Benjamin ♦ Henderson, Robert
Source CiteSeerX
Content type Text
Publisher ACM Press
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Various Application ♦ Program Performance ♦ Memory Allocation ♦ Increased Paging ♦ Poor Locality ♦ Reference Locality ♦ Ubiquitous Operation ♦ Trace-driven Simulation ♦ Memory Allocator ♦ Adjacent Free Object ♦ Performance Evaluation ♦ Large Allocation-intensive Program ♦ Dynamic Storage Allocation Algorithm ♦ Poor Reference Locality ♦ System Perform ♦ Programmer Concern ♦ Cache Locality ♦ Modern Computer Architecture ♦ Sequential-fit Allocation Algorithm ♦ Cache Miss Rate
Description The allocation and disposal of memory is a ubiquitous operation in most programs. Rarely do programmers concern themselves with details of memory allocators; most assume that memory allocators provided by the system perform well. This paper presents a performance evaluation of the reference locality of dynamic storage allocation algorithms based on trace-driven simulation of five large allocation-intensive C programs. In this paper, we show how the design of a memory allocator can significantly affect the reference locality for various applications. Our measurements show that poor locality in sequential-fit allocation algorithms reduces program performance, both by increasing paging and cache miss rates. While increased paging can be debilitating on any architecture, cache misses rates are also important for modern computer architectures. We show that algorithms attempting to be space-efficient by coalescing adjacent free objects show poor reference locality, possibly negating the benef...
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 1993-01-01