Static and Dynamic Partitioning of Pointers

as Links and Threads

Technical Report 437

David S. Wise and Joshua Walgenbach

Computer Science Department, Indiana University

Bloomington, Indiana 47405{4101 USA

dswise,[email protected]

Abstract

Identifying some pointers as invisible threads, for the purposes of storage management, is a generalization from several widely used programming conventions, like threaded trees. The necessary invariant is that nodes that are accessible (without threads) emit threads only to other accessible nodes. Dynamic tagging or static typing of threads ameliorates storage recycling both in functional and imperative languages.

We have seen the distinction between threads and links sharpen both hardware- and software-supported storage management in Scheme, and also in C. Certainly, therefore, implementations of languages that already have abstract management and concrete typing, should detect and use this as a new static type.

Categories and subject descriptors:
D.3.3 [Programming Languages]: Language Constructs and Features|data types and structures, dynamic storage management, abstract data types; E.2 [Data Storage Representations]: Linked representations; B.3.2 [Memory Structures]: Design Styles|primary memory.
General Term: Languages.
Additional Key Words and Phrases: storage management, reference counting, garbage collection, tags.

1 Introduction

All active references or pointers originate from roots" in the programming environment; common roots are the register file and recursion stack. Storage management preserves linked structures that are accessible from roots, where the garbage-collecting traversal begins.
Definition 1 A pointer is a link if it is essential to the integrity of a linked structure.

Copyright c 1996 by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or [email protected]. To appear in Proc. of 1996 Intl. Conf. on Functional Programming, May 1996, Philadelphia and in SIGPLAN Notices 31.

Informally, a linked structures must be rooted and spanned by links.

Definition 2 A pointer or reference is a thread [12] if it is optional in a linked structure, in the sense that it can be inferred from a traversal from the roots that follows links exclusively.

On first reading of any program, one may assume that all pointers/references are links; threads can be introduced later. Usually there are several ways to establish a partitioning between links and threads. Of course, it is best to choose a simple one; for instance, links originate from roots and extend homogeneously to the more remote nodes of a structure. Some fields in each record can be statically typed to link" and others to hread." Often, however, a dynamic attribute is used with run-time tags present to distinguish the kind of pointer.

Whether or not threads are identified, however, the semantics of a program must remain the same. Our purpose in identifying them is to unburden the storage manager from dealing with them. Because threads are redundant, it can ignore them and the performance of the program improves without changing its result. That is, link/thread can be a static type like lazy/strict (w.r.t. evaluation of a function's argument) or sticky/unique (w.r.t. reference counting); we might conservatively presume that an unknown type is the first of each pair but, whenever we can discover the second, we can compile for better run-time performance.

Examples of threads are already familiar to the reader. The rear pointer to the end of a singly-linked queue should statically be treated as a thread. Threaded trees [12], in contrast, are an example of a dynamic link/thread distinction, because a pointer requires a run-time tag to imply its meaning. Another familiar thread is the reverse" pointer paired to every forward" link as an edge in a doubly-linked list. Others include weak pointers [15] in many Lisp and Scheme implementations.

The new principle for implementors of programming systems and for low-level programmers is (Invariant 1) that threads point only to nodes accessible exclusively via links.

Programmers should recognize dynamic threading more effectively than they do now; compilers should better recognize static threading [17]. Their use accelerates production code (sometimes called the mutator in systems with automatic storage management) by short-circuiting redundant reallocation, and also they can accelerate space recovery (the collector when one exists). This observation certainly applies to systems with automatic collection, like Lisp, Scheme, ML, Haskell, and Smalltalk, but we