Free item distribution among multiple free lists during garbage collection for more efficient object allocation Number:7,149,866 from the United States Patent and Trademark Office (PTO) owispatent

Title: Free item distribution among multiple free lists during garbage collection for more efficient object allocation

Abstract: A method, system, and program for improving free item distribution among multiple free lists during garbage collection for more efficient object allocation are provided. A garbage collector predicts future allocation requirements and then distributes free items to multiple subpool free lists and a TLH free list during the sweep phase according to the future allocation requirements. The sizes of subpools and number of free items in subpools are predicted as the most likely to match future allocation requests. In particular, once a subpool free list is filled with the number of free items needed according to the future allocation requirements, any additional free items designated for the subpool free list can be divided into multiple TLH sized free items and placed on the TLH free list. Allocation threads are enabled to acquire free items from the TLH free list and to replenish a current TLH without acquiring heap lock.

Patent Number: 7,149,866 Issued on 12/12/2006 to Blandy

---

Inventors:	Blandy; Geoffrey Owen (Austin, TX)
Assignee:	International Business Machines Corporation (Armonk, NY)
Appl. No.:	10/862,151
Filed:	June 4, 2004

---

Current U.S. Class:	711/170 ; 707/206; 711/156; 711/165
Current International Class:	G06F 13/00 (20060101)
Field of Search:	707/206 711/156,165,170

---

References Cited [Referenced By]

---

U.S. Patent Documents

	6070173		May 2000		Huber et al.
	6148310		November 2000		Azagury et al.
	6173294		January 2001		Azagury et al.
	6226653		May 2001		Alpern et al.
	6289360		September 2001		Kolodner et al.
	6317756		November 2001		Kolodner et al.
	6393440		May 2002		Salant et al.
	6434575		August 2002		Berry et al.
	6457023		September 2002		Pinter et al.
	6470361		October 2002		Alpern et al.
	6490599		December 2002		Kolodner et al.
	6510440		January 2003		Alpern et al.
	7010555		March 2006		Blandy et al.
	2002/0055941		May 2002		Kolodner et al.
	2003/0009547		January 2003		Benfield et al.
	2003/0220952		November 2003		Borman et al.
	2005/0273567		December 2005		Blandy
	2005/0278487		December 2005		Blandy
	2006/0064564		March 2006		Achanta et al.

Foreign Patent Documents

	2 345 159		Jun., 2000		GB
	2 345 160		Jun., 2000		GB

Other References

Wilson, Paul R., "Uniprocessor Garbage Collection Techniques", pp. 1-66, 1994. cited by examiner . Dimpsey et al, "Java Server Performance: A case study of building efficient, scalable JVMs", IBM Systems Journal, vol. 39, No. 1, 2000, pp. 151-174. cited by other.

Primary Examiner: Elmore; Reba I.
Attorney, Agent or Firm: Dawkins; Marilyn S. Pattillo; Amy J.

---

Claims

---

What is claimed is:

1. A method for dynamically distributing free items for efficient allocation, comprising: responsive to detecting an end of a cycle, accumulating a recent allocation history of allocations of a plurality of free items from a plurality of different sized free lists maintained by a heap manager; predicting future allocation requirements for said heap manager from said recent allocation history and a prior allocation history; and dynamically adjusting at least one from among a number of said plurality of different sized free lists, a size minimum for each of said plurality of different sized free lists, and a number of entries needed in each of said plurality of different sized free lists to reflect said future allocation requirements, such that a next plurality of free items located during a sweep cycle are dynamically distributed to said plurality of different sized free lists for efficient future allocations.

2. The method according to claim 1 for dynamically distributing free items for efficient allocation, further comprising: sweeping a heap to locate said next plurality of free items; distributing said next plurality of free items among said plurality of different sized free lists according to said number of entries needed in each of said plurality of different sized free lists for best fit distribution; and responsive to a number of available free items for a particular sized free list from among said next plurality of free items exceeding a particular number of entries needed for said particular sized free list, dividing each additional free item into at least one free item of a thread-local heap size and placing each said additional free item on a thread-local heap free list, wherein an allocation thread is enabled to efficiently acquire a free item from said thread-local heap free list to replace an existing thread local heap without acquiring heap lock and wherein free items are allocated for efficient memory usage.

3. The method according to claim 1 for dynamically distributing free items for efficient allocation, wherein predicting future allocation requirements for said heap manager from said recent allocation history and a prior allocation history, further comprises: predicting a distribution of sizes among said different sized free lists wherein future requests will most likely match one of said sizes from among said different sized free lists.

4. The method according to claim 1 for dynamically distributing free items for efficient allocation, wherein accumulating a recent allocation history of allocations of a plurality of free items from a plurality of different sized free lists maintained by a heap manager further comprises: accumulating a plurality of hit counters maintained by each of a plurality of application threads, wherein each of said plurality hits counters identifies a number of hits for each existing sized subpool from among a plurality of existing subpools and a number of hits for each candidate sized subpool from among a plurality of candidate subpools.

5. The method according to claim 4 for dynamically distributing free items for efficient allocation, wherein predicting future allocation requirements for said heap manager from said recent allocation history and prior allocation history further comprises: removing each candidate subpool that has less than a threshold number of hits; adjusting said number of hits for said each existing sized subpool according to a previously predicted number of hits for said each existing sized subpool; and adding any remaining candidate subpools from among said plurality of candidate subpools to a list of subpools currently comprising said plurality of existing subpools, wherein said list of subpools is a prediction of future allocation requirements.

