Wednesday – 10:30-12:00
Convention Ctr - Ballroom 6C

Storage Management

Chair: Tony Hosking
Purdue University

Storage Management is an inherent and important underlying, enabling technology for modern object-oriented languages and systems. The first paper proposes a new storage allocator called reaps that combines the benefits of both region-based allocation and individual, object-based deletion. The second paper aims to improve garbage collection time by exploiting the locality of objects and their allocations during traversal. The third paper considers transactional caching in a distributed objects setting and proposes a technique to exploit the cached objects in peers, thus eliminating expensive roundtrip access to remote servers.

Reconsidering Custom Memory Allocation
Emery Berger
The University of Texas at Austin

Benjamin Zorn
Microsoft Research

Kathryn McKinley
The University of Texas at Austin

Programmers hoping to achieve performance improvements often use custom memory allocators. This in-depth study examines eight applications that use custom allocators. Surprisingly, for six of these applications, a state-of-the-art general-purpose allocator (the Lea allocator) performs as well as or better than the custom allocators. The two exceptions use regions, which deliver higher performance (improvements of up to 44%). Regions also reduce programmer burden and eliminate a source of memory leaks. However, we show that the inability of programmers to free individual objects within regions can lead to a substantial increase in memory consumption. Worse, this limitation precludes the use of regions in common programming idioms, reducing their usefulness.

We present a generalization of general-purpose and region-based allocators that we call reaps. Reaps are a combination of regions and heaps, providing a full range of region semantics with the addition of individual object deletion. We show that our implementation of reaps provides high performance, outperforming other allocators with region-like semantics. Our results indicate that programmers needing fast regions should use reaps, and that most programmers considering custom allocators should instead use the Lea allocator.

Creating and Preserving Locality of Java Applications at Allocation and Garbage Collection Times
Yefim Shuf
Princeton University

Manish Gupta
IBM T. J. Watson Research Center

Hubertus Franke
IBM T. J.Watson Research Center

Andrew Appel
Princeton University

Jaswinder Pal Singh
Princeton University

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 technique for traversing live objects at garbage collection (GC) time. The benefits of this techniques are twofold: (i) it improves 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, SPECjbb2000, and jOlden), from an implementation of these techniques in the Jikes RVM, 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 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.

BuddyCache: High Performance Object Storage for Collaborative Strong-Consistency Applications in a WAN
Magnus Bjornsson
Brandeis University

Liuba Shrira
Brandeis University

Collaborative applications provide a shared work environment for groups of networked clients collaborating on a common task. They require strong consistency for shared persistent data and efficient access to fine-grained objects. These properties are difficult to provide in wide-area networks because of high network latency. BuddyCache is a new transactional caching approach that improves the latency of access to shared persistent objects for collaborative strong-consistency applications in high-latency network environments. The challenge is to improve performance while providing the correctness and availability properties of a transactional caching protocol in the presence of node failures and slow peers. We have implemented a BuddyCache prototype and evaluated its performance. Analytical results, confirmed by measurements of the BuddyCache prototype using the multi-user 007 benchmark indicate that for typical Internet latencies, e.g. ranging from 40 to 80 milliseconds round trip time to the storage server, peers using BuddyCache can reduce by up to 50% the latency of access to shared objects compared to accessing the remote servers directly.