Adaptive type-partitioned garbage collection

A collector for collecting non-referenced objects stored in a heap by a program while the program is executing in a computer system is presented. A sample and partition routine in the collector partitions the heap into cold space and hot space. The sample and partition routine defines hot space objects and cold space objects. After the heap has been partitioned, an object allocation routine in the collector stores hot space objects in hot space and cold space objects in cold space. A collection routine in the collector searches hot space for referenced objects and reclaims non-referenced objects stored in hot space. Upon determining that hot space is full, the collection routine searches cold space and hot space for referenced objects and moves referenced objects stored in hot space to cold space.

BACKGROUND OF THE INVENTION

A block of memory may be allocated for use by a program executing in a computer system. The block of memory is typically referred to as a heap. The heap may be further divided into fixed size pages. The program requests a portion of memory from the heap when needed, for example, to store an object such as an array.

A garbage collector, also referred to as automatic storage reclamation, manages the heap by reclaiming memory no longer required by the program. Typically, the garbage collector is executed if a currently executing program is unable to allocate memory for new objects because all the allocatable memory has been allocated to other objects. Garbage collection is required by computer programming languages such as LISP™, Java™, SmallTalk™ and ML™. Garbage collection can also be used by programing languages such as C and C++.

In order to determine which objects may be collected, the garbage collector traverses all pointers to objects reachable from the processor's call stack and registers. Objects reachable from the processor's call stack are considered non-collectable because there are currently being used. All the objects in the heap that are not reachable from the processor's call stack are collectable because they are no longer in-use and are thus garbage. The collectable objects are collected for future allocations.

Techniques for garbage collection include reference counting, mark-sweep collection and copying collection. The reference counting technique stores a reference count for each object stored in the heap equal to the number of pointers pointing to the object. The reference count is stored in a header field in the object. Objects may be reclaimed if the reference count is zero. However, the reference counting technique decreases the performance of the program because the cost of reference counting is proportional to the number of pointer stores. Also, cycles of garbage cannot be reclaimed by the garbage collector.

The mark-sweep collection technique marks all reachable objects. Reachable objects may be marked by setting a bit in the header field of each reachable object. After reachable objects are marked, the unmarked objects are stored in memory in a doubly-linked free list. Subsequently, memory is allocated by removing objects from the free list.

The copying collection technique divides the heap into two contiguous regions; a first region and a second region. Memory is allocated for an object from a first region. When all the memory in the first region is in use by the program, reachable objects are copied from the first region to a second region. The roles of the first region and the second region are reversed. This effectively provides available memory, for allocation purposes, from the end of the new first region formerly called the second region. However, the time taken to copy large objects from a first region to a second region can consume a large portion of the total program execution time.

Garbage collection can consume a portion of the total program execution time. In some object oriented programming languages, such as Java™, the garbage collector may occasionally consume as much as fifty percent of program execution time because collection is required to reclaim memory from the heap for the executing program.

Techniques are available for reducing the amount of program execution time consumed by the garbage collector for copying objects. One such method is age-based generational collection. An age-based garbage collector segregates objects into old and young objects dependant on the time at which memory was allocated for the object. The assumption is that memory allocated for young objects can usually be freed before memory allocated for old (longer lived) objects. Thus, the age-based generational collector collects the youngest objects; that is, those more recently having memory allocated to them. By doing so, long-lived-objects are not copied. By collecting only the youngest objects, the program execution time consumed by garbage collection is reduced.

However, age-based generational collection is not always appropriate for computer languages such as Java™. Java™ frequently updates long-lived objects, for example, by adding data to elements of an array. This updating may result in excessive copying which consumes program execution time.

Thus, various disadvantages exist in currently existing garbage collection techniques/methods and there is a need for improvement in garbage collecting.

SUMMARY OF THE INVENTION

The present invention provides a collector for collecting non-referenced objects stored in a heap by a program while the program is executing in a computer system. An object allocation routine stores an object of a particular type in one of a plurality of spaces in heap dependent on a predefined category for the type. A collection routine searches one of the spaces for referenced objects and reclaims non-referenced objects stored in the searched space. A sample and partition routine defines a category of an object stored in the heap to be hot or cold.

