UCLA COMSCI 239 - AnanianRinard03 (10 pages)

Previewing pages 1, 2, 3 of 10 page document View the full content.
View Full Document

AnanianRinard03



Previewing pages 1, 2, 3 of actual document.

View the full content.
View Full Document
View Full Document

AnanianRinard03

90 views


Pages:
10
School:
University of California, Los Angeles
Course:
Comsci 239 - Current Topics in Computer Science: Programming Languages and Systems
Unformatted text preview:

Data Size Optimizations for Java Programs C Scott Ananian Martin Rinard Laboratory for Computer Science Massachusetts Institute of Technology Cambridge MA 02139 Laboratory for Computer Science Massachusetts Institute of Technology Cambridge MA 02139 cananian lcs mit edu rinard lcs mit edu ABSTRACT Keywords We present a set of techniques for reducing the memory consumption of object oriented programs These techniques include analysis algorithms and optimizations that use the results of these analyses to eliminate fields with constant values reduce the sizes of fields based on the range of values that can appear in each field and eliminate fields with common default values or usage patterns We apply these optimizations both to fields declared by the programmer and to implicit fields in the runtime object header Although it is possible to apply these techniques to any object oriented program we expect they will be particularly appropriate for memory limited embedded systems We have implemented these techniques in the MIT FLEX compiler system and applied them to the programs in the SPECjvm98 benchmark suite Our experimental results show that our combined techniques can reduce the maximum live heap size required for the programs in our benchmark suite by as much as 40 Some of the optimizations reduce the overall execution time others may impose modest performance penalties Embedded systems size optimizations static specialization field externalization field packing bitwidth analysis 1 INTRODUCTION We present a set of techniques for reducing the amount of data space required to represent objects in object oriented programs Our techniques optimize the representation of both the programmer defined fields within each object and the header information used by the run time system Field Reduction Our flow sensitive interprocedural bitwidth analysis computes the range of values that the program may assign to each field The compiler then transforms the program to reduce the size of the field to the smallest type capable of storing that range of values Categories and Subject Descriptors C 3 Computer Systems Organization Special Purpose and Application Based Systems Real time and embedded systems D 3 2 Programming Languages Language Classifications Object oriented languages Java D 3 4 Programming Languages Processors Compilers D 3 4 Programming Languages Processors Optimization E 2 Data Storage Representations Object representation General Terms Unread and Constant Field Elimination If the bitwidth analysis finds that a field always holds the same constant value the compiler eliminates the field It removes each write to the field and replaces each read with the constant value Fields without executable reads are also removed Static Specialization Our analysis finds classes with fields whose values do not change after initialization even though different instances of the object may have different values for these fields It then generates specialized versions of each class which omit these fields substituting accessor methods which return constant values Field Externalization Our analysis uses profiling to find fields that almost always have the same default value It then removes these fields from their enclosing class using a hash table to store only values of the field that differ from the default value It replaces writes to the field with an insertion into the hash table if the written value is not the default value or a removal from the hash table if the written value is the default value It replaces reads with hash table lookups if the object is not present in the hash table the lookup simply returns the default value Languages Performance Experimentation Algorithms This research was supported by DARPA AFRL Contract F33615 00 C 1692 NSF Grant CCR 0086154 NSF Grant CCR 0073513 NSF Grant CCR 0209075 and the Singapore MIT Alliance Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page To copy otherwise to republish to post on servers or to redistribute to lists requires prior specific permission and or a fee LCTES 03 June 11 13 2003 San Diego California USA Copyright 2003 ACM 1 58113 647 1 03 0006 5 00 Class Pointer Compression We use rapid type analysis to compute an upper bound on the number of classes that the program may instantiate Objects in standard Java implementations have a header field 59 public class JValue int integerType 0 int floatType 1 int type positive Object value void setInteger Integer i type integerType value i positive i intValue 0 1 0 void setFloat Float f type floatType value f positive f floatValue 0 1 0 commonly called claz which contains a pointer to the class data for that object such as inheritance information and method dispatch tables Our compiler uses the results of the analysis to replace the reference with a smaller offset into a table of pointers to the class data Byte Packing All of the above transformations may reduce or eliminate the amount of space required to store each field in the object or object header Our byte packing algorithm arranges the fields in the object to minimize the object size Figure 1 The JValue class All of these transformations reduce the space required to store objects but some potentially increase the running time of the program Our experimental results show that for our set of benchmark programs all of our techniques combined can reduce the peak amount of memory required to run the program by as much as 40 although the running time may increase In a memory limited embedded system where performance is not critical cost savings may directly result from the reduced minimum heap size that can appear in each variable This analysis tracks the flow of values across procedure boundaries via parameters into and out of the heap via instance variables of classes and through intermediate temporaries and local variables in the program It also reasons about the semantics of arithmetic operators such as and to obtain bounds for the values computed by arithmetic expressions Assume that the analysis examines the rest of the program not shown and discovers the following facts about how the program uses this class a the integerType field always has the value 0 b the floatType field always has the value 1 c the type field always


View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view AnanianRinard03 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view AnanianRinard03 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?