reused. The resident Smalltalk-80 interpreter keeps reference counts of short pointers. This count is kept in the ROT. LOOM uses the ROT reference count to keep the number of short pointers to an object. In addition, every object on the disk contains a reference count which is the number of long pointers to the object. The total count is the sum of the number of short and long pointers to an object. Whenever a long Oop is converted to a short Oop and installed in a field in main memory, both counts for the object pointed at must change. To avoid a disk access to find and modify the long Oop count every time a field is converted, LOOM keeps a "delta" or running change in the long Oop reference count for each object in main memory. The true long pointer reference count of any object is the count found on the disk in the object's header plus the count found in the "delta" part of the object's delta word in main memory. Fig. 14.8 shows the ROT entry, object body, and disk image of an object. The object has three short Oops pointing at it. It used to have pointers from 6 long Oops, but two were destroyed recently (they were probably converted to short Oops). The total number of references to the object is seven.

There are three sources of reference-count changes. One pointer can be stored over another, a long pointer can be converted to a short pointer, and a short pointer can be converted back. Since the interpreter only deals with short Oops, every store consists of a short pointer replacing another short pointer. This high-bandwidth operation touches only the short pointer reference counts, so the existing code in the interpreter does not need modification. When a leaf expands to a normal object, pointers in its fields change from long Oops to short ones. The expand-a-leaf routine increments the short count of that object and decrements the delta of its long count. The inverse happens when the routine which shrinks objects into leaves converts short Oops to long ones.

Consider the case when the short Oop count of an object goes to zero. The reference-count routine then looks at the object's long Oop count to see if the total count of the object is zero. If it is zero, the object is truly free, and its storage can be recycled. If not, the object is still held by some long pointers. When the short Oop reference count goes to zero, and the delta reference count is zero, then the object's long Oop count on disk need not change. Thus if the ultimate long pointer count of a leaf can be guessed correctly when the leaf is created, the disk count and delta count can be adjusted so that the leaf disappears from main memory without further disk references.

As a help to the LOOM system, two other bits are added to the ROT entry for any object—"clean" and "unTouched." Clean is cleared whenever a field of the object is changed; unTouched is cleared whenever a field of the object is read or changed. Clean tells the LOOM system that it need not rewrite the object's image on disk (unless of course, its true reference count changed). Clean is set when the object is newly created
## The Three Types of Reference Counts

<figure><img src="image_39.png" /></figure>

## Example Reference Counts

<figure><img src="image_40.png" /><figcaption>Figure 14.8</figcaption></figure>

or swapped in. UnTouched is set by a routine that sweeps core whenever space is needed. Any object that the routine finds with unTouched still set has not been touched in an entire pass through memory, and is thus a candidate for being *contracted* (turned into a leaf).

The activity which is most likely to cause LOOM to thrash is the resolution of lambdas. When a lambda needs to be resolved (turned into a leaf or discovered to be an existing short Oop), LOOM must first look at the disk image of the parent object. If the pattern of computation is
such that the noLambda hint does not correctly predict which fields are needed by the interpreter, lambdas would have to be resolved often. Even so, lambda resolution is likely to happen soon after the parent was expanded, so keeping the most recently fetched disk pages in a cache relieves the need to go to the disk. When a lambda needs to be resolved, the LOOM procedure looks first in the cache of pages that is called the *disk buffer*. If it finds the object in the buffer, it can directly retrieve the long Oop for the lambda, saving one disk access.

## LOOM
Implemented in the
Smalltalk-80
Language

The LOOM design, though based on only a couple of simple principles, has a number of reasonably complex algorithms that require a substantial amount of code. We were faced with the problem of whether to implement LOOM's object swapping algorithms in a low-level language or a high-level language. Low-level implementations typically provide better performance at the cost of some flexibility.

We opted to implement the LOOM system in our favorite high-level system, the Smalltalk-80 system. A number of factors influenced this choice. The overriding factor was that for us, the Smalltalk-80 language was the most natural way to express and understand complex algorithms. We are implementing LOOM on the Xerox Dorado computer⁵ (see also Chapter 7). We believe that the Dorado has sufficient performance and memory space so that the LOOM system will not be called very often. When LOOM is called, it will run with acceptable performance. Also, once the system is up and running, we will have a complete, debugged high-level description of the algorithms. Should we decide to reimplement LOOM on the Dorado or another machine in a lower-level language, only a translation of the code would be required. In addition, we designed LOOM not only as a working virtual memory system for our Smalltalk-80 work, but also as a test-bed for virtual memory techniques. Jim Stamos' master's thesis⁶ is an example of one experimental technique based on simulation. We want further studies to use a real virtual memory system.

Deciding to implement LOOM in the Smalltalk-80 language itself led to problems that might not be encountered in a low-level language implementation. In particular, the amount of "machine state" that needs to be saved when switching between running the Smalltalk-80 interpreter for "user" and for LOOM was quite large. The amount is much larger than the amount of Smalltalk-80 virtual machine state that would have to be saved to run the LOOM code written in machine language. Also, to avoid a fault on the faulting code, all of the code and other objects which comprise the implementation of LOOM must be guaranteed to stay in main memory at all times.
We handled the first problem, saving state, by reworking our interpreter. It now obeys the convention that within the execution of a bytecode, an object fault is possible only before any "destructive" operations occur. In other words, before the interpreter writes into a field of any object or changes the reference count of any object, it reads fields from all objects needed by the current bytecode. In this way, the state we needed to save was only the "permanent" state that exists between bytecodes. Temporary state within a bytecode is not saved. In our system then, if an object fault occurs, we back up the Smalltalk program counter, switch the interpreter to the LOOM system, handle the fault, and then restart the bytecode.

The second problem, insuring that no object faults occur during the execution of the LOOM algorithms themselves, went through a couple of different designs. The first method we tried was to have the LOOM objects and the user's objects in the same Smalltalk-80 space, but to mark all the objects LOOM would ever need "unpurgable", and to guarantee that free space never went below a certain level. We made an almost-complete implementation of LOOM using this method on the Xerox Alto computer⁷ before moving onto the Dorado. The problem with LOOM and the user sharing the same Smalltalk is retaining the marks on objects that LOOM needs. If the user adds many methods to class SmallInteger and its method dictionary grows, how does the new array in the dictionary get marked "unpurgable"? There are many similar cases.

The LOOM implementation on the Dorado has two separate Smalltalk-80 systems in the same machine: a full-size system for user's programs, and a smaller one for LOOM. The LOOM system has some primitives that enable it to manipulate the bits inside of objects in the user system. (Note that because they use the same interpreter, the user system has these primitives also. However, they make no sense in the user system, so are never used.) Because the LOOM system uses only a small subset of the Smalltalk-80 system, it can be much smaller, and can be guaranteed to fit entirely within its portion of main memory and never cause an object fault. Fig. 14.9 provides a view of the communication between the systems.

Alternative Smalltalk Virtual Memory Designs

The LOOM virtual memory design is only one of many ways to implement a virtual memory for a Smalltalk-80 system. The advantages of the LOOM design are:

1. It runs as fast as a resident Smalltalk-80 interpreter when the working set is in core,
<figure><img src="image_41.png" /><figcaption>Figure 14.9</figcaption></figure>
2. It uses 16-bit fields in core to conserve space,

3. It allows the interpreter to avoid handling 32-bitOops, which makes the interpreter smaller and faster on 16-bit machines,

4. It only uses memory for objects that are actually referenced, and

5. It provides a large, 32-bit virtual address space.

Its major disadvantages are:

1. It relies on fairly complicated algorithms to translate between the address spaces,

2. It takes no advantage of current hardware technology for memory fault detection, and

3. It must move objects between disk buffers and their place in memory.

There are alternatives to many of the design decisions within LOOM and to using the LOOM design itself.

LOOM was designed specifically to experiment with various methods of "grouping" objects on disk pages. If objects which are likely to be faulted on at the same time live on the same disk page, only the first fault actually has to wait for the disk. Static grouping restructures the arrangement of objects on disk pages while the system is quiescent. It reduces the number of disk accesses for both paged virtual memories and object swapping systems. Stamos extensively studied the advantages of static grouping and compared LOOM to paged virtual memories⁸. LOOM is also designed for experiments in dynamic grouping. We have several algorithms in mind for moving objects on the disk while Smalltalk is running. These algorithms will endeavor to reduce faulting by dynamically placing related objects on the same disk page.

We also mentioned that a LOOM system can be built that only uses leaves and not lambdas. Another alternative that we did not pursue is to use a marking garbage collection scheme for resident objects and reference counting for disk references. This should be possible using the delta reference-count scheme.

LOOM is currently intended for use over a local area network. The design could be extended to bring many users, many machines, and large quantities of immutable data into the same large address space. If 32-bit longOops are not big enough, objects in secondary memory could be quad-word aligned, giving 2³⁶ bytes of address space. The LOOM algorithms are parameterized for the width of long pointers, so that a change to 48-bit wide longOops would not be difficult to do.

The LOOM design may be used for non-Smalltalk systems. In particular, we have proposed a LOOM-like design to extend the address space of Interlisp-D. The design adds another level of virtual memory to the
existing Interlisp-D paging system by treating a page as a single object and an existing page address as a short pointer.

## Learning from LOOM

Our LOOM virtual memory system is in its infancy. We are only beginning to make measurements on its performance. The design choices of the LOOM system are based on the belief that the way to design good virtual memory systems is to determine what happens most of the time, make it go fast, and hope it continues to happen most of the time. Many trade-offs were made to meet this goal. Some of the design choices we made apply to almost all Smalltalk-80 implementations and some were determined by our hardware/software environment. For example, the general idea that object swapping saves main memory over paging applies to all Smalltalk-80 systems, but the relative cost of object swapping versus paging can be heavily influenced by hardware support for one or the other. Since we know of no current hardware that supports object swapping, but we do know that a great deal of current hardware supports paging, paging has a tremendous advantage. Many of the costs of paging are hidden, such as the address computation on every memory reference, and the "built in" paging hardware on many machines. If those costs were brought into the open, and the same amount were spent on assisting object references, object oriented virtual memories might have better cost-performance than paging systems.

The LOOM design uses two levels of object addressing and translates between address spaces when necessary. Up to 2³¹ objects residing on secondary storage are represented by a cache of 2¹⁵ objects in main memory. These behave almost identically to resident Smalltalk-80 objects. When a reference from an object in main memory to one in secondary memory is made, an object fault occurs, the latter is brought into main memory, and processing continues. This design allows for a large virtual address space and a space- and speed-efficient resident space. Because the major algorithms in LOOM are written in Smalltalk itself, LOOM will be a major test-bed for new swapping algorithms and for new ways of reducing page faults by grouping objects in secondary storage.

## Acknowledgments

The design of LOOM was a true group effort. Jim Althoff and Steve Weyer proposed an early version to improve the speed of their work on programmer directed object overlays. Peter Deutsch worked out a design for an early version of the dual name spaces (short and long Oops).
Dan Ingalls, Glenn, and Ted designed the three kinds of reference counts. Danny Bobrow said that leaves were not enough, and Larry Tesler suggested lambdas from the design of his operating system called Caravan. Ted, Dan, and Glenn worked out the final system design, and Ted and Diana Merry built a test version of the LOOM algorithms. Ted and Glenn did the Alto and Dorado implementations.

## References

1. Denning, Peter J., "Virtual Memory", Computing Surveys vol. 2, no. 3, Sept. 1970.

2. Burton, Richard R., et al., (The Interlisp-D Group), Papers on Interlisp-D, Xerox PARC CIS-5, July 1981; (a revised version of Xerox PARC SSL-80-4).

3. Kaehler, Ted, "Virtual Memory for an Object-Oriented Language", Byte vol. 6, no. 8, Aug. 1981.

4. Goldberg, Adele, and Robson, David, *Smalltalk-80: The Language and Its Implementation*, Addison-Wesley, Reading, Mass., 1983.

5. Lampson, Butler W., and Pier, Kenneth A., "A Processor for a High-Peformance Personal Computer", Seventh International Symposium on Computer Architecture, SigArch/IEEE, La Baule, France, May 1980; (also in Xerox PARC CSL-81-1, Jan. 1981.)

6. Stamos, James W., "A Large Object-Oriented Virtual Memory: Grouping Strategies, Measurements, and Performance," Xerox PARC SCG-82-2, May 1982.

7. Thacker, C. P., et al., "Alto: A Personal Computer", in *Computer Structures: Readings and Examples*, 2nd Edition, Eds. Sieworek, Bell, and Newell, McGraw-Hill, New York, 1981; (also Xerox PARC CSL-79-11, Aug. 1979).

8. See reference 6.
<figure><img src="image_42.png" /></figure>

RUNNING OUT OF MEMORY
IS LIKE COMING TO THE
END OF YOUR ROPE

<figure><img src="image_43.png" /></figure>
<figure><img src="image_44.png" /></figure>
# Managing the Evolution of Smalltalk-80 Systems

Steve Putz

Software Concepts Group
Xerox Palo Alto Research Center
Palo Alto, California

## Introduction

This paper describes a software system currently being used by the Software Concepts Group (SCG) to help facilitate and document our development of the Smalltalk-80 system. The central feature of this development support system is a remote database containing information about past and proposed changes to the Smalltalk-80 system, as well as bug reports and an informal library of application programs. We call the present program which maintains this database the Smalltalk-80 version handler.

Three kinds of documentation which we have found to be important in the development of the Smalltalk-80 system are:

1. Documentation of system changes and system release versions,

2. Documentation of known bugs and other problems, and

3. Maintenance of a software applications library.

## A Research Programming Environment

The SCG Smalltalk-80 programming environment is used as an experimental basis for the development of new concepts in user interfaces, language, and system development tools. The system is modified in order to repair bugs, to enhance existing functions, and to introduce new
functionality. New versions of the system are released for use within the group frequently. Since different people are often working on the system at the same time, it is important to coordinate and document changes to the system, so that inconsistencies are not introduced and new bugs are kept to a minimum. Since each user has their own copy of the system, those who are using the Smalltalk-80 system for creating independent applications also need to know about changes to the system, so they can maintain compatibility and take advantage of new features. Documentation of problems found by users of the system can help to warn other users, as well as serving as a list of "things to fix." It is therefore very desirable to have a well maintained bug list which is easy to update and access.

In addition to fixing and improving the Smalltalk-80 system itself, SCG and other users often create small software applications or enhancements which may be of interest to others. We call these programs and enhancements "goodies." It is useful to have easy availability and documentation for these goodies in the form of a software applications library. If popular, goodies may be incorporated into a later version of the system.

## Past Practices

In the early development of the Smalltalk-80 system, as with its precursors, we had only some *ad hoc* and informal mechanisms for maintaining the three kinds of system documentation mentioned earlier. At any given time, our current Smalltalk system would be more or less stable depending on the current focus of activity. During a period of rapid change and development, many people are doing systems programming and new versions of the system may be created as often as several times a day. Eventually this is followed by a more stable period in which more people are doing applications and other independent experiments; new versions of the system, with minimal changes, are then released every few months or so.

During the periods of rapid system development, changes were frequently made directly to the current system image, which was then written out to become the new, current system. Although old versions were always maintained for reference and recovery, no systematic documentation was kept of the changes made, other than verbal communication and some notes (written by the programmer) kept within the system itself. Bugs were either communicated verbally or sometimes listed on a whiteboard until fixed.
During more stable periods, changes were collected in Smalltalk-80 code files and later applied to the system all at once. A more or less detailed message would be distributed (via electronic mail) outlining the changes in the new version. Problems and bugs were usually communicated verbally and not necessarily written down.

An informal applications ("goodie") library evolved where users placed Smalltalk-80 code files on a special file directory and announced the new goodie via electronic mail. Usually little or no documentation accompanied the announcement. The announcements were not systematically collected, so unfortunately there was not a satisfactory index of what was available.