Upon determining that hot space is full, the collection routine searches cold space and hot space for referenced objects and moves referenced objects of the hot category stored in hot space to cold space. The sample and partition routine also includes a write barrier elimination routine. The write barrier elimination routine eliminates a write barrier for an intergenerational pointer between an object stored in hot space and an object stored in cold space. The write barrier elimination routine preferably eliminates a write barrier by replacing machine code instructions for a write barrier with no operation machine code instructions.

The sample and partition preferably defines an object to be hot or cold dependent on object type mortality. Object type mortality is estimated dependent on the difference of the number of bytes of the object type stored in the heap before a collection and the number of bytes of the object type stored in the heap after the collection.

The sample and partition may partition the heap to minimize intergenerational pointers between hot space and cold space. The collection routine copies referenced hot objects to a new page in hot space.

DETAILED DESCRIPTION OF THE INVENTION

FIG. 1is a block diagram illustrating the use of a garbage collector100to reclaim memory in a heap102for an executing program108according to the principles of the present invention. The program108processes data stored in an input file106and generates an output file110. For example, the program may be a parser which processes a source code file and generates a parsed file or the program may be a database search program which searches a database for entries including a keyword and generates a list of database entries including the keyword. The program is written in a programming language that provides a type for each object.

While the program108executes, a heap102is allocated for the program108by the operating system. The heap102is an area of computer memory from which the executing program108can request (allocate) memory in which to store objects. The adaptive based garbage collector100manages the heap102for the program102by reclaiming memory storing objects which are no longer referenced by the executing program108.

A stack frame104stores a root list of pointers to objects stored in the heap102. Pointers to objects stored in the heap102are also stored in the registers116of the processor (not shown) in the computer system executing the program108.

The garbage collector100determines which of the objects stored in the heap102may be reclaimed dependent on pointers to objects in the heap102stored in the registers116and the stack frame104.

The root set of pointers for the program108consists of all pointers stored in the stack frame104and pointers stored in the registers116. An object is reachable if it is a member of the root set or pointed to by a reachable object. The set of reachable objects forms a directed graph. An object can be reclaimed if it is no longer reachable by the program108. The adaptive-type based garbage collector100reclaims non-reachable objects for use by the program108.

FIG. 2is a block diagram illustrating the logical partitioning of the heap102shown inFIG. 1. The initial size of the heap102provided to the executing program is specified before executing the program. For example, the heap size may be specified by the user in the command issued to request execution of the program. The heap102may grow as necessary while the program is executing.

The heap102is physically subdivided into a plurality of same size pages206. Each page206is a fixed number of bytes. For example, the heap may be subdivided into 4 Kilobyte pages. However, the number of bytes per page is not limited to 4 Kilobytes; the number of bytes per page may be greater or less than 4 Kilobytes.

The garbage collector100logically partitions the heap102into two spaces, a hot space200and a cold space202. It is important to note that there is no physical division between pages206stored in hot space200and pages206stored in cold space202. The space in which a page206is located is dependent on a space identifier stored in a Page Control Block (“PCB”)212associated with the page206. The program108allocates memory from the heap102in which to store an object by requesting memory from a page206in the hot space200or the cold space202dependent on the object's category.

An object is allocated to a page206in hot space200if the object category is ‘hot’; that is, it is likely not to be a long-lived object and thus it is highly probable that the garbage collector100will be able to reclaim the object. An object is allocated to a page206in cold space202if the object's category is ‘cold’; that is, likely that it is a long-lived object and thus it is less probable that the garbage collector100will be able to reclaim the object.

The number of logical spaces is not limited to the two spaces, hot space200and cold space202shown. The heap102may be partitioned into more than two logical spaces with objects assigned a preferred space dependent on how likely it is that the object may no longer be referenced by the program108.

Each space200,202includes a current space pointer208,210. The current space pointer208,210stores the address of the next available location in a page206in the space200,202in which the program108may store an object. The program108stores the next hot object in the location in the page206in hot space200stored in (referenced by) the current hot space pointer208. The program stores the next cold object in the location in the page206in cold space202stored in (referenced by) the current cold space pointer210.

FIG. 3is a block diagram illustrating one of the PCBs212associated with any one of the pages206shown inFIG. 2. The PCB212includes a space identifier302and a pointer304to the first object stored in the page206. A page206may be a member of hot space200or cold space202dependent on the state of the space identifier302stored the PCB212associated with the page206.