6. The method according to claim 4 for dynamically distributing free items for efficient allocation, wherein predicting future allocation requirements for said heap manager from said recent allocation history and prior allocation history further comprises: comparing a total number of bytes allocated in a recent cycle with a total amount of free space available at the beginning of said recent cycle; and responsive to said total number of bytes exceeding a threshold amount of said total amount of free space available, calculating a ratio for adjusting a predicted number of free items needed for each of a plurality of existing subpools and a plurality of candidate subpools.

7. The method according to claim 1 for dynamically distributing free items for efficient allocation, wherein said heap manager is a Java Virtual Machine.

8. A system for dynamically distributing free items for efficient allocation, comprising: means, responsive to detecting an end of a cycle, for accumulating a recent allocation history of allocations of a plurality of free items from a plurality of different sized free lists maintained by a heap manager; means for predicting future allocation requirements for said heap manager from said recent allocation history and a prior allocation history; and means for dynamically adjusting at least one from among a number of said plurality of different sized free lists, a size minimum for each of said plurality of different sized free lists, and a number of entries needed in each of said plurality of different sized free lists to reflect said future allocation requirements.

9. The system according to claim 8 for dynamically distributing free items for efficient allocation, further comprising: means for sweeping a heap to locate said next plurality of free items; means for distributing said next plurality of free items among said plurality of different sized free lists according to said number of entries needed in each of said plurality of different sized free lists for best fit distribution; and means, responsive to a number of available free items for a particular sized free list from among said next plurality of free items exceeding a particular number of entries needed for said particular sized free list, for dividing each additional free item into at least one free item of a thread-local heap size and placing each said additional free item on a thread-local heap free list, wherein an allocation thread is enabled to efficiently acquire a free item from said thread-local heap free list to replace an existing thread local heap without acquiring heap lock and wherein free items are allocated for efficient memory usage.

10. The system according to claim 8 for dynamically distributing free items for efficient allocation, wherein said means for predicting future allocation requirements for said heap manager from said recent allocation history and a prior allocation history, further comprises: means for predicting a distribution of sizes among said different sized free lists wherein future requests will most likely match one of said sizes from among said different sized free lists.

11. The system according to claim 8 for dynamically distributing free items for efficient allocation, wherein accumulating a recent allocation history of allocations of a plurality of free items from a plurality of different sized free lists maintained by a heap manager further comprises: accumulating a plurality of hit counters maintained by each of a plurality of application threads, wherein each of said plurality hits counters identifies a number of hits for each existing sized subpool from among a plurality of existing subpools and a number of hits for each candidate sized subpool from among a plurality of candidate subpools.

12. The system according to claim 11 for dynamically distributing free items for efficient allocation, wherein said means for predicting future allocation requirements for said heap manager from said recent allocation history and prior allocation history further comprises: means for removing each candidate subpool that has less than a threshold number of hits; means for adjusting said number of hits for said each existing sized subpool according to a previously predicted number of hits for said each existing sized subpool; and means for adding any remaining candidate subpools from among said plurality of candidate subpools to a list of subpools currently comprising said plurality of existing subpools, wherein said list of subpools is a prediction of future allocation requirements.

13. The system according to claim 11 for dynamically distributing free items for efficient allocation, wherein said means for predicting future allocation requirements for said heap manager from said recent allocation history and prior allocation history further comprises: means for comparing a total number of bytes allocated in a recent cycle with a total amount of free space available at the beginning of said recent cycle; and means, responsive to said total number of bytes exceeding a threshold amount of said total amount of free space available, for calculating a ratio for adjusting a predicted number of free items needed for each of a plurality of existing subpools and a plurality of candidate subpools.

14. The system according to claim 8 for dynamically distributing free items for efficient allocation, wherein said heap manager is a Java Virtual Machine.

15. A computer program product, residing on a computer readable volatile or non-volatile medium, for dynamically distributing free items for efficient allocation, said computer program product comprising: means, responsive to detecting an end of a cycle, for accumulating a recent allocation history of allocations of a plurality of free items from a plurality of different sized free lists maintained by a heap manager; means for predicting future allocation requirements for said heap manager from said recent allocation history and a prior allocation history; and means for dynamically adjusting at least one from among a number of said plurality of different sized free lists, a size minimum for each of said plurality of different sized free lists, and a number of entries needed in each of said plurality of different sized free lists to reflect said future allocation requirements.

16. The computer program product according to claim 15 for dynamically distributing free items for efficient allocation, further comprising: means for sweeping a heap to locate said next plurality of free items; means for distributing said next plurality of free items among said plurality of different sized free lists according to said number of entries needed in each of said plurality of different sized free lists for best fit distribution; and means, responsive to a number of available free items for a particular sized free list from among said next plurality of free items exceeding a particular number of entries needed for said particular sized free list, for dividing each additional free item into at least one free item of a thread-local heap size and placing each said additional free item on a thread-local heap free list, wherein an allocation thread is enabled to efficiently acquire a free item from said thread-local heap free list to replace an existing thread local heap without acquiring heap lock and wherein free items are allocated for efficient memory usage.

