Browse Prior Art Database

Estimation of "Dark Matter" in Just In Time Compilation to Trigger Compaction in Garbage Collection Disclosure Number: IPCOM000179045D
Original Publication Date: 2009-Feb-05
Included in the Prior Art Database: 2009-Feb-05
Document File: 4 page(s) / 88K

Publishing Venue



"Dark Matter" (arising as small pockets of unusable free- space) is a major performance problem in GC leading to very low throughputs and excessive memory footprint. A Just-in-Time (JIT) compiler can avoid generating dark matter at an allocation site, using a first method described in a previous invention, but the optimization can occur too late to avoid the dark matter that was generated up to that point in time. A second method is described which causes the JIT compiler to inform the garbage collector of a one-off opportunity to remove this residual dark matter. It is a one-off opportunity because after the first method dark matter will no longer be produced by the allocation site. A further refinement is for either the JIT compiler or the garbage collector to accumulate the estimated dark matter, and only trigger removal when this aggregate has reached a threshold.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 22% of the total text.

Page 1 of 4

Estimation of "Dark Matter" in Just In Time Compilation to Trigger Compaction in Garbage Collection


    Memory management techniques are now ubiquitous in object oriented programming languages and methodologies. For instance it occurs in the Java* Programming Environment, in the Microsoft** .NET Framework Common Language Runtime, and in non object-oriented programming languages and runtimes, such as functional programming languages. A comprehensive background to memory management is given in [1].

    In memory management, allocation and storage of memory is managed in a memory structure called the heap. Instead of the programmer controlling the lifetime of dynamically allocated memory, the runtime system does this automatically, and this is termed garbage collection. In object oriented programming, it is typically objects that are dynamically allocated, so this term will be used to describe such memory. Objects may no longer be needed by the application. When such objects are no longer referenced by other live objects or by the application they are termed "dead" objects. Objects that are not "dead" are "alive". When the runtime system decides, dead objects are recycled, so that future allocations can reuse memory.

    A common throughput performance problem in memory managed applications is dark matter[2]. Dark matter is caused when small objects die leaving free space ("holes") that is too small to be reused. This occurs for instance in the mark-sweep algorithm. Most managed runtimes using mark-sweep will not reuse holes that are smaller than a certain size. Let us call this the "dark matter size". The sum of these holes is thus termed "dark matter" because it contains neither live nor free memory, and is effectively lost to the runtime environment.

    The total dark matter can be very large. For instance when running one application at a high occupancy (64% live objects), the total dark matter adds another 47% to this.

    This leads to many significant problems for the runtime. Firstly, with less heap available for allocation, garbage collections (GC's) happen more often. Also the heap may become more fragmented as pressure on space increases, and this can lead to smaller and more frequent allocations from the list of free chunks (the "freelist"). This leads to reduced throughput as the percentage of time in GC increases, and as contention increases on the heaplock that guards the freelist. In measurements we have seen throughput decrease to a fifth of its optimum because of dark matter in one application.

    The standard solution to dark matter is to compact the heap. Compaction moves live objects together closing the gaps between objects, releasing all the dark matter, and reducing fragmentation. However, few solutions other than compacting more frequently or changing the granularity of memory maps are known [3]. In cases where dark matter creation is a problem in many cases the best solution is...