The space identifier302for a heap102logically partitioned into hot space200and cold space202as shown inFIG. 2may be implemented as a single byte storing a hot space identifier or a cold space identifier. Thus, a page206may effectively be moved between cold space202and hot space200by modifying the space identifier302in the PCB212associated with the page206.

FIG. 4is a block diagram illustrating an object400stored in any one of the pages206shown inFIG. 2. The object400includes an object header402and object data404. The object header402includes a pointer to an object type structure412. There is one object type structure414per object type. The object type structure414includes a class name field406, a preferred space field408and an object size field410.

The object size field410stores the size of the object type; that is, the number of bytes stored in the object header402and the object data404. The class name field406stores the class name of the object type. The class name is assigned by the program language. For example, in the Java™ programming language, the class name assigned to an object may be “char[ ]” if the object type is an array of characters. The contents of the preferred space field408stores an indication of the preferred space, that is; hot space200or cold space202, in which an object400of this object type may preferably be stored. The contents of the preferred space field408thus indicates the category of the object type; that is whether the object category is hot or cold. The contents of the preferred space field408for each object stored in the heap102is defined by the garbage collector100. The method for defining the preferred space for an object400is described later in conjunction withFIG. 7.

Objects400are added sequentially to a page206. Thus, the next object for an object type of the list category is stored in a page206in hot space200starting at the location identified by the current hot space pointer208. A plurality of objects400may be stored in each page206, the number of objects stored in a page206is dependent on the size of each object400and the size of the page206. For example, eight512byte objects and four 1 Kilobyte objects can be stored in an 8 Kilobyte page206. The location of the start of the first object stored in the page206is stored in the pointer304to the first object in a page206in the PCB212associated with the page206. The start address for the second object400stored in the page206can be determined from the start location and the size of the first object400stored in the page206. The start addresses for succeeding objects400stored in the page206are similarly determined from the start address and size of respective preceding objects400stored in the page206.

FIG. 5Ais a block diagram illustrating components of the garbage collector100shown inFIG. 1. The adaptive type-based garbage collector100includes a hot/cold category list506, a major collection routine502, a minor collection routine500, a sample and partition routine504, a write barrier elimination routine510, an object allocation routine508and an scan queue524.

The object allocation routine508provides a starting address518of a location in a page206in the heap102in which the program108may store an object upon receiving an allocation request516from the program108. The allocation request516includes the type of object to be stored in the heap102. The starting address518returned is dependent on whether the object category for the object type is hot or cold.

The minor collection routine500searches pages206in hot space200for referenced objects400. An object400is referenced if the object400can be reached directly by a pointer stored in the CPU registers116or the stack frame104or by another referenced object. Pages including referenced objects are stored in the scan queue524. The scan queue524is only valid while the minor collection routine500is collecting objects400. If an object400is unreachable, the memory occupied by the object400is reclaimed for use by the object allocation routine508.

Similar to the minor collection routine500, the major collection routine502reclaims memory for use by the object allocation routine508. However, the major collection routine502searches for referenced objects in both hot space200and cold space202. Thus, the major collection routine502consumes more execution time than the minor collection routine500because it examines more pages206. The major collection routine502also uses the scan queue524while it is reclaiming memory storing non-referenced objects400.

During normal program execution, current_space525stores an even number. Hot category objects are allocated to pages numbered with current_space525; that is, hot space200. Cold category objects are allocated to pages numbered with the number stored in current_space525plus 1; that is, cold space202.

The minor collection routine500, copies all live hot objects to pages with space identifiers302equal to the number stored in current_space525plus 2; that is, hot space200. Also, pages206can be conservatively “promoted” by incrementing the number stored in the space identifier302by 2. When the minor collection routine500completes the collection, the number stored in current_space525is incremented by 2. Thus old hot pages are automatically freed, because their space identifiers302are even and less than the number stored in current_space525. Cold pages are not reclaimed by the minor collection routine500.

The major collection routine502renumbers pages206with space identifier302set to an odd number (cold space202) with the number stored in current_space525. Then, the major collection routine502copies all live objects to pages206with space identifier302set to the number stored in current_space525plus 1. Thus, live objects on pages206stored in cold space202are copied to other pages206in cold space202and live objects on pages206stored in hot space200are copied to other pages206in cold space202. At the end of the collection, the major collection routine502increments current_space525by two. Thus, all the old pages automatically become free because their space identifiers306are even and less than the number stored in current_space525.