These informal methods worked reasonably well due to the small number of people involved, and the relative simplicity of the changes being made. One of the disadvantages was that less urgent information, such as a small bug, was often forgotten. Another disadvantage was that no detailed record was kept of *why* a particular change or fix was made, and why it was done the way it was. Often the programmer is not even fully aware of his implicit design decisions. As a result, sometimes an important part of a change would be accidentally undone or interfered with by a later change.

## An Interim Development Support Mechanism

During one period of especially frantic development, we decided that some more formal mechanisms for dealing with documentation and system software were required in order to better support our needs for communication about our changing Smalltalk-80 system. One reason for this is that the Smalltalk-80 system is significantly larger and more complex than earlier Smalltalk systems. Software tools for manipulating this information would be very helpful and would be much less tedious than the corresponding manual methods.

Although we planned to create software within the Smalltalk-80 system itself for system development support, we started with a simple mechanism consisting of a minimum of automation in order to gain some preliminary experience. Fig. 15.1 is a diagram of the components of the interim support system, outlining as an example the submission of a bug fix report.

Initially we used an electronic mail system that was not part of the Smalltalk-80 system in order to enter and collect messages about the Smalltalk-80 system. Standard forms were used to send messages to a special " mailbox" (called "Smalltalk80Support") regarding bug reports,
<figure><img src="image_45.png" /><figcaption>Figure 15.1</figcaption></figure>

bug fixes, system changes, "goodies," or miscellaneous comments about the Smalltalk-80 system. Copies of these messages were also sent to a Smalltalk-80 users' group called "Smalltalk80Users." Fig. 15.2 shows the form used for submitting bug fixes. These messages were collected daily by a system maintainer in a number of mail files on a remote file server.

Subject: Smalltalk-80 Bug Fix: **ShortDescription**

To: Smalltalk80Support.PA

cc: Smalltalk80Users.t.PA

Source-File: [Phylum] < Smalltalk80Support > **FileName** .st

From-Version: **VersionDate**

Bug: **DescriptionOfBug**

Fix: **DescriptionOfFix**

Methods Affected:

**ListMethodsAffected**

Figure 15.2 Reviewer: **NameOfReviewer**

Messages regarding software submissions (e.g., bug fixes or goodies) contained the field *Source-File* indicating the name of a centrally-located file containing the source code. Periodically new versions of the system would be created based on the messages received. An electronic message would then be sent documenting the new version.

A simple user interface was created for browsing the message files from within the Smalltalk-80 system. The mail browser window shown in Fig. 15.3 has two parts. The top part is a menu containing the titles of the messages in the file. When the user selects a title, the corresponding message is displayed in the lower part, Fig. 15.4.
<figure><img src="image_46.png" /><figcaption>Figure 15.3</figcaption></figure>

<caption>Figure 15.4</caption>

This user interface also allows the Smalltalk-80 source code referenced by a message to be inspected or incorporated into the user's Smalltalk-80 system via additional pop-up menu commands. Fig. 15.5 shows the user invoking the browseSource command for the bug fix entry being viewed; Fig. 15.6 shows the file window obtained as a result. The user is not allowed to modify the message text or the source code.

## Detecting Conflicts Between Software Submissions

One of the problems encountered with this distributed approach to system development and maintenance is avoiding (or at least detecting) conflicts in work done by different people in parallel. The longer the time span between system releases, the more likely that incompatible conflicts will arise between system changes submitted by different
<figure><img src="image_47.png" /><figcaption>Figure 15.5</figcaption></figure>

<figure><img src="image_48.png" /><figcaption>Figure 15.6</figcaption></figure>

users. In the Smalltalk-80 system, this usually occurs when two programmers have modified the same Smalltalk method definition.

In order to help solve this problem, we developed a program for analyzing Smalltalk-80 code files and reporting the ways in which they conflict, i.e., by modifying the same method definition or other Smalltalk object. This approach works very well since most Smalltalk method definitions are very short and perform a very specific function. Whenever two or more submissions define the same method, all conflicting definitions are appended to a "conflict report" file. It is then up to the programmers involved to determine how to resolve the conflicts. Often one of the definitions can be chosen over the others. Otherwise a
new method must be written which merges or resolves the functionality of the conflicting definitions. No automatic conflicts resolution was attempted.

Although this tool is fairly crude, it has proven very useful for detecting and resolving at least some conflicts which otherwise would have gone undetected or surfaced later as annoying bugs.

## An On-Line System Development Database

After using the interim support mechanism for several months, we were ready to create a development support system within the Smalltalk-80 system itself. Since the Smalltalk-80 system did not then interface with the Xerox internal electronic mail system, one of the main disadvantages of the interim mechanism was that users were not able to submit reports directly from the Smalltalk-80 system. In addition to allowing users to submit bug reports and software submissions directly from within the Smalltalk-80 system, we wanted the new system to provide a Smalltalk-style user interface for browsing, adding to, and editing the system development database. Fig. 15.7 shows the components of the current support system involved in submitting a bug fix.

The new database, like the mail files of the interim system, resides in a number of data files on a remote file server, accessible to any running Smalltalk-80 system. Since the database is accessed by Smalltalk-80 systems rather than standard mail programs, we were able to automatically include additional information, such as cross references between related entries in the database.

<figure><img src="image_49.png" /><figcaption>Figure 15.7</figcaption></figure>
## Structure of the Database

The current version handler database is patterned strongly after the mail files used in the interim system. The database contains three kinds of entries: *system versions*, *bug reports*, and *system changes* (including bug fixes and "goodies"). Each entry has a unique ID, and a user supplied title and message body describing the entry. The system adds fields specifying the date and the version of the Smalltalk-80 system from which the entry has been generated. Additional fields may contain various status conditions of the entry. Most fields are stored as text in the header portion of the message; some special fields (e.g., whether an entry is new or old or has been deleted) are hidden from the user.

*System version* entries also contain the ID's of the *system changes* which differentiate the version from its predecessor. Thus a new version can be generated from some previous version by automatically incorporating the appropriate changes into the user's Smalltalk-80 image. Version entries also contain the ID's of all *bug reports* which apply to that version.

In addition to containing a description of the bug, *bug report* entries contain the ID's of available *system changes* that fix the bug.

*System change* entries contain the names of one or more remote files containing Smalltalk-80 source code. If the change fixes a reported bug, the change entry also contains the ID of the corresponding bug report entry. No firm distinction is made between submissions which are actually changes or fixes to the Smalltalk-80 system and arbitrary user applications (i.e., goodies). Some changes get incorporated into later versions of the system while others simply remain in the database for optional retrieval.

The database is maintained by a special object, named *VersionHandler*, which is in every Smalltalk-80 system. The *VersionHandler* object acts as an interface to the actual database stored on a remote file server. It is responsible for reading and writing portions of the database and coordinating access among multiple Smalltalk-80 systems.

## A Browser Style User Interface

The user creates Smalltalk windows for accessing the database by sending Smalltalk messages to the *VersionHandler*. The top level commands available to the user for accessing the database include:

* Open a version browser
* Submit a bug report

* Submit a bug fix

* Submit a software goodie

* Create a new system version

Fig. 15.8 shows a workspace containing the Smalltalk messages used to invoke these commands.

<figure><img src="image_50.png" /><figcaption>Figure 15.8</figcaption></figure>

Each of these commands causes a new window to be created. There are three kinds of database browsers for the three kinds of database records: version browsers, change browsers and bug report browsers. These browsers differ only in their contents and the command menus they provide. Fig. 15.9 shows a version browser in which the user is selecting the browse changes command. Fig. 15.10 shows the changes browser created as a result of the selection.

Fig. 15.11 shows the command menus provided by each kind of browser. Selecting browse changes creates a browser on the changes which make up the version. The browse goodies command creates a browser on all changes which are *not* included in the current version. This is equivalent to searching an applications library of user programs and optional system enhancements. The retrieve version command is useful if the version of the Smalltalk-80 system one is running is not the most recent. By selecting retrieve version, the user can upgrade the system. The system then automatically retrieves all the required changes.

The browse source files and file in changes commands in the changes browser are similar to the special commands provided by the interim mail browser. File in changes allows a user to incorporate a bug fix or other change into the Smalltalk-80 system.
<figure><img src="image_51.png" /><figcaption>Figure 15.9</figcaption></figure>

<caption>Figure 15.10</caption>

Fig. 15.12 shows the window obtained by selecting the browse bugs command. Unlike the interim mail browser, the text description associated with an entry may be modified by simply editing the text which appears in the database browser. Fig. 15.13 shows the user selecting the file in changes command in order to try out an experimental change to the Smalltalk-80 system. The goodie browser shown was obtained by selecting the browse goodies command in the version browser.

<figure><img src="image_52.png" /><figcaption>Figure 15.11</figcaption></figure>
<figure><img src="image_53.png" /><figcaption>Figure 15.12</figcaption></figure>

<figure><img src="image_54.png" /><figcaption>Figure 15.13</figcaption></figure>

## Creating Database Entries

There is also a special window used for creating each kind of database record. The user sends a Smalltalk message to the VersionHandler requesting to submit a bug report, bug fix, goodie or new system version. In response, a new window is created that contains a form for the user to fill in. The entry is added to the database when the user selects the accept command.

Figure 15.14 shows the window for creating a *system change* entry which fixes some known bug. The lower half of the window contains a bug report browser. The user selects the titles of the bug reports which he has fixed. Before selecting accept, the user also fills in a title, his name, and the name of the Smalltalk-80 code file he has already created.
The user can submit changes or goodies which are not bug fixes using a window which resembles just the top half of the bug fix window. Bug reports are also submitted using a similar window.

<figure><img src="image_55.png" /><figcaption>Figure 15.14</figcaption></figure>

<figure><img src="image_56.png" /><figcaption>Figure 15.15</figcaption></figure>

Fig. 15.15 shows a new system version being created. This is done by selecting from a menu of the system changes (goodies) submitted since the last version. A conflict detection program can then point out possible conflicts between the selected changes. (This is currently not done automatically.) The ID's of any bugs which have not been fixed by the selected changes are inherited and included in the new version. Whenever a new version is created, the source files involved are automatically copied to a new sub-directory on the file server to freeze and preserve the integrity of the new Smalltalk-80 system. The new system may be released as a new image file, or, due to the large overhead of
generating an entire system, it may be left as an *interim release* which can be quickly generated from a previous image version each time it is used.

Fig. 15.16 is a diagram of a portion of the database. Bug reports are shown in the first column with lines connecting them with entries for corresponding fixes, if any. The second column shows the changes (including bug fixes) which have not yet been incorporated into any version; these make up the "goodies" application library. The third column shows changes entries connected by lines to the versions in which they have been incorporated. The rectangular boxes denote image versions, while the large ovals are interim release versions. The links between version entries and bug reports are not shown. When the next version, V9, is created, the changes C21, C22, and C23 will no longer be considered "goodies."

<figure><img src="image_57.png" /><figcaption>Figure 15.16</figcaption></figure>
## Conclusion

The system version database has proved to be a very useful software tool for managing and maintaining our Smalltalk-80 research system. It has provided us with a convenient mechanism for documenting versions of the Smalltalk-80 system. Each change made to the system has a corresponding entry in the database. This provides a complete history of the system's evolution. The most popular feature is that users may submit or browse bug reports directly from their Smalltalk-80 system. The database also provides a software applications library which may be easily accessed and augmented.

<figure><img src="image_58.png" /></figure>
# Implementing a Smalltalk-80 File System and the Smalltalk-80 System as a Programming Tool

D. Jason Penney*

Tektronix, Inc.
Beaverton, Oregon

## Abstract

The Smalltalk-80 system may be used without any file system, but a number of its features presuppose a working file system. Work must be done to effect a file system on a new Smalltalk-80 implementation. This paper describes the design and implementation of the file system for a Tektronix Smalltalk-80 implementation and concludes with some reflections on the use of Smalltalk-80 as a programming tool.

## Background

The Smalltalk-80 system is designed to be host machine independent. The system uses files, but file systems tend to rely on the idiosyncrasies of a particular host. Thus the Smalltalk-80 virtual image can support files for a new implementation in an abstract manner. Higher-level methods in the system usually deal with files throughindeed, a subclass of ReadWriteStream. Files themselves have their functionality partially separated out into abstract classes File, FileDirectory, and FilePage. Fig. 16.1 shows the superclass relationships of these classes.

<footnote>*Mr. Penney is currently employed by Servio Logic Corp., Portland, Oregon.
Copyright © Tektronix, Inc. 1982. All rights reserved.</footnote>
<figure><img src="image_59.png" /></figure>

The virtual image contains the details of one implementation in the "concrete" subclasses of File, FileDirectory, and FilePage; to wit, AltoFile, AltoFileDirectory, and AltoFilePage.

Implementors could implement the primitives these classes require, reimplement subclasses of the abstract classes, or start from scratch. The Alto classes presuppose a particular kind of disk and disk controller, as well as the existence of system utilities to manage the disk. Starting from scratch would require reimplementing, which is the interface class for all file manipulation in the system. We eventually chose the second approach, creating TekFile, TekFileDirectory, and TekFilePage.

## Description of Chosen Problem

Class distinction divides files into fixed-length chunks of bytes, called a FilePage. FilePage is intended to map directly to page-oriented media. A FilePage is associated with a File, and has additional state such as the page's pageNumber in the file, actual number of bytes used on the page, and a hardware-related address.

A File contains such things as where to find its FilePages and the String that represents the file's name. When the file is open, some of its state is cached in the File instance.

A FileDirectory contains the necessary information to access all the files within a given directory. It responds to some Stream messages such as reset and next (but not atEnd). A FileDirectory can iterate over all of its files (with do: but not reverseDo:). A FileDirectory keeps some of its state in object memory when it is open, hence it responds to state-caching messages (open, close, and flush).
Alternate Programming Approaches

At Tektronix we did not have the luxury of an existing file system on our Smalltalk-80 hardware. Thus it was not appropriate for us to try to emulate the Alto file system or to make another existing file system work on our hardware and map into the Smalltalk-80indeStream class.

Since our virtual machine was originally implemented in Pascal, we briefly considered writing the file system itself in Pascal and providing a minimal interface in the Smalltalk-80 system. The disadvantage in this approach is that the resulting file system would be largely opaque to Smalltalk-80 inspectors and debuggers. Instead we chose to design, implement, and test the file system using Smalltalk and a small number of disk primitives.

Design Constraints

Our primary constraint was that the file system had to be simple, debuggable, and maintainable, so that we could use the file system in a short amount of time.

The Alto file system puts enough redundant information on file data pages so that a "scavenger" can recover significant amounts of a disk after a disk crash. We felt that this should be in our own file system.

Since the Smalltalk-80 source file system manipulates one very large file, it is necessary to be able to find the address of a specified page number in the file with relatively little effort. In other words, the file system should have reasonable performance for random access as well as sequential access.

Design Approach

Abstract class FilePage allows a chunk of data bytes to be sandwiched between a non-data header and trailer of a specified (possibly zero) length. We use a header in TekFilePage to describe the data bytes on the page. Since our disk driver does address checking and data checksumming, we did not include these in the page header. The page header does however, have redundant information (file serialNumber, file pageNumber, previous page's address, next page's address) as well as necessary state (size of data in bytes). Fig. 16.2 shows the organization of a TekFilePage.

Instances of a concrete subclass of File are supposed to "open" themselves when issued the message findLastPageNumber. Since the last page number (and the address of the last page) are quite useful for appending a new page to the end of a file and truncating a page from the end of an existing file, our concrete instances of TekFile have lastPageNumber and lastPageAddress as additional information for an open file.
<figure><img src="image_60.png" /><figcaption>Figure 16.2</figcaption></figure>

*The Smalltalk-80 System's Role in Initial Design Effort*

Our first descriptions of file system design presupposed using Pascal. Pascal will handle certain types of data structures (such as 32-bit machine integers) more gracefully than the Smalltalk-80 system will. Pascal encourages fixed-length data typing. Sometimes this is acceptable, since FilePage pages are fixed length. On the other hand, a file name is merely a String of arbitrary length, which is not convenient at all with Pascal data structures. For this and other reasons, we chose to use Pascal for only the disk primitives.