17. The computer program product according to claim 15 for dynamically distributing free items for efficient allocation, wherein said means for predicting future allocation requirements for said heap manager from said recent allocation history and a prior allocation history, further comprises: means for predicting a distribution of sizes among said different sized free lists wherein future requests will most likely match one of said sizes from among said different sized free lists.

18. The computer program product according to claim 15 for dynamically distributing free items for efficient allocation, wherein accumulating a recent allocation history of allocations of a plurality of free items from a plurality of different sized free lists maintained by a heap manager further comprises: accumulating a plurality of hit counters maintained by each of a plurality of application threads, wherein each of said plurality hits counters identifies a number of hits for each existing sized subpool from among a plurality of existing subpools and a number of hits for each candidate sized subpool from among a plurality of candidate subpools.

19. The computer program product according to claim 18 for dynamically distributing free items for efficient allocation, wherein said means for predicting future allocation requirements for said heap manager from said recent allocation history and prior allocation history further comprises: means for removing each candidate subpool that has less than a threshold number of hits; means for adjusting said number of hits for said each existing sized subpool according to a previously predicted number of hits for said each existing sized subpool; and means for adding any remaining candidate subpools from among said plurality of candidate subpools to a list of subpools currently comprising said plurality of existing subpools, wherein said list of subpools is a prediction of future allocation requirements.

20. The computer program product according to claim 18 for dynamically distributing free items for efficient allocation, wherein said means for predicting future allocation requirements for said heap manager from said recent allocation history and prior allocation history further comprises: means for comparing a total number of bytes allocated in a recent cycle with a total amount of free space available at the beginning of said recent cycle; and means, responsive to said total number of bytes exceeding a threshold amount of said total amount of free space available, for calculating a ratio for adjusting a predicted number of free items needed for each of a plurality of existing subpools and a plurality of candidate subpools.

---

Description

---

CROSS-REFERENCE TO RELATED APPLICATION

The present application is related to the following co-pending application:

(1) U.S. patent application Ser. No. 10/862,137.

BACKGROUND OF THE INVENTION

1. Technical Field

The present invention relates in general to improved heap management and in particular to improved efficiency of heap management by a virtual manager in a multiprocessor system. Still more particularly, the present invention relates to improved free item distribution among multiple free lists during garbage collection to improve memory usage and to increase the frequency of allocations from thread-local heaps.

2. Description of the Related Art

Software systems, such as the Java Virtual Machine (JVM) that employ garbage collection, typically provide an explicit call for allocating objects, but no explicit call for freeing objects. Instead, in a system that employs garbage collection, when available storage on a heap is exhausted, an allocation failure occurs, operations are suspended, and garbage collection is invoked to replenish the free storage.

In one example, the JVM employs a mark and sweep phases during garbage collection to replenish the free storage. During a mark phase, items that are still referenced are located and marked. Then, during the sweep phase, free space of sufficient size is located and added as free items to a free list. Free items that are not large enough to be added to the free list are discarded. A free list may include a linked list of freed items, for example, with a pointer to the first item in the list held in global memory.

In addition, during garbage collection, compaction may occur. Compaction, in general, requires adjusting the position of objects within the heap to reduce fragmentation and attempt to make larger free items available. A forced compaction may occur if the sweep phase completes without finding a sufficiently large free item for the allocation request.

When an allocation request is received, a heap lock is acquired and the free list is scanned to locate a free item of sufficient size to meet the allocation request. If a free item of sufficient size is available on the list, it is popped from the list so that the new object can be allocated at the free item location. If a free item of sufficient size is not available, then garbage collection is initiated again to replenish the free list.

Because the heap lock is an exclusive lock and is acquired to search a free list, it is important that free items are efficiently located and popped from the list during allocation and, in particular, that the free list can be efficiently scanned to determine if a free item is available. In addition, because garbage collection is time consuming, it is important that larger items are not prematurely popped from the free list such that premature garbage collection is initiated. In particular, a premature garbage collection may occur if an allocation failure occurs and there is a large amount of free storage available, but no single free item large enough to satisfy the allocation request.

In an attempt to reduce the chance of premature garbage collection and reduce free list scanning time, some JVM's implement a large object area (LOA) or other large object protection area within the heap, where the LOA includes objects that are greater than a large object size threshold. Objects within the LOA are typically not allocated unless the requested allocation size is larger than the large object size threshold in an attempt to reduce premature garbage collection when large object requests are received.

In addition, in an attempt to increase the efficiency of searching for a free item, some JVM's implement multiple free lists, where each free list holds free items of a particular size. A vector maintains the list of sizes, wherein the list of sizes is scanned to locate a particular sized free list and then that sized free list is scanned for a free item of sufficient size for the allocation request, rather than requiring a scan of each item of a free list. While multiple free lists organized by a searchable vector reduce the number of free items that must be searched, searching a free list requires acquiring a heap lock.

Further, in an attempt to increase the efficiency of allocations of smaller objects, thread-local heaps (TLHs) may be implemented. In one example, a TLH is a cache buffer that has been previously reserved for use by a single thread. TLHs are advantageous because objects can be allocated directly to a TLH without the thread grabbing a heap lock. Furthermore, TLH's typically employ simple and fast allocation schemes, such as pointer bumping. Thus, it is advantageous to allocate as often as possible from the TLH, rather than searching from general free lists.