For example, current_space525is set to ‘2’, thus, a page206with space identifier302set to ‘1’ (“page 1”) is in cold space202, a page206with space identifier302set to ‘2’ (“page 2”) is in hot space200and a page206with space identifier set to ‘0’ (“page 3”) is free. The page 1 stores live and dead cold category objects. The page 2 stores live and dead hot category objects.

Assuming no conservative collection, after the minor collection routine500has completed a minor collection, current_space525is set to 4. The live object on Page 2 is moved to Page 3 and the space identifier302of page 3 is set to ‘4’. Thus, Page 3 is now in hot space200and Page 2 is free. Page 1 is still in cold space202.

After the major collection routine502has completed a major collection. The live cold object on Page 1 is moved to Page 3 and the live object on Page 2 is moved to Page 3. The current space525is set to ‘4’. The space identifier302in Page 3 is set to ‘3’. The space identifier302in Page 1 and Page 2 are set to ‘2’. Thus, Page 3 is in cold space and Page 1 and Page 2 are free.

Current_space525is incremented until it reaches a predefined maximum number. In one embodiment the predefined maximum number is 250. Once the predefined maximum number is reached, all the pages206in the heap are scanned. Free pages are re-labeled by setting the space identifier302to ‘0’. Cold pages are re-labeled by setting the space identifier302to ‘1’. Hot pages are re-labeled by setting the space identifier302to ‘2’. After the re-labeling is complete, current_space525is set to ‘2’.

The sample and partition routine504computes the number of bytes in the heap102used to store all objects of each type. The sample and partition routine504then calls the major collection routine500to perform a major collection. The sample and partition routine504defines the object's category to be hot or a cold dependent on the difference of the number of bytes of each object type stored in the heap102after the major collection is complete. Having defined an object category for each object type used by the program108to be hot or cold, the sample and partition routine stores an object category for each object type in the object hot/cold category list506.

The write barrier elimination routine510determines whether machine code instructions inserted by a compiler to record the location of a pointer in the heap102are necessary. Machine code instructions to record the location of the pointer in the heap102are typically referred to as a write barrier. A write barrier is not required if the object400and a pointer to the object400are both stored in the same space200,202or if the object400is stored in cold space202and the pointer to the object is stored in hot space200. Thus, the memory referencing machine code instructions may be replaced with No Operation (“NOP”) instructions in order to decrease the execution time of the program. The modification of the machine code to eliminate a write barrier is described later in conjunction withFIG. 12B.

FIG. 5Bis a block diagram illustrating the object hot/cold category list506shown inFIG. 5A. The object hot/cold category list506stores an object category530for each object type. In the object hot/cold category list506shown inFIG. 5Bthe program language defines seven object types. Object types 1,2 and 5 have been defined as cold category objects and object types 3, 4, 6 and 7 have been defined as hot category objects. The invention is not limited to seven object types, the object hot/cold category list may store more than seven object types. For example, in the Java™ computer programming language the number of object types is unbounded because user defined object types or classes are permitted. A user defined object type may be a Tree or a VideoGame or any other user defined object type.

FIG. 6is a flow chart illustrating the steps performed in the garbage collector100shown inFIG. 1for managing the heap102. The steps are described in conjunction with FIGS.2,3,4and5.

At step600, initially the object category530defined for all object types is cold in the object hot/cold category list506. The space identifier302stored in each PCB212associated with a page206in the heap102identifies the space as cold space202. Thus, the object allocation routine508allocates memory to store the objects in cold space202starting at the location stored in the current cold space pointer210. Processing continues with step602.

At step602, the sample and partition routine504is called by the object allocation routine508, after the object allocation routine508determines that a first collection511is required because there are insufficient pages206available in the cold space202for allocation to the executing program108. The sample and partition routine504requests a collection by the major collection routine502. After the collection is complete, the sample and partition routine504defines a category for each object type as described in conjunction withFIG. 7. Alternatively, the sample and partition504may use statistics from a previous execution of the program108to define a category for each object type.

Having defined a category for each object type to be a hot or cold, the sample and partition routine504stores an object category530for the object type in the object hot/cold category list506. Then, the sample and partition routine504copies all objects to cold space202. Processing continues with step604.