*Directory Design*

Since we were free to design the directory in any way, we chose to implement it as a sequential file in the format shown in Fig. 16.3. This format allows the directory to be human readable as well as readable by Smalltalk-80 classes. Many Smalltalk-80 classes support a self description facility through the selectors readFrom: and storeOn:. These selectors do their work on an accompanying Stream in a human-readable as well as Smalltalk-80-readable form. Since a FileDirectory is expected to deliver up a sequence of files in a Stream-like fashion, a Smalltalk-80 directory can be naturally envisioned as a FileStream that has a sequence of file definitions.

* ('Directory',1,1,12,2567462400,41166,2567462400,41166,11)

* ('FreeList',0,1188,1260,2567462400,41166,2567462400,41166,1)

* ('Smalltalk80.sources',2,1242,1259,2567462400,41242,2567462400,60378,13)

Items for each file are in order:

1. filename, a String

2. serialNumber, an Integer

3. lastPageNumber, an Integer

4. firstPageMap, an Integer

5. creationDate, seconds since 1 Jan 1901

6. creationTime, seconds since midnight

7. modificationDate, seconds since 1 Jan 1901

8. modificationTime, seconds since midnight

9. lastPageAddress, an integer

<caption>Figure 16.3</caption>
Design Details

Our hardware provides random access to a variable number of "sectors" 1024 bytes long. There is exactly one TekFileDirectory for a medium. The exact number of sectors available for each medium is available through a primitive.

Each "medium" may have bad sectors—i.e., ones that the device drivers will not handle without raising error conditions. One sector at a fixed address is presupposed to be good. This sector with its prespecified address is called a "leader"; it provides information about the medium as a whole.

Each sector on a medium (including the leader) is treated as a TekFilePage. A TekFilePage has a 24-byte "header" and 1000 bytes of data. "Data" refers to bytes that are handled by Stream messages next and nextPut.

The header on a TekFilePage contains a back pointer to the previous TekFilePage within a file (or a nil-address if none), a pointer to the next TekFilePage within a file (or nil), the serial number of the page's file, the ordinal page number of this page in its file (i.e., "1" for the first page in a file), and the number of data bytes that are actually in use on this page (the size). All pages in a file except the last one are guaranteed to be full.

The header information in a TekFilePage is, strictly speaking, sufficient to completely recover files on a crashed disk. Exceptions to this are lost sectors containing file data and some information in the directory file such as creation/modification date and the String used for the file name. On the other hand this is not enough information to allow rapid nonhomogeneous access to a file, such as is required by the Smalltalk-80 browser. To accomplish this an extra data structure is written with each file in the system: pageMap pages. Fig. 16.4 shows the organization of secondary structures on a medium.

<figure><img src="image_61.png" /><figcaption>Figure 16.4</figcaption></figure>
The directory entry for a file specifies the address for the first pageMap for that file. A file always has at least one pageMap page. A pageMap is forward- and reverse-linked with other pageMaps. Its serialNumber is the same as the one used for the FreeList file, so that a disk scavenger will not confuse it with data. The pageNumber field of a pageMap page is not used in practice. A pageMap contains 250 4-byte addresses in its data section, each address corresponding to the appropriate page in a file. For instance, if one wished to read the 300th page in a file, one would read the first pageMap for the file, use the forward-link in that pageMap to read another pageMap, and read the 50th address in that pageMap to determine the correct address for the 300th page in the file.

As files are created on a given media, they must be given unique serialNumbers. The next available serialNumber is written on the leader page, using Integer storeOn:. The leader page's forward-link points to the first pageMap page of the file which is the Directory file.

The first two file definitions in a directory file are special: The first is the directory file itself (named "Directory") and the second is a relatively large file that occupies all the unused pages in the system (named "FreeList"). Both of these files are bona fide in the sense that they have a serialNumber and a complete set of pageMaps. The serialNumber of FreeList is zero, which signifies non-data. For the sake of consistency, FreeList's "data" pages are fully linked just like all other files in the system.

## Implementation Approach

There is a bootstrap problem involved with implementing a file system. The source code for the new classes must be typed in by hand. The physical media must be formatted with a Directory and a FreeList. Once the file system is up and running, the very large file that contains the commented sources for the system must be converted to reside on the new format. Finally, one must recompile the file system methods, adding comments and regenerating variable names.

Typing in the new classes was irritating but not difficult on our implementation. If one's interpreter runs at 3500 bytecodes per second, keyboard echo requires three to five seconds. Our virtual image had a built-in performance problem that additionally delayed keyboard echo. Since there is no source code system, all the new and untested methods lack argument variable names, temporary variable names, and comments.

None of the file system could be tested until all necessary methods were typed in and initialization code written to properly initialize a new media. The debugging itself will be described later.
Converting the source code to the file system format turned out to be easy but time consuming. Our system already has software for saving and restoring memory images on our disk media. We split the source file into manageable chunks, converted the ASCII text to a downloadable image (as if the text were executable processor code), and saved the resulting memory-images on floppies using the existing non-file system format. A small bit of code in a workspace was necessary to read bytes off of a bogus *TekFilePage* onto a legitimate * fileStream*, and a very large amount of time was necessary for the conversion (about 11 hours).

*Managing
Windows*

Before implementing the file system, we were familiar with the Smalltalk-80 user interface, but we had only superficial experience with it. Each of us had his favorite snapshot with his windows placed just the way he liked it, but our interaction with the system was casual. We typically would execute selected examples to show to visitors or compose short methods to answer specific questions.

When we started the file system project, our placement of windows underwent metamorphosis. The old arrangements changed as new things came to light. For instance, the only kind of browser that we ever had at first was a full five-pane System Browser. These are useful because of their full generality. Unfortunately five panes take up a lot of room on our 512 x 512 display, which in turn means that less of each method ends up visible in the code pane. Since all of the code that we were entering belonged in a single class category, "Files-Tektronix," we quickly collapsed the System Browser and kept a Class Category Browser instead, which has proportionately more room in the code part of the browser.

Our typical display had a System Category Browser and a Workspace to do development work in. A System Transcript, a collapsed System Browser, and a collapsed System Workspace were kept off to the side. At first we did not overlap the Category Browser and the Workspace. After a little bit of use we reframed these two windows so that they did overlap substantially. Since we typically moved between the two windows, making changes in one window and testing the changes in the other, it was not necessary to see all of both windows at the same time. This was a significantly better use of display space on our system.

*Using the Browser*

The Browser worked pretty much as advertised. We added our classes without any difficulty, but when we finished, we discovered that we had misspelled an instance variable name. Several methods later in that class, we decided to change the class definition. Much to our surprise, when we changed the spelling of the instance variable, we did not get any syntax error messages while the class was being recompiled. If we had attempted to change the order of the instance variables, the actual
roles of the instance variables would have reversed. This is because the decompiler used the new instance variable names rather than the old.

The method category pane of the browser, which provides categories of methods within a given class, was originally a nuisance. We chose to ignore it initially. An odd thing was that as long as we added methods to a new class, the selection in this pane read "no messages" but if we switched to another class and back, the selection would then change to "As yet unclassified".

## Using the Editor

