Creating and preserving locality of Java applications at allocation and garbage collection times

Yefim Shuf, Manish Gupta, Hubertus Franke, Andrew Wilson Appel, Jaswinder Pal Singh

Research output: Contribution to journalArticle

Abstract

The growing gap between processor and memory speeds is motivating the need for optimization strategies that improve data locality. A major challenge is to devise techniques suitable for pointer-intensive applications. This paper presents two techniques aimed at improving the memory behavior of pointer-intensive applications with dynamic memory allocation, such as those written in Java. First, we present an allocation time object placement technique based on the recently introduced notion of prolific (frequently instantiated) types. We attempt to co-locate, at allocation time, objects of prolific types that are connected via object references. Then, we present a novel locality based graph traversal technique. The benefits of this technique, when applied to garbage collection (GC), are twofold: (i) it improves the performance of GC due to better locality during a heap traversal and (ii) it restructures surviving objects in a way that enhances locality. On multiprocessors, this technique can further reduce overhead due to synchronization and false sharing. The experimental results, on a well-known suite of Java benchmarks (SPECjvm98 [26], SPECjbb2000 [27], and jOlden [4]), from an implementation of these techniques in the Jikes RVM [1], are very encouraging. The object co-allocation technique improves application performance by up to 21% (10% on average) in the Jikes RVM configured with a non-copying mark- and-sweep collector. The locality-based traversal technique reduces GC times by up to 20% (10% on average) and improves the performance of applications by up to 14% (6% on average) in the Jikes RVM configured with a copying semi-space collector. Both techniques combined can improve application performance by up to 22% (10% on average) in the Jikes RVM configured with a non-copying mark-and-sweep collector.

Original languageEnglish (US)
Pages (from-to)13-25
Number of pages13
JournalACM SIGPLAN Notices
Volume37
Issue number11
DOIs
StatePublished - Nov 1 2012

Fingerprint

Storage allocation (computer)
Data storage equipment
Copying
Synchronization

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Cite this

@article{fc1ba26638534475bf3c3f97ed28302e,
title = "Creating and preserving locality of Java applications at allocation and garbage collection times",
abstract = "The growing gap between processor and memory speeds is motivating the need for optimization strategies that improve data locality. A major challenge is to devise techniques suitable for pointer-intensive applications. This paper presents two techniques aimed at improving the memory behavior of pointer-intensive applications with dynamic memory allocation, such as those written in Java. First, we present an allocation time object placement technique based on the recently introduced notion of prolific (frequently instantiated) types. We attempt to co-locate, at allocation time, objects of prolific types that are connected via object references. Then, we present a novel locality based graph traversal technique. The benefits of this technique, when applied to garbage collection (GC), are twofold: (i) it improves the performance of GC due to better locality during a heap traversal and (ii) it restructures surviving objects in a way that enhances locality. On multiprocessors, this technique can further reduce overhead due to synchronization and false sharing. The experimental results, on a well-known suite of Java benchmarks (SPECjvm98 [26], SPECjbb2000 [27], and jOlden [4]), from an implementation of these techniques in the Jikes RVM [1], are very encouraging. The object co-allocation technique improves application performance by up to 21{\%} (10{\%} on average) in the Jikes RVM configured with a non-copying mark- and-sweep collector. The locality-based traversal technique reduces GC times by up to 20{\%} (10{\%} on average) and improves the performance of applications by up to 14{\%} (6{\%} on average) in the Jikes RVM configured with a copying semi-space collector. Both techniques combined can improve application performance by up to 22{\%} (10{\%} on average) in the Jikes RVM configured with a non-copying mark-and-sweep collector.",
author = "Yefim Shuf and Manish Gupta and Hubertus Franke and Appel, {Andrew Wilson} and Singh, {Jaswinder Pal}",
year = "2012",
month = "11",
day = "1",
doi = "https://doi.org/10.1145/583854.582422",
language = "English (US)",
volume = "37",
pages = "13--25",
journal = "ACM SIGPLAN Notices",
issn = "1523-2867",
publisher = "Association for Computing Machinery (ACM)",
number = "11",

}