At step604, upon receiving a request516for allocation of memory for an object400of a particular type from the program108, the object allocation routine508examines the object category530corresponding to the object type stored in the object hot/cold category list506. If the object category530is hot, the object allocation routine508stores the object400starting at the location in the page206in hot space200pointed to by the current hot space pointer208. If the object category514is cold, the object allocation routine508stores the object400starting at the location in the page206in cold space202pointed to by the current cold space pointer210. Processing continues with step606.

At step606, the object allocation routine508determines if a minor collection is required as described above. If not, processing continues with step604. If so, processing continues with step608.

At step608, the minor collection routine500performs a minor collection to reclaim non-referenced memory in hot space200for use by the object allocation routine508. The method for performing a minor collection is described in conjunction withFIG. 8.

At step610, after the minor collection routine500reclaims memory storing non-referenced objects, the object allocation routine508determines if a major collection is required. A major collection is required if the minor collection did not reclaim sufficient memory for use by the object allocation routine508. The object allocation routine508also requests a major collection if the retention rate of a minor collection exceeds that of the retention rate of the last major collection. Retention rates are estimated by counting the number of pages206in use before and after collection. If a major collection is required, processing continues with step612. If not, processing continues with step604described above.

At step612, the major collection routine502performs a major collection. A major collection examines both hot space200and cold space202for memory storing referenced objects400and reclaims the memory storing non-referenced objects400for use by the object allocation routine508. The method for performing a major collection is described in conjunction withFIG. 8. Processing continues with prior step604.

FIG. 7is a flow chart illustrating the steps performed by the sample and partition routine504shown inFIG. 5for defining an object category530for an object type and logically partitioning the heap102.

At step700, the sample and partition routine504counts the number of bytes used in the heap102per object class stored in the class name field406in the object400and stores the number of bytes in parameter ‘b’. To count the number of bytes, the sample and partition504searches each page206for objects400by reading the class name field406and the object size410in the object header402and determining the location of the start of the next object stored in the page206. The starting location of the next object400in the page206is determined from the size of the previous object400. The sample and partition504counts the number of bytes for each object class stored in the heap102. Alternatively, the sample and partition may randomly select objects for which to count bytes. One method for randomly selecting object types selects a random subset of pages and counts the number of each object type stored in these pages206. Processing continues with step702.

At step702, the sample and partition routine504calls the major collection routine502to perform a major collection. The method for performing a major collection is described in conjunction withFIG. 8. Processing continues with step704.

At step704, the sample and partition routine504counts the number of bytes per object type after the major collection and stores the number of bytes in parameter ‘a’. The method used to count the number of bytes after the major collection is the same method described in conjunction with step702. Processing continues with step706.

At step706, the sample and partition routine504calculates the mortality rate for each object type found in the heap102using the below algorithm.
mortality=((b−a)/b)

where:a=number of bytes of the object type stored in the heap before the minor collectionb=number of bytes of the object type stored in the heap after the minor collection

The mortality of an object type is a measure of how likely the object of the type are to survive a collection. The category of an object type with a high mortality probability is defined to be hot. The category object type with a low mortality probability is defined to be cold. Processing continues with step708.

At step708, the sample and partition routine504stores an object category530for each object type in the object hot/cold category list506. The object category530is dependent on the calculated mortality of the object class. The object hot/cold category list506is provided for the object allocation routine508so that in subsequent memory allocations for objects400, the object allocation routine508can determine whether to store the object400dependent on the type of the object in hot space200or cold space202in the heap102. Processing continues with step710.

FIG. 8is a flow chart illustrating the steps performed in either the major collection routine502or the minor collection routine500shown inFIG. 5. In an alternative embodiment the major collection routine502and the minor collection routine500may be implemented as a single collection routine, with the collection routine having a collection type argument requesting a major or minor collection.

At step800, the collection routine500,502examines a pointer stored on the stack frame104or in one of the CPU's registers116and determines if the pointer points to a location in a page206in the heap102. If performing a minor collection, the minor collection routine500determines if the pointer points to a location in a page206in hot space200. If performing a major collection, the major collection routine502determines if the pointer points to a location in a page206in hot space200or cold space202in the heap102. If so, processing continues with step802. If not, processing continues with step804.

