The primary goal of the Cedar effort was to achieve major improvements in the costs of producing reliable, high-quality software. The Cedar language is derived from Mesa, which is a compiled, production-quality system implementation language in the Pascal family with extensive facilities for static checking, error handling, modularity, separate compilation and light-weight processes [1]. Mesa and Cedar are the result of an evolutionary research and development effort in programming languages and systems at XEROX PARC that spans more than a decade.

Work on Cedar began in 1978 with two studies [2,3]: a preliminary one to gather and discuss issues, features, priorities and opportunities based on experience with the Lisp [5], Mesa and SmallTalk[6, 16] programming environments at Xerox PARC, and a follow-up study to look more closely at design tradeoffs between a Lisp starting point and a Mesa one. A Mesa base was then chosen and detailed design and implementation work began in mid-1979.

Experience with Lisp and SmallTalk had taught us that the use of a single virtual address space enables the rapid development of highly integrated applications that share packages and present a standard, ubiquitous user interface. Experience with Mesa had demonstrated the additional value of a single virtual address space for concurrent applications that share packages and can be built on each other. It was clearly important for a human user to be able to deal with several concurrently active tasks at once, switching his attention between them as desired (editting, compiling, debugging, reading or sending mail, printing a file, clock-driven tasks like a reminder system).

Cedar had to manage shared resources well enough to support a disparate mix of ambitious applications; efficient, non-disruptive, concurrent garbage collection was seen as a crucial requirement. It was our goal to achieve a dramatic decrease in the relative cost of managing storage compared to other programming tasks.

A reference-counting scheme much like the one in InterLisp [4] was designed, built and used for early versions of Cedar, but was abandoned later in favor of the design outlined here. The cost of reference-counted assignment was too high; we were able to cut it by roughly 60%. In addition, the InterLisp scheme was overly complex; this limited our ability to make changes or port the system to other machines. It also had two serious problems: a fixed-size reference-count table and fixed-size reference-count table entries. Solving these problems would have required adding still more complexity. And our experience indicates that the page-fault behaviour of the design outlined here is no more of a problem than for the InterLisp scheme.

A word about tactics. Storage management in Mesa is done via language features that allow a program to construct, modify and manipulate pointers. It is effectively impossible for Mesa to protect against a memory smash caused by a buggy program. It was necessary to identify these features and exclude them from a "storage-safe" subset of Cedar for which garbage collection is possible [7]. Though most new code for Cedar was written in the safe subset, it was still possible for debugged Mesa code that uses unsafe features to run in Cedar. This allowed of Cedar development to build on a working compiler and runtime system.

The current Cedar system includes the Cedar language [8]; communication software that uses the Ethernet [9] to provide a "remote procedure call" facility [10] and a distributed file system; a comprehensive suite of integrated packages [11] for graphics [12], screen management, input/output, and text manipulation; a user-extendable executive; debugging facilities based on an abstract machine model; and facilities for managing multiple versions of large software components [13]. Cedar runs on the Dorado, a high-performance personal computer [17, 18] and on other Xerox computers. The system is currently being used by about 80 computer professionals at the Xerox Palo Alto Research Center and elsewhere within Xerox for their daily work. Development continues on various experimental prototypes such as a data base system [14], a calendar system, a mail system, three-dimensional graphics applications, color graphics applications, some CAD tools, an experimental system for organizing information spatially, and several distributed applications based on the remote procedure call facility. Cedar and its applications comprise over 500,000 lines of source program and 3000 files, and represent roughly 60 person-years of effort over a 6 year period. An overview of a recent version of Cedar from a user's point of view can be found in [15].

The most profound extensions of Mesa for Cedar were ones to enable automatic storage deallocation and the manipulation of objects whose types are not known until runtime. This section contains a brief overview of these aspects of the Cedar language. For more complete language descriptions of Mesa and Cedar, the reader is directed to [1] and [8].

A word about the notation used below will help. In the examples, keywords are shown in all caps, in THIS FONT. ":" should be pronounced "has type", "←" as "gets", "[" as "of" or "applied to."

Pretty much any allocation scheme having proper synchronization between the collector and multiple concurrent client programs would work for Cedar, though the major design issue is performance, as usual. Allocation should be fast and require small storage overhead, though its OK for the cost of an allocation to be roughly proportional to the size of the request. Reference-counted assignment should be fast. The work required by the reference-counting collector to reclaim an object should be small. Operations that determine the size and type of an object should be fast. It should be possible to implement a stop-the-world, trace-and-sweep collector that runs in a reasonable amount of time and requires only a modest amount of storage space.