While allocating from a TLH is most efficient for smaller objects, when the current TLH does not have sufficient space to satisfy an allocation request, but the allocation request is within the size boundaries of a TLH, the heap lock must still be acquired to search the free list for a free item of sufficient size. The current TLH is replaced by a free item popped from a general free list. In addition, if an allocation request size exceeds the size boundaries of a TLH, the heap lock must still be acquired and the free lists must be searched to find a free item large enough to satisfy the request size. Thus, while implementing TLHs may improve efficiency of allocations when the requested allocation fits within the current TLH, current object allocation is still limited when the current TLH does not satisfy the allocation request.

Another issue arises in TLH allocation because the majority of requests for free items from the heap manager become requests for TLH replenishments. As a result, the free lists with smaller free items that are also large enough for TLH allocation will quickly be depleted, leading to premature garbage collection as larger items are carved up to meet normal smaller object allocation requests. One solution to the smaller free item depletion problem has been to increase the size of TLH's, however merely increasing the size only adjusts the low value of the range of free list sizes that are most quickly depleted by TLH requests, still leading to premature garbage collection/when other allocation requests within the TLH size range are received.

Therefore, in view of the foregoing, there is a need for a method, system, and program for improving free item distribution among free lists to avoid premature depletion from TLH requests by using recent allocation history to predict future allocation requirements and distributing free items among free lists to meet the predicted future allocation requirements. In addition, to increase the efficiency of object allocation, there is a need for a method, system, and program for avoiding the acquisition of heap lock and in particular avoiding the acquisition of heap lock during TLH replenishment.

SUMMARY OF THE INVENTION

Therefore an improved method, system, and program provide improved heap management and in particular provide improved efficiency of heap management by a virtual manager in a multiprocessor system. Still more particularly, an improved method, system, and program provide improved free item distribution among multiple free lists during garbage collection to increase the frequency of allocations from thread-local heaps and improve memory usage.

According to one embodiment, a heap manager includes a TLH free list and multiple subpool free lists that are quickly searchable through a vector of subpool sizes. The TLH free list is accessible to all the application threads for replenishing TLH's. In particular, application threads need not acquire the heap lock, but only need to ensure that garbage collection is blocked, when searching the TLH free list for a free item to replenish the thread's TLH. Advantageously, the TLH free list is filled such that TLH's are replenished most often from the TLH free list. However, if the TLH free list is empty, then the thread may acquire the heap lock and search a size vector identifying the sizes of multiple subpool free lists to efficiently locate a free item of sufficient size for TLH replenishment.

According to another embodiment, a garbage collector predicts future allocation requirements and then distributes free items to the multiple subpool free lists and TLH free list during the sweep phase according to the future allocation requirements. Advantageously, free items are distributed among free lists, the sizes of which are predicted to most likely match the sizes of future allocation requests. Advantageously, once a subpool free list is filled with the number of free items needed based on the future allocation requirements, any additional free items designated for the subpool free list can be divided into multiple TLH sized free items and placed on the TLH free list. In particular, to minimize fragmentation and increase the average TLH size, subpool free lists are filled with the best fitting free items and larger items tend to be assigned to the TLH free list.

Responsive to detecting an end of a cycle, a recent allocation history of the allocations from the multiple subpool free lists is accumulated from multiple allocation threads. Future allocation requirements are then predicted from the recent allocation history and a prior allocation history. Then, the number of free lists, the size associated with each free list and the number of entries need in each free list are dynamically adjusted to reflect the future allocation requirements for efficient memory usage.

Accumulating the recent allocation history includes accumulating multiple hit counters, where each hit counter identifies a number of hits for each existing subpool and a number of hits for candidate subpools. Any candidate subpool with less than a threshold number of hits is discarded. Then, the existing subpool list is combined with the candidate subpool list to predict the needed sizes of free lists. If too many sizes are in the combined list, then the subpools with the least number of hits are discarded.

The total number of hits accumulated for each subpool size may be used as the prediction of future allocation requirements, and in particular may be smoothed to reflect prior allocation history. In particular, accumulating recent allocation history also includes accumulating the total number of bytes allocated since the last cycle. If the total number of bytes allocated since the last cycle less the total free space previously available exceeds a threshold, then a ratio is calculated and the total number of hits for each subpool size are adjusted by the ratio. Further, the current total number of hits for an existing subpool may be smoothed by averaging the current total number of hits with a previous smoothed number of hits for the existing subpool.

BRIEF DESCRIPTION OF THE DRAWINGS

The novel features believed characteristic of the invention are set forth in the appended claims. The invention itself however, as well as a preferred mode of use, further objects and advantages thereof, will best be understood by reference to the following detailed description of an illustrative embodiment when read in conjunction with the accompanying drawings, wherein:

FIG. 1 is a block diagram depicting one embodiment of the hardware and software implemented in a computer system through which the present method, system, and program may be implemented

FIG. 2 is a block diagram depicting the memory management and allocation within a JVM in accordance with the method, system, and program of the present invention

FIG. 3 is a block diagram depicting multiple free lists from which efficient object allocation may be performed in accordance with the method, system, and program of the present invention;

FIG. 4 is a block diagram depicting the information tracked to enable prediction of future allocation requirements and distribute free items according to the future allocation requirements in accordance with method, system, and program of the present invention

