Data Size Optimizations for Java ProgramsC. Scott AnanianLaboratory for Computer ScienceMassachusetts Institute of TechnologyCambridge, MA [email protected] RinardLaboratory for Computer ScienceMassachusetts Institute of TechnologyCambridge, MA [email protected] present a set of techniques for reducing the memoryconsumption of object-oriented programs. These techniquesinclude analysis algorithms and optimizations that use theresults of these analyses to eliminate fields with constantvalues, reduce the sizes of fields based on the range of val-ues that can appear in each field, and eliminate fields withcommon default values or usage patterns. We apply theseoptimizations both to fields declared by the programmer andto implicit fields in the runtime object header. Although itis possible to apply these techniques to any object-orientedprogram, we expect they will be particularly appropriate formemory-limited embedded systems.We have implemented these techniques in the MIT FLEXcompiler system and applied them to the programs in theSPECjvm98 benchmark suite. Our experimental results showthat our combined techniques can reduce the maximum liveheap size required for the programs in our benchmark suiteby as much as 40%. Some of the optimizations reduce theoverall execution time; others may impose modest perfor-mance penalties.Categories and Subject DescriptorsC.3 [Computer Systems Organization]: Special-Purposeand Application-Based Systems—Real-time and embeddedsystems; D.3.2 [Programming Languages]: Language Clas-sifications—Object-oriented languages, Java; D.3.4 [Program-ming Languages]: Processors—Compilers; D.3.4 [Program-ming Languages]: Processors—Optimization; E.2 [DataStorage Representations]: Object representationGeneral TermsLanguages, Performance, Experimentation, AlgorithmsThis research was supported by DARPA/AFRL Con-tract F33615-00-C-1692, NSF Grant CCR-0086154, NSFGrant CCR-0073513, NSF Grant CCR-0209075, and theSingapore-MIT Alliance.Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission 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.KeywordsEmbedded systems, size optimizations, static specialization,field externalization, field packing, bitwidth analysis1. INTRODUCTIONWe present a set of techniques for reducing the amount ofdata space required to represent objects in object-orientedprograms. Our techniques optimize the representation ofboth the programmer-defined fields within each object andthe header information used by the run-time system:• Field Reduction: Our flow-sensitive, interprocedu-ral bitwidth analysis computes the range of values thatthe program may assign to each field. The compilerthen transforms the program to reduce the size of thefield to the smallest type capable of storing that rangeof values.• Unread and Constant Field Elimination: If thebitwidth analysis finds that a field always holds thesame constant value, the compiler eliminates the field.It removes each write to the field, and replaces eachread with the constant value. Fields without exe-cutable reads are also removed.• Static Specialization: Our analysis finds classes withfields whose values do not change after initialization,even though different instances of the object may havedifferent values for these fields. It then generates spe-cialized versions of each class which omit these fields,substituting accessor methods which return constantvalues.• Field Externalization: Our analysis uses profilingto find fields that almost always have the same defaultvalue. It then removes these fields from their enclosingclass, using a hash table to store only values of the fieldthat differ from the default value. It replaces writes tothe field with an insertion into the hash table (if thewritten value is not the default value) or a removalfrom the hash table (if the written value is the defaultvalue). It replaces reads with hash table lookups; ifthe object is not present in the hash table, the lookupsimply returns the default value.• Class Pointer Compression: We use rapid typeanalysis to compute an upper bound on the numberof classes that the program may instantiate. Objectsin standard Java implementations have a header field,59commonly called claz, which contains a pointer to theclass data for that object, such as inheritance informa-tion and method dispatch tables. Our compiler usesthe results of the analysis to replace the reference witha smaller offset into a table of pointers to the classdata.• Byte Packing: All of the above transformations mayreduce or eliminate the amount of space required tostore each field in the object or object header. Ourbyte packing algorithm arranges the fields in the objectto minimize the object size.All of these transformations reduce the space required tostore objects, but some potentially increase the running timeof the program. Our experimental results show that, for ourset of benchmark programs, all of our techniques combinedcan reduce the peak amount of memory required to run theprogram by as much as 40%, although the running timemay increase. In a memory-limited embedded system whereperformance is not critical, cost savings may directly resultfrom the reduced minimum heap size.1.1 ContributionsThis paper makes the following contributions:• Space Reduction Transformations: It presents aset of novel transformations for reducing the memoryrequired to represent objects in object-oriented pro-grams.• Analysis Algorithms: It presents a set of analysisalgorithms that automatically extract the informationrequired to apply the space reduction transformations.• Implementation: We have fully implemented all ofthe analyses and techniques presented in the paper.Our experience with this implementation enables us todiscuss the pragmatic details necessary for an effectiveimplementation of our techniques.• Experimental Results: This paper presents a setof experimental results that characterize the impact ofour transformations, revealing the extent of the savingsavailable and the performance cost of attaining them.2.