Browse Prior Art Database

Reducing the cost of data structure backing store growth in Java

IP.com Disclosure Number: IPCOM000191571D
Original Publication Date: 2010-Jan-07
Included in the Prior Art Database: 2010-Jan-07
Document File: 4 page(s) / 36K

Publishing Venue

IBM

Abstract

Data structure expansion can be an expensive operation for a Java (tm) application to accomplish, both in terms of memory footprint and performance. This disclosure describes a mechanism that allows a light weight expansion of a core data structure building block (arrays) without modification of application code.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 49% of the total text.

Page 1 of 4

Reducing the cost of data structure backing store growth in Java

Disclosed is a mechanism to reduce JavaVirtual Machine (JVM) object heap pressure during data structure growth. The disclosed mechanism transparently represents internal contiguous data structures as a series of disjoint elements, such that during expansion only parts of the data structure need replacing. The disclosed mechanism can be used on primitive data types such as arrays without any modification to existing application code. During an expansion operation when a copy of an existing data structure must be made but with more capacity, duplicating only necessary elements drastically reduces heap requirements of the second data structure.

Many data structures within Java programming make use of an array as backing storage for its contents, for example, HashMap. Because total expected storage capacity of these data structures is difficult to determine in advance, the data structures must support the ability to expand dynamically as contents grow. Dynamic expansion is needed because arrays in Java are not infinite in length,

p

             roviding no language representation for the array to grow or shrink and is the reason for encapsulating the backing store to data structures from the application developer.

When a data structure expands, as shown in Figure 1, the data structure must allocate a new array of a greater size than the current array (1), transfer the contents of the old array to the new array (2), and discard the old array to use the new array (3).

Figure 1:

Drawbacks to this approach include heap resource pressure from keeping both arrays present at the same time during the expansion, selection of an expansion policy in advance of having the data structure that includes predicting the expected capacity, and a potential for unwanted garbage collection pauses as the memory resource is freed to accommodate new storage. Use of custom built data structures to allow dynamic expansion, such as buckets with node lists, lose an

1

[This page contains 1 picture or other non-text object]

Page 2 of 4

ability to be used transparently by applications because the custom data structures are not a core data type within the JVM. The custom data structures are not recognized as a core element of the Java class libraries, and also incur a major heap overhead regardless of expansion issues due to the increase in per-object header overhead.

An existing tiered array system known as Arraylets appears in a Metronome Garbage Collector
[1]. Arraylets introduces a notion of a "spine" that is the main storage of the array, referred to by all other objects in the JVM as the array object, and "leaves" which are the actual body of the array,

pointed to by the spine as depicted in Figure 2.

The underlying format used by the JVM for arrays is transparent to the Java application de...