Uniprocessor Performance of a Reference-Counting
Technical Report 401
David S. Wisey, Brian Hecky, Caleb Hessy, Willie Hunty, and Eric Ostyz
c 1994: Indiana University (all rights reserved)
Bloomington, Indiana 47405-4101 USA
A hardware implementation of a self-managing heap has been designed, built, and tested. It's uniprocessor performance demonstrates real-time storage management for general-purpose heap-based programs, and the availability of that performance on multiprocessors.
On every pointer write, remote reference-counting transactions occur in real-time memory; available space is maintained there without processor cycles. A processor obtains a new node simply by reading its address from a distinguished location there. Hardware support for off-line, multiprocessing mark/sweep collection is also provided.
Performance statistics are presented from an implementation of SCHEME,
but this hardware is immediately useful also for languages like Lisp, Smalltalk,
and C++. Although this prototype was fitted to a NeXT uniprocessor, the
design is motivated by shared-heap multiprocessing, the target of a revised
CR categories and Subject Descriptors:
E.2 [Data Storage Representations]: Linked representations; D.4.2 [StorageManagement]: Allocation/Deallocation strategies; B.3.2 [Memory Structures]: Primary memory, Shared memory; C.1.2 [Multiple Data Stream
?Research reported herein was sponsored, in part, by the National Science Foundation under
grants numbered DCR 85-21497 and DCR 90-027092.
yComputer Science Department
zCenter for Innovative Computer Applications