At step802, a pointer to the start of the page206is added to the scan queue524. The scan queue524includes a list of pointers to pages206in the heap106in which there is at least one referenced object. If the collector (a conservative collector)100executes in a system in which the compiler cannot distinguish whether the contents of the stack frame104are pointers or data, the collection routine500,502moves all the pages206pointed to by the stack frame104; that is, the root pages, to an unclaimable region in hot space200. A page206is moved by relabeling the space identifier302of the page206. Processing continues with step804.

At step804, the collection routine500,502determines if there is another pointer stored in the stack frame104or in one of the CPU's registers116to be examined. If so, processing repeats beginning with step800. If not, processing continues with step806.

At step806, the collection routine500,502examines the pages206stored in the scan queue524. The collection routine500,502examines objects in pages206reachable from a root page and objects reachable from reachable objects by performing a breadth-first search from the root pages. If the collection routine500,502finds a reachable object processing continues with step810. If not, processing continues with step812.

At step810, the collection routine500,502determines whether to move objects pointed to by pointers stored in the current object (the children of the current object) to a new page206. If performing a minor collection and the child is in hot space200, the minor collection routine502moves the reachable object to a newly allocated page206in hot space. If performing a major collection, the major collection routine500moves an object of the hot category and an object of the cold category to a newly allocated page206in cold space202. Processing continues with step812.

At step812, the collection routine500,502determines if there is another reachable object stored in the current active page. If so, processing continues (repeats) with step806. If not, processing continues with step814.

At step814, the collection routine500,502gets the pointer to the next page206in which to search from the scan queue524. Processing continues with step816.

At step816, the collection routine500,502determines if all the active pages in the scan queue524have been searched for reachable objects400. If so, the collection is complete. If not, processing continues with step806as described above.

FIG. 9Ais a block diagram showing objects400stored in hot space200in the heap102before a minor collection is performed by the minor collection routine500shown inFIG. 5. As shown inFIG. 9A, the hot space200includes four pages206a,206b,206cand206d. Three objects400a,400band400care stored in page206a, three objects400d,400eand400fare stored in page206band one object400gis stored in page206c.

Page206cincludes Page C free space906. Page C free space906is memory available in the page206cfor storing objects400. The current hot space pointer208stores the address of the first location in Page C free space906.

Page206aincludes two referenced objects400aand400b. Object400ais referenced by pointer900astored in the stack frame104or in a CPU register116and object400bis referenced by pointer900bstored in referenced object400a. Page206bincludes one referenced object400fwhich is referenced by pointer900cstored in object400e. Page206cincludes one referenced object400g. Object400gis referenced by pointer900dstored in referenced object400a.

Pointer900ato object400ain page206ais a member of the root set of pointers stored in the stack104(FIG. 1) or in one of the CPU registers116. Object400ais an active page because it is referenced by one of the root set of pointers and hence a pointer to page206ais stored on the scan queue524. A pointer to page206bor206cis not on the scan queue524because neither page206bor page206cis referenced by one of the root set of pointers.

After a pointer to active page206ahas been discovered, the pointer to page206ais added to the scan queue524, the minor collection routine500searches in the pages206referenced by pointers stored in the scan queue524for children of the objects400stored in the pages206. Object400ais a reachable object stored in page206abecause it is directly referenced by pointer900awhich is a member of the root set of pointers. Object400bin page206cis reachable because it is indirectly reachable through pointer900bwhich is stored in reachable object400a. Similarly, object400gis reachable because it is indirectly reachable through pointer900dwhich is stored in reachable object400a.

However, object400fstored in page206bis deemed not reachable, even though it is referenced by pointer990cstored in object400ebecause object400eis not directly or indirectly reachable by a pointer which is a member of the root set of pointers.

FIG. 9Bis a block diagram showing hot space200after a minor collection is performed by the minor collection routine500on the pages206a,206b,206cshown inFIG. 9B. Page206band206chave been reclaimed by the minor collection routine500and are available for allocation by the object allocation routine508.

FIG. 10is a block diagram of the heap102logically partitioned into hot space200and cold space202illustrating intergenerational pointers1000a,1000b. An intergenerational pointer is a pointer to an object in the other space. Intergenerational pointer1000ais a pointer from hot space200to cold space202and intergenerational pointer1000bis a pointer from cold space202to hot space200.