FIG. 5 is a block diagram of the processes controlled by the heap manager in accordance with the method, system, and program of the present invention;

FIG. 6 is a high level logic flowchart depicting a process and program for controlling heap allocation in a JVM in accordance with the method, system, and program of the present invention;

FIG. 7 is a high level logic flowchart of a process and program for determining whether free space is available in the heap responsive to a pools search initiation for object allocation in accordance with the method, system, and program of the present invention;

FIG. 8 is a high level logic flowchart depicting a process and program for controlling TLH replenishment in accordance with the method, system, and program of the present invention.

FIG. 9 is a high level logic flowchart depicting a process and program for counting the requested sizes of object allocations in accordance with the method, system, and program of the present invention;

FIG. 10 is a high level logic flowchart depicting a process and program for predicting future allocation requirements and dynamically adjusting distribution requirements at the start of garbage collection in accordance with the method, system, and program of the present invention;

FIG. 11 is a high level logic flowchart depicting a process and program for controlling each helper thread during the sweep process in accordance with the method, system, and program of the present invention; and

FIG. 12 is a high level logic flowchart of a process and program for controlling the distribution of free items by the main thread during the sweep process in accordance with the method, system, and program of the present invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

Referring now to the drawings and in particular to FIG. 1, there is depicted one embodiment of the hardware and software implemented in a computer system through which the present method, system, and program may be implemented. The present invention may be executed in a variety of systems, including a variety of computing systems and electronic devices.

Computer system 100 generally includes a bus 122 or other communication device for communicating information within computer system 100, and at least one processing device, such as processor 112a, coupled to bus 122 for processing information. Bus 122 preferably includes low-latency and higher latency paths that are connected by bridges and adapters and controlled within computer system 100 by multiple bus controllers. When implemented as a server system, computer system 100 typically includes multiple processors, such as processors 112a 112n that operate in parallel to improve network servicing power.

Processors 112a 112n may be general-purpose or specified purpose processors that, during normal operation, operate under the control of one or more of a number of different operating systems, such as operating system 142, and execute various computer software applications, programs, objects, modules and other processes from a memory 114. Although not depicted, memory 114 may include dynamic storage such as random access memory (RAM) and static storage such as Read Only Memory (ROM). In addition, although not depicted, each of processors 112a 112n may include levels of cache and registers local to a central processing unit.

In one embodiment, a Java Virtual Machine (JVM) 140 is loaded in memory on top of operating system 132. JVM 140 appears as an application to (native) operating system 142, but in fact functions as a virtual operating system, supporting Java applications. In particular, Java applications are preferably portable applications that when run by JVM 140, can run on any platform, regardless of operating system or hardware specifications. Although not depicted, JVM 140 compiles byte code from Java applications and a Java interpreter converts the byte code into instructions understandable by operating system 142. The components of JVM 140 may be incorporated into a standalone application, a part of an operating system, or a part of a larger application, such as a browser application or middleware. In an alternate embodiment, JVM 140 and any of the components of JVM 140 may, at different times, be resident in whole or in part in any of memory 114, mass storage device 118, network 102, or within registers or cache of processors 112a 112n or other processor registers and cache.

In one embodiment, operating system software or JVM 140 contains machine executable instructions that when executed on processor 112 carry out the operations depicted in the flowchart of FIGS. 6 13, and other operations described herein. Alternatively, the steps of the present invention might be performed by specific hardware components that contain hardwired logic for performing the steps, or by any combination of programmed computer components and custom hardware components.

The present invention may be provided as a computer program product, included on a machine-readable medium having stored thereon the machine executable instructions used to program computer system 100 to perform a process according to the present invention. The term "machine-readable medium" as used herein includes any medium that participates in providing instructions to processors 112a 112n or other components of computer system 100 for execution. Such a medium may take many forms including, but not limited to, non-volatile media, volatile media, and transmission media. Common forms of non-volatile media include, for example, a floppy disk, a flexible disk, a hard disk, magnetic tape or any other magnetic medium, a compact disc ROM (CD-ROM) or any other optical medium, punch cards or any other physical medium with patterns of holes, a programmable ROM (PROM), an erasable PROM (EPROM), electrically EPROM (EEPROM), a flash memory, any other memory chip or cartridge, or any other medium from which computer system 100 can read and which is suitable for storing instructions. In the present embodiment, an example of a non-volatile medium is mass storage device 118 which as depicted is an internal component of computer system 100, but will be understood to also be provided by an external device. Volatile media include dynamic memory such as RAM. Transmission media include coaxial cables, copper wire or fiber optics, including the wires that comprise bus 122. Transmission media can also take the form of acoustic or light waves, such as those generated during radio frequency or infrared data communications.

Moreover, the present invention may be downloaded as a computer program product, wherein the program instructions may be transferred from a remote system, such as a server 136, to requesting computer system 100 by way of data signals embodied in a carrier wave or other propagation medium via a network link 134 (e.g. a modem or network connection) to a communications interface 132 coupled to bus 122. Communications interface 132 provides a data communications coupling to network link 134 that may be connected, for example, to a local area network (LAN), wide area network (WAN), or directly to an Internet Service Provider (ISP). In particular, network link 134 may provide wired and/or wireless network communications to one or more networks.