Creating and preserving locality of Java applications at allocation and garbage collection times. / Shuf, Yefim; Gupta, Manish; Franke, Hubertus; Appel, Andrew Wilson; Singh, Jaswinder Pal.

In: ACM SIGPLAN Notices, Vol. 37, No. 11, 01.11.2012, p. 13-25.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Creating and preserving locality of Java applications at allocation and garbage collection times

AU - Shuf, Yefim

AU - Gupta, Manish

AU - Franke, Hubertus

AU - Appel, Andrew Wilson

AU - Singh, Jaswinder Pal

PY - 2012/11/1

Y1 - 2012/11/1

N2 - The growing gap between processor and memory speeds is motivating the need for optimization strategies that improve data locality. A major challenge is to devise techniques suitable for pointer-intensive applications. This paper presents two techniques aimed at improving the memory behavior of pointer-intensive applications with dynamic memory allocation, such as those written in Java. First, we present an allocation time object placement technique based on the recently introduced notion of prolific (frequently instantiated) types. We attempt to co-locate, at allocation time, objects of prolific types that are connected via object references. Then, we present a novel locality based graph traversal technique. The benefits of this technique, when applied to garbage collection (GC), are twofold: (i) it improves the performance of GC due to better locality during a heap traversal and (ii) it restructures surviving objects in a way that enhances locality. On multiprocessors, this technique can further reduce overhead due to synchronization and false sharing. The experimental results, on a well-known suite of Java benchmarks (SPECjvm98 [26], SPECjbb2000 [27], and jOlden [4]), from an implementation of these techniques in the Jikes RVM [1], are very encouraging. The object co-allocation technique improves application performance by up to 21% (10% on average) in the Jikes RVM configured with a non-copying mark- and-sweep collector. The locality-based traversal technique reduces GC times by up to 20% (10% on average) and improves the performance of applications by up to 14% (6% on average) in the Jikes RVM configured with a copying semi-space collector. Both techniques combined can improve application performance by up to 22% (10% on average) in the Jikes RVM configured with a non-copying mark-and-sweep collector.

AB - The growing gap between processor and memory speeds is motivating the need for optimization strategies that improve data locality. A major challenge is to devise techniques suitable for pointer-intensive applications. This paper presents two techniques aimed at improving the memory behavior of pointer-intensive applications with dynamic memory allocation, such as those written in Java. First, we present an allocation time object placement technique based on the recently introduced notion of prolific (frequently instantiated) types. We attempt to co-locate, at allocation time, objects of prolific types that are connected via object references. Then, we present a novel locality based graph traversal technique. The benefits of this technique, when applied to garbage collection (GC), are twofold: (i) it improves the performance of GC due to better locality during a heap traversal and (ii) it restructures surviving objects in a way that enhances locality. On multiprocessors, this technique can further reduce overhead due to synchronization and false sharing. The experimental results, on a well-known suite of Java benchmarks (SPECjvm98 [26], SPECjbb2000 [27], and jOlden [4]), from an implementation of these techniques in the Jikes RVM [1], are very encouraging. The object co-allocation technique improves application performance by up to 21% (10% on average) in the Jikes RVM configured with a non-copying mark- and-sweep collector. The locality-based traversal technique reduces GC times by up to 20% (10% on average) and improves the performance of applications by up to 14% (6% on average) in the Jikes RVM configured with a copying semi-space collector. Both techniques combined can improve application performance by up to 22% (10% on average) in the Jikes RVM configured with a non-copying mark-and-sweep collector.

UR - http://www.scopus.com/inward/record.url?scp=85062241029&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85062241029&partnerID=8YFLogxK

U2 - https://doi.org/10.1145/583854.582422

DO - https://doi.org/10.1145/583854.582422

M3 - Article

VL - 37

SP - 13

EP - 25

JO - ACM SIGPLAN Notices

JF - ACM SIGPLAN Notices

SN - 1523-2867

IS - 11

ER -