Object400pin page206ein hot space200includes intergenerational pointer1000ato object400min page206gin cold space202. Object400nin page206hin cold space202includes an intergenerational pointer1000bto object400kin page206fin hot space200. Machine code instructions to store the location of intergenerational pointers1000a,1000bare generated when a program108is compiled to generate machine code instructions. The set of machine code instructions to store the location are typically referred to as a write barrier. A compiler typically generates a write barrier for every pointer store.

The write barrier consumes program execution time and may not always be necessary. A write barrier is not necessary if it is a pointer from hot space200to cold space202. Thus, the garbage collector ignores all recorded pointers from hot space. For example, intergenerational pointer1000astored in object400pin hot space200points to object400min cold space202. Upon executing a minor collection in hot space, object400pis not reclaimed because it is referenced by an object stored in hot space200as follows: pointer900hstored in object400hstored in hot space200points to object400pand pointer900awhich is a member of the root set of pointers, points to400hstored in hot space200. Thus, intergenerational pointer1000afrom hot space200to cold space202is not required to perform a minor collection.

However, intergenerational pointer1000bfrom object400nstored in cold space202points to object400kstored in hot space200. Intergenerational pointer1000bis required so that the intergenerational pointer1000bcan be referenced in the minor collection and object400kwill not be reclaimed as an unreferenced object. Otherwise, upon executing a minor collection in hot space200, object400kwould be reclaimed because it is not directly referenced by any object in hot space200even though object400kis directly referenced by object400nin cold space202.

FIG. 11is a block diagram showing the components required to generate machine code instructions1108for a Java™ application1100in which write barriers may be eliminated. The Java™ application1100is architecturally neutral. The byte code file1104is hardware and operating system independent. In order to execute the Java™ application1100, a just in time compiler1106compiles the byte code1104into executable machine code instructions1108.

Java™ is a strongly typed language; that is, every variable must have a declared type. The type of an object can be easily determined. In Java™ primitive object types include char, boolean, int, short, long and byte. Primitive object types are not allocated in the heap102(FIG. 1). Non-primitive object types (reference types) are allocated in the heap102(FIG. 1). Non-primitive object types may be used to represent a string, title, backgroundcolor, link, document, form, anchor, image and web page. For example, a Webpage class object may include a Title, a Backgroundcolor and a Link to another Webpage object. A document class may include an Image, a Form and a Password.

As the just in time compiler1106is converting the byte code1104to machine code instructions1108, the just in time compiler1106adds write barriers for each intergenerational pointer1000a,1000bin the byte code1104.

FIG. 12Ais a flow chart illustrating a method for logically partitioning the heap102so as to reduce the number of intergenerational pointers between hot space200and cold space202. By reducing the number of intergenerational pointers, fewer write barriers are needed. Thus the write barriers that are no longer needed may be eliminated as described later in conjunction withFIG. 12B.

Even if the write barrier is not eliminated, the number of write barriers scanned is reduced by reducing the number of intergenerational pointers. Thus, the garbage collector100is faster because of this reduction in intergenerational pointers.

A 2×2 matrix M is provided, where M[i,j] is the approximate number of pointers between objects of type i and j. The matrix is computed when the sample and partition routine requests a major collection (step702inFIG. 7). When the major collection routine502encounters a pointer between an object of type i and j during step806(FIG. 8), M[i,j] is incremented. The sample and partition routine504considers several classes or object types at a time.

At step1208, the sample and partition routine504initializes the working set S to contain a single unplaced class or object type (i)(one not in hot space or cold space). Processing continues with step1210.

At step1210, the sample and partition routine504sets j=0. Processing continues with step1212.

At step1212, the sample and partition routine504checks if M[i,j] is above a pre-defined threshold for the class i in S. If so, processing continues with step1214. If not processing continues with step1216.

At step1214, class j is added to S. Processing continues with step1216.

At step1216, j is incremented. Processing continues with step1218.

At step1218, if j is the last class in the matrix processing continues with step1220. If not, processing continues with step1212.

At step1220, the net mortality rate of all the classes of the set S is considered. If this is high, processing continues with step1222. If not, processing continues with step1224.

At step1222, the classes in the working set are added to hot space. Processing continues with step1226.

At step1224, the classes in the working set are added to cold space. Processing continues with step1226.

At step1226, the sample and partition routine504determines of there if there is another unplaced class. If so, processing continues with step1208. If not, processing is complete.

This method avoids intergenerational pointers because classes whose instances are likely to point to one another are placed in the same space. In alternative embodiments, other data structures could be used for the matrix M, such as sparse graph representations. Also, step1220could be done in a variety of manners.