Network link 134 in turn provides data communication services through network 102. Network 102 may refer to the worldwide collection of networks and gateways that use a particular protocol, such as Transmission Control Protocol (TCP) and Internet Protocol (IP), to communicate with one another. Network link 134 and network 102 both use electrical, electromagnetic, or optical signals that carry digital data streams. The signals through the various networks and the signals on network link 134 and through communication interface 132, which carry the digital data to and from computer system 100, are exemplary forms of carrier waves transporting the information.

In addition to server 136, any number of computers and other devices may be networked through network 102. Further, operating system 142, JVM 140, and various applications, programs, objects, modules and other processes may execute on one or more processors in server 136 and other computer systems accessible via network 102 in a distributed environment. In particular, when implemented as a server system, computer system 100 typically includes multiple communication interfaces accessible via multiple peripheral component interconnect (PCI) bus bridges connected to an input/output controller. In this manner, computer system 100 allows connections to multiple networked accessible computers.

In addition, computer system 100 typically includes multiple peripheral components that facilitate communication. These peripheral components are connected to multiple controllers, adapters, and expansion slots coupled to one of the multiple levels of bus 122 and herein referred to by I/O interface 130.

Those of ordinary skill in the art will appreciate that the hardware depicted in FIG. 1 may vary and can be implemented within multiple types of systems. For example, computer 100 can be a standard computer or server, but can also be an embedded system, such as a set top box, handheld device, or any other hardware device including a processor and JVM 140. Furthermore, those of ordinary skill in the art will appreciate that the depicted example is not meant to imply architectural limitations with respect to the present invention.

With reference now to FIG. 2, a block diagram depicts a block diagram of the memory management and allocation within a JVM in accordance with the method, system, and program of the present invention. As depicted, JVM 140 includes a memory management controller 202, in addition to interpreters, controllers, and other components not depicted, but typically implemented within a JVM.

Initially, memory management controller 202 requests memory space 210 from the operating system for storing objects and data for a Java application. In the embodiment depicted, memory management controller 202 is a component of JVM 140, however it will be understood that memory management controller 202 may be located within other software systems. Further, it will be understood that memory management controller 202 may include processes that can be invoked by application threads and may also invoke threads to perform memory management processes.

In one embodiment, memory space 210 includes is a contiguous block of memory, called the heap. Same sized blocks of heap 220 are represented by bits in an independent bit vector 224. For example, 8-byte blocks of heap 220 may each be represented by a bit in independent bit vector 224.

In this example of a multiprocessor system, heap 220 is assigned among multiple sections 212a 212n. Each of sections 212a 212n is represented by a data structure that including section identifiers 218a 218n that identify the portions of heap 220 and bit vector 224 assigned to each section. In addition, the data structures representing each of sections 212a 212n include prefix and suffix fields 216a 216n that identify the number of consecutive zero bits at the beginning and end of a section. The prefix field that identifies the number of consecutive zero bits at the beginning of a section and the suffix field identifies the amount of free space at the end of a section or if there is no free space, the number of bytes a marked object projects into subsequent sections.

Memory management controller 202 includes an object allocator 204 and a garbage collector 206. Object allocator 204 provides invocable processes for enabling the allocation of free space of heap 220 to objects needed for execution of a Java application. Garbage collector 206 controls the deletion of objects from heap 220 when those objects are no longer required. In particular, an advantage of the Java programming language is that Java applications do not need to specifically control the allocation or deallocation of memory, rather the allocation and deallocation of memory is controlled by JVM 200.

When an allocation request is received from an application thread, a storage subsystem data structure 222 is searched for a free item of sufficient size to meet the allocation request. As will be described in detail in FIG. 3, storage subsystem data structure 222 may include multiple free lists, including a TLH free list, subpool free lists, and an LOA free list. According to an advantage of the invention, as free items are allocated, each application thread records information about each allocation. If a free item of sufficient size to meet the allocation request cannot be located, then an allocation failure occurs and garbage collector 206 is invoked.

According to an advantage of the invention, when garbage collector 206 is invoked, garbage collector 206 initially accumulates the recent allocation history from each of the application threads into multiple counters and arrays within global data structures 232. Based on the recent allocation history and prior allocation requirements, future allocation predictions are made and a preferred distribution of free lists and the number of items needed for each free list are adjusted based on the future allocation predictions.

Garbage collector 206 may perform garbage collection using mark and sweep phases, for example. During a mark phase, objects that are still actively referenced in heap 220 are identified and the bit in a bit vector 224 that corresponds to the first byte of each referenced object is marked.

Next, during garbage collection, in a phase commonly referred to as the "sweep phase", sufficient helper threads are initiated to use all of the available processors. Each of the helper threads initializes a data structure within helper thread data structures 230. As will be described in more detail with reference to FIG. 4, each helper thread data structure includes a set of queues for each subpool and counters and a TLH queue and counter. Each of the helper threads may perform an atomic operation to acquire the next unprocessed section from among sections 212a 212n and efficiently identify free space. In particular, in one example, also described in U.S. patent application Ser. No. 10/862,137 each helper thread scans the portion of the bit array assigned to a section to locate the first marked bit. If no marked bit is found, then the prefix value is set to the number of bits in the portion of the bit array and the next section, if any, is acquired. If a marked bit is found, the number of preceding zero bits is stored in the prefix field of the section data structure. The helper thread counter is reset and incremented for each zero in a consecutive sequence following the marked bit. If the counter value exceeds a threshold, then the size of the marked object is fetched and the size indicated by the counter bits is subtracted from the size of the marked object. If the marked object size exceeds the size indicated by the counter bits, then the remainder of the bits representing the marked object are skipped and any consecutive sequence of zero bits following the marked object bits are counted. Advantageously, by fetching the size of a marked object once the marked object represents the size of a potentially free item, not all the bits of a larger marked object need be scanned.

