Generational Cache Management of Code Traces in Dynamic Optimization Systems

A dynamic optimizer is a runtime software system thatgroups a program's instruction sequences into traces, optimizesthose traces, stores the optimized traces in a software-basedcode cache, and then executes the optimized code inthe code cache. To maximize performance, the vast majorityof the program's execution should occur in the codecache and not in the different aspects of the dynamic optimizationsystem. In the past, designers of dynamic optimizershave used the SPEC2000 benchmark suite to justifytheir use of simple code cache management schemes.In this paper, we show that the problem and importance ofcode cache management changes dramatically as we movefrom SPEC2000, with its relatively small number of dynamicallygenerated code traces, to large interactive Windowsapplications. We also propose and evaluate a new cachemanagement algorithm based on generational code cachesthat results in an average miss rate reduction of 18% over aunified cache, which translates into 19% fewer instructionsspent in the dynamic optimizer. The algorithm categorizescode traces based on their expected lifetimes and groupstraces with similar lifetimes together in separate storage areas.Using this algorithm, short-lived code traces can easilybe removed from a code cache without introducing fragmentationand without suffering the performance penaltiesassociated with evicting long-lived code traces.