Every collectible object in Cedar has a header. One word carries the object's typeTag; this is 0 if the object is on a free list. Another word carries a coded size field, a reference-count field and four tag bits named "maybeOnStack", "rcOverflowed", "onZCT" and "finalizationEnabled." The headers of small objects have only these two words; the headers of larger objects have an additional two words.

For small objects, the Cedar allocator uses a vector of free lists, each a chain of blocks of uniform size. Block sizes are quantized to decrease fragmentation, but the quantization grain is fine enough to keep expected excess storage in a block to under 10% of the requested size. Indices into this vector (called "block size indices") are stored in object headers to identify both the size of the object and the free list from which it came and to which it should be returned by the collector. This enables use of a small size field in object headers. Table lookup is used to convert among raw size, quantized size and block size index. When a free list is found to be empty, a sequence of pages is acquired from the operating system's VM allocator. This has sufficient length to be carved up into an integral number of blocks of the desired size. Such blocks are never subdivided or merged with others.

For medium-sized objects, a modified first-fit algorithm using a doubly-linked free list of variable-sized blocks is used. For each large object, Cedar utilizes a sequence of pages that is acquired directly from the operating system's VM allocator. Both medium-sized and large objects require extended headers to store their lengths; a special block size index is used to identify such objects.

The Cedar allocator maintains a vector of bits, one for each page in VM, called the "allocation map." The bit for a page is set TRUE if the page is assigned to the allocator. This is used by the trace-and-sweep collector both to determine whether a bit pattern found on the active stack could be a ref to an allocated object that should be traced, and to enumerate all objects during its sweep phase.

Critical allocation and reclamation operations are microcoded for performance reasons. These either run to completion (i.e. are atomic with respect to all other operations) or they trap to equivalent software procedures to handle unusual situations, for example when a free list is found to be empty. If a trap does occur, the microcode has made no changes.

Concurrency is managed in software through the use of Mesa Monitors and Condition Variables. The method outlined below enables both low-cost execution via microcode in the simple, normal case and flexible, synchronized load-sharing between microcode and software in unusual, more complex cases. Similar techniques can be used in a concurrent execution environment to do incremental development or testing of an ensemble of microcode and software routines that require synchronization and mutual exclusion.

The distinguishing characteristic of a good garbage collection scheme is that under normal circumstances you never notice it. It certainly should not interrupt the user or cause a noticeable suspension of system activity or degradation of system performance. It should be extremely reliable. And the cost of garbage collection (storage overhead, execution time, working set requirements) should be comparable to the cost of manual storage management.

Cedar provides both a concurrent reference-counting collector that runs in the background when needed and a pre-emptive, conventional "trace-and-sweep" one that can be invoked explicitly by the user to reclaim circular data structures; a reference-counting collector cannot reclaim these.

Both collectors treat procedure-call activation records (called frames) "conservatively"; i.e., they assume that every ref-sized bit pattern found in a frame might be a ref, hence its referent might be accessible. An object referenced from a frame will not be reclaimed. For the reference-counting collector, this trick eliminates the need to count references in frames, a substantial optimization. For the trace-and-sweep collector, this eliminates the need to locate refs in frames, which would require much more complex and expensive synchronization between the trace-and-sweep collector and compiled code, not to mention a major overhaul of the compiler and parts of the microcode. The conservative collection scheme can cause unnecessary retention. We did extensive experiments under a variety of execution circumstances to determine an upper bound on the amount of storage retained by the conservative collection scheme and found it to be insignificant. Uncertainty as to whether a particular object will get finalized after it becomes inaccessible is more of a problem.

It is often useful to specify actions to take when an object of a particular type is no longer accessible to any client of the package that created it. Such "package finalization" actions might include (for example) removal of the object from a cache that the package maintains.

In a world without garbage collection, special-purpose finalization actions are performed by the same application-dependent code required to explicitly free the object; deciding when to finalize is not an issue. In a world with garbage collection, explicit de-allocation is not required but the need for finalization remains. Application-dependent arrangements for deciding when to finalize are usually inconvenient, expensive, error-prone and they duplicate in one way or another functions that the collector provides; they defeat its purpose. Like automatic storage management, automatic finalization is more than a convenience.

Cedar provides an automatic finalization mechanism that is efficient, type-safe and storage-safe. Though one can imagine more general facilities for finalization, we have found that the features described below are a useful and powerful set.

Looking a little more carefully at usage, there appear to be three kinds of applications for finalization: ones with no package data structure, ones with a package data structure that is accessed only during object creation or object finalization, and ones with a package data structure that is used as a cache from which copies of refs to existing objects are handed out to clients. Finalization for the first two applications is straightforward, but the synchronization required for caching applications is somewhat subtle. For caching applications, finalization actions must be synchronized with access to the cache. The following example illustrates what is believed to be a correct framework for such applications ...