Once the end of the section or a marked bit is detected, if a consecutive sequence of zero bits exceeds a threshold, then the sequence of zero bits is considered a free item and the helper thread determines which of the subpool queues or TLH queue on which the free item should be placed. Further, in particular, when the end of the section is reached, the size indicated by the current counter is subtracted from last marked object size and the value is stored in the suffix field of the section's data structure. In one example, the suffix value will be a zero if the object ends at the boundary, negative if the object extends beyond the boundary, or positive if there is free storage at the end of the section.

Once all the helper threads complete the sweep of sections 212a 212n, garbage collector 206 acquires a lock on execution by any other Java processes and executes a single thread. The single thread collects all the free items stored in helper thread data structures 230 and distributes the free items among the free lists in storage subsystem data structure 222. In addition, the single thread collects all the prefix/suffix values 216a 216n and identifies free items of sufficient size that overlap sections for placement in one of the free lists in storage subsystem data structure 222. In one example, free items are distributed among the free lists in storage subsystem data structure 222 according to the preferred distribution determined by garbage collector 206 at the onset of garbage collection, however, the distribution may be adjusted to reflect the actual sizes of free items found during garbage collection

Referring now to FIG. 3, there is depicted a block diagram of multiple free lists from which efficient object allocation may be performed in accordance with the method, system, and program of the present invention. As illustrated, multiple free lists are managed within storage subsystem data structure 222. In the example, the free lists include an LOA free list 316, subpool free lists 312a 312n, and a TLH free list 310.

In one embodiment, TLH free list 310 references free items within heap 220 that range in size from a minimum TLH size to a maximum TLH size. Free items in TLH free list 310 may be popped from TLH free list 310 and used to replenish TLHs used by different application threads. In particular, each application thread implements one of thread data structures 322a 322n within a thread subsystem 320. Thread data structures 322a 322n respectively include TLH pointers 324a 324n. The TLH pointers for each thread data structure include pointers to the location of a TLH allocated to the thread data structures. For example, TLH pointers 324a point to a space indicated by TLH 302a in heap 300 and TLH pointers 324n point to a space indicated by TLH 302n in heap 300. Thus, when a free item is popped from TLH free list 310 and used to replenish a TLH for a thread data structure, the TLH pointers for the data structures are reset to the address of the free item within heap 220. It is important to note that allocations by threads to TLHs are fast because a thread need not acquire heap lock, but rather the thread allocates from the thread's TLH and adjusts the TLH pointers to indicate the space remaining on the thread's TLH.

It is important to note that advantageously, any of thread data structures 322a 322n can access TLH free list 310 and replenish a TLH using an atomic operation, and thus are not required to acquire heap lock for TLH replenishment from TLH free list 310. However, an application thread may be required to acquire a share of a delayGC lock when acquiring a free item to replenish a TLH from TLH free list 310. The delayGC lock is a shared lock that, when held, postpones stop-the-word garbage collection. In addition to the delayGC lock, other techniques may also be employed to insure that garbage collection does not occur while a thread is acquiring a TLH from TLH free list 310.

In addition, in one embodiment, LOA free list 316 includes free items from within the range of storage designated for LOA 304. In particular, when implemented, LOA 304 is a dedicated storage area for objects that exceed a large object size. In one example, free items from LOA free list 316 can only be allocated to if the requested size exceeds to the large object size, however, LOA free list items may be divided to avoid a premature garbage collection or forced compaction. LOA 304 and LOA free list 316 may be allocated or deallocated as needed for efficient free item distribution to avoid premature garbage collection or forced compaction.

Further, in one embodiment, subpool free lists 312a 312n each represent pools of free items of a range of sizes. In one embodiment, free items placed on a particular subpool free list are at least as large as the indexed size, but less than the next larger indexed size. In addition, items placed in the last subpool may contain free items as large as the maximum object size for the heap.

To improve the efficiency of locating a free item of sufficient size in subpool free lists 312a 312n, a size vector 314 can be searched for the first size as large as the requested size. In particular, size vector 314 indexes the minimum sizes of subpool free lists 312a 312n.

According to one advantage, although depicted within storage subsystem data structure 222, size vector 314 may be redundantly maintained in the cache of each processor of a system or in other quickly accessible memory locations. In particular, the sizes in size vector 314 are typically only changed during garbage collection, but are referenced often during allocation and thus can be shared across multiple processor caches.

In one example, application threads first determine whether a requested allocation can be satisfied within the thread's TLH. If sufficient space is not available within the thread's TLH and the requested size is smaller than a maximum TLH size (maxTLHSize), then an attempt is made to pop an item from TLH free list 310. If the attempt succeeds, then the free item is used to replenish the TLH pointed to by the thread's data structure.