In general the text editor was a joy to use: all basic editing operations conform nicely with user intuition. Some features are not intuitive, but neither are they difficult to learn. For example, using control-F for "ifFalse:" or control-[ for inserting "[]".

We used a full-ASCII keyboard on our implementation, which caused a special set of problems using the editor. Some of us were initially perplexed about how to type the back-arrow assignment symbol which is pervasive in Smalltalk-80 code: it turns out that this maps into the ASCII underscore character. A more serious problem was presented by the unencoded keyboard interface. Xerox uses an unencoded keyboard for their own Smalltalk-80 systems. An unencoded keyboard reports only key-up and key-down activity on the keyboard. An unencoded keyboard is closer functionally to a piano than a typewriter.

Whereas an unencoded typewriter keyboard provides greater flexibility than a conventional encoded-ASCII keyboard, they are less common. Our Smalltalk-80 hardware uses a readily available encoded-ASCII keyboard. The way Xerox has written InputSensor and InputState gave us a little grief. We were unable to force a user interrupt with the control-C character simply because no one at Xerox thought it would be possible for a keyboard to generate a control-C character without causing a control-key event. Thus when one types a control-C on an untuned Smalltalk-80 system with an encoded keyboard, one gets a garbage character instead of the expected Notifier. The unencoded keyboard also manifests itself as a problem with such things as control-0 through control-9 (used for changing fonts), and control-[ (which is different from ASCII ESCAPE). Although the encoded keyboard was suitable for use with the Smalltalk-80 system, the control-C problem caused us grief when we were debugging the file system.

## Using the Debugger

The debugger has done more to spoil us than any other single feature in the user interface. All aspects are fully integrated. It was never necessary for us to go to machine-level debuggers or anything else in order for us to fully debug the file system.

The interpreter simulator, invoked whenever one selects "step" or "send", runs about 1000 times slower than the machine interpreter. On our system this meant that the simulator ran at an effective 3 or 4 bytecodes per second. On at least one occasion we accidentally started
the simulator only to determine afterward that we would have to wait
longer than the MTBF of our hardware to allow the simulation to com-
plete.

## Typical Programming Problems

During the course of "accepting" methods into the system and testing
our resulting code, we ran into a series of problems familiar to every
programmer. In our estimation, this is the part of the Smalltalk-80 sys-
tem that must distinguish itself: from a productivity standpoint, the
amount of time that it takes to effect an application and the resulting
reliability are paramount indices into a workbench's success.

### Syntax Errors

Syntax errors on any system have a fairly limited number of causes, in-
cluding user unfamiliarity and "cockpit errors". Those of us accustomed
to higher level languages such as Pascal or Modula-II are familiar with
a definite syntax phase when entering new program text. Such strongly
typed languages attempt to limit certain kinds of errors by making a
large number of static checks on the program text. The Smalltalk-80
compiler makes relatively few static checks. It does little or no semantic
checking. Abnormal conditions are left to the objects involved during
execution to report. This is all right in principle, but there are some se-
mantic checks that the compiler does not do which could theoretically
be done.

One syntax error that occurred early on is worth mentioning. When
one writes a Smalltalk-80 conditional expression, it will look something
like

3 frob ifTrue: [11]
    ifFalse: [12].

However, if one wishes to code a `whileFalse:`, one might be tempted to
type

3 frob '' creates syntax error ''
    whileFalse: [4 frob].

This latter construct gives a syntax error because the compiler requires
the receiver of a `whileFalse:` to be a literal block. Thus the correct syn-
tax for a `whileFalse:` using the previous example would be

[3 frob] whileFalse: [4 frob].

Once the novice user has discovered this, he may be tempted to write
[3 frob] '' gets by compiler but doesn't work''
ifTrue: [↑1]
ifFalse: [↑2].

The compiler will accept this without complaint because it makes no re-
quirements on the receiver of an ifTrue:ifFalse:. However, when this
method is executed the response is a mustBeBoolean notifier, because
the receiver is a block instead of a boolean.

Off-by-One Errors

Programming languages that allow indexing data structures open
themselves up to off-by-one errors. Smalltalk-80 is such a language. The
first item in a Smalltalk-80 indexable collection is indexed by one in-
stead of zero. Some of us have grown accustomed to programming with
adjustable-offset indexes, which resulted in three off-by-one errors in
our initial attempts.

Learning Curve

As with any problem, there is a "learning curve" involved with ap-
proaching a novel situation. In implementing the file system, we tra-
versed learning curves involved with file systems, disk hardware, and
the Smalltalk-80 system itself.

Familiarization with the abstract and concrete implementations of
File took a significant amount of the time necessary to implement the
file system. After that, there was a certain amount of raw familiariza-
tion that had to take place. For instance, is the correct selector to ap-
pend an object to an OrderedCollection addLast: or lastAdd?: (The
former is correct). Also, several times we discovered that we had made
inefficient use of existing methods.

Once we discovered that although we could add and update files
properly, we could not delete them from the directory. Closer examina-
tion revealed that close-ing a FileStream does not necessarily entail
shorten-ing a FileStream. In other words, there were indeed occasions
where hidden functionality of the supplied building blocks caused prob-
lems.

After we had corrected most of the rudimentary syntax and design
errors, a peculiar snag came to light. The system returns self from a
message in absence of some particular result that is expected. This is
reminiscent of the difference between procedures and functions in more
traditional languages. Unfortunately, unlike functions, a Smalltalk-80
method can rely on "self" being returned from a message. This caused a
problem for us when the documentation for the abstract file classes
specified no particular result for TekFile read:. It turns out that this se-
lector is supposed to return the TekFilePage that it reads, not self. The
error that resulted from this misunderstanding was a doesNot-
Understand: message quite removed in time and execution from the ac-
tual source of the error.
## Design Errors

After the first several hours of debugging, the remaining errors in the system were all in our design. There were such things as Disk (a TekFileDirectory) telling itself to close in the midst of closing itself. There were some problems involving managing the pageMaps, particularly on larger files.

Since problems in this category go directly back to the definition and solution of the actual problem to be solved, these problems must reflect the programmer/analyst more than the system itself. The impressive part of the Smalltalk-80 system's performance in this regard is that the turnaround from clerical, syntactic, and learning curve errors back to design errors occurred quickly, even though the system itself was slow.

## Summary/Conclusions

Design and implementation of concrete subclasses for the file system took 43 hours over the space of two and a half weeks. A large part of this time reflects the speed of our implementation as opposed to programmer time.

At the end of this time all of the higher file-related functions in the system worked perfectly. Most debugging problems were due to our incomplete understanding of the Smalltalk-80 system.

One measure of success of a workbench is the quality and applicability of the tools that it offers. Our experience with workbenches in general is that if a tool indeed exists for the problem at hand, its interface is poorly documented and its behavior erratic if not outright destructive. This is the first workbench we have ever used in which we are willing —albeit reluctantly—to use new and unfamiliar tools that are already available. The integration of tools in the system is so complete that the apparent reliability of higher level system components (such as browsers and debuggers) is enhanced.

Like any large software system, the Smalltalk-80 system has its share of bugs. By and large, bugs tend to remain isolated, although a bug in a widely used component will have significant repercussions throughout the system. To this extent the full integration of the system is a double-edged sword: although compactness and ultimate reliability are aided, one is also able to make changes that blow up the system. Then again, the system uses snapshots and transaction files to help a user regain his work in the event of a system crash.

Our final judgment is that yes, the Smalltalk-80 system is a good programming tool. It would be simplistic to cite a single reason for our decision, but one of the salient strengths of the system is its high reliability and useability.
# Implementing a Smalltalk-80 System on the Intel 432: A Feasibility Study

Guy Almes

Alan Borning

Eli Messinger

Department of Computer Science

University of Washington

Seattle, Washington

During autumn 1981, the authors carried out a feasibility study on the implementation of the Smalltalk-80 language on the Intel iAPX 432. This report presents the conclusions of that study, together with supporting technical material.

Briefly, a Smalltalk implementation on the 432 would result in several important advantages over Smalltalk on conventional computers. These advantages include support for multilingual systems and for parallelism, including parallel garbage collection. There are also however, some corresponding disadvantages that could prevent a Smalltalk implementation on the 432 from being competitive with implementations on conventional computers. These disadvantages include large storage overhead per object, very heavy loading of the parallel garbage collector, and the possibility of insufficient microcode space. These difficulties can probably be surmounted; some approaches to dealing with them are discussed below.
## Introduction

This report describes an effort to study the feasibility of a Smalltalk-80 implementation on the Intel 432. The main body of the report is divided into three parts:

* The potential benefits of a Smalltalk-432 system.

* The principal threats to the feasibility of Smalltalk-432.

* A sketch of an implementation of Smalltalk-432.

A final section presents some conclusions and recommendations for further study.

## Background

We assume that readers of this report are acquainted with the Smalltalk-80 system. However, not all readers will know about the Intel 432 processor, so in this section we give a brief description of the features of the 432 that are particularly relevant to the task at hand.

The Intel iAPX 432 is a 32-bit microprocessor. It is designed to be a processor for Ada; however, as we shall see, with suitable modifications it may be an effective Smalltalk engine as well. Physically, the 432 consists of a two-chip general data processor (GDP) and a single-chip inter-face processor (IP). Standard I/O functions are handled separately by one or more attached processors, which will typically be Intel 8086s. The basic clock rate is 8 MHz. The 432 chips include microcode in read-only memory; there is no user-modifiable microcode.

The 432 supports an object-oriented environment (although the meaning of "object" is not the same as in Smalltalk). A 432 object is a contiguous segment of memory, up to 64K bytes in length, containing data and addresses. There can be up to $2^{24}$ segments in a system. Each segment has a type, which determines the operations that can be performed on it. Addresses for these segments are called access descriptors, and are protected addresses very similar to capabilities on systems such as Hydra$^{1,2,3}$. Two fields totaling 24 bits contain the unique identifier for the object, 1 bit indicates whether the 32 bits in fact constitute a valid access descriptor, and each of the remaining 7 bits indicates whether the owner of the access descriptor has a given right for the segment in question. These rights include "read rights" (can parts of the segment be examined?), "write rights" (can the segment be modified?), and "delete rights" (can the access descriptor be deleted or overwritten?). Every access to a segment is checked automatically to see
that the possessor of the access descriptor has the required rights, and
that the access is within the bounds of the segment. The hardware and
microcode makes a distinction between data and access descriptors, so
that it is not possible to inadvertently treat 32 bits of data as an access
descriptor or vice versa.

The 432 is designed for multiprocessing. Many 432s can be connected
to a common memory, the maximum being determined by electrical
rather than logical characteristics. Within the common memory, *process
objects* represent tasks requiring servicing, and *processor objects* are the
representatives of the physical processors. This representation makes it
easy to add new processors without the need for making software modi-
fications.

Interprocess communication is handled by a *port* mechanism. A given
process can send an access descriptor for a message segment to a port
object, which can be received by any process with an access descriptor
for that port.

Objects can be allocated from a global heap or on a local stack. Par-
allel garbage collection for heap-allocated objects is supported. Using
Dijkstra's parallel garbage collection algorithm, objects are marked as
"white" (possibly inaccessible), "black" (accessible and traversed), or
"gray" (accessible but not traversed). The hardware supports parallel
garbage collection by marking each white object as gray when a pointer
to it is copied. A software garbage collector, running as a 432 process in
parallel with other processes, handles the rest of the work.

Papers on the 432 architecture have recently appeared in the litera-
ture. These include papers describing the port system⁴, the structured
address space⁵, and the structure of the operating system⁶.

## Approaches to Running Smalltalk on the 432

There are a number of possible ways to run Smalltalk on the 432. The best approach is probably to make a Smalltalk object be the same as a 432 object (in general), and to modify the microcode of the 432 to allow it to execute Smalltalk bytecodes directly. A system that used this chip would include both Smalltalk processors (STPs) and ordinary Ada GDPs.

In the remainder of this section, we describe some of the alternatives
and indicate why the above approach was selected.

It would be very convenient to run Smalltalk on the 432 without
modification to the chip. One way of doing this would be to allocate a
set of 64K-byte 432 data segments to hold Smalltalk objects, and to
handle Smalltalk object allocation and deallocation independently of
the facilities provided by the 432. This may in fact be the best way to
run Smalltalk on the 432 as it exists. However, if this is the case, then
the 432 is just being used as a rather slow conventional processor, with
no use being made of its special properties. If this is the best that can
be done, it would be better to select another processor.

A more attractive alternative, still using an unmodified 432, would
be to identify Smalltalk objects and 432 objects. There are two possibili-
ties for storing Smalltalk code: writing an interpreter for the present
bytecode set, or changing the Smalltalk compiler to emit mixed native
432 code and subroutine calls. We suspect that a software interpreter
for the present bytecode set would be quite slow. Nevertheless, such an
interpreter should be developed for at least two reasons:

* It might turn out to be acceptably fast.

* Even if it is too slow, it will yield valuable experience that will in-
form the eventual Smalltalk processor design. Specifically, it will
show how well the Smalltalk object to 432 object mapping works.

Once this interpreter is built, its designers will be able to judge the ex-
tent to which such an implementation is competitive with other
Smalltalk-80 systems.

Another alternative would be to mix native 432 code and subroutine
calls. A severe disadvantage of doing this is that there will be an enor-
mous expansion in code size, probably by 5 to 10 times. This expansion
would be acceptable only if done for those methods most frequently exe-
cuted. If a small set of very frequently executed methods can be identi-
fied, either statically or dynamically, then this set might be a candidate
for such expansion.

We are thus led to consider producing an additional 432 processor
type. In addition to the present Ada GDP and IP processors, there
would be a new Smalltalk processor (STP) designed as a modification of
the present Ada GDP processor. Our approach is to try to modify only
one of the two chips, by making changes to the microcode stored in its
ROM and in its PLAs. Again, we make Smalltalk objects and 432 ob-
jects be the same, since not doing so would lose whatever advantages
the 432 has over a conventional chip. The advantage of this approach is
that it is faster than other approaches; a disadvantage is that it does
not allow its implementors to change the interpreter or bytecode format
without replacing the processor chips.

## Benefits of Smalltalk-432

The implementation of Smalltalk on a 432 would yield many benefits. Some of these benefits improve the performance of the system, while others make a Smalltalk system on the 432 qualitatively better than Smalltalk systems on conventional machines.
## Support for Large Numbers of Smalltalk Objects

One of the most important benefits of implementing Smalltalk on the 432 would be its ability to handle systems of more than 32,000 objects. Most existing Smalltalk implementations use 16-bit words for pointers, and one bit is effectively lost in implementing Small Integers. It should also be pointed out that a 432 implementation would share this benefit with any other implementation with a large address space; an implementation on the Digital Equipment Corp. VAX, for example, can support similarly large numbers of objects.

Since the Smalltalk system moreover, is well suited for large advanced applications, this benefit could be crucial.

## Support for Communication with non-Smalltalk Programs

The design of the 432 system seems to lend itself particularly well to the idea of a multi-lingual system. With Smalltalk and, for example, Ada processes agreeing on the "432 protocol," communication between them can be done.

A Smalltalk processor and a general Ada processor would have the same notion of what 432 objects and messages are. Thus processes running concurrently in different languages would be able to share memory, and send messages to each other through 432 ports. No existing Smalltalk implementations support such a multi-lingual system. The Dolphin and Dorado systems at Xerox PARC, for example, run either Smalltalk or Mesa, but never both within the same processor. This is due in part to conflicting technical requirements of Mesa and Smalltalk runtime environments.

## Support for Parallelism

One of the primary advantages of a 432-based Smalltalk system would be support for parallelism. As described in the introduction, the 432 environment includes process and processor objects. Instances of the Smalltalk class Process can be mapped in a straightforward way onto the 432 process objects, so that in a system with multiple STPs, Smalltalk processes could be executed in parallel.

There are a number of relatively simple ways of exploiting this parallelism:

* When filing in a class definition, each method is compiled separately. It would be easy to make each of these compilations a separate process, thus speeding up filing in considerably. The only synchronization needed would be a lock on the method dictionary when a new method was being inserted.

* There are a number of messages to dictionaries for doing searches for example, to find all classes that implement a method for some selector, to find all methods that invoke a given selector, to find all references to a symbol, and so forth. All these searches could profitably employ parallelism.

* Parallelism could also be used in graphics. When displaying a paned window, or updating several windows, each pane or window
could have a separate process to display it. When displaying an elaborate image, the display method could divide the work among several processes. In general some synchronization between the subprocesses would be necessary, but in many cases (e.g., when the subimages were nonintersecting, or when they were or'd together to form the entire image) the subprocesses could proceed asynchro- nously.

There are other applications for which parallelism would be valuable, but its use would require more sophisticated synchronization tech- niques. In simulations for example, it is sometimes useful to have one process perform the simulation, and a separate viewing process to dis- play snapshots of the simulation's state.

### *Support for Virtual Memory*

Because a virtual memory scheme is in the design of the 432 system, it will automatically accrue as a benefit to the Smalltalk system. This will be especially important for applications with large numbers of objects. The quality of the iMax virtual memory mechanism will be very impor- tant for the quality of the Smalltalk implementation.

Similarly the parallel garbage collector, which is to be part of the stan- dard 432 system, will also benefit the 432 Smalltalk implementation.

### *Support for Parallel Garbage Collection*

Because a storage manager will not have to be written anew for the Smalltalk virtual machine, the task of implementation will be simpli- fied. Also, because the garbage collector—as opposed to reference counting techniques—will be able to collect circular structures, Smalltalk users will not have to break loops explicitly to deallocate them. (An anomaly of the Smalltalk object representation called "soft fields" requires modification to the garbage collector. The soft field technique is used to add a pseudo field to instances of some class. Soft fields are implemented through the use of a global dictionary whose entries contain a pointer to an object, paired with that object's soft field. The problem then is that an object whose sole reference is from the soft field dictionary is in fact garbage. Given the large overhead per object already present, one might prefer to add a real field to Object to point to a list of backpointers. This would remove this special case in the garbage collector, at the cost of 4 more bytes per object.)

A scheme is planned for iMax that would allow 432 objects to be filed away in an archival format, onto external memory⁷. Thus Smalltalk ob- jects could be stored and later retrieved from secondary memory after an arbitrary amount of time. This scheme would allow Smalltalk pro- grammers a more flexible facility than the saving of entire work-spaces.

### *Support for Object Filing*
## Threats to Smalltalk-432

The Smalltalk-80 implementation on the 432 seems to be feasible, and due to the advantages cited above would result in a qualitatively better facility. There are several potential problems however, with the mapping of Smalltalk onto the 432 which could make the performance of the resulting implementation unacceptable. At this point we do not believe that any of these threats is fatal, but they do serve to focus our attention on the real issues in the rest of the study.

## Storage Overhead

Release Three of the 432's architecture incurs an average storage overhead of approximately 24 bytes per object. This breaks down as 16 bytes for the object descriptor, and a minimum of 8 bytes for the "memory image." On the other hand, in the model implementation of the Smalltalk-80 system, there is only an 8-byte overhead per object; similarly, the LOOM implementation has 14 bytes of overhead per object (see Chapter 14).

Statistics show that the initial Xerox Smalltalk virtual memory contains approximately 20K objects (including 4K method objects), with a mean size of 20 bytes. However, since the 432 implementation would use 32-bit object pointers (as opposed to 16-bit pointers on the Xerox systems), the average object size would increase. At one extreme, where no Smalltalk object contains a pointer to another object (e.g., strings), the average size would remain at 20 bytes; at the other extreme, where all Smalltalk objects are composed solely of pointers to other objects, the average size would double to 40 bytes. Clearly the true average lies somewhere in between. For the basic Smalltalk system, Ballard (see Chapter 8) found that its size increased by 50% when going from 16 to 32 bit pointers, implying that the average object size increased to 30 bytes. For a big application program with more data than code, the average number of bytes per object might be somewhat larger.

Regardless of the average object size, the overhead remains 24 bytes per object. Thus a system of 20K objects would incur approximately 0.5 Mbytes of overhead for about 0.6 Mbytes of objects. (Assuming here an average object size of 30 bytes.) Also note that the 20K objects figure is only for the Smalltalk system itself. A reasonably large application, which takes advantage of the 432's ability to support more than 32K objects, might use upwards of 100K objects, thus making the overhead about 2.5 Mbytes for 3.0 Mbytes of objects.

It is thus clear that the Smalltalk-80 system on the 432 is practical only with a virtual memory system; otherwise the number of objects that could be used would be so restricted that one would lose all the advantages of moving from 16-bit to 32-bit pointers.

Also, even with virtual memory, the large per object storage overhead will increase the amount of real memory required to support a
given working set of Smalltalk objects. This increases both the cost of a given hardware configuration and the amount of disk traffic due to swapping. The user should certainly not be forced into a constrained style of programming where she or he becomes wary of using too many objects; this would be very destructive of good Smalltalk programming style. Any way that is found to reduce the storage overhead of 432 object descriptors or memory images would certainly benefit Smalltalk. However, even if the 24 bytes/object overhead is regarded as a fixed parameter of the 432, there are other things that can be done to reduce the total overhead in a Smalltalk system.

One technique would be to represent some Smalltalk objects in other ways than as full-fledged 432 objects, for example, by embedding their representation in a pointer rather than storing it separately as a 432 object. Small integers are a prime candidate for such a representation, but other objects could be so represented as well. This topic is discussed on p. 316 below.

*Insufficient*
*Microcode Space*

Experience with the Xerox Smalltalk system has shown the value of implementing a good portion of the Smalltalk virtual machine in the host system's micro-architecture. At a minimum, the bytecode interpreter, plus some critical primitives, must be implemented in microcode if reasonable performance is to be achieved on the 432.

Clearly the size of the 432's microcode store is much smaller than any of the Xerox systems. For example, the Xerox Alto has a 32-bit microinstruction, in comparison to the 432's 16-bit word. Further, the Alto has 1K of ROM and 3K of RAM available to the Smalltalk implementor; the 432 has much less. In speaking of the microcode requirements of the Smalltalk-80 system, Glenn Krasner⁸ says:

> For the systems that we have implemented at Xerox, the Smalltalk-80 Virtual Image consists of about 300K bytes of objects. Our typical implementation of the Smalltalk-80 virtual machine is 6 to 12K bytes of assembly code, or 2K microcode instructions plus 10K bytes of assembly code. Of this, about 40% is in the storage manager, 20% in the interpreter, and 40% in the primitive subroutines.

The 432 has a total of 4K microwords, of which a certain amount will be left devoted to 432 system primitives (e.g., ports and object tables). A rough guess would estimate this at 2K, thus leaving 2K for the Smalltalk implementor. It is difficult to evaluate the extent to which the PLAs and special-purpose data paths of the 432 microengine will offset the smaller amount of microcode space.

There are several functions which should be implemented within the microcode of the 432 in order to achieve reasonable performance. We list them here in decreasing order of importance:
* The standard object table functions—necessary. In order for Smalltalk programs and Ada programs to be able to share the same memory space, it is necessary that both have the same notion of object table and access descriptor.

* The standard port functions—necessary. In order for Smalltalk programs and Ada programs to be able to engage in interprocess communication, it is necessary that both have the same notion of port and carrier.

* The standard process and processor functions—necessary. In order for Smalltalk processes to be dispatched in a uniform manner, it is necessary that Smalltalk processes share the same structure and dispatching functions as Ada processes. (Note that these three requirements, taken together, require that the Smalltalk processor support the standard 432 Carrier, Communication Segment, Descriptor Control, Object Table, Port, Process, Processor, Refinement Control, and Type Definition Objects. It is not however, necessary to support the standard 432 Context, Domain, Instruction, or Storage Resource Objects.)

* The bytecode interpreter—necessary. The bytecode set of the Smalltalk machine is a relatively simple set of instructions. Most of them are simple push, store, and jump instructions. The others are more complex instructions for sending a message to an object and returning from such a send; these functions are similar both in nature and complexity to the call-context and return instructions on the standard GDP.

* The Smalltalk primitives—varying. The Smalltalk bytecodes do not for example, include add or compare instructions per se. Rather, these functions are handled by invoking special methods, called primitive methods, known to the Smalltalk virtual machine implementation. These methods are primitive for either of two reasons:

1. Intrinsic. Some primitives would be impossible or at least very hard, to express as ordinary methods coded with ordinary bytecodes. Examples are the Process Resume and BitBlt methods for process synchronization and icon manipulation, respectively. Most of these primitives could be supported by sending a request message to an Ada program executing on a standard GDP, then receiving a reply from it.

2. Performance. Some primitives are invoked so frequently that the system would be slower if they were handled by the standard message-sending scheme. Examples are the methods for stream operations next, nextPut, and atEnd. (Note that these
two motivations for making a method primitive are not mutually exclusive. Consider, for example, the `at:` and `at:put:` methods for indexing into objects. They would be hard to implement as ordinary methods both for intrinsic and performance reasons. Those methods that are primitive only for intrinsic reasons can often be implemented by auxiliary processes running either on Ada GDPs or on attached processors. Those that are primitive only for mild performance reasons might best be implemented by means of standard Smalltalk methods or by auxiliary processes as above. Many however, will best be implemented directly in the microcode. Various techniques for implementing primitives other than directly in the microcode will be discussed on p. 317 below.)

* **Object creation—optional.** We may decide to have actual allocation of segments from Storage Resource objects be performed by an auxiliary Ada process. It should be put into microcode only if there is plenty of microcode to spare. Allocation of Smalltalk objects is discussed in more detail in the implementation sketch.

* **Large integer and floating point—optional.** The primitives for large integers and floating point numbers may also be handled by an auxiliary Ada process. Since the floating-point microcode in the standard 432 uses considerable space, there would be substantial benefit in performing floating-point arithmetic using an auxiliary Ada process.

Thus just what can be fit into microcode is bound to be a central issue. However, a partial solution can be effected by implementing some of the Smalltalk primitives "off board." Here, low-overhead linkage to primitives will be very important. Possible implementation techniques include using an attached processor (AP), an Ada co-process, or inter-processor communication (IPC). We would expect that some combination of these techniques would be used in an eventual system. These techniques are discussed in more detail in the implementation sketch.

A final major threat is the overloading of the garbage collector, since Smalltalk will put a much heavier load on it than does Ada. In the 432 implementation of Ada, contexts and local variables for procedure calls are not stored in the global heap, and so don't need to be reclaimed by the parallel garbage collector. However, in the book implementation of Smalltalk, all objects are allocated from a global heap.

If the garbage collector can keep up, then all is well. However, if Smalltalk processes spend a significant amount of time blocked, waiting
for the garbage collector to free up some storage, or if the garbage collector consumes a large amount of processor or memory resources, then performance will be improved if ways can be found to reduce the number of objects that need to be garbage collected. This could be done either by reducing the number of real 432 objects created in the first place, or by reclaiming some objects by means other than the parallel garbage collector.

One place to look is contexts. In general, contexts must be allocated from the heap, since it is possible, for example, to obtain a pointer to the current context and store it into a global variable. However, in most cases, contexts will be allocated and deallocated in a stack-like fashion, and probably advantage could be taken of this fact. (The presence of block contexts, used for many control structures, complicates the situation. Each block context includes a pointer to its "home context", which will be some method context. When used to implement such standard control structures as iterations through the elements of a collection, the block context is only passed up the stack, and the method contexts still obey a stack discipline. However, there is no guarantee that a pointer to the block context won't be bound to an instance or global variable. Hence the presence of block contexts makes it more difficult to keep track of all the pointers into the stack.)

Another place to look is short-lived objects in general, that is objects that are created, bound to temporary variables, and used in the course of executing a method, but which are not returned or bound to an instance or global variable.

For Ada, the 432 uses "level numbers" to help with this situation. Each context object, along with that context's local variables/objects, contains a level number that is one greater than that of the calling context. Upon termination of a context (i.e., a return instruction), the runtime stack is popped by deallocating all objects whose level number matches that of the terminating context. We devoted some effort to studying whether modifications to the level-number scheme could be used with Smalltalk, for example, just using level numbers for method and block contexts. Unfortunately, none of the techniques we devised had satisfactory characteristics. Generally, these techniques suffered either from too much complexity, too little applicability, or too great an overhead. We believe however, that reasonable solutions to this problem can be found with additional work. For example, in Ballard's VAX implementation, which uses a garbage collector together with a limited reference count scheme, only about 5% of the contexts needed to be garbage collected (see Chapter 8).

This is an area that will require further investigation if in fact the garbage collector threat materializes. Intelligent responses to this threat will be based on detailed experience with running Smalltalk systems (for example, what is the rate of creation of method contexts,
block contexts, and other objects, and how frequently do they exhibit stack-like behavior?) with the iMax Garbage Collector, and a detailed review of current garbage collection literature. (See for example, the October 1981 issue of *Computing Surveys*. This area is very active, partly due to work on various kinds of Lisp machines.) If this area is pursued, benefits will accrue not only to Smalltalk programmers, but also to Ada programmers who desire to use the heap heavily.

## Implementation Sketch

This section presents approaches to several aspects of Smalltalk implementation. Areas discussed include the representation of Smalltalk objects, special system types for Smalltalk, allocation of Smalltalk objects, ways of reducing storage overhead, execution of primitive methods, communication between Smalltalk and Ada programs, and interfacing to the display.

### Representation of Smalltalk Objects

Smalltalk objects would be represented directly as 432-objects, each with an object descriptor and a memory image. The object descriptor would include the object's length and its system type, if any. The few system types needed specifically for Smalltalk will be presented in a following section. The Smalltalk notion of class would be mapped directly onto the Release Three 432 extended type notion. Thus Smalltalk objects that are not of some system type would contain an access descriptor to a Type Definition Object, which would take the form of a Smalltalk Class object.

With the exception of Smalltalk methods, all Smalltalk objects are either pure data objects, e.g., strings, or pure access objects, e.g., dictionaries. In the case of pure data objects, they may be byte-addressed or (16-bit) word-addressed, depending on the characteristics of the Smalltalk class. In the case of pure access objects, they will use the release three notion of embedded values (see p. 316).

### System Types for Smalltalk

The Smalltalk system makes heavy use of several system types. Ordinary Ada GDPs need only be able to access these types as generic objects, i.e., be able to access their fields, but not their peculiar operations.

☐ *Class* The first type is *Class*. Each object of this type describes some Smalltalk Class, and includes the following kinds of information:

* How to create a new object of this *Class*, and

* Methods to be executed when a message is sent to an instance of this *Class*.
The format of this type is shown in Fig. 17.1. The first pointer leads to another Class object, which is the Superclass of this Class. The second leads to a Message Dictionary, which contains the Methods for all messages defined directly on this Class. The third pointer is actually an embedded value, which includes:

* The number of fixed fields in an instance of this Class,

* Whether the instance's representation contains pointers or numeric data,

* If data, whether it is organized as bytes or words, and

* Whether the object is indexable.

<figure><img src="image_62.png" /></figure>

□ *Message Dictionary* Just as in the model implementation, we require a Message Dictionary to be an array of pointers to Symbols with a parallel array of pointers to Methods. This Message Dictionary is used by the microcode which implements Message Send bytecodes.

□ *Method* Another system-defined type is the Method, an analogue of the Ada Instruction Segment. This type is the only Smalltalk class to contain both data and pointers. The format of these objects is shown in Fig. 17.2. The byte-organized data, shown below the thick line, contain the bytecodes for the Method. (A nice property of the 432 implementation is that the initial instruction address is always zero!) All but the first pointers are literals, i.e., pointers to constants or global variable objects. The first pointer is the Method Header, packed within an embedded value. The representation for the Header is:

* Temporary Frame Size: 5 bits

* Argument Count: 5 bits
* IsPrimitive: 2 bits

* Context Size: 1 bit

* Primitive Index: 8 bits

<figure><img src="image_63.png" /><figcaption>Figure 17.2</figcaption></figure>

The alignment of these data should be designed to simplify the microcoding of the Send bytecodes. The IsPrimitive field has the following four values:

**00** Not a primitive Method.

**01** The special primitive "return pointer to Self".

**10** The special primitive "return a field from within Self". In this case the primitive index can be used to indicate which field.

**11** An ordinary primitive. In this case the primitive index tells which one.

□ *Contexts* The other two system-types are Method Context and Block Context. The Smalltalk Method Context is the activation record that results from a message being sent to a receiving object, and corresponds to the standard Ada Context object. Unlike the Ada Context object however, Smalltalk Method Contexts are allocated from a global heap and can persist after they return. The format of a Method Context is shown in Fig. 17.3.
<figure><img src="image_64.png" /><figcaption>Figure 17.3</figcaption></figure>

The fields in a Method Context are as follows:

* Pointer to the Sender, i.e., the Context that issued the Send instruction that caused this Context to be created. On the 432, this pointer would lack DeleteRights.

* The Instruction Pointer and Stack Pointer embedded in one pseudo-access descriptor. The IP is a byte offset into the Method's bytecode part. The SP is a pointer offset into the Context itself, and indicates the top of the stack region of the Method Context.

* Pointer to the Method of which this Context is an invocation. This pointer would also lack DeleteRights on the 432.

* Pointer to the receiving object (`=Self`). This pointer would also lack DeleteRights on the 432.

* Next come zero or more arguments. These are the values pushed on the stack by the sender prior to issuing the Send bytecode. The number of these is specified by the Method Header, Fig. 17.2.

* Next come zero or more Temporaries, or local variables. The number of these is also specified by the Method Header, Fig. 17.2.

* Finally, there is room for the expression stack for this context. This stack is initially empty, so the initial value of the SP must be determined from the size of the Argument and Temporary frames.
The Block Context system type is very much like the Method Context, and is used to implement control structures other than ordinary Message Sending. Like the Method Context and all other Smalltalk objects, it is logically allocated from a heap. The format of the Block Context is shown in Fig. 17.4.

<figure><img src="image_65.png" /></figure>

Three fields of the Block Context differ from those in the Method Context:

* The caller field of the Block Context points to the (Block or Method) Context that called this Block Context. Note that this may differ from the Context that created the Block Context.

* An embedded value storing the initial IP and argument count replaces the Method pointer of the Method Context. These values allow the interpreter to initialize the Block Context for a new call. (The Method can be found via the Home Method Context pointer.)

* The Home Method Context points to the Method Context that created the Block Context. It is used for locating the receiver and temporaries of the Method.
The allocation and deallocation of Smalltalk objects poses several difficulties:

* Smalltalk objects are allocated from global heaps. Their deallocation cannot therefore, be performed simply because some method has executed a return instruction. As mentioned earlier, this threatens to overload the parallel garbage collector.

* Microcode space on the processor chip is at a premium. It would conserve microcode space if object allocation, including maintenance of Storage Resource Objects and Object Tables, could be removed from the microcode.

One consequence of the first point is that any implementation of Smalltalk on the 432 (or any other machine) must pay serious attention to efficient garbage collection of Smalltalk objects. This topic is discussed fully on p. 308.

The allocation of objects, on the other hand, is easier and gives us an opportunity both to speed allocation and to save microcode space. We propose that an Ada auxiliary process be assigned to maintain a data structure that contains pointers to well-formed, unallocated segments. This data structure would take the form of an access segment, with one access descriptor for each of several commonly used sizes of segments. (Since most Smalltalk objects are small, and since object images in the 432 come in chunks of 8 bytes, the sizes 8, 16, 24, 32, 40, 48, 56, 64 would take care of the vast majority of cases.) Each access descriptor in this structure would be the head of a singly-linked list of unallocated segments of a certain size. If the Smalltalk processor wants to "create" a new Smalltalk object, it need only pull a segment of the right size off the appropriate list. No carving of storage from heap SROs or allocation of entries from object tables is needed. Also, the auxiliary process could ensure that the segments it places in the list are all zeroed out. The Smalltalk processor would only have to adjust the object descriptor to indicate the proper actual size and type, and would have to put the class access descriptor in the object.

This way of allocating objects should in fact be faster than doing the actual manipulation of SROs and object tables required of the Ada 432. In addition to entries in the list for each of the most common sizes, there should also be a port for use in making requests for odd sizes. (Handling this case by having a request-reply protocol via ports would not be very fast, but it is general and simple and would only be used rarely.) Another set of lists should be maintained specifically for the two sizes of method contexts; here there would not even be any need for setting the class/type in the object. One elegant possibility is to use ports as the heads of the linked lists—pulling a segment off a list then
becomes the ordinary Receive Port primitive, synchronized access to the list is taken care of, and the auxiliary process could use surrogate sends to find out when certain sizes of segments are being used up. Furthermore, this auxiliary process could coordinate closely with the parallel garbage collector to effectively recycle objects, rather than going through the overhead deallocating objects by putting their storage back into an SRO and deallocating their object table entries.

As discussed on p. 305, one of the threats to a 432 Smalltalk implementation is excessive storage overhead per object.

## Reducing Storage Overhead

* **Embedded Values** One technique for reducing this overhead would be to represent some Smalltalk objects in other ways than as full-fledged 432 objects, for example, by embedding their representation in a pointer rather than storing it separately as a 432 object. Note that any object stored this way must be of an immutable class, since one isn't sharing pointers to a mutable piece of storage. (The model implementation uses this technique to represent small integers. Instead of small integers being represented as an object pointer to an integer object, the value of the integer is encoded directly into the object pointer.)

On the 432, if the "valid bit" of an access descriptor is turned off, that access descriptor is not regarded as referencing any 432 object, and the remaining 31 bits can be used to store the representation of some object. Since we would have more bits available than in 16-bit implementations, more things than just small integers can be encoded. A reasonable set of objects to be encoded in the access descriptor is as follows. (We assume that bits 29-30 are used to disambiguate the different sorts of objects so encoded, so that bits 0-28 are available for storing data. If it were important, another bit could be squeezed out for representing some of the classes by a more clever encoding.)

**small integers** These are integers between $-2^{28}$ and $2^{28}-1$. Note that this is much larger than the maximum small integer in the 16-bit implementations, and should mean that large integers would be used even less frequently.

**the constants true, false, and nil** There would in fact be only a trivial space saving due to encoding these constants as embedded values, since there is only one instance of each. However, this will make life much simpler for the garbage collector, since it will be able to ignore these oft-encountered values.

**characters** There are exactly 256 distinct instances of this class, representing the ASCII characters. As with the above constants, there would only be
a trivial space saving due to this encoding; the garbage collector would be the primary beneficiary.

In the current version of the Smalltalk-80 system, points are mutable objects. However, it would take a relatively small amount of work to make them immutable. If this were done, small points would be another good candidate for representation as embedded values. (Making points be immutable would also eliminate some annoying sorts of bugs arising from accidental sharing.) The x and y values of a small point could be stored in 2's complement in the low-order 28 bits of the access descriptor, 14 bits each. This is sufficient to hold points arising in nearly all graphics applications, save perhaps the generation of very high resolution hardcopy images. There would also be a class LargePoint to hold points with floating point values or large integer values, in analogy with the Smalltalk classes LargePositiveInteger and LargeNegativeInteger.

Floating point numbers are another possible candidate for this representation. They are stored in 32-bit fields on the 432, so if one is willing to give up 2 bits of precision, they could be represented as embedded values. However, as described on p. 306, it is likely that floating point arithmetic will be handled by an auxiliarly Ada process running on another chip, rather than on the Smalltalk chip. In this case, it would be better to let floating point numbers be ordinary 432 objects, making it easier to send them to the Ada process.

□ Other Techniques for Reducing Storage Overhead Another—more problematic—possibility for reducing the number of objects is to merge some collections of objects into a single object. This sort of merging should be used in only a few critical places, if at all; certainly the average programmer shouldn't need to think about it. As an example of this technique, rather than maintaining each method object as a separate segment, all the methods for a given class could be stored in a single object, with 432 refinements being used to refer to individual methods. There are about 4000 methods in the Smalltalk virtual image, so this would reduce the number of objects by close to 4000, since most classes have many methods. Making this modification might also improve swapping behavior, but would have the disadvantage that all the code for a given class would need to be in main memory at one time, rather than just the methods being used.

As discussed on p. 306, several time-critical primitives will be directly executed on the processor chip. Other primitives are best executed off the chip. This section discusses several different ways of executing these primitives.
□ *Execution of Primitives on an Attached Processor* One alternative is to send requests for primitives to a port served by an attached processor. In the 432, this is the natural technique to use for i/o primitives. It may also be important for non-i/o primitives handled better by an attached processor than by another 432 GDP. If BitBlt is not implemented on the Smalltalk processor, it may be an example of this.

□ *Execution of Primitives by an Ada Process* Here we devote an Ada process to be a Smalltalk primitive server. Then, using inter-process communication (i.e., ports), the Smalltalk system sends requests to the Ada co-process to execute primitives. Again, this is a natural technique to use on the 432, and if it works well, is the method of choice for most non-i/o primitives handled off-board. The speed, and therefore the value, of this idea will hinge on both the execution speed of Ada programs, and the speed of inter-process communications. Preliminary statistics give an overhead of approximately 300 microseconds for such inter-process communications.

One advantage of this technique is that the primitives will be coded in Ada; this should simplify the implementation. Also, with this technique, the Ada co-process is not locked onto a particular GDP as it is with the inter-processor communication technique discussed below.

Note that in both of these first two techniques, a message is sent to a port, and a reply is received on another port. This means that the implementors of Smalltalk can postpone or change the decision as to whether a given primitive is implemented by an attached processor or by an Ada process, and that no change to the microcode would be required. This flexibility would be achieved by having an access segment, indexed by the primitive index, that mapped a primitive to a port. This would make the first two techniques indistinguishable at the microcode level.

□ *Execution of Primitives by a Dedicated GDP* This technique devotes one GDP exclusively to the Ada primitive handler. Thus when Smalltalk needs an off-board primitive executed, it sends a wake-up signal to the GDP and then sends its request. When the GDP is finished handling the request, it sends itself a stop processor signal. Thus the GDP is either working for the Smalltalk system, or it is blocked, waiting for a wake-up signal from Smalltalk. The Intel 432 Architecture Group suggested implementing this approach via the Lock instruction on the standard GDP.

The advantage here is that we make use of the faster inter-processor communications facilities of the 432. The disadvantage is that the system becomes less general, since the Ada process must be resident on the GDP whenever the Smalltalk processor is active. This alternative is attractive only if the improved overhead is worth the reduced generality and dedicated processor.
## Communication between Smalltalk and Ada Programs

As described in the introduction, one of the potential benefits of a 432 implementation of Smalltalk would be support for multi-lingual systems. In this section we outline how communication between Smalltalk and Ada programs might take place.

Within the Smalltalk image, there would be "local representatives" of Ada tasks with which the Smalltalk program could communicate. These would be full-fledged Smalltalk objects to which one would send messages in the usual way. Internally, these representatives would have an access descriptor for a 432 port. The Smalltalk invocation messages would thus run methods that would in turn send 432 messages to the Ada task. There should be a Smalltalk class AdaTask that holds this general sort of information, with subclasses of AdaTask used to represent particular Ada tasks.

Smalltalk and Ada will have different ideas about how data is to be represented. For example, Smalltalk integers will be represented either as embedded values or as large integers; Ada integers will be stored simply as 32-bit quantities. To convert between these representations, the class AdaTask should have a set of conversion messages that accept certain Smalltalk objects as arguments and encode them on a byte stream for eventual transmission to the Ada task. For example, the message encodeInteger would take a (Smalltalk) integer argument and a stream of bytes, and put out the 4 bytes representing the integer as a 32-bit quantity. An analogous set of messages would be used to convert values returned by the Ada task back to Smalltalk objects.

## Interface to the Display

A critical factor in the performance of a Smalltalk system, particularly the user's perception of its performance, is the speed of the graphics. There are a number of plausible ways in which the display can be connected to the processor, as discussed below. In regard to the production of a new version of the 432, the relevant question is whether BitBlt should be supported on the chip; other decisions regarding the display can be made independently. We conclude that to ensure flexibility, BitBlt should indeed be supported on the 432, unless there is a severe shortage of microcode space. While the 432 hardware doesn't have any special facilities to support BitBlt, its performance would still be quite adequate if it were implemented in microcode.

One way of connecting the bitmap display to the processor, used in the Xerox machines, is to make the memory for the bitmap display be simply part of the machine's main memory. This approach gives maximum flexibility. An unfortunate problem is that the maximum size of a 432 object is just short of what would be needed to represent the bitmap as a single 432 object. The maximum size of a 432 object is 64K bytes. A 600x800 display would just fit, but a more generous size (1000x1000) would not; such a limitation shouldn't be built into the system. With some additional software complexity, the problem can be overcome by
mapping the display memory onto several 432 objects. The 432 would write some data into these objects, which would be reflected on the display. This approach clearly requires that BitBlt be implemented on the 432.

Another approach is to have the display memory be separate from the machine's main memory, and to send messages to a separate display processor to make changes to it. For this approach to have acceptable performance, there should be some high-level requests that can be made of the display processor, for example, to display a paragraph or to replicate a bit pattern along a given path. For flexibility and completeness, low-level BitBlt requests should be supported as well. There would need to be facilities for swapping fonts and the like into display memory. Even with this approach, there may well be occasions on which BitBlt on the 432 itself would be valuable. For example, the programmer might create an image in main memory—not displayed at all—and only later show this image on the display.

Thus for maximum flexibility, we recommend that BitBlt be included in the primitives supported by the 432 microcode, unless there is a severe shortage of microcode space.

## Conclusions

Our study of Smalltalk and the 432 leads us to conclude that the implementation we have described here is feasible. We have pointed to what we believe to be the three chief technical threats, but we believe them to be surmountable. The potential qualitative advantages of Smalltalk on the 432 present real motivations to attempt its implementation.

## References

1. Wulf, William A., Cohen, Ellis; Corwin, William, Jones, Anita, Levin, Roy, Pierson, Charles, and Pollack, Frederick, "Hydra: The Kernel of a Multiprocessor Operating System", *Comm. of the Assoc. for Computing Machinery* vol. 17, no. 6, pp. 337-345, June 1974.

2. Wulf, William A., Levin, Roy, and Pierson, Charles, "Overview of the Hydra Operating System Development", in *Proceedings of the Fifth Symposium on Operating Principles*, Assoc. for Computing Machinery, pp. 122-131, Austin, TX, Nov. 1975.

3. Wulf, William A., Levin, Roy, and Harbison, Samuel P., Hydra/C.mmp: An Experimental Computer System, McGraw-Hill, New York, 1980.
4. Cox, George W., Corwin, William M., Lai, Konrad K., and Pollack, Fred J., "A Unified Model and Implementation for Interprocess Communication in a Multiprocessor Environment", Presented at the Eighth ACM Symposium on Operating Systems Principles, 1981; (to be published).

5. Pollack, Fred J., Cox, George W., Hammerstram, Dan W., Kahn, Kevin C., Lai, Konrad K., and Rattner, Justin R., "Supporting Ada Memory Management in the iAPX-432", in *Proceedings of the Symposium on Architectural Support for Programming Languages and Operating Systems*, Assoc. for Comp. Machinery, pp. 117-131, March 1982; (also distributed as *SigArch Computer Architecture News* vol. 10, no. 2, and as *SigPlan Notices* vol. 17, no. 4).

6. Kahn, Kevin C., Corwin, William M., Dennis, T. Don, D'Hooge, Herman, Hubka, David E., Hutchins, Linda A., Montague, John T., and Pollack, Fred J., "iMAX: A Multiprocessor Operating System for an Object-Based Computer", in *Proceedings of the Eighth Symposium on Operating Systems Principles*, Assoc. for Comp. Machinery, pp. 127-136, Dec. 1981; (also distributed as *SigOps Review* vol. 15, no. 5).

7. Pollack, Fred J., Kahn, Kevin C., and Wilkinson, Roy M., "The iMAX-432 Object Filing System", in *Proceedings of the Eighth Symposium on Operating Systems Principles*, Assoc. for Comp. Machinery, pp. 137-147, Dec. 1981; (also *SigOps Review* vol. 15, no. 5).

8. Krasner, Glenn, "The Smalltalk-80 Virtual Machine", Byte vol. 6, no. 8, pp. 300-320, Aug. 1981.
# Preferred Classes: A Proposal for Faster Smalltalk-80 Execution

Robert Hagmann

Computer Science Division

Department of Electrical Engineering and

Computer Sciences

University of California, Berkeley

## ct

A straightforward implementation of a Smalltalk-80 interpreter has two main bottlenecks: memory management and message send/return overhead. In addition, since Smalltalk-80 is a typeless language, it is harder to compile than to interpret. This proposal addresses both the send/return bottleneck and the difficulty of compilation by introducing an optional limited typing mechanism for the Smalltalk-80 language. The typing mechanism does not change the Smalltalk-80 semantics in any way. Its sole purpose is to allow for a more efficient execution.

## uction

This proposal is for a Smalltalk-80 implementation strategy¹ that is different from conventional interpreters. Where existing implementations typically try to gain performance through caching and special casing of high probability cases (see Chapter 11), this proposal explores the gains made possible by using compiler technology. This strategy has not been implemented, nor have all of the performance data needed to validate the effectiveness of this proposal been collected. This paper presents only one way to apply compiler technology to Smalltalk-80 implementa-
tions. The author hopes that by illustrating one technique that other researchers will be motivated to explore alternate strategies.

Briefly, the idea is to "fix" the class of arguments and variables to selected Smalltalk-80 methods by explicit declaration. By making the "fixed" classes be only hints, the semantics would not change. Several benefits could then occur. First, the target methods of some sends could be identified at compile time. Second, translation to machine code instead of bytecodes would be made easier since the class of all objects used in some methods would be known at compile time. Finally, some methods could be compiled in-line.

The proposals in this paper have some similarity to those of Borning and Ingalls². Where their proposal deals with compile time type checking, this proposal addresses the issue of performance.

## Assumptions

There are three assumptions that are necessary for this technique to be efficient in speeding up Smalltalk-80 execution.

1. The overhead associated with the send and return bytecodes is high.

2. A Smalltalk-80 application spends a large fraction of its time at or near the leaves of the message-send tree: that is, in methods that send no other messages other than to primitive methods.

3. A significant portion of methods executed dynamically do not exploit the polymorphic nature of the Smalltalk-80 language: that is, the classes of the arguments and variables used by the method remain nearly constant over some relatively long time period.

The assumption that message sends and returns are a bottleneck was confirmed by measuring several implementations. The percentage of execution time attributable to send/return, excluding memory management, for the Dorado and Dolphin are 38% and 34%³. For Berkeley Smalltalk, the same statistic is about 30%⁴. Since memory management during message send/return is also a bottleneck for the Dorado and Dolphin⁵, for these implementations about half of the execution time is directly attributable to message-send and return bytecodes.

The second assumption has also been verified. In measurements of a Smalltalk-80 interpreter⁶, it was found that 55% of all non-primitive message sends go to methods that do no further non-primitive sends. That is, 55% of all methods executed dynamically are at the leaves of the message send tree. A second interesting result is that the leaf nodes
tend to be extremely short: 70% of the leaf nodes executed 5 or fewer bytecodes before returning. The conclusion is that most methods execute at the leaves of the message-send tree and they tend to be small.

The final assumption is that a significant portion of the methods do not exploit the polymorphic nature of the Smalltalk-80 language. In particular, a large fraction of methods are executed with "fixed" classes for the arguments and variables. That is, for many methods, the classes of the arguments and variables nearly always are the same from call to call. No direct evidence has been collected to verify this assumption. However, one measurement has been made that makes this seem plausible. As measured dynamically, for a given send bytecode in a given method, the probability is 95% that the receiver is of the same class as the last time this particular bytecode was executed[^7]. This indicates a strong lack of polymorphism for a large part of the system.

Of course, this measurement does not directly validate the third assumption. Even though the class of the receiver was often the same, the classes of the arguments and variables (if any) were not measured. However, it is unlikely that the 5% of variability in receiver is distributed evenly over the system. Probably, many sends almost always have the same receiver as the last time. It is also likely that similar results hold for arguments and variables in methods.

For this final assumption to be true, there must be dynamically a significant number of methods that are almost always presented with the same classes for the arguments and variables as the last time. While the number of methods for which this holds is unknown, it is certainly true for some methods. For example, some graphics methods most certainly expect only to be passed an instance of class Point.

## The Technique

The proposal is to augment the Smalltalk-80 language with an optional declaration of the class of arguments, instance variables and class variables. In addition, some methods would have optional declarations of the class of the value returned from the method and/or the class of the receiver. These declarations would define the *preferred class* of the argument, variable, return value, or receiver. This preferred class is the class expected to match the actual class used in the method in the vast majority of activations of the method. The receiver and arguments are not forced to match: if at run time the actual class did not match the preferred class, then the method would be executed by a conventional interpreter. If however, the preferred classes match the actual classes for all arguments and variables, then a more efficient method of execution could be performed.
At least two other techniques for introducing the notion of types to Smalltalk languages have been documented. One⁸ uses type inferencing, and the other⁹ uses type declarations. This proposal is somewhat different from either of these.

For the purpose of this paper, the use of pool dictionaries or the Smalltalk-80 dictionary in a method would make it ineligible for this technique. The problems involved in incorporating these dictionaries appear not to be insurmountable, but they confuse the concept being presented here.

Since the system would always interpret bytecodes when the actual and preferred classes did not match, the Smalltalk-80 semantics would not change. The only effect of the preferred classes would be that some methods would run more efficiently.

The idea behind all of this is that the upper portions (near the root) of the message-send tree are likely to be polymorphic. However, to perform some low level function, only a small locus of methods is used. Many sends and much looping occur inside of this locus. If the boundary of this locus can be identified and the classes passing over this boundary checked, then the class of objects inside the locus might be predicted. This would lead to faster execution of this small part of the computation. The rule of thumb in conventional programming languages is that 10% of the code accounts for 90% of the execution. Typically most of this 90% is found in inner loops. If this conjecture is also accepted for the Smalltalk-80 language, then this technique could effect the vast majority of execution.

There is a danger in this approach: by having two execution strategies for methods, the more efficient one with preferred classes might tend to encourage programmers not to exploit the polymorphic nature of the language. Programmers might tend to use the more restrictive but more efficient style of programming rather than the fuller and more powerful nature of the Smalltalk-80 language. If however, the addition of preferred classes to a collection of methods is viewed as an optimization step performed by the applications programmer after initial system test, then the polymorphic nature of the Smalltalk-80 language will be effectively preserved.

**Implementation**
The implementation technique is to compile methods to machine code as much as possible. For methods where the preferred classes are declared, two types of compiled methods are produced: the existing compiled method and a new machine code compiled method. It is assumed that a conventional interpreter is available to execute methods where
there are no preferred classes and for use when the preferred classes do not match the actual classes.

For methods where the preferred classes of all arguments, instance variables, and class variables are declared, a variant of the message dictionary will be used. This will be set up at compile time. The message dictionary entry will be flagged to indicate machine code is to be executed. The machine code for the method will be divided into two sections. The first section, called the *prologue*, will validate the class of the arguments and variables. To do so, only a few instructions are executed for each argument and variable. Variables will only be checked if they are used in the method (unused instance and class variables need not be checked). If the method explicitly uses self, the class of the receiver will also be checked. If any of these tests fail, the method will be run by the standard interpreter. If all these tests succeed, the second part of the machine code, called the *body*, will be executed. The body is the machine code program to perform the method. The body would be all that would be executed from other machine code methods when the classes matched. That is, there will really be two entries to the machine code: a checked (prologue) and an unchecked (body) entry. The first is used when the classes of the arguments and variables cannot be predicted at compile time. The second will be used when this prediction is possible.

More optimizations could occur during compilation. If the class of the receiver of a send can be predicted at compile time and the target method is short, then it could be compiled in-line. If the target method is not short and the classes match, the send could be bound to the unchecked entry. Finally, if the target method can be predicted, a hard pointer to this method can be used instead of a lookup at execution time. Primitives are prime candidates for these optimizations.

Additional information must be kept to allow the debugger to operate as usual. In case of an error, it must be possible to map from machine code and expanded in-line machine code to a more conventional representation. This could be done with an auxiliary table for each machine code method that would set up the correspondence of program counter values between the two types of methods. Code would be generated such that at each potential error point, the execution would cleanly map into the conventional representation. Dependency lists could be kept to detect what methods need to be recompiled after another method is changed¹⁰.

Sometimes during the execution of a method in machine code, the class of the value returned by some message might not match the preferred class. In this case, the machine code form of the execution would also need to be converted to interpreter form (i.e., compute the effective program counter for the interpreter). The interpreter would then start executing as usual.
For example, suppose the `+` primitive when called with a receiver and argument of class `SmallInteger`, returns either a `SmallInteger` or `LargeInteger`. The normal case is for a `SmallInteger` to be returned. If a `LargeInteger` is to be returned (possibly detected by testing the overflow bit in machine code), the system would invoke full fault recovery to convert the executing machine code form to the normal interpreter format. Once this is done, the interpreter would continue to execute the method. It is hoped that this type of fault is a low probability event, so that it would not add significant overhead.

By insuring the class of the receiver, arguments, and variables at method entry, the class of all objects relevant to the computation at the start of the method are known at compile time. By checking the class of all objects returned by message sends where needed, the class of all objects would be known at compile time for the whole method.

The checking of the preferred class at method entry need not be too time consuming. For class variables, checking could occur when they are changed. If the setting did not match the preferred class, then the object table could be flagged to not execute the machine code for those methods that depend on this class variable. Conversely, the setting of a class variable to the preferred class would re-enable the execution of machine code. By doing the checking of class variables when they are set, normal method execution would do no class variable checking. This would be faster since it is presumed that variables are read more often than they are written. The instance variables would have to be checked, but this could also be reduced to checking a flag in the object if the setting of the instance variables by the standard interpreter also caused a check of the preferred class. Note that changing an instance or class variable might involve converting existing suspended methods from the machine to the bytecode form of execution. Finally, the arguments would have to be checked. Since dynamically, most methods have few arguments (an average of 1.3 has been reported<sup>11</sup>), this would take only a few instructions. The number of machine instructions to check the classes might be about six. This would make the checking be about three times faster than executing a single bytecode in a conventional interpreter. If the tests succeeded in the clear majority of the cases, then this overhead would be acceptable.

The final question is that of execution efficiency. Will anything be gained or lost by the use of this technique? Certainly there will be added complexity during compilation, debugging, and error handling. Additional space will be consumed with machine instructions, mappings from bytecodes to machine instructions, and dependency lists. Additional overhead will be incurred when sending messages to methods with preferred classes when the actual classes do not match the preferred classes. The interpreter must also do extra work when setting instance and class variables that have preferred classes. But what savings can be
obtained from running part of the system in machine code instead of using a standard bytecode interpreter? If we assume:

1. Executing machine instructions is five times faster than interpretation,

2. Half of all executed bytecodes are compiled to machine mode, and

3. Half of all messages sends are eliminated by compilation in-line or direct calls without method lookup,

then the savings would be that half the execution would run five times as fast, while the other half would run at nearly the same speed. This means that a savings of about 40% could be obtained. Of course this number is approximate and depends on the selection of the preferred classes to be nearly correct. However, this shows that there is potentially a large gain possible by using techniques like the one proposed here.

## Conclusions

A technique to augment a conventional Smalltalk-80 interpreter has been proposed. This technique uses the concept of a preferred class to gain efficiency in those methods that do not use the polymorphic nature of the Smalltalk-80 language. This technique allows for more efficient compilation to machine code. Since the receiver class can sometimes be identified at compile time, either the method lookup can be done at compile time, or the method can be expanded in-line.

With the assumptions stated in the body of this paper, it seems possible that some form of optimizing compiler techniques can be used to gain efficiency. Although only one technique was presented here (explicit declaration), many variations on this theme are possible. Type deduction, where the type is inferred from dynamic usage, seems equally viable but requires more compiler sophistication¹².

## Acknowledgments

Professor David Patterson provided overall motivation, help, and guidance for this work. Hewlett-Packard allowed Berkeley to run an early version of their interpreter that was helpful in understanding Smalltalk-80 implementations and allowed certain statistics to be acquired. Xerox granted Berkeley access to documentation as well as many personal discussions. In particular, L. Peter Deutsch was most
helpful in providing statistics and discussing alternate implementation strategies. L. Peter Deutsch, Adele Goldberg, Glenn Krasner, and D. Jackson Penny also served as reviewers for this paper. Their comments were most helpful and greatly improved the quality of this paper.

References

1. Goldberg, Adele, and Robson, David, *Smalltalk-80: The Language and Its Implementation*, Addison-Wesley, Reading, Mass., 1983.

2. Borning, Alan H., and Ingalls, Daniel H. H., "A Type Declaration and Inference System for Smalltalk"; Ninth Symposium on Principles of Programming Languages, pp. 133-141, Albuquerque, NM, 1982.

3. Deutsch, L. Peter, Berkeley Computer Systems Seminar, Fall 1981.

4. Ungar, David M., Private Communication, 1982.

5. See reference 3.

6. Hagmann, Robert, "Some Smalltalk Performance Measurements Emphasizing Compiler Performance and/or Context Windows", Unpublished Class Paper for CS292R, Computer Science Div., Dept. of E.E.C.S., Univ. of California, Berkeley, Fall 1981.

7. Deutsch, L. Peter, Private Communication, 1982.

8. Suzuki, Nori, "Inferring Types in Smalltalk", Eighth Symposium on Principles of Programming Languages, pp. 187-199, Williamsburg, VA, 1981.

9. See reference 2.

10. Mitchell, James A., "The Design and Construction of Flexible and Efficient Interactive Programming Systems", Garland, N.Y., 1979; (A Monograph of Mitchell's 1970 thesis at Carnegie-Mellon University).

11. See reference 7.

12. See reference 10.
# Low-Overhead Storage Reclamation in the Smalltalk-80 Virtual Machine

Scott B. Baden

Computer Science Division

Department of Electrical Engineering and

Computer Sciences

University of California, Berkeley

## Abstract

Measurements of the Smalltalk-80 virtual machine indicate that 20% to 30% of the time is spent managing storage. Following the work of Deutsch, Bobrow, and Snyder¹,²,³,⁴, we introduce a strategy that reduces the overhead of storage reclamation by more than 80%. We also discuss the design of simple hardware to support this strategy, and compare our approach to one using only software. We conclude by suggesting directions for future research.

## Introduction

Last fall, Smalltalk came to Berkeley. Under the direction of Professor David Patterson, students in the Computer Science department ported the Smalltalk-80 virtual machine (SVM), generously provided by Hewlett-Packard Laboratories, to a research VAX-11/780, and analyzed several aspects of its performance⁵,⁶,⁷.

As a result of these studies, we discovered that a large percentage of SVM execution time was spent managing storage—20% to 30%⁸,⁹. Most
of this overhead is due to management of activation contexts. According to our statistics, context objects account for 82% of all object allocations and deallocations, and references from the evaluation stack and from local variables (both of which are contained by contexts) cause 91% of all reference-count operations.

These findings are encouraging: if the SVM could treat context objects as special objects, then it would save considerable time managing them. Consistent with this reasoning we show how to reduce storage reclamation overhead by a factor of five.

## Assumptions

Our assumptions deal with changes to the SVM, both to its specification and implementation, and to the processor that executes it.

## SVM Changes

An invariant of the SVM specification states that "the reference count of an object must equal the number of references to that object"¹⁰. In our implementation we will relax this invariant; the reference count of an object will usually not include the references made from the *n* most recent context activations. We call those contexts whose fields are not reference counted *volatile contexts*¹¹.

Owing to the presence of volatile contexts, an object might not be free when its reference count reaches zero. This condition prevents the SVM from reclaiming storage incrementally. Instead it reclaims storage periodically, accounting for all the volatile references before freeing any storage (we must ensure that the Smalltalk-80 virtual machine never runs out of storage between reclamation phases).

In addition to relaxing the reference-count invariant we also relax one other: that "all objects must be assigned an Oop"¹². Usually, the proposed SVM does not assign Oops to method contexts nor does it allocate space in the object memory for them. Instead, the system stores the contexts in FIFO order from a fixed region of physical memory.

Occasionally, nonlinearities in the context nesting sequence or other exceptions will arise, causing the system to momentarily enforce previously relaxed invariants. Later, we will show that these conditions arise infrequently enough so that they do not degrade performance significantly.

## Hardware

Although volatile contexts can be stored in main memory, they are used like registers in a conventional CPU, so we provide a small register cache, called the *context cache*.

Two registers, the *Top Window Pointer* and the *Bottom Window Pointer*, mark the physical memory bounds of the volatile contexts. The
system uses these pointers, as in RISC-I¹³, to resolve references to contexts (e.g., is the context volatile—in the registers—or not?). All the contexts between the two markers are volatile, while all the contexts below the Bottom Window Pointer are *stable* (i.e., their fields are reference countable). In our implementation, the storePointer operation will not do any reference counting if the destination field is volatile. To simplify the cache design we assume that all contexts are 32 words deep.

To speed up storage reclamation, we provide a special memory, called the Zero Count Table (ZCT), that indicates all the objects with a zero reference count. The ZCT has 32K entries and is 1 bit wide (the depth of the ZCT will always equal the number of possible Oops in the system). It is capable of operating in both random access and content associative modes. The system accesses the ZCT over its memory data and address busses, using a special request line to distinguish the ZCT from the object memory. The ZCT will behave like a Content Associative Memory (CAM) when the system searches it for free objects—this behavior speeds up the search time considerably (compare with queues elsewhere¹⁴,¹⁵,¹⁶). At all other times it behaves like a RAM. When an object's reference count reaches zero the CPU sends the object's Oop over the memory address bus and tells the ZCT to mark the appropriate entry (owing to possible volatile references to the object, it might not be free).

## Reclamation

The CPU suspends normal execution during the storage reclamation phase. First, it accounts for the volatile references—a process we call *stabilization*¹⁷. To stabilize a register, the CPU increments the reference count of its contents (*a ref*¹ operation). During the stabilization phase, a reference count may get incremented from zero to one—we call such a zero reference count a *spurious zero reference count*. To prevent the Smalltalk-80 virtual machine from freeing an object that had a spurious zero count, the CPU clears the ZCT entry on a zero to one reference count transition.

After stabilizing the registers, the CPU frees any object marked in the ZCT. During the reclamation phase further storage may become free and so new ZCT entries will be set. When reclamation finishes, the system *volatilizes* the registers by decrementing the reference count of their contents (*we call a reference-count decrement a ref*¹).

The difference between our scheme and that of its predecessors lies in the structure of the ZCT (Others used a queue.). Our implementation of the ZCT is preferable to a queue for two reasons:

1. The table will not overflow.

2. The search time will depend on the number of free objects, and not on the number of possible objects (i.e., there is no need to examine spurious zero counts).
## Overhead

There are three potential causes of overhead in a volatilizing system:

1. Window underflows and overflows.

2. Periodic stabilizations and revolatilizations.

3. Special case treatment of volatile contexts.

Since the depth of the stack is bounded, some sends will cause a window overflow and some returns will cause a window underflow. The system must stabilize the bottom window in the cache on an overflow and volatilize the top window in memory on an underflow. For an 8 deep context cache, we found that only 3% of all message sends and returns caused an overflow or an underflow; these conditions result in negligible overhead¹⁸.

There are certain cases where improper treatment of volatile contexts could cause the system to fail: non-linearities in the context nesting sequence, caused by blocks (e.g., a message may return a block as a result), and sending messages to contexts (e.g., sending a thisContext message). We assume that these activities have a negligible cost. We have observed that only 6% of all activations are due to blocks¹⁹, and it is well known that messages to contexts happen much less frequently than method activations and messages to other types of objects²⁰.

Although we have provided a fixed region of memory devoted to contexts, this does not mean that we have imposed a hardwired limit on the maximum context nesting depth. When the system overflows the fixed region, it migrates least-recently used contexts into the object memory²¹. We believe that this exceptional case can be ignored—we have observed a maximum context nesting depth of only 40 contexts in an execution trace of 559K bytecodes²². Assuming that the sample is representative, it would be reasonable to allocate a fixed region of, say, 64 contexts.

## Experiments and Their Interpretation

Experimental evidence shows that our scheme improves storage reclamation overhead by at least 80%. First we will discuss our general method for gathering statistics; next, the experiments; and finally, our conclusions.

### General Method

We monitored a session involving the execution of system code and application code—browsing, compiling, and execution of simple messages—a total of 559K bytecodes were executed. To collect a more representative
tive sample we started the measurements after system initialization had completed.

The H-P code was written exactly as specified in the Smalltalk specification²³, hence it was highly modular and easy to change. We modified the code by inserting non-invasive calls to special auditing routines. Appropriate Oops, method headers, and other data were written onto disk. Owing to its size (17 megabytes), the audit file was copied onto magnetic tape. A context cache simulator was written and ran directly from the magnetic tape audit files. Complete documentation for the audit tape format appear in our previous work²⁴.

Several activities were audited:

1. Bytecode Execution

2. Reference Counting

3. Deallocations and Allocations

4. Method Lookups

5. Context Activations and Returns

6. Primitive Successes and Failures

## The Experiment

We measured the effects of volatilization in a non-volatilizing system. There are two experimental variables: stabilization period (in bytecodes) and context stack depth (in 32-word windows). First we introduce a set of criteria for assessing the validity of our approach. Then we present the numbers to support our claims.

We had to adjust our figures to account for four optimizations not present in the Smalltalk-80 specification, that reduce reference-counting activity by 50%²⁵,²⁶,²⁷. These optimizations include: nilling the top of stack on a pop, not reference counting explicit use of distinguished values (nil, true, false) in the push and return bytecodes, and not reference counting when moving Oops (e.g., return top of stack).

Since we did not have access to a volatilizing Smalltalk-80 system, we could not measure certain fine-grained activities such as spurious zero counts, or overflowed queues. Hence, we could not quantify our choice of ZCT implementation over that in the literature. However, we can justify our choice from an analytic standpoint since it allows us to place an upper bound on the cost of scanning for free objects. Resolution of this issue is a topic for future research.

## Figures of Merit

We evaluate our results by reporting the net savings in:

1. Reference Counting,

2. Allocation Activities, and
### 3. Deallocation Activities.

The savings in 2 and 3 equal the number of allocated and deallocated method contexts. We do not include block contexts owing to the difficulties with handling blocks (see p. 332). This omission will not affect our results significantly because we observed that only 7% of all contexts *allocated* are block contexts (in contrast to 6% of all *activated* contexts). The savings in 1 equals the number of reference counts of cached method context fields (e.g., in active and deactivated contexts, also in initialized, but inactive, contexts) minus a small overhead.

The Smalltalk-80 system has three types of reference-count operations, listed here in order of increasing time complexity:

1. Reference-count requests that cannot be satisfied (the object cannot be reference counted).

2. Reference-count increment (*refI*).

3. Reference-count decrement (*refD*).

1 is decided by a simple check of the object table. 2 or 3 occur depending on the outcome of the check in 1, and 3 is accompanied by a check for zero, since the object might be free.

We simplify the analysis of reference-count savings by ignoring references from block contexts (they account for only 5% of all references²⁸) and by assuming a minimum cache depth of two windows. This latter simplification forces most references contained by method contexts to always be in the cache:

1. The home context.

2. The sender (the caller context for blocks) context.

3. A newly created context.

Only two of these three contexts need be cached at one time since the SVM disposes of the sender context when activating a new one. To determine the savings owing to volatilization we maintained separate tallies for reference-count operations of volatile fields (as mentioned in 1 through 3 above) and nonvolatile fields. The tallies were broken down further into *refI*'s and *refD*'s. Table 19.1 summarizes these data—it shows that volatilization of contexts reduces reference counting by 91%.

*Experimental Results—The Effects of Volatilization*
<table><caption>Table 19.1 Savings Owing to Volatilization</caption><thead><tr><th>Object</th><th>refT's</th><th>refD's</th><th>Totals</th></tr></thead><tbody><tr><td>Volatile Contexts</td><td>492890</td><td>847979</td><td>1340869</td></tr><tr><td>Other Objects</td><td>65747</td><td>66789</td><td>132536</td></tr><tr><td><strong>Savings (%)</strong></td><td><strong>88</strong></td><td><strong>93</strong></td><td><strong>91</strong></td></tr></tbody></table>

Two events reduce these savings:

1. Window underflows and overflows.

2. Periodic stabilization.

To measure these reductions we simulate a register cache. The simulator stacks the active contexts (in memory and in the registers) and maintains the bounds of the cached contexts to keep track of underflows and overflows.

On an overflow the SVM writes out part of the bottom window to memory: the stack, header, and temporaries. When done writing it also reference counts these fields. Owing to linear context nesting the SVM can infer the sender from the top of stack pointer so the context header is shortened to four fields.

On an underflow the SVM restores the top window in memory into the registers and then it refD's the cached fields. The cost of an underflow is the same as an overflow. Table 19.2 shows that for an 8 window cache, the additional reference-count operations caused by underflows and overflows offsets the gains (of 91%) by no more than 2%.

<table><caption>Table 19.2 Cost of Overflows and Underflows</caption><thead><tr><th rowspan="2">Activity</th><th colspan="3">Cache Depth (# of Windows)</th></tr><tr><th>4</th><th>8</th><th>16</th></tr></thead><tbody><tr><td>% overflows</td><td>19</td><td>3.0</td><td>0.0</td></tr><tr><td>% underflows</td><td>20</td><td>3.0</td><td>0.0</td></tr><tr><td>% degradation</td><td>6</td><td>2.0</td><td>1.4</td></tr></tbody></table>

During reclamation the Smalltalk-80 virtual machine accounts for all reference-countable cached references, so it does not reference count the ip and sp fields of volatile contexts. When done it revolatilizes these fields. Table 19.3 shows that this overhead degrades the savings (by causing extra reference-count operations) by less than 1%.
<table><caption>Table 19.3 Losses Owing to Periodic Stabilization and Volatilization</caption><thead><tr><th rowspan="2">Period<br>(Bytecodes)</th><th colspan="2">4 Windows</th><th colspan="2">Cache Depth<br>8 Windows</th><th colspan="2">16 Windows</th></tr><tr><th>Loss<br>(Ops)</th><th>Loss<br>(%)</th><th>Loss<br>(Ops)</th><th>Loss<br>(%)</th><th>Loss<br>(Ops)</th><th>Loss<br>(%)</th></tr></thead><tbody><tr><td>8000</td><td>3354</td><td>0.2</td><td>6707</td><td>0.4</td><td>13414</td><td>0.8</td></tr><tr><td>16,000</td><td>1676</td><td>0.1</td><td>3354</td><td>0.2</td><td>6707</td><td>0.4</td></tr><tr><td>32,000</td><td>838</td><td>0.1</td><td>1676</td><td>0.1</td><td>3354</td><td>0.2</td></tr><tr><td>64,000</td><td>419</td><td>0.0</td><td>838</td><td>0.1</td><td>1676</td><td>0.1</td></tr><tr><td>128,000</td><td>210</td><td>0.0</td><td>419</td><td>0.0</td><td>838</td><td>0.1</td></tr></tbody></table>

Besides register examination, reclamation includes pointer chasing (number of recursive refD's done), exclusive of those done to method contexts, plus object deallocations. Since this work is also done incrementally in a non-volatilizing system it does not affect reference-counting activity but it does affect reclamation latency time. To calculate the reclamation latency we assume that the SVM executes 128K bytecodes/second and that it takes 400ns to execute an instruction or to locate a free object in the ZCT. The Appendix shows that it takes 2.8µs to free an object and 2.7µs, on average, to "chase a pointer". Table 19.4 shows the latency period for different combinations of the experimental variables. The latency time is always less than 41ms (the time spent stabilizing and volatilizing the cache is insignificant compared to the time spent reclaiming²⁹), so it does not slow down the system's response time appreciably. Table 19.4 provides the information needed by an implementor to adjust the reclamation period to suit any response time constraints.

<table><caption>Table 19.4 Reclamation Latency Time</caption><thead><tr><th>Reclamation<br>Period (K BC)</th><th>Execution<br>Time (ms)</th><th>Frees</th><th>Fields<br>Chased</th><th>Reclamation<br>Time (ms)</th></tr></thead><tbody><tr><td>8</td><td>63</td><td>136</td><td>811</td><td>3</td></tr><tr><td>16</td><td>125</td><td>271</td><td>1622</td><td>5</td></tr><tr><td>32</td><td>250</td><td>543</td><td>3245</td><td>10</td></tr><tr><td>64</td><td>500</td><td>1085</td><td>6489</td><td>21</td></tr><tr><td>128</td><td>1000</td><td>2170</td><td>12978</td><td>41</td></tr></tbody></table>
## Evaluation

For interactive use, we recommend 128K bytecode reclamation periods. At this interval the accumulation of unusable storage is reasonable, 10K words³⁰, and the latency time is short, 41ms. We recommend an 8 window cache. Eight windows are far superior to four, but we appear to reach a diminishing rate of return at 8; 16 windows do not improve performance (i.e. overflow and underflow rates) significantly.

Our scheme reduces storage reclamation time by at least 80%—it rarely allocates method contexts, avoiding 82% of the object allocations and deallocations, and does 89% fewer reference-count operations than a non-volatilizing implementation. Reclamation overhead is reduced to 4% to 5%, and generally, the SVM performance is improved by 22%-27%³¹.

Although we have not considered the speedup due to the caching of contexts in fast registers, we feel that it will be significant. We base our choice of fast registers over slower memory on current trends which favor the inclusion of more processor registers³².

Our results were based on a 400ns processor cycle time. If a faster or slower one is available, then an implementor will adjust the reclamation period to suit any response time requirements.

## Conclusions

A Smalltalk-80 system can save considerable time managing dynamic storage if it treats context objects as special objects. The hardware is inexpensive and a 20% general improvement in performance is realizable. The savings could be as high as 30%, depending on the implementation³³.

Although the strategy looks attractive, we must caution the reader that we have not dealt with two significant issues: how to reclaim cyclic garbage, and how to handle the special cases mentioned on p. 332. In the first case, we must resort to garbage collection or develop a scheme to keep track of cycles³⁴. In the second case, the system implementor must weigh the technique's benefits against its complexity. The special cases are not straightforward and their complexity may make our scheme appear less attractive, i.e., we may want to replace the reference-count technique by garbage collection. No clear-cut answer has been found.

## Acknowledgments

I'd like to thank my colleagues here at Berkeley: Ricki Blau, Clem Cole, John Foderaro, Robert Hagmann, Peter Kessler, Ed Pelegri, Richard Probst, Russell Wayman, and especially David Ungar, with whom I
spent many enjoyable evenings discussing Smalltalk. At Xerox: Adele Goldberg, Dan Ingalls, Ted Kaehler, Glenn Krasner; also Peter Deutsch, who has shared with me and my colleagues a good deal of his insight into the Smalltalk-80 system. At Hewlett-Packard, I'd like to thank Bob Ballance, Ted Laliotis, and Jim Stinger. Without their help this work would never have been possible.

Two faculty members have been instrumental in the execution of this project: Yale Patt and my advisor David Patterson. Yale kindly offered his time as second reader. Dave made Smalltalk a reality at Berkeley. He provided a good deal of moral support—I am grateful for his time and for his consideration throughout the project.

## Appendix—Analysis of Storage Reclamation Times

Reclamation consists of two activities: marking the entry as "free" in the object table, and chasing its pointers. We present both algorithms, assuming one 400ns machine instruction per step. We include branching probabilites at all decision steps (they are enclosed in square brackets, e.g. "[0.24]"). These probabilities were reported in³⁵.

The freeing algorithm involves seven steps totaling 2.8µs:

1. Read and clear a ZCT entry.

2. Shift the Oop (to remove the tag bit).

3. Read the OT entry.

4. Set the "free" bit.

5. Write the OT entry back.

6. Thread the free object (in the object memory) into the free list.

7. Update the head-of-free-list pointer.

The pointer chasing algorithm involves 12 steps totaling 2.7µs:

1. Read the field.

2. Nil the field.

3. Was the field a SmallInteger? If so, exit [0.10].

4. Shift the Oop to remove the tag bit.

5. Read the OT entry.

6. Extract the Permanent bit.
7. Is the object Permanent? If so, exit [0.80].

8. Read the reference count.

9. Decrement the count.

10. Write back the count.

11. Is the count zero? If not, exit [0.97].

12. Toggle the ZCT entry.

References

1. Deutsch, L. Peter, and Bobrow, Daniel G., "An Efficient Incremental Automatic Garbage Collector", Communications of the ACM vol. 19, no. 9, pp. 522-526, Sept. 1976.

2. Deutsch, L. Peter, Lecture given to the Berkeley Smalltalk Seminar, Feb. 5, 1982.

3. __________, Private Communication, 1982.

4. Snyder, Alan, "A Machine Architecture to Support an Object-Oriented Language", Ph.D. Dissertation, MIT Laboratory for Computer Science, MIT/LCS/TR-209, March 1979.

5. Baden, Scott, "Architectural Enhancements for an Object-Based Memory System", CS292R Class Report, Computer Science Div., Dept. of E.E.C.S., Univ. of California, Berkeley, CA, Fall 1981.

6. Cole, Clement T., Pelegri-Llopart, Eduardo, Ungar, David M., and Wayman, Russell J., "Limits to Speed: A Case Study of a Smalltalk Implementation under VM/UNIX", CS-292R Class Report, Computer Science Div., Dept. of E.E.C.S., Univ. of California, Berkeley, CA, Fall 1981.

7. Hagmann, Robert, "Some Smalltalk Performance Measurements Emphasizing Compiler Performance and/or Context Windows", Unpublished Class Paper for CS292R, Computer Science Div., Dept. of E.E.C.S., Univ. of California, Berkeley, Fall 1981.

8. Cole, Clement T., Pelegri-Llopart, Eduardo, Ungar, David M., Wayman, Russell J., "Limits to Speed: A Case Study of a Smalltalk Implementation Under VM/UNIX", CS-292R Class Report, Computer Science Div., Dept. of E.E.C.S., Univ. of California, Berkeley, Fall 1981.

9. See reference 2.
10. *Ibid.*

11. *Ibid.*

12. *Ibid.*

13. Patterson, David A., Sequin, Carlo H., "RISC I: A Restricted Instruction Set VLSI Computer", Eighth Symposium on Computer Architecture, Minneapolis, Minn., May 1981.

14. See reference 1.

15. See reference 4.

16. See reference 2.

17. *Ibid.*

18. Baden, Scott, "High Performance Storage Reclamation in an Object-Based Memory System", Master's Report, Computer Science Div., Dept. of E.E.C.S., Univ. of California, Berkeley, June 9, 1982.

19. *Ibid.*

20. See reference 3.

21. *Ibid.*

22. See reference 18.

23. Goldberg, Adele, and Robson, David, *Smalltalk-80: The Language and Its Implementation*, Addison-Wesley, Reading, Mass., 1983.

24. See reference 18.

25. See reference 3.

26. Ungar, David, Private Communication, 1982.

27. See reference 18.

28. *Ibid.*

29. *Ibid.*

30. *Ibid.*

31. *Ibid.*

32. See reference 13.

33. See reference 18.

34. See reference 3.

35. See reference 18.
Index

Applications 12, 14, 76, 273-286, 287-297

Benchmarks 153-173, 187, 203, 208, 235-236

Cache'd interpreter state 45, 51, 55, 86, 120-123

Code files 29-40, 275

Code representation 11, 14, 16, 21, 108

Contexts 10, 14-16, 18, 20, 100, 147, 312-314, 332

Display subsystems 60, 71, 81, 88-91, 189, 196-197, 319-320

File systems 8, 32, 76, 287-297

Graphics

BitBlt 13, 18, 45, 61, 63, 88-91, 98, 196-197, 319

Turtles (Pens) 12

Hardware considerations 45, 113-126

Image format 92, 149

Implementation languages 46, 63, 114-117, 302

Assembler 46, 114-117, 171

Bliss-32 171

C 81, 82, 170, 171

Pascal 43-44, 54, 61-62, 81, 171

Smalltalk-80 41-44, 265-266

Implementors

Apple Computer Inc. 5, 171, 175-187

Digital Equipment Corp. 5, 127-150, 171

Fairchild Laboratory for Artificial

Intelligence Research 8

Hewlett-Packard 5, 79-112, 171, 207-237, 331

Tektronix Inc. 5, 45, 54-55, 59-78, 171, 287-297

University of California, Berkeley 8, 84, 170, 189-206, 239, 243, 245, 324, 331

Xerox Corp. 113-126, 170

Inheritance 22

Interpreter organization 114-117, 176-179, 233-234, 306-308

Measurements

BitBlt 197

Bytecode characteristics 181, 184, 190, 191, 196, 208-210, 217-223

Send characteristics 184-186, 210-217

Storage management 198-202, 223-233

Method lookup cache 87, 148, 202, 239-247

Multiple processes 51, 303-304

Mutation (Become) 19, 143

Operating system 70, 81, 109, 147-148

UNIX 82, 107-108, 109, 171

VMS 130, 171

Smalltalk systems

Smalltalk-72 3, 5, 10-13

Smalltalk-74 13-14
Smalltalk-76 3, 7, 14-17
Smalltalk-78 17-20
TinyTalk 20
Smalltalk-80 Implementor's Conference 7, 153
Snapshot/Crash recovery 23, 37, 90
Software development environment 61, 68, 71, 72, 82, 101, 103-108, 149, 181
Storage Management 10, 48-50, 52-54, 61-62, 70, 91, 118-119, 128, 176, 194-195, 305-306, 315-317
Object Pointer formats 16, 18, 46-48, 55, 91, 129, 130-132, 252-253, 303
Object table formats 93, 146, 253
Storage reclamation 53-54, 55, 95, 96, 100, 102, 128-129, 130, 133-144, 147, 192-193, 262-263, 304, 308-310, 331-342
Virtual Memory 21, 129, 144-146, 251-271, 304
LOOM 144, 251-271
Ooze 14, 17, 25, 144

Word size/Object body format 93, 130, 254-257, 310-314, 327-328
System cloning 17, 24, 26
Target Machines 80-81
Alto 12
DECSYSTEM-20 61-62, 81
Dolphin 44, 170, 172, 324
Dorado 44, 113-126, 170, 324
iAPX-432 299-321
MC68000 45, 46, 54, 60-62, 171, 175-187
NoteTaker 17-20
PDP-11/23 128-129
VAX/11-780 81, 127-150, 171, 189, 201
Variable Typing 21, 323-330
Version management 6, 273-286
Virtual Image Traces 6-7
Virtual Images
First Image 6, 64, 81
Fourth Image 7, 74, 85
Second Image 6, 69, 83
Third Image 7, 71, 74, 84
<figure><img src="image_66.png" /></figure>
**Smalltalk-80: Bits of History, Words of Advice** provides insights into the implementation of the Smalltalk-80 system — a personal, integrated, interactive programming environment. It will be of value to Smalltalk-80 system implementors, as well as to system programmers in general.

This book is organized into four sections. The first section contains papers discussing the history of the Smalltalk-80 system, and in particular the development of the Smalltalk-80 Virtual Machine. In the second section the authors discuss their implementation experiences. The third section provides measurements of key parts of the implementations. The papers in the fourth section describe the future paths that Smalltalk-80 implementors may take.

The authors of these papers are affiliated with five different corporations and two universities. Glenn Krasner, the editor, is a member of the Software Concepts Group at the Xerox Palo Alto Research Center (PARC). This book of implementation considerations is the second in a series of four books on the Smalltalk-80 programming environment.

Other books in the Addison-Wesley Smalltalk-80 Series:

*Smalltalk-80: The Language and Its Implementation* (11371-6)

*Smalltalk-80: The Interactive Programming Environment* (11372-4)

*Smalltalk-80: Creating a User Interface and Graphical Applications* (11370-8)