FIG. 12Bis a flow chart illustrating a method for eliminating write barriers from machine code instructions1108generated by the just in time compiler1106for a Java™ application program1106. The flow chart is described in conjunction withFIG. 5,FIG. 11,FIG. 13AandFIG. 13B.

At step1200, the write barrier elimination routine510(FIG. 5) examines the machine code instructions for a write barrier. A list of write barriers in the program are stored in a write barrier data structure (not shown).FIG. 13Aillustrates a set of compiled machine instructions1300stored in memory in the computer system. The set of compiled machine instructions1300include an add instruction1302, a load instruction1304and write barrier machine instructions1306a,1306band1306c. As shown inFIG. 13B, the write barrier machine instructions may include a shift instruction1306ato compute the location in which to store the pointer, a store instruction1306bto store the pointer in the computed location and a store instruction1306cto mark that the pointer is stored. An example of write barrier machine instructions follows:

stb zero, 0 (a2)where:register a0 stores the location in which to store the pointerregister a1 is the pointer to storeregister a2 is a scratch registerGC_CARD_SHIFT is an integer indicating the number of bits to shift

The write barrier machine instructions1306a,1306band1306care added by the just in time compiler1106upon detection of an intergenerational pointer.

At step1202, the write barrier elimination routine510determines the object category530of the object400in which the pointer is stored and the object category530of the object400to which the pointer is pointing. The write barrier elimination routine510determines the object category530for an object class by searching the object hot/cold category list506after it has been generated by the sample and partition routine504as described in conjunction withFIG. 5. If the pointer stored in a cold object points to a hot object, the write barrier is needed and processing continues with step1206. Otherwise, processing continues with step1204.

At step1204, the write barrier is for an intergenerational pointer from hot space200to cold space202, cold space202to cold space202or hot space200to hot space200and thus can be removed.FIG. 13Billustrates the compiled machine instructions1300stored in memory after the memory barrier machine instructions have been removed by the memory barrier elimination routine510shown inFIGS. 5 and 12B. As shown the memory barrier instructions1306aand1306care replaced by No Operation (“NOP”) machine code instructions. Thus, the memory barrier instructions1306aand1306bthat record the pointer store are removed. However, the pointer store instruction1306bis not removed. Unlike the memory barrier machine code instructions, NOP machine instructions do not reference memory and thus will typically execute faster than the memory barrier instructions that they replace because the execution of NOPs will never result in a cache miss.

Returning toFIG. 12Band continuing with step1204. After the memory barrier instructions have been replaced with NOP instructions as described in conjunction withFIG. 13, processing continues with step1206.

At step1206, the write barrier elimination routine510(FIG. 5) determines if all the machine code instructions1108have been examined. If so, processing is complete. If not, processing repeats beginning with step1200.

Thus, the collector100is adaptive because the decision as to which space200,202the object is to be placed in can be modified while the program108is executing. Furthermore, the same object type may be treated differently in different programs. For example, string may be cold in one program and hot in another program. Also, the collector100has better cache locality than a standard collector because same object category objects are stored together in the same area of the heap102. For example, in an application which sorts arrays of strings, the improved locality of the strings results in significant increase in performance. Also, by collecting in a smaller partition, pause times are reduced. To further decrease the execution time of the program108, a known cold object may be initially stored in the cold space202so that it never has to be copied from hot space200to cold space202.

FIG. 14is a block diagram of a computer system1400in which the present invention is used. Included in the computer system1400are at least one Central Processing Unit (“CPU”) module1408, a memory system1406and a system bus interface1410connected by a processor bus1412. The CPU module1408includes a processor (not shown). The system bus interface1410is further connected to an Input/Output (“I/O”) system1404by a system bus1414. An external storage device1416is connected to the I/O system1404. A collector100according to the principles of the present invention is stored in the storage device1416and also stored in the memory system1406. The collector100manages memory for executing programs stored in the memory system1406.

It will be apparent to those of ordinary skill in the art that methods involved in the present invention may be embodied in a computer program product that includes a computer usable medium. For example, such a computer usable medium may consist of a read only memory device, such as a CD ROM disk or conventional ROM devices, or a random access memory, such as a hard drive device or a computer diskette, having a computer readable program code stored thereon.