In the example, if, however, TLH free list 310 is searched and found empty, then a heap lock may be acquired and a free item from one of subpool free lists 312a 312n located to replenish the thread's TLH. In particular, when a search of size vector 314 is initiated for a TLH replenishment, the search may start at the position in size vector 314 pointed to by TLHStealPool and only search the smaller sized subpools, as marked by the boundary of minTLHStealPool, if the TLH replenishment request cannot be met by one of the larger subpools. In particular, by controlling the boundaries of TLH replenishment by the TLHStealPool and minTLHStealPool values, a policy is implemented requiring TLH replenishment first from larger subpools and then by smaller subpools only when larger subpools are exhausted. As a result, TLH replenishment does not deplete all the smaller subpools first and thus avoids premature garbage collection. In addition, by setting minTLHStealPool to a subpool size that is at least as large as the TLH size, only those subpools with free items of sufficient size to be a TLH are accessed.

In addition, in the example, if the allocation request size is larger than a maximum TLH size, then a heap lock is acquired and the allocation is satisfied from one of subpool free lists 312a 312n or garbage collection is initiated. First, size vector 314 is scanned looking for the first size that is at least as large as the allocation requested size. If a size at least as large as the requested size is located, the size is set as the original target pool. If the original target pool is not empty, then the first item is popped from the list and used to satisfy the request. If the original target pool is empty, then subsequent pools indicated in size vector 314 are scanned to determine if any are not empty. If the subsequent pools are all empty and the requested size is smaller than the target pool, the pool preceding the target pool may be searched for a free item of sufficient size to satisfy the request.

Further, if a TLH cannot satisfy the allocation request, the request size is at least the size of the minimum LOA object size, and no free item is available from the subpool free lists, then LOA free list 316 may be searched. In one embodiment, LOA is an optional reserve area of the heap that is advantageously used to allocate large objects, thereby reducing the possibility of fragmentation among large items. In particular, in one embodiment, since the largest subpool may include items as large as the minimum LOA object size, the LOA is effectively only accessed when the largest subpool is empty.

In general, whenever a free item of sufficient size is located from subpool free lists 312a 312n, the requested size is subtracted from the free item size and if the remaining size is at least as large as the smallest subpool size, the remainder is placed on the appropriate subpool from among subpool free lists 312a 312n. Otherwise, the remainder is discarded.

According to an advantage, bookkeeping may be performed in conjunction with object allocation to provide recent allocation history that can be used to predict future allocation requirements during the next garbage collection cycle. In particular, as will be further described with reference to FIG. 4, each application thread may maintain counters 326a 326n that are updated during object allocation and TLH replenishment.

With reference now to FIG. 4, there is depicted a block diagram of the information tracked to enable prediction of future allocation requirements and distribute free items according to the future allocation requirements in accordance with method, system, and program of the present invention. During the allocation process, different application threads may search for free items to allocate to a new object. As described with reference to FIG. 3, each application thread creates and maintains an independent local data structure within thread subsystem 320. In the example depicted in FIG. 4, counters 404 of a thread data structure 402 are amplified. In particular, Counters 404 may include multiple types of counters including, but not limited to, subpool hit counters 410, candidate hit counters 412, a TLH allocation counter 412, and heap allocation counter 416.

TABLE-US-00001 TABLE 1 Hit Counter for Subpool Allocations Subpool Potential Sizes Hits Candidates Hits 8 5 12 1 16 2 24 3 48 10 64 30

Table 1 illustrates one example of how a thread tracks allocations in subpool hit counters 410 and candidate hit counters 412 for bookkeeping. In the example, if the requested size exactly matches the target pool size, then that pool's thread local hit counter is incremented. For example, if the requested size is 8, then the counter corresponding to the subpool size of 8 is incremented from 5 hits to 6 hits. Otherwise, if the requested size does not exactly match the target pool size, then the requested size becomes a candidate for a future subpool. If the requested size is already included in the list of potential candidate sizes, then the hit counter for the matching potential candidate size is incremented; otherwise, if there is sufficient room in the list a new candidate size is added and the hit counter for the new candidate size is set to 1. For example, if the requested size is 12, then the counter corresponding to the candidate size of 12 is incremented from 1 hit to 2 hits; if the requested size is 52, then a potential candidate size of 52 is added to the potential candidate sizes list and the counter corresponding to potential candidate 52 is set to 1 hit.

At the start of garbage collection, the local counters from each thread's data structure, such as local counters 404, are accumulated into corresponding global counters 432. Next, a free list distribution process begins that may dynamically adjust the number and sizes of subpool free lists listed and the TLHStealPool field 450 and minTLHStealPool field 452 based on recent allocation history.

In one example, first, according to the counters accumulated in current global counters 432, a resizeSubpoolAggregate field 434 is incremented by the total amount of storage allocated from the heap since the last garbage collection as calculated by the local counters such as heap allocation counter 416. A resizeSubpoolTarget field 436 is maintained that designates the amount of available free space after the last garbage collection after subpools were established. Next, a ratio field 438 is set to the fraction of resizeSubpoolTarget field 436 divided by resizeSubpoolAggregate field 434. In one embodiment, however, the subpools are not altered until the resizeSubpoolAggregate is at least as large as the resizeSubpoolTarget to avoid subpool reassignment based on an inadequate number of allocations.

In predicting future allocation requirements and adjusting free list distribution requirements, a selection of reserved subpools may be automatically designated. In particular, first, one subpool may