A New Solution to the Hidden Copy Problem

Editor(s)

Levi, Giorgio

Abstract

We consider the well-known problem of avoiding unnecessary costly copying that arises in languages with copy/value semantics and large aggregate structures such as arrays, sets, or files. The origins of many recent studies focusing on avoiding copies of flat arrays in functional languages may be traced back to SETL copy optimization [Schwartz 75]. The problem is hard, and progress is slow, but a successful solution is crucial to achieving a pointer-free style of programming envisioned by [Hoare 75]. We give a new solution to copy optimization that uses dynamic reference counts and lazy copying to implement updates effciently in an imperative language with arbitrarily nested finite sets and maps (which can easily model arrays, records and other aggregate datatypes). Big step operational semantics and abstract interpretations are used to prove the soundness of the analysis and the correctness of the transformation. An efficient algorithm to implement the analysis is presented. The approach is supported by realistic empirical evidence. Our solution anticipates the introduction of arbitrarily nested polymorphic sets and maps into JAVA. It may also provide a new efficient strategy for implementing object cloning in Java and object assigment in C++. We illustrate how our methods might improve the recent approach of [Wand and Clinger 98] to avoid copies of flat arrays in a language of first-order recursion equations.

Department(s)

Mathematics and Statistics

Keywords and Phrases

Copy Optimization; Big Step Operational Sementics; abstract interpretation; Must Alias Analysis

Document Type

Article - Journal

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 1998 Springer Verlag, All rights reserved.

Publication Date

01 Jan 1998

Link to Full Text

Share

 
COinS