Our experience with programming Cedar and its applications indicates that it is natural to use the REF ANY feature extensively, but only if the runtime type-equivalence predicate is fast.

To this end, we developed a finite-state-machine model for the Cedar type system (recursively defined types are common) and designed an algorithm based on FSM minimization techniques to derive a canonical FSM for a given Cedar type. We also developed an algorithm for converting the representation of such a "canonical" FSM into a variable-length string of characters with the property that any two equivalent types would yield the same "type string." The Cedar type equivalence algorithm was thereby reduced to comparison of two variable-length strings for equality [21]. A further reduction in the cost of the algorithm can be achieved by computing a fixed-length hash code from the type string and using equality comparison of hash codes, then using a runtime data structure to map hash-codes to the smaller typeTags. With careful choice of hash code length and algorithm, this scheme can be shown to have an expected failure rate due to hash collisions that can be safely ignored.

The computation of type string hash codes is done by the compiler. The Cedar runtime software keeps the hash code with each type descriptor; use of a hash code equality test enables the loader to acquire typeTags rapidly when a new program module is loaded. TypeTags are simply indices in a table of pointers to type descriptors. TypeTags are stored in object headers. Two (one-word) typeTags are equal IFF the corresponding Cedar types are equivalent. Thus, the runtime type-equivalence predicate is fast.

Perhaps the largest challenge in the design of the allocator, collector and reference-counting machinery was dealing with concurrency. Deadlock had to be avoided. Maximal concurrency was needed to minimize suspension of client activity and degradation of system performance. Atomicity requirements for operations on shared resources had to be specified correctly and guaranteed by the implementation. An ability to debug concurrent programs that exhibit unreproduceable behaviour was necessary.

One example of a concurrency-related problem has to do with changes made to the contents of an active procedure frame while the collector is running. Consider the following scenario: at the start of a collection, an object X has a reference count of 2; one reference resides in an accessible object Y, and the other resides in an inaccessible object Z. No references to X reside on the stack. The collection begins; a client program picks up the reference to X that is in Y and then NIL-ifies it, decreasing X's count to 1 but leaving a reference to X in a procedure variable on the stack. The collector finds Z; the reclaimer decrements the count on X when it discovers the reference within Z; X now has a count of 0 and gets reclaimed. Disaster ensues sometime later when the client program tries to make sense of its reference to what used to be X. The solution to this problem is to provide a flag named "maybeOnStack" in each object's header; this is set while the collector is active whenever a client assignment decrements the reference count. Any increment of the reference-count clears the flag. The collector checks the flag before deciding that an object can be reclaimed. All maybeOnStack flags in objects referenced from the zero-count-table are cleared by the collector just before it finishes.

Our experience with Cedar indicates that the design outlined here works well. Time and effort spent by programmers to solve storage management-related problems has decreased from an estimated 40% in Mesa to an estimated 5% in Cedar (the remaining problems deal almost exclusively with the management of large areas of virtual memory). Automatic storage deallocation helps make building, debugging and integrating new system components and experimental applications fast and easy.

A major design criterion for the Cedar allocator, collector and reference-counting machinery (as usual) was good performance. In current Cedar, reference-counted assignment takes about 2 microseconds on a Dorado [17, 18]. The average "round trip" time for allocation and collection of an object, including collector overhead, is roughly 150-200 microseconds. Very little tuning has been done to decrease these costs; it should be easy to do so.

Cedar is a large, complex system. Bigness and complexity are not good when smaller and simpler will do as well. "Systems should be as simple as possible, but no simpler", however [19]. It is often the case that increased implementation complexity leads to decreased complexity for the client or the user; a good example from this paper is the elaboration to support concurrency on what could have been a simpler design. Another is the provision of a finalization mechanism. Complexity is a fact of life that we must learn to deal with if we are to continue making progress towards systems that bring the best possible communication and computing functions to people.

A complete realization of the Cedar features required a substantial increase in the level of integration among the compiler, allocator, collector, microcode, loader, and debugger. Of necessity, this (and other integration problems) led both to the exploration of some new ideas for managing the development of large software systems [13] and to several architectural overhauls of the system. The ability to fold experimental techniques and applications smoothly back into an evolving system as they are completed and proven valuable is crucial to system research projects like Cedar [22]. Perhaps the most important contribution of the Cedar work is the set of techniques and research directions that were developed to enable the orderly evolution of such big systems.

XXX.