Since the cached IP and SP values change during execution, occasionally it is necessary to synchronize them with their values in object memory. Some of these occasions are:

1. Change of current active context.

2. Access of the current active context (e.g., `instVarAt:` and `instVarAt:put:` primitives).

3. Certain object memory management operations (e.g., compaction).

The most complex operation in the interpreter is message selector lookup. A message send enters the interpreter along with the class of its receiver and a selector. The *current class* below is initially the class of the receiver of the message. The algorithm implementing class behavior inheritance is as follows:

1. Search for the selector in the message dictionary of the current class.

2. If the selector is not found and the superclass of the current class is not nil, then set the current class to its superclass and go to (1).

3. If the selector is not found or the search reaches the end of superclass chain, then give a *message not understood* error.

Unfortunately, even though message dictionary access is through a hash function, the inevitability of selector collisions and the attractiveness of behavior inheritance cause a fair amount of *both* linear dictionary searching and superclass chain traversal. We added a simple method cache which eliminated much of the overhead, especially during repetitive tasks. The clumping of both selector and class values required a hash scheme with unusual characteristics. The cache has 509 elements and the hash function is

((selector bitShift: -1) bitXor: (class bitShift: -1) \ 509) bitShift: 2

Using a large prime for the cache size distributes hashes more evenly and gives performance comparable to caches four times the size. Unfortunately, any time the system changes the object pointer of a compiled method, selector, or class, Smalltalk invalidates the entire cache. A more sophisticated approach to cache management would be a welcome addition.

We have recently modified the interpreter to transfer the receiver and arguments using the fast block move instruction on the VAX. This has significantly reduced the overhead of context initialization.
## Primitives

The system primitives are the roots of the Smalltalk-80 virtual machine. One can view the primitives as a collection of system calls, a library of procedures, or a set of very important methods. Primitives exist for two reasons: Smalltalk cannot implement all system functions (e.g., I/O and basic arithmetic), and more important, Smalltalk code often cannot perform well enough for certain special functions (e.g., graphics).

We implemented most of the non-arithmetic primitives with UNIX system subroutines, and added additional software layers to handle error conditions, to interface with other software and hardware components, and/or to simulate particularly unusual operations. In all, a mass of over 100 C procedures implements the more than 80 primitives included in our system.

While it is not possible to code some primitive operations in Smalltalk, not all of them have to be implemented underneath the system. Indeed, some primitives begin life as Smalltalk methods and enter native code after careful evaluation of cost and benefit. As a result, some primitives remain as optional native implementation candidates, with backup Smalltalk code in place to execute if the associated primitive routine is absent or fails. An example is the set of primitives which handle arbitrary precision arithmetic, all of which have Smalltalk code to execute if the primitive invocation balks.

The term *primitive* does not refer to the complexity of the routine, though many are simple, straightforward functions. Rather, it describes the level of implementation—the lowest level possible. Our decision to develop the system in portable high-level languages was in direct conflict with this notion. However, since we could not modify the microcode on our VAX, we had no alternative for the prototype system and the performance of the primitives suffered accordingly. We feel that microcoded Smalltalk-80 virtual machine support could have improved performance by an order of magnitude over our existing system.

One of the more unwieldy concepts in the implementation was that of primitive failure: how and where to look for it, and what to do about it. We implemented most primitives with relatively strict runtime checking of the classes and value ranges of receivers, arguments and their fields. The current system probably has too many checks for valid receivers and arguments, but in some cases these were vitally necessary and helped us considerably during the debugging phase. In particular, the `copyBits` primitive contains a number of such checks. This checking may be stricter than absolutely necessary given the way the Smalltalk-80 code actually uses the primitives. However, we did not feel the specification of the Smalltalk-80 virtual machine was precise enough to rule out the need for these checks.

The addition of primitives for string processing (`replaceFrom:to:with:startingAt:`) and for line drawing (`drawLoopX:Y:`) re-
sulted in impressive performance gains for work in those domains. However, we did not implement the arbitrary precision arithmetic and the file system primitives. Currently the arbitrary precision arithmetic primitives default to backup Smalltalk code which is relatively slow. This is not a serious problem since most Smalltalk system arithmetic stays within the signed 15-bit range of immediate small integer objects. Unfortunately, we will have to redesign most of the Smalltalk file support code to incorporate a reasonable interface for sophisticated hierarchical file systems (like UNIX). The file interface supported by Smalltalk is very low level, using too much information about physical disc operation. We do not consider this approach appropriate even for implementations without an underlying file system.

Currently, we use a Lexidata 3400 graphics system connected to a VAX UNIBUS via HP-IB. The physical pointing device, a Summagraphics Bitpad One with a four-button puck, operates through the Lexidata graphics processor. The routines for graphics device interaction shield the Smalltalk-80 system from the details of these lower levels. The Lexidata display memory is maintained by tracking the class Bitmap object associated with the current display form. Every time the bit map of the current display form changes, the graphics driver sends a copy of the altered area to the Lexidata. Since the at:put: primitive can potentially change the bit map, it recognizes when the destination is the display bit map and invokes the graphics driver.

The graphics system required much work to get to its present condition. We began with a 1280 x 1024 display optimized for white on black graphics and a track ball with illuminated throw switches. An HP-IB interface was designed especially for the Lexidata under a special contract and this was our pathway into the host machine. As time passed, pieces of the system fell into place. We developed microcode to use the bit pad in place of the track ball. The bit plane logic was reversed to display a white dot when the corresponding bit is off for black on white graphics. Other parameters and microcode in the graphics processor were modified to enhance black on white graphics, but there were limits to this. Regardless of mode, we could not use the system at its maximum resolution. We compromised for improved readability by using the graphics processor to double the pixels in both the X and Y dimensions so that a 640 x 480 Smalltalk screen neatly occupies the display. We even have room at the bottom of the display for system messages. In short, this experience was a baptism of fire in computer graphics.

We did try to optimize copyBits by implementing the bit copying operations in VAX assembly language. In this experimental version of copyBits we could copy an entire 640 x 480 pixel bit map in 0.08 second (about 10 times faster than the C routine). Unfortunately, the VAX bit operations work in the opposite direction of that needed for bit map manipulation. Our priorities prohibited modifying all of the bit map
management code for reverse bit ordering, which now included micro-code in the Lexidata graphics processor.

The current implementation of copyBits makes little use of the extended functionality of the graphics processor, such as area fill or polygon moves. The Lexidata system does manage and update the cursor as it tracks the mouse. In addition, having a screen bit map that is separate from CPU memory permits us to continuously display its contents without regard to processor operation. This is not the case with some integrated graphics configurations where display refresh consumes a significant percentage of CPU bandwidth.

The buttons on our mouse conform to the Smalltalk-80 color scheme: red on left, yellow in middle, blue on right. Because we had four buttons, we could attach more functions to our mouse. The fourth one, the green or HP button, acts as a shift key for the other three buttons. The following extended functions are available on our system:

1. green + red Take a snapshot of the system.

2. green + yellow Stop the system.

3. green + blue Print the screen.

The HP system offers two flavors of snapshot. Besides the standard Smalltalk snapshot, we implemented a *flash freeze* snapshot which saves the image without executing any Smalltalk code. This avoids the rather tedious motions of the standard mechanism, including restoration of the display screen. The user may select this alternative snapshot through a mouse function or a monitor command. Since this facility permits snapshots at arbitrary bytecode boundaries, we must preserve more state information than is strictly necessary for saving an image via the Smalltalk mechanism. For example, the keyboard input buffer would not need to be kept if we had only the Smalltalk facility. The state information falls into three categories:

**Monitor State**

Bytecode count and current bytecode. Although this information is not needed to resume execution, it is nonetheless useful, especially during debugging. When a system resumes we always know the exact bytecode where it left off.

**Cached Objects**

Oops of the current display form, the current cursor bit map, the current input semaphore, the clock semaphore, and any new process waiting to be run. In addition, we save theOops of all semaphores that have been signaled due to the occurrence of an input event. The Oop of the current active context is saved by storing it in the active context field of the current active process prior to taking a snapshot; similarly the cached stack pointer and cached in-
## I/O State

struction pointer are saved by storing their current values
in the current active context.

Cursor position, mouse position, last mouse buttons pressed, current sample interval, input polling interval, the time at which to signal the clock semaphore, the keyboard input buffer, and various indices and flags including the state of the link between the mouse and the cursor (linked or unlinked).

The system can print screen images on Printronix line printers, Versatec electrostatic plotters, and Hewlett-Packard graphics terminals in a variety of resolutions and magnifications. Anytime during a session the user may request a copy of the screen via the mouse buttons or monitor. The screen image is sent to a general bit map spooler.

We process external events and manage the input word buffer on a Smalltalk-80 virtual machine bytecode-synchronous basis. The system recognizes external events by (just before executing the next bytecode) explicitly polling the devices to determine whether they have changed state. One UNIX process implements all Smalltalk processes as well as the switching mechanism. The Smalltalk-80 system does not explicitly use the UNIX interrupt mechanism to support multiple processes. The system checks certain I/O queues after executing a fixed number of bytecodes since the last inspection. The user sets this inspection interval at system initialization.

The object memory itself is a simulator underneath the Smalltalk-80 virtual machine emulator, implementing a small-object dynamic storage manager within the large virtual memory of our host machines. As mentioned before, there are two versions of our memory system. The slow or protected version checks field index bounds and operand classes at the interpreter/object memory interface. The fast version does no checking and consists mainly of C macros. The protected version was very useful for detecting memory problems close to their source.

Access to objects in Smalltalk is via object pointers (Oops) which can be either signed 15-bit immediate integers (small integer objects) or 15-bit indexes into tables of state entries and field addresses (indirect object pointers). The 15-bit range of the object pointer (the other bit decides between small integer and indirect pointer objects) limits the number of indirect objects in the system to 32767. This limit was not a factor in our research.

The final Smalltalk-80 image is by no means small as it contains over 450 kilobytes of objects and requires at least half a megabyte with its object table. The suggested Xerox implementation uses a 20 bit address into the object space, but our implementation uses 32-bit virtual addresses. This required a reorganization of the object table into sepa-

## Memory
rate tables for the state entries and the field addresses, but the results were favorable.

<table><caption>Table 6.1 Hewlett-Packard Smalltalk-84 Image Format</caption><thead><tr><td>Word</td><td>Entry</td></tr></thead><tbody><tr><td>0-1</td><td>number of entries in the object table</td></tr><tr><td>2-3</td><td>the length of the object space in 16-bit words</td></tr><tr><td>4</td><td>system state object Oop</td></tr><tr><td>5</td><td>offset to the first entry in the table (the first offset)</td></tr><tr><td>6</td><td>object state header of the first active entry in the object table</td></tr><tr><td>7</td><td>length in 16-bit words of the first active entry in the object table</td></tr><tr><td>8</td><td>Oop of the Class of the first active entry in the object table</td></tr><tr><td>9</td><td>offset to the second entry in the table (the second offset)</td></tr><tr><td>10-12</td><td>the second active entry in the object table</td></tr><tr><td>13</td><td>offset to the next entry in the table (the third offset)</td></tr><tr><td>14-end of entries</td><td>the remainder of the object table entries</td></tr><tr><td>followed by</td><td>the fields of the objects in the table</td></tr></tbody></table>

Because of host machine differences and efficiency considerations, the HP Smalltalk-80 system uses the image format in Table 6.1 which differs from the standard interchange format. The HP format uses a special coding scheme to indicate free entries in the object table, whereas the interchange format does not eliminate the space wasted by these entries. This format is also space efficient and easy to load and save. The first 8 bytes contain the image size parameters as 32-bit unsigned integers. The number of object table entries is followed by the number of 16-bit words in the object fields space. Next, is the Oop of the system state object, used to restore Smalltalk and the support environment to their exact condition before a snapshot.

The object table follows. It is *not* stored as an exact image of the system object table (that would waste space). Each object table entry in the image is preceded by a 16-bit offset from which the next table entry location is derived. For example: if the first active Oops in the system were 12, 16, 18, 26, and 56, then the offset values (in brackets) would be:

$$ [12] > 12 + [4] > 16 + [2] > 18 + [8] > 26 + [30] > 56 $$

The first of these offsets determines the location of the first used object table entry. Thereafter the offsets are used to skip the unused entries in between the active ones.
The field pointer portion of the object table entry in memory is ini-
tialized by cumulatively adding the object lengths to the base address of
the memory allocated for the object space. Therefore, each object table
entry in the snapshot consumes 8 bytes: 2 for the offset, 2 for the head-
er, 2 for the length, and 2 for the class. After the object table entries are
read in, a single mass read brings the object field space into memory.

Saving an image is similar, except that the object field space must be
written on an object-by-object basis, since we cannot assume contiguous
allocation on a used system.

We convert the image from the standard interchange format into the
HP format by the following transformations:

1. Convert the interchange format state entries into the HP layout.

2. Move the class and length from the fields of each object into the object table entry.

3. Swap the bytes of all non-byte objects (our hosts use low-byte/high-byte ordering rather than the high/low of the image interchange format).

4. Convert objects of class Float in the image from IEEE format to VAX format. The ranges are slightly different so the conversion program indicates when it encounters an IEEE floating point number which has no VAX format correspondent.

5. Create the special HP system state objects in which the snapshot process saves relevant details so that the system may continue later from the same state.

The conversion process takes less than a minute and includes a consistency check on the interchange format image.

The implementation of our object memory system differs from that
in the Smalltalk-80 virtual machine specification. The system main-
tains two tables of object information: the first table contains the 16-bit
state entries while the second table has the length and class Oops plus
the pointer to the object fields for a size of 64-bits. Since the size of the
entries in each table is a power of two, access is fairly efficient. Previ-
ous single table versions used either 96- or 80-bit entries which re-
quired multiplies by three or five for indexing.

Each state entry contains an 8-bit reference count (used fully), and 6
flag bits for the following conditions:

1. Reference-count overflow and exemption.

2. Object is permanent.

3. Object table entry is available.
4. Object contains pointers.

5. Byte object is odd length.

6. Object has a mark (from garbage collector).

The two remaining bits are for future enhancements, such as a code bit for compiled method objects. We moved the length and class Oops from the fields of the object into this table for more efficient access. This change significantly improved performance for the protected version of object memory, and also reduced the load on the dynamic memory allocator by two words per request, but in doing so increased static allocation by 128 kilobytes. With an object table that is three-quarters full, the actual waste from this is 32 kilobytes, which is negligible in a large virtual memory system. The length entry contains the actual number of words allocated to the object fields (not the same plus two for length and class, as suggested). The pointer to the fields is a 32-bit virtual address instead of a 20-bit quantity divided into a 16-bit offset and a 4-bit segment number.

Early in the implementation, we defined the interface through which the interpreter and primitives communicate with the object memory. The strict adherence to this interface permitted an easy transition from the DEC-20 to the VAX even though their memory systems differed considerably. The interface consists of:

1. Instantiate pointer, word, and byte objects.

2. Load and store pointer, word, byte and float values.

3. Get object length and class.

4. Test and convert small integer and pointer objects.

5. Decrement and increment reference counts.

6. Find first and next instance of a class.

7. Swap object pointers.

8. Query memory allocator state.

The memory system initializes all objects upon instantiation. Word and byte objects need to have their fields set to zero, while pointer objects require nil values or 2's, which most architectures cannot do efficiently. The VAX has a block move instruction which, combined with a predefined array of nil values, is an efficient solution to this problem. The cost of using standard memory accesses to store nil in every field is excessive (since the average size is about 18 words).

Reference-count activity dominates the time spent in the memory system. We implemented a straightforward strategy and attempted to reduce the amount of checking necessary to determine whether an ob-
ject actually must be reference counted. For example, the shortest path for the count decrement operation is

check if small integer bit of Oop is set (is object a small integer?).

ifFalse: [ fetch the header of the object pointed to by the Oop.

check if exempt flag is set (is object free, permanent or overflow?).

ifFalse: [ decrement reference count.

check if reference count > zero.

ifFalse: enter deallocation routine. ] ]

The sequence for the count increment operation is

check if small integer bit of Oop is set (is object a small integer?).

ifFalse: [ fetch the header of the object pointed to by the Oop.

check if exempt flag is set (is object free, permanent or overflow?).

ifFalse: [ increment reference count.

check if reference count > zero.

(note: the byte arithmetic wraps around to zero on overflow.)

ifFalse: set exempt flag in header to overflow ] ]

Measurements of our Smalltalk-80 object memory and similar dynamic memory systems indicate that count maintenance consumes from 20% to 40% of execution time. The implementors of the M3L machine¹ demonstrated the performance advantages of special reference-count hardware. Reference-count maintenance is expensive because it congests data paths with extra traffic and requires ALU cycles during every count function. For example, a *store pointer* operation includes both a count down on the Oop at the destination and a count up on the source Oop. The cost of *store pointer* was the motivation behind its reimplementation in assembly language.

The availability of virtual memory on our host machine was an advantage in the early phases of design. Makeshift memory systems could run even while wasting a lot of space or thrashing over lists. Thus a gradual evolution of object memory implementations progressed until the better ones emerged. The current version implements:

1. A set of special allocation pools.

2. A mechanism for coalescing blocks on the general free list.

3. A marking garbage collector.

The special allocation pools were the most significant addition to the system, and they differ considerably from the free lists described in the specification. There are four pools in the system: one for each of the three most popular sizes of pointer objects and a general pool for the rest. The three special pools take advantage of the allocation frequency of small contexts, points, and large contexts. Each special pool is a
linked-list of fixed-length pieces of memory allocated at system initial-
ization and permanently residing in that pool. Only transactions requir-
ing pointer fields of the three sizes can use the special pools so there is
no fragmentation in the pool. In our standard configuration, 16
kilobytes of memory in the special pools satisfies over 97% of all instan-
tiation requests.

The transaction traffic of the memory system is very different from
that of most programming environments. The system allocates,
accesses, and just as quickly deallocates megawords of memory in
chunks typically less than 20 words. Since the special pools handle
nearly all memory traffic, we have fragmentation effects from only 3%
of allocations. Our memory allocator continuously coalesces and recy-
cles this space on the general free list, thus preventing most fragmenta-
tion problems. In view of these facts, we feel that the actual long term
fragmentation is not serious enough to warrant *dynamic* compaction.
Compaction does happen whenever we save and reload an image. This
scheme suits our view of personal computer usage patterns well—load-
ing an image, working for a while, then saving the results—and since it
takes less than 15 seconds to save and reload an image, we see little ad-
vantage to having a separate compactor.

Cycles of inaccessible objects occur with reference-counting memory
management schemes. Sadly, some of the occasions for cycle creation
involve fundamental concepts in the language, such as sending a mes-
sage with a block as an argument (where the pointer to the block con-
text is in the temporary variable area of the home context). Periodically
we run an auxiliary garbage collector to sweep the object table of all
derelict objects caught in cycles. The cost of such a collector in CPU
time is high, so it is advantageous to avoid running it. Because contexts
are most frequently involved in these cycles, the system invokes the col-
lector when either of the two special allocation pools devoted to con-
texts becomes empty. By setting the sizes of these pools at system boot
we can vary garbage collection frequency. The collector also runs when-
ever the object table becomes full, but this is a far less frequent occur-
rence. We found it necessary to lock out the garbage collector whenever
the reference counts do not accurately reflect the condition of object
memory. The current system requires collector lock-out in only a hand-
ful of situations.

The Smalltalk-80 distribution process proceeded through five test re-
leases. Each new release posed a variety of problems which we usually
resolved after a month or so of changes and corrections. Smalltalk
proved to be an incredibly robust system—so robust that it could con-
tinue to run after bugs had corrupted major sections of data or code.
For example, in implementing the primitive methods sometimes we did
not push a result on the stack before returning. In spite of this, the sys-
tem was able to execute many bytecodes before giving any indication that something had gone wrong. Problems such as this were often difficult to diagnose, even with the sophisticated debugging tools at our disposal.

We list here some of the problems and issues faced in implementing the Smalltalk-80 system in the hope that future implementors can benefit from our experience. These problems are in six categories: arithmetic, primitive methods, input/output, object memory, programming, and general problems.

□ *Arithmetic Problems* Many of the problems in the arithmetic area were with floating point numbers. One problem was that we were not certain which floating point representation was used in the first test image. In particular, floating point objects in the first image were *three* words or 48-bits, which seemed to contradict the claim that the Smalltalk-80 system used IEEE standard 32-bit single precision format. As it turned out, it was IEEE format and the system simply ignored the third word. But this was bad news—the VAX did not have IEEE standard floating point arithmetic at that time. We had to convert all objects of class Float to VAX floating point format and hope that none would be outside the VAX range. Fortunately, no Smalltalk floating point numbers have exceeded this limit. And after we went through all of this, DEC introduced IEEE floating point support for the VAX.

In another situation, the routine that extracted the fields of floating point numbers treated the fields as small integers (-16384 to 16383), when in fact they have a range of zero to 65535. This problem occurred in several places throughout the system and was the source of many bugs. As a result of these complications, we were well into converting the system for the second image before the floating point primitives went into operation.

Another problem involved the initialization of the fields of LargePositiveInteger objects. When we first installed the special allocation pools in the memory system, we set the fields of all pool objects to nil upon deallocation. The only requirement to request memory from a special pool was to be the appropriate size—there was no pointer object check. Occasionally a large integer happened to be one of the sizes handled by the special pools, and thus had nils in its fields. If one performed bit operations such as bitOr: on a large integer, these nil values could affect the result. Indeed, we found that when one added two large positive integers of certain values there were extraneous 2's in some of the lower digits of the result. The solution was to correct the locator to ensure that it only initialized pointer objects with nils.

A third arithmetic problem had to do with the // operation. It was not clear from the original documentation for the first image just what the definition of // was. As we began to use the system, occasionally we
would get a mysterious error 'Subscript out of bounds:' which did not seem to have any relation to what we were doing. We had spent quite some time searching for the cause when we discovered that the system was using the // operation to compute the index for a table, and because it truncated in the wrong direction, it often produced a negative index. As the corresponding C operator differed from the Smalltalk definition, we had some difficulty implementing the // operation correctly. Because of this confusion, the specification now includes both variants of the operation.

☐ *Problems with Primitive Methods* There was confusion over the extent of error checking to include in the implementation of primitive methods. Because there were no specific guidelines in the documentation, we decided to implement comprehensive checking. We checked the class and range of the receiver and the arguments and their fields. However, we soon encountered problems with class checking. In some cases the receiver or argument need only belong to a specified class or any subclass thereof. The class check in this situation could be time consuming since it involves a traversal of the superclass chain. Rather than endure this overhead, we removed the class check in these cases. In general, we feel that this checking gave us a useful safety net to protect the system from corrupted code and other problems, but it is not clear that such checking would be desirable in a production system.

During testing of the system with the slow version of object memory, we encountered many *load word* and *store word* range errors in the copyBits primitive. Some of these were caused by insufficient clipping of the source and destination forms. We eliminated them by adding more checks for clipping based on the sizes and relative positions of the source and destination forms. Other range errors stemmed from the way the BitBlt algorithm handled the transition from one row of the bit map to the next. When doing a preload on the last word of a bit map row, the next word loaded in computing the destination word comes from the next bit map row instead of the current row. This did no harm except when the last word of the last bit map row was at the end of the bit map. If it was, the next *load word* generated an error. We fixed this by checking whether the second *load word* goes past the end of the bit map. If it reaches the end of the bit map, we substitute zero for the second *load word* value. This is not the most efficient solution to the problem, but it preserved our investment in the copyBits primitive (which no one wanted to rewrite).

Another problem with copyBits on the third test image involved the coordinate arguments. In some instances, these coordinates contained floating point numbers instead of small integers. We had to check for floating point arguments in the makePoint routine. When the arguments to makePoint were instances of class Float, the primitive convert-
ed them to integers before making them into a coordinate point. The
final image does not suffer from this problem.

There was a rather simple problem with the swapPointersOf primi-
tive. An early implementation swapped the reference counts along with
everything else. Since the reference counts must follow the Oop and not
the table entry, the system behaved strangely until we realized what
had happened and repaired the primitive.

☐ *Input/Output Problems* We had many problems with keyboard input and character mapping. With each new Smalltalk-80 test release, we modified our keyboard input routine to accept numeric ASCII codes instead of characters in order to determine the appropriate mapping. This process became easier with each new release and particularly after the second release which was the first to use the ASCII character set.

With the second release came more problems as we had to find a way
to input control key codes for those not in the ASCII character set (e.g.,
control-0 to control-9). Since the Smalltalk I/O code could handle either
ASCII-encoded or unencoded keyboards, we designated an escape se-
quence to input unencoded control characters (control-↑ followed by the
character). In the final release, the Smalltalk methods for keyboard in-
put interfered with this scheme so we rewrote most of them.

We found it difficult to implement the polling scheme for keyboard
input on the first test image. Often the last character in the buffer
would not appear on the screen until the user typed another character
and it was interminably slow. Finally, after rewriting the keyboard in-
put primitives and maintaining better control of the buffer, the system
improved, although it was still slow. With the second test image, key-
board input was to be interrupt-driven and synchronized with sema-
phores. Initially we simulated this behavior with another polling
scheme. The system checks for keystrokes every *n* bytecodes, and if any
are waiting, it places the key codes in an input buffer and signals the
input semaphore. Recently we developed a way to eliminate polling for
text input using an interrupt scheme based on UNIX intrinsics. This
has improved overall system performance by eliminating the terminal
buffer count check which was a part of polling.

Our Smalltalk system manages the mouse in a similar manner.
Whenever the system polls the keyboard, it also checks the mouse posi-
tion and mouse buttons for activity since the last poll. If there are any
changes, the system generates appropriate event words, places them in
the input buffer, and then signals the input semaphore. Various
Smalltalk routines also query mouse position directly, posing some
question about the need for our system code to do it as well. A series of
experiments suggested that the system was more responsive with mouse
position polling in both places.
□ *Object Memory Problems* The problems with the object memory manager centered around around allocation, reference count management, and garbage collection. At one point there was infrequent trashing of some of the fields of method and block contexts. Somehow the memory system was allocating objects that were overlapping contexts. While we never discovered the source of the problem, we solved it for a while by isolating contexts into special allocation pools. The problem reappeared however, when running the interpreter on the final image. Again we redesigned the memory allocator, this time using linked lists for the pools instead of a table of pointers. We have had no problems with object memory since.

During testing of the interpreter on the second image we noticed that the memory system was allocating many small contexts while deallocating only a few through the reference counting mechanism. We later discovered that when performing sends we neglected to nil out the argument fields of the sender after transferring the arguments. This enabled cycles to develop involving block arguments and contexts. The correct transfer mechanism eliminated over 90% of these cycles.

Shortly after investigating these cycles in object memory, we decided to add a marking garbage collector to our system. At the time, our primary motivation was to reduce the size of the special pools from which the system allocated contexts. In the process of implementing the garbage collector we had to determine the root objects from which marking should proceed. We start from all cached object pointers, plus the Oop of the Smalltalk object. We were then faced with the problem of deciding when to activate the collector. Activation would certainly be tied to some sort of low watermark in the allocator, but should the collector proceed directly from there or be postponed to a safe period or a bytecode boundary? There are times when the garbage collector could do much damage, so it is vital to ensure that it cannot run during these periods. For example, sometimes the system temporarily increases the reference count of an object to ensure that it remains through a critical operation. During the interval between the artificial increment and decrement operations the reference count is inconsistent, and intervention by the collector would discard such an artificially protected object. This is because the collector chases pointers to determine the number of references to an object instead of relying on the reference count in the state header. To prevent intrusion during such operations, we devised critical section locks which disable and re-enable the collector. In addition, we make permanent (via a *permanent* bit in our object state header) those objects that are not to go away under any circumstances (e.g., true).

Once our garbage collector was working, we reduced the small context pool size from 8192 to 256 contexts, a saving of nearly 300 kilobytes of memory. Our investigations have shown that garbage collections are relatively infrequent when browsing or text editing, but
that at least one occurs when compiling or decompiling a method,
reclaiming as many as 500 objects.

☐ *Programming Problems* As with any programming project involving more than one person, we found ourselves confronted with problems of version management, communication among the members of the team, and implications of changes made to the system. We found UNIX tools to be very useful for managing these situations. In most respects, the project was a model of modern software management. All of us had a background of software projects and we placed a heavy emphasis on software tools and techniques. In fact, we considered managing the software effectively to be almost as important as implementing Smalltalk itself. Some of the management tools are described on p. 103.

We had a resource problem in having to share our host machines with other projects, some of which involved signal processing. There were times when the load on the system was so heavy that it was hopeless to attempt debugging the system. For demonstrations we would get the machine all to ourselves for acceptable performance.

Global variables, of which there were many, gave us the usual prob-
lems with proper initialization and usage. We tried to localize state
variables as much as possible to only those modules that used them. In
spite of these precautions, global variables were the source of several
bugs in the system.

Macros were also a source of problems in coding the system. Since we tried to optimize code as much as possible by using macros, we sometimes nested them several levels deep. Upon expansion, these macros could get quite large—nearly 900 characters for the *push* macro, for example. Increasing the size of these macros could produce complaints from the C preprocessor in some situations. We also had to parenthesize macro arguments to ensure the proper order of expansion. A significant difference between macros and procedures is that macro arguments are evaluated at each appearance in the definition instead of only once on procedure entry. For example, a macro may use an argument in a number of different places in the definition. If we pass it a function which always returns the same value, the macro will operate properly. However, if we pass a function like *popStack*, then at each appearance of the function in the definition it will return a different result (plus there will be too many stack pops). We used temporary variables within macro definitions to ensure that arguments are evaluated only once.

We encountered an optimization problem with printing hard copy of
the Smalltalk screen. The routine for dumping the screen to the printer
worked fine until we ran the system through the C code optimizer. Af-
ter that, the hard copy routine would print only garbage. Later we dis-
covered that the c2 code optimizer for the VAX produced incorrect code
for certain bit operations, and unless it has been changed, it still has
this bug.
□ *General Problems* The biggest general problem was with the in-complete and sometimes erroneous details of the implementation given in the book. The agreement with Xerox made it our task to debug the documentation and image test releases. As we read through the chap-ters, we found we had many questions and comments. For example, we had difficulty getting nested blocks to work. Our system was not prop-erly initializing the instruction pointer for a nested block. The initial instruction pointer was coming from the home context instead of the active context as it should have been. The documentation did not make this detail clear, and we wasted some time tracking it down.

Another problem was the result of a similar oversight. In early Sep-
tember, many of the methods in the first image were operational, but
some still were not working and others gave 'message not understood'
errors. There was no pattern to the failures and the cause seemed al-
most impossible to isolate. We had just about given up when, in a mar-
athon debugging session, we discovered that the Smalltalk compiler was
using *byte* stores to set the 16-bit header *word* of new compiled method
objects. Because byte ordering on our host machines is the opposite of
that on Xerox systems, a method header constructed in this fashion had
the bytes in reverse order. As this header encodes the number of liter-
als and temporaries as well as a special method flag, mere chance dic-
tated whether the byte-reversed header would affect the execution of
the method. The final system avoids this problem by having primitives
for compiled method creation and manipulation.

A fascinating problem cropped up when we ran the Arc example pro-
vided with the third release image. The system mysteriously went into
an infinite loop and eventually ran out of object table space through
the activation of thousands of contexts! By tracing the execution of the
interpreter and looking at the Smalltalk source code, we were able to
determine the cause of the infinite loop. The method for the Arc exam-
ple included the following

anArc Arc new.

Since Arc class did not understand the message new, it defaulted to the
new message understood by Path class, the superclass of Arc class. The
method for new in Path class contained the statement

†super new initializeCollectionOfPoints.

Following the superclass chain, we made the transition from the
metaclass to the class hierarchy by passing through Object class into
Class and eventually ended up in Behavior. Here the method new had a
primitive associated with it. However, since the receiver was an
indexable object, the primitive failed and invoked the backup Smalltalk
code which included

self isVariable ifTrue: [^self new: 0].
Since self was Arc class, we now followed a similar path starting at Arc class looking for a new: message. Again we found it in Path class, and the associated method contained

↑super new initializeCollectionOfPoints: anInteger.

The infinite loop now begins, since we were again looking for the new method in the superclass of Path class and so on. This switching back and forth between new and new: continues until memory is exhausted. The final image release avoids this problem by having the new and new: methods in Path class use basicNew instead of new. The method for basicNew in Behavior has backup Smalltalk code which uses basicNew: instead of new:. Since Path class does not understand the basicNew: message, the basicNew: message in class Behavior is executed and it succeeds, avoiding the infinite loop.

We had problems in making the transition of our system from one release of a Xerox Smalltalk image to the next. These problems were generally minor, although annoying. The most extensive changes occurred in going from the first image to the second. In general, there were differences in some class Oops, and sometimes the structures of some objects changed. Unfortunately, in most cases we had to discover these differences ourselves. These should not be problems for future implementors since the documentation has been rewritten and there will be only one Smalltalk image to deal with. This image is the fifth or final one referred to herein.

## Development Environment

An extensive collection of development tools complements the Smalltalk system at Hewlett-Packard. These tools compose our software development environment, which consists of the following layers:

1. The Smalltalk-80 system with its debugger.

2. The Smalltalk-80 virtual machine execution monitor and object memory inspector.

3. The UNIX operating system², SCCS version controller, *make* system builder, *sdb* symbolic debugger, and *prof* execution profiler.

These levels offer access to different aspects of execution. For example, we have the capability of setting breakpoints at the Smalltalk-80 statement level (Smalltalk debugger), the Smalltalk-80 virtual machine bytecode level (Smalltalk-80 virtual machine monitor), or the C source level (*sdb*). Often we use all three mechanisms to attack a problem from
each particular level of detail. The same goes for performance evaluation as we have the capability to tap in at any level to spy on the activities of the system.

We structured the first level of our development environment using the hierarchical file system of UNIX. A read-only copy of the latest stable version of the system is in a source directory, and each of the project members owns a subdirectory under it. Each member can modify, test, and debug sections of code in his subdirectory without affecting the other members who may also be debugging. This feature was made possible by the UNIX *make* facility for creating, maintaining, and installing software. Someone working in a subdirectory who wants to put together a system using some changed source files simply asks *make* to build it. *Make* determines whether any source needs to be recompiled, and then loads the new code from the subdirectory and the rest from the source directory. Duplication is minimal as there is only one copy of the master source plus those pieces that people are working on in their subdirectories.

The Source Code Control System (SCCS) was our primary tool for dealing with version management issues. Whenever one wants to make a change to a piece of the system, one asks SCCS for a modifiable copy of the latest version. If no one else has a copy out, SCCS acquiesces and places the copy in the subdirectory. After successful testing of the modifications, one sends the modified copy back to SCCS and informs the system version manager of the change. The version manager asks SCCS to place a read-only copy of the new files into the source directory, and then gets *make* to build a new system. It is important that only well tested modifications make it to the source directory since all of the work in the subdirectories depends on the stability of that code. Fig. 6.1 depicts an execution monitor command menu, and Fig. 6.2 shows an execution monitor chain of context display.

type ?? for the list of commands
>> ??
>>
System multiple step ms, single step ss, continue cs, run rs
display state ds, update freq us, breakpoint bs, trace ts
Image load li, inspect ii, save si
Graphics reset rg, print pg
Other monitor mc, statistics sc, context chain cc, receiver update ru
Window Help wh, Banner wb, Inspector wi, Smalltalk ws
Context wc, Receiver wr, Methodwm
Keys ↑C interrupt, ↑V quote, ↑X break, ↑Z suspend, ↑\core dump
↑ upArrow, ← leftArrow, ↑T ifTrue:, ↑F ifFalse:, ↑↑ control
ESC select, DEL delete, ↑W deleteWord, ↑↑[0-9] fonts
** default radix is Decimal - prefix with 0 for Octal, 0x for Hex
** Shell sh * Help ?? * Exit qq

<caption>Figure 6.1</caption>
<table><caption>Figure 6.2</caption><thead><tr><th>context</th><th>class</th><th>method</th><th>receiver</th><th>class</th></tr></thead><tbody><tr><td>7c3a</td><td>16</td><td>72cc</td><td>238a</td><td>1a &lt; Point &gt;</td></tr><tr><td>7c06</td><td>16</td><td>552e</td><td>8aa</td><td>66a &lt; InputSensor &gt;</td></tr><tr><td>7c3e</td><td>16</td><td>232c</td><td>7908</td><td>3ef4 &lt; StringHolderController &gt;</td></tr><tr><td>7d32</td><td>16</td><td>4bae</td><td>7908</td><td>3ef4 &lt; StringHolderController &gt;</td></tr><tr><td>7cf6</td><td>16</td><td>650</td><td>7908</td><td>3ef4 &lt; StringHolderController &gt;</td></tr><tr><td>7c74</td><td>16</td><td>660</td><td>7908</td><td>3ef4 &lt; StringHolderController &gt;</td></tr><tr><td>7abe</td><td>16</td><td>632</td><td>7932</td><td>11f0 &lt; StandardSystemController &gt;</td></tr><tr><td>7cb2</td><td>16</td><td>648</td><td>7932</td><td>11f0 &lt; StandardSystemController &gt;</td></tr><tr><td>7d10</td><td>16</td><td>1ae8</td><td>7932</td><td>11f0 &lt; StandardSystemController &gt;</td></tr><tr><td>7c96</td><td>16</td><td>650</td><td>7932</td><td>11f0 &lt; StandardSystemController &gt;</td></tr><tr><td>7cae</td><td>16</td><td>660</td><td>7932</td><td>11f0 &lt; StandardSystemController &gt;</td></tr><tr><td>7d5c</td><td>18</td><td>5606</td><td>7d6e</td><td>16 &lt; MethodContext &gt;</td></tr><tr><td>79f8</td><td>18</td><td>784</td><td>798c</td><td>16 &lt; MethodContext &gt;</td></tr></tbody><tfoot><tr><td colspan="5">active process: 7c40 priority = 4</td></tr></tfoot></table>

Central to the multi-level environment is the Smalltalk-80 virtual machine execution monitor (Fig. 6.1), a runtime facility offering the following services:

1. Transfer Smalltalk-80 images between object memory and the UNIX file system.

2. Variable step and run modes for the Smalltalk-80 virtual machine interpreter.

3. Manipulate Smalltalk-80 virtual machine-level breakpoints.

4. Display the current state of the Smalltalk-80 virtual machine.

5. Trace the chain of method and block contexts, as in Fig. 6.2.

6. Print the contents of the display bit map on a hardcopy device.

7. Enable Smalltalk-80 virtual machine functional tracing.

8. Invoke the object memory inspector.

In Fig. 6.3, a memory inspector subsystem command menu is presented. The last capability links the monitor to this inspector subsystem, a family of services concerned with object memory state:

1. Examine and change the current state of object memory.

2. Create new instances of classes in object memory.

3. Verify the current reference-count state of object memory.

4. Invoke garbage collection for object memory.
type ?? for the list of commands

< < ??

< <

Load word lw, byte lb, float lf, string ls

Store word sw, byte sb, float sf, string ss

Length word wl, byte bl

Show header hs, object os, context cs, method ms

Reference Count display rc, verification vc, garbage collection gc

Instantiate Class withWords iw, withBytes ib, withPointers ip

Window Help wh, Banner wb, Inspector wi, Smalltalk ws

Context wc, Receiver wr, Methodwm

** default radix is Decimal - prefix with 0 for Octal, 0x for Hex

** answer 'y' or 'n' when asked 'more?'

** Shell sh * Help ?? * Exit qq

To diagnose problems in dynamic memory management, we developed a facility to verify the reference counts of all objects in the system. It steps through the object table recording the number of pointers to each object and then checks this against the reference count field of each object. The routine produces a listing of objects with reference count dis-

HP Labs Smalltalk-84 System

>> ds

| RS| AC 7cca| 13501316 | Next b0/260 + | Last 76/166 P+1

>>

<table><caption>Figure 6.4</caption><tr><td>OTE7cca| 1VDfmPe[18</td><td>OTE7cba| 9VDfmPe[12</td><td>OTE135e| 2VDfmpo[54]</td></tr><tr><td>Se 7c92 &lt;MethodConte</td><td>#00 7c7c &lt;Text&gt;</td><td>Hdr 0519= 0 5 s 12</td></tr><tr><td>PC 85</td><td>#01 7ca8 &lt;TextStyle&gt;</td><td>L00 0130 A 0010 C &lt;Array&gt;</td></tr><tr><td>SP 7</td><td>#02 7cc0 &lt;Point&gt;</td><td>L01 0041 32D</td></tr><tr><td>Me 135e &lt;CompiledMet</td><td>#03 0002 Nil</td><td>L02 0dd6 U "height:"</td></tr><tr><td>RM 0002 Nil</td><td>#04 7ca4 &lt;Rectangle&gt;</td><td>L03 1360 U "in:"</td></tr><tr><td>Re 7cba &lt;Paragraph&gt;</td><td>#05 7cda &lt;Rectangle&gt;</td><td>L04 1362 A 1366 C &lt;Compo&gt;</td></tr><tr><td>T0 0061 48D</td><td>#06 0a52 &lt;DisplayScr&gt;</td><td>L05 1302 U "lineAt:put:"</td></tr><tr><td>T1 0087 67D</td><td>#07 0007 3D</td><td>L06 1376 U "composeLine"</td></tr><tr><td>T2 000d 6D</td><td>#08 1560 &lt;Form&gt;</td><td>Index:inParagraph</td></tr><tr><td>T3 0093 73D</td><td>#09 0001 0D</td><td>L07 01fe U "max:"</td></tr><tr><td>T4 7cdc &lt;Composition</td><td>#0a 7cd8 &lt;Array&gt;</td><td>L08 1378 U "rightX"</td></tr><tr><td>S1 006f 55D</td><td>#0b 000d 6D</td><td>L09 01d0 U "last"</td></tr><tr><td>S2 0003 1D</td><td></td><td>L0a 12f4 U "updateCom"</td></tr><tr><td>S3 7cf2 &lt;TextLineInt</td><td></td><td>L0b 12f6 U "trimLines:"</td></tr><tr><td>S4 000d 6D</td><td></td><td>#00 4021cd820a75820b756</td></tr><tr><td>S5 0061 48D</td><td></td><td>#10 75e287137c768142680</td></tr><tr><td>S6 7cba &lt;Paragraph&gt;</td><td></td><td>#20 6c1011b399a41c701214</td></tr><tr><td>S7 0002 Nil</td><td></td><td>#30 8714d813e76b0a12c0d</td></tr><tr><td></td><td></td><td>#40 6aa3de70da87701276</td></tr></table>
crepancies as well as those with permanent or overflow bits set. Usually all objects, except for a handful, have valid reference counts. The few exceptions are the objects cached by the system (e.g., the active context), and the Smalltalk object (SystemDictionary) which has an artificially increased reference count to prevent accidental deallocation.

Our system actually uses two displays: a graphics display for Smalltalk and a CRT terminal for the monitor and UNIX. Smalltalk, the monitor, and UNIX share the terminal keyboard. The presentation of information from the monitor facilities posed an interesting problem. It was impossible to squeeze everything into the 24 x 80 terminal format so we took a lesson from Smalltalk itself and implemented seven overlapping windows for the user interface. The user can select which windows to view and the system preserves the contents across selections. General command interaction uses a window consisting of the top four lines of the screen and the other windows do not overlap this region. Windows for diagnostic, inspector, and Smalltalk interaction fit into the other twenty lines. Fig. 6.4 shows the three vertically-overlapping 20 x 40 windows which display the active context, receiver, and compiled method components of the Smalltalk-80 virtual machine state. Most of the context and receiver information is in the leftmost 20 columns of their windows, so having those windows overlap was not a problem. The user can also close the receiver window to get full view of the context and the method.

<table><caption>Table 6.2 Notation for Displaying Objects</caption><thead><tr><td>class</td><td>example</td><td>description</td></tr></thead><tbody><tr><td>Small Integer</td><td>0205 258D</td><td>small integer value in decimal</td></tr><tr><td>Special Object</td><td>0006 True</td><td>name of object</td></tr><tr><td>Symbol</td><td>0132 U "Array"</td><td>(unique strings) U followed by string</td></tr><tr><td>String</td><td>0664 S "a string"</td><td>S followed by string</td></tr><tr><td>Association</td><td>0008 A 6f20 &lt;Arc&gt;</td><td>A followed by value field</td></tr><tr><td>Metaclass</td><td>73ea C &lt;File&gt;</td><td>C followed by class name</td></tr><tr><td>Other</td><td>72cc &lt;Turtle&gt;</td><td>class name within angle-brackets</td></tr></tbody></table>

The user can have the context, receiver, and method windows of the Smalltalk-80 virtual machine state display dynamically updated with execution. The frequency of update is selectable, and performance is acceptable even for small granularity updates. One can watch the stack values, temporaries, and instance variables change, and display enhancements indicate the current positions of the stack pointer and program counter. We follow a convention for single-line object descriptions in the window system. In all cases, we display the object pointer in hexadecimal format, and the additional object-specific information is
described in Table 6.2. The motion-picture Smalltalk-80 virtual machine state display proved invaluable to the debugging effort. The performance of the system under full display is quite good.

Both the monitor and the inspector can escape to the UNIX shell to execute commands there. The monitor intercepts certain control characters and will halt execution, kill the system, or dump the core image to a file on request. As a special feature, the monitor traps all fatal errors and recursively invokes a new copy of itself to hunt for the cause. Then we can use the inspector to fix wayward values and continue execution.

## Future Directions

As Smalltalk enters the real world there is much speculation over future directions for the system. Although the Smalltalk-80 distribution test process was thorough in eliminating problems in the system, many issues remain unresolved such as network interfacing and multiple inheritance, and there has been little time to implement the more ingenious optimizations. Hence there is much room for improvement in the design.

All of the test site implementations used high-level or assembly language to implement an interpreter for the Smalltalk-80 virtual machine. Unfortunately, this approach produced significantly degraded performance compared to native mode execution of the processor (a penalty of 40 to 200 times slower). The elimination of the Smalltalk-80 virtual machine as an intermediate stage could boost performance considerably, but this would necessitate the implementation of a Smalltalk-80-to-native-code compiler.

Early in our project we had investigated a native compiler strategy. Our bytecode execution frequency figures indicate that such an approach would be worthwhile. Over 70% of the Smalltalk-80 virtual machine bytecodes executed in normal usage (push, pop, store, jump, return) map to at most a few instructions in an ordinary computer. In addition, nearly 85% of all bytecodes executed (those above plus the special sends) translate to in-line sequences of instructions, including a procedure call escape for the exceptional cases. Only about 15% of Smalltalk execution requires the message lookup process where procedures perform the late binding. Because the Smalltalk-80 virtual machine compiler is written in the Smalltalk-80 language, the development of a native code version requires a stable Smalltalk-80 system to begin with.

In spite of the myriad optimizations proposed and implemented, a Smalltalk-80 system seems doomed to lower performance than more
traditional programming systems. There are two areas where Smalltalk loses to other languages. One is the 15% of execution which requires message lookup. Message cache schemes lessen the penalty, but speed is still impaired by the symbol matching and indirection. The other area involves the automatic memory management provided by reference counting and/or garbage collection mechanisms. The memory manager is very expensive to operate and it is not clear that performance problems in this area can be solved. This may impact the ultimate success or failure of Smalltalk, as users of traditional programming systems may be reluctant to give up performance in exchange for Smalltalk.

Alternative implementation hosts also merit consideration. Although we have yet to implement the system on an HP 3000, we have derived performance estimates for the Smalltalk-80 virtual machine on the HP 3000 and the HP 1000 A Series minicomputer systems. With its stack-oriented architecture, an HP 3000 could be capable of 200,000 bytecodes per second. The HP 1000 A Series is a more attractive candidate because of its excellent price/performance ratio and compact packaging. Performance in excess of 100,000 bytecodes per second might be possible for an A Series processor with writable control store.

Implementations can benefit from special hardware for functions which do not perform well on general-purpose processors. Xerox solved this problem by adding special-purpose microcode for such functions to their general-purpose hardware. We have already commented on how the performance of our primitives suffered from lack of access to microcode or hardware support. This situation is most serious for graphics operations where microcode or instruction cache support for block moves would expedite matters by at least a factor of 10.

Since the Smalltalk-80 system is geared toward the personal computing community, the microprocessor is a natural area for investigation. However, most microprocessors do not have modifiable control stores and so special-purpose hardware may be the only efficient option to achieve acceptable performance. In fact, advances in VLSI design and fabrication have promoted the development of many such special-purpose chips for graphics control, memory management, and I/O support. A native code compilation system integrating these chips with one of the new 16- or 32-bit microprocessors could be an excellent Smalltalk-80 host.

There is also the issue of having an operating system alongside or underneath an implementation of the Smalltalk-80 system. The HP implementation runs on top of UNIX, which has significant advantages and disadvantages over the strategies of other implementors in the test program. UNIX has many features which assist the development of protototype software. For example, the debugging utilities are key components of our development environment. However, there are a few points where the integration of UNIX into Smalltalk could have helped us,
such as in multiprocess control. As it stands we simulate this feature on UNIX, thus incurring additional overhead. The file system was another area where UNIX could have helped. By integrating the UNIX hierarchical file system into Smalltalk, we could have structured the system source into a hierarchical collection of files reflecting class relationships instead of the single large file currently used.

The Smalltalk-80 language itself is another direction for research. We find the language to be excellent for systems programming of applications with superior user interface characteristics. Contrary to popular belief, we do not feel that it is a programming language for the naive user community. Instead, it has proven itself to be a very good language for developing application kits to enable naive users to solve problems in limited domains, as in *ThingLab*³. The object orientation lends itself especially well to the programming of graphics problems. As other languages incorporate similar graphics capabilities, it will be interesting to note how their user interfaces compare with Smalltalk's.

There have been proposals to include types in Smalltalk, either through inference or declaration⁴,⁵. Each approach has its own merits, but more work needs to be done to determine the best way to integrate type structure into the system. In particular, we look forward to ways of using type information to optimize certain operations in the system.

## Conclusions

The Hewlett-Packard team was curious about Smalltalk and we approached the task of implementing the Smalltalk-80 system with both reservations and enthusiasm. And indeed, some of our reservations were warranted: the Smalltalk-80 language did not prove to be a workingman's programming language and did not perform well enough on conventional hardware. The mystery surrounding Smalltalk for so many years had inspired grand expectations in us. In the end we were disappointed, but our curiosity was sated and we are perhaps better for it. The concepts embodied in Smalltalk have a heritage which goes back over 20 years, yet many have not achieved widespread acceptance by the research or marketing communities. There is little doubt now that the new economics of VLSI will make many of these concepts standard features of computing products.

It remains to be seen however, whether Smalltalk itself will succeed in the marketplace. All during the project we dreamed of a Smalltalk-80 product. These visions gradually became a nightmare as we discovered the pitfalls of an environment with the flexibility of Smalltalk. A Smalltalk-80 user can break the system by changing a single method. More important, one can make it incompatible with the distribution just as easily. From a product support standpoint, this would be chaos. Software distribution would be difficult to impossible.
Application software could assume very little about the runtime envi-
ronment, since it might have been modified extensively by the user. In
tracing down system problems, it would be tricky to determine whether
the problem was in the distribution or in the changes made by the user.
One solution would be to restrict what a user can change, but this de-
feats the whole purpose of Smalltalk. We can not see how an organiza-
tion could hope to provide any form of comprehensive support for a
Smalltalk product. The only way we can envision Smalltalk in the mar-
ketplace is as an unsupported package.

Acknowledgments

We would like to acknowledge the tenacious efforts of our fellow mem-
bers of the HPL Smalltalk team in coping with the vagaries of a distri-
bution test program. In particular, Alec Dara-Abrams for stalking the
wild interpreter, Bob Shaw for graphics support beyond the call of duty
on the Lexidata, and Bob Ballance for his work on the interpreter and
primitives, especially in floating point and process control. Our project
leader, Jim Stinger, provided technical arbitration and primitive design.
Joe Falcone contributed in the object memory, development environ-
ment, and performance evaluation areas.

There are others who contributed to the project in advisory and man-
agerial capacities. Ching-Fa Hwang, Dan Conway, and Sam Gebala
helped review the chapters of the Smalltalk book and participated in
the early discussions about target machines. We would also like to
thank our department manager, Ted Laliotis, for his support through-
out and beyond the life cycle of the project. None of this would have
been possible without the work of Jim Duley and Paul Stoft, who were
responsible for bringing the Smalltalk-80 system to Hewlett-Packard.
Finally, we express our appreciation to David Casseres, Ann Falcone,
Karri Kaiser, Glenn Krasner, Rick Meyers, and Steve Muchnick for
their editorial assistance.

All of us involved with the Smalltalk-80 system at Hewlett-Packard
appreciate the efforts of the Xerox Software Concepts Group. We grate-
fully acknowledge their support and tolerance during the test program.

References

1. Sansonnet, J. P., et. al., "Direct Execution of LISP on a List-Directed Architecture", Proceedings at the Symposium on Architectural Support for Programming Languages and Operating Systems, Palo Alto, CA, pp. 132-139, March 1982.
2. Ritchie, Dennis M., and Thompson, Ken, "The UNIX Time-Shar-
ing System" *Comm. ACM* vol. 17, no. 2, pp. 365-375, July 1974.

3. Borning, Alan H., "The Programming Language Aspects of Thing Lab, A Constraint-Oriented Simulation Laboratory", *ACM Transactions of Programming Languages and Systems* vol. 3, no. 4, pp. 353-387, Oct. 1981.

4. 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.

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

<figure><img src="image_13.png" /></figure>
# The Dorado Smalltalk-80 Implementation: Hardware Architecture's Impact on Software Architecture

L. Peter Deutsch

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

## Abstract

The implementation of the Smalltalk-80 virtual machine on the Dorado, an experimental high-performance microprogrammed personal computer, was strongly influenced by a few attributes of the Dorado hardware architecture: a large microprogram memory, a hardware instruction prefetch and decoding unit, an effective memory cache, and the use of base registers for memory addressing. Each of these features substantially reduced the complexity and/or improved the performance of the Smalltalk implementation.

## Introduction

The Dorado is an experimental high-performance microprogrammed personal computer, the latest and most powerful descendent of the Xerox Alto. Because the Dorado is relatively easy to microprogram, and because it incorporates many architectural features for aiding implementors of higher-level languages, the Software Concepts Group chose the Dorado as the first target machine for implementing the Smalltalk-80 virtual machine. The first version of the implementation
ran successfully in early 1981, after approximately six months' work by a single person.

Three excellent papers on the Dorado hardware architecture have appeared elsewhere¹, so we will only mention the machine's most important attributes. The Dorado is microprogrammed, with a 70 ns microinstruction time and a 36-bit microinstruction. The microprogram memory holds 4K microinstructions, all in RAM. The internal registers and data paths are 16 bits wide. The processor accesses main memory through a 4K-word cache, which can accept a reference every microinstruction and deliver data 1 or 2 microinstructions after a read request. The processor includes pipelined hardware for prefetching and decoding macroinstructions. Later we will describe other details of the Dorado hardware in connection with their impact on the Smalltalk-80 virtual machine implementation.

## Emulator Architecture

The Dorado microinstruction memory (microstore) holds 4K instructions. In the standard Dorado microcode, approximately 1300 microinstructions implement I/O controllers and 700 microinstructions implement a simple macroinstruction set inherited from the Alto². (The I/O control microcode is a consequence of the Dorado's I/O architecture, which emphasizes simple controller hardware and uses microcode multiprocessing to provide most of the control function.) The remaining 2000 microinstructions are available for implementing other macroinstruction sets and/or extending the Alto instruction set: normally they implement an instruction set specialized for Mesa³. The hardware instruction fetch unit (IFU, described in more detail below) allows switching between instruction sets in less than a microsecond, simply by reloading an IFU register.

In our Smalltalk-80 implementation, we had a number of choices:

1. Keep the Alto and/or the Mesa macroinstruction set, and implement the Smalltalk-80 virtual machine entirely in it/them.

2. Keep the Alto macroinstruction set; implement the Smalltalk-80 virtual machine mostly in microcode, and the remainder in Alto code.

3. Discard the Alto microcode; implement the Smalltalk-80 virtual machine mostly in microcode, and partly in Smalltalk extended with special primitives for manipulating memory or the I/O devices directly.
4. Discard the Alto microcode; implement the Smalltalk-80 virtual machine entirely in microcode.

We rejected approach 1 for performance reasons: although somewhat harder to write, microcode is approximately five times as fast as either Alto code or Mesa for straightforward instructions, and also offered the opportunity to fully exploit the available processor registers and the IFU.

It was likely that the microstore was not large enough for 4; 4 would also have deprived us of the ability to write debugging aids in Alto code or Mesa, and to use the standard debugger (as opposed to a microcode debugger) during Smalltalk development.

In finally choosing 2 over 3, we were motivated by several principal arguments:

* We wanted the parts of the Smalltalk-80 system written in Smalltalk to be completely portable, i.e. not contain code specific to any particular storage or I/O system, and were willing to tolerate a larger non-Smalltalk kernel to achieve this.

* Both the Dorado and the Dolphin, a less powerful machine for which we also wanted a Smalltalk implementation, already had Alto emulation microcode. Those parts of the Smalltalk system written in Alto code could be shared between the two implementations. We were also considering an implementation on the Alto, which has less powerful microcode and a smaller microstore. A system architecture which allowed us to move small functional units of code between microcode and Alto code implementations was likely to be more transportable between the three machines.

* Keeping the Alto emulator, which occupies less than 20% of the microstore, would relieve us of the 4K limit (by allowing us to write arbitrarily large fractions of the system in Alto code) without depriving us of a lot of microstore space.

It is interesting to note that Interlisp-D⁴, where these desires were not as important, made the opposite choice. Interlisp-D originally adopted approach 2, later replacing it by 3. The Interlisp-D system now contains literally thousands of lines of machine-dependent source code written in Lisp: it has no clear division between a portable virtual machine and an implementation level, but the instruction set is much closer to the machine level and is much easier to implement efficiently.

Two features of the hardware architecture helped reduce the cost of approach 2 compared to 3, specifically by reducing the cost of passing control and data between the two implementation levels: quick switch-
ing between instruction sets in the IFU, and the fact that the Alto in-
struction set deliberately included a large number of undefined opcodes
to which we could assign our own interpretation. We used these opcodes
to optimize the transfer of information between the microcode and Alto
code implementation levels. The appendix (p. 123) lists these opcodes in
detail; we believe that any Smalltalk-80 implementation that uses a
combination of microcode and an existing macroinstruction set will find
this list a useful guide.

In retrospect, this decision to split the implementation between two
levels worked out extremely well. The decision gave us a great deal of
flexibility to move parts of the Smalltalk kernel between Bcpl (a system
programming language which compiles into Alto code), Alto assembly
language, and microcode as we investigated its performance character-
istics. As it turned out, we only used Bcpl for initialization, since it
could not generate our extended Alto instructions and since its subrou-
tine calling sequence is less efficient than a hand-coded one by a factor
of about 3. Typical Smalltalk-80 benchmarks show between 5% and
15% of the time being spent executing Alto code, and the remainder in
Smalltalk microcode.

In the final implementation, the main part of the system is
implemented entirely in microcode:

* Instruction set interpreter (with assistance from the IFU)

* Process switching

* Reference counting

* Object allocation and deallocation

In addition, the following primitive methods are implemented in micro-
code:

* Small integer arithmetic

* Subscripting and instance variable access: `at:`, `at:put:`, `size`, `characterAt:`, `characterAt:put:`, `objectAt:`, `objectAt:put:`, `instVarAt:`, `instVarAt:put`:

* Object creation (new, new:)

* Block context creation and execution: `blockCopy:`, `value/value:`, `valueWithArguments`:

* Process scheduling (signal, wait, resume, suspend)

* `BitBlt` (copyBits)
* Miscellaneous: `asOop`, `==`, `class`, `flushMessageCache`, `perform`, `performWithArguments`:

The following primitive methods for storage management were originally implemented in microcode, but were later translated into Alto code for reasons explained below: `refct`, `become`-, `asObject`, `someInstance`, `nextInstance`.

The following primitive methods are implemented in Alto code:

* 16-bit large integer arithmetic

* Floating point arithmetic

* All I/O primitives (disk, Ethernet, display, keyboard, mouse) except `BitBit`

* The remaining storage management primitives: `newMethod:header:`, `coreLeft`

* Snapshot

The following optional primitive methods are not implemented on either the Dorado or the Dolphin: `next`, `nextPut`-, `atEnd`.

When the interpreter microcode encounters a Smalltalk method that includes a call on a primitive, it consults a table stored in main memory to determine whether the primitive is implemented in microcode (the table contains a microcode dispatch address) or Alto code (the table contains the address of an Alto code routine). In the latter case, the interpreter switches the IFU to Alto emulation, and the machine starts executing the Alto code that implements the primitive. The Alto code typically contains some special Smalltalk-specific instructions (described in the appendix on pg. 123) which allow it to interact with the Smalltalk world: `LDSS` instructions to access the receiver of the message and its arguments, `SETDS` and `LDFD/STFD` instructions to access the instance variables of the receiver, and finally a `PRET` instruction to return the result of the primitive and resume Smalltalk execution. All these trapped opcodes are of course implemented in microcode. `PRET` switches the IFU back to the Smalltalk instruction set and resumes execution with the next Smalltalk bytecode.

## Instruction Sequencing

The Dorado's Instruction Fetch Unit (IFU)⁵ prefetches and decodes instructions in a manner almost ideally matched to the Smalltalk instruction set. In fact the three language-oriented instruction sets designed at the Palo Alto Research Center (Lisp, Mesa, and Smalltalk) and the Do-
rado design influenced each other considerably. The IFU prefetches up to 6 bytes, accessing the memory through the same cache the processor uses, and only when the processor is not accessing it. The first 8-bit byte of an instruction indexes a 256-entry RAM. The entry in the RAM gives the address of the microcode that implements the instruction, says how many additional bytes the instruction uses (0, 1, or 2), and supplies a 4-bit parameter for any purpose the microcode wants. (For example, each group of Smalltalk "load" instructions uses the same microcode, but different parameter values corresponding to the offset of the desired variable within the context, instance, or literals.) The RAM also contains information which allows the IFU to execute certain unconditional jumps itself. The microcode that implements a given macroinstruction can read the parameter and the additional bytes from the IFU onto a convenient bus. The last microinstruction of each macroinstruction contains a field that informs the processor's control logic that the processor should ask the IFU for a new dispatch address for the next microinstruction; under this arrangement, there is normally no delay at all between macroinstructions. Thus the overhead of fetching, decoding, and dispatching on macroinstructions, and returning to a central loop after a macroinstruction is finished, is reduced essentially to zero. This overhead may take up as much as 20% of the time in an interpreter implemented without hardware assistance⁶.

The entire job of instruction sequencing and decoding is handled by the IFU. The microprogram only intervenes to restart the IFU for jumps, message sends, and returns, and when switching between the Smalltalk and Alto instruction sets. The IFU RAM actually holds up to four instruction sets at once, and the overhead of switching is less than a microsecond if the first instruction to be executed is in the memory cache. Only 2.4% of execution time is spent waiting for the IFU to supply a dispatch address; we cannot determine what fraction of this time is due to cache misses and what fraction to competition with the processor for cache cycles. For a deeper discussion of IFU performance, see the Dorado papers.⁷

## Memory Management

The Dorado provides hardware support for a paged virtual address space, but the Smalltalk-80 implementation makes no use of it—Smalltalk initializes the page tables to map virtual addresses one-for-one into real addresses. Recovering from a page fault at the microcode level is potentially complicated. A single Smalltalk instruction can make many memory references, so we would have had to adopt some combination of resuming execution of a Smalltalk instruction in mid-flight, arranging all instructions to be restartable, and/or letting the
page fault handler complete the faulting reference. For this reason, and because past experience with a paged Smalltalk suggested that it would perform very badly if the working set exceeded real memory significantly, we did not go to the trouble of observing the microcoding restrictions which would make recovery from faults possible.

Recursive freeing of objects with zero reference count is implemented in microcode; the main loops of the compactor, but not the overall control, are also in microcode. This arrangement has worked out extremely well. In fact so little time is spent in recursive freeing (1.9%) that we might be able to move at least some cases of the rather complex recursive freeing algorithm into Alto code as well with relatively little performance penalty. This is partly a result of a minor interpreter change: when control returns from a context which has no other references to it, the interpreter essentially "unrolls" the top loop of the recursive freer, i.e., there is a special loop which iterates through the fields of the context (but only up to the current position of the stack pointer), decrementing the reference counts and calling the actual recursive freer if needed.

## Memory Cache

The Dorado's memory cache is nearly as fast as the processor registers. A memory fetch in microinstruction N produces data in a register in microinstruction N+1 which can be used for computation in microinstruction N+2. Memory stores are even faster, taking a single microinstruction. The cache is pipelined, so a new fetch or store can be started in every microinstruction. As a result, we decided to implement even the very highest-bandwidth operations of the Smalltalk-80 implementation—pushing and popping quantities (particularly variables) on the stack—using memory references at the microcode level without significant time penalty. Thus for example, the microcode that implements the "load local variable" instruction reads the local variable using the current context as a base and the parameter supplied by the IFU as the offset, increments a stack pointer held in a register, and then writes the value onto the stack (in main memory) using the stack pointer as an offset from another base register.

In retrospect this decision was almost certainly correct. The memory references to the stack and the local variables in a context never cause cache misses. The bookkeeping required to manage a finite-size register stack (the Dorado has four 64-register stacks in the processor) would have been relatively complex, especially since Smalltalk does not always transfer control between contexts in LIFO order. However, this decision is critically dependent on the speed of the cache. If the cache
had been only half as fast—taking 3 to 4 microinstructions to fulfill a request—it would probably have been better to store some of the current context in registers.

Despite its small size, the Dorado cache works effectively for Smalltalk. Our measurements show that cache misses account for only 11% of execution time. References to the stack and the current context never cause misses; most misses are caused by accesses to method dictionaries during message lookup, and to method headers when starting execution of a method.

## Registers

The Dorado includes 256 16-bit working registers, organized as 16 groups of 16 registers each. One of the 16 groups is current at any time, selected by a processor register called RBase. Microinstructions supply a 4-bit register address within the current group, which is concatenated with RBase to provide the full register address. The Smalltalk microcode uses three groups:

* The "main" group, described in more detail just below

* A group used only by the compactor and recursive freer

* A group used almost exclusively by the process scheduler

Because changing the RBase register ties up a microinstruction field that is also involved in many other operations (such as memory references and constant generation), it is highly valuable to divide the registers into blocks according to major sections of the microcode control, to minimize the frequency of group switching. The convention we chose in the Smalltalk microcode was to define a single "main" group to be current throughout the entire microcode, except for local switching to access individual registers in other groups, and self-contained routines like the recursive freer which would restore the "main" group to currency when they were done.

Since the contents of the "main" group are a valuable indication to implementors as to what information should be held in machine registers, we list them here, in approximate order of decreasing utility:

**SPR** The stack pointer, relative to the base of the current context

**9 temporary registers** Also used for passing arguments and results to and from microcode subroutines

**Nargs** The number of arguments to the current method
<table><tr><td>Self</td><td>The Oop (object identifier) of the current receiver</td></tr><tr><td>SI</td><td>A flag indicating whether the last (or current) primitive is "fast" (entered directly in response to a special selector) or "slow" (entered through method lookup)</td></tr><tr><td>MyPC</td><td>The byte PC (relative within the method), saved whenever control might switch to another context or to Alto code</td></tr><tr><td>Context</td><td>The Oop of the current context</td></tr><tr><td>Method</td><td>The Oop of the current method</td></tr></table>

Note that direct pointers to the bodies of some of these objects (the receiver, context, and method) are also held in base registers, as described in the next section.

The limitation of 16 readable registers was much less of a nuisance than might be expected. The original Dorado prototype had 32 groups of 8 registers, which was a tremendous nuisance: the microcode shrank by about 15% from the prototype version simply through elimination of microinstructions whose main purpose was to switch register groups. Expansion to direct addressing of all 256 registers would probably eliminate only another 20 microinstructions: the figure is small because of our careful division of registers into meaningful groups. In other words, our experience indicates that for Smalltalk-80 implementation, there is a "knee" in the utility curve somewhere between 8 and 16 directly accessible registers.

The Dorado also includes 4 stacks of 64 registers which can only be accessed through a pointer register, the processor stack pointer (StkP). The microinstruction format supports pushing and popping quantities in the current stack as easily as addressing the current block of 16 addressable registers. Unfortunately, StkP is awkward to load and read, and recovering from over- or underflow is even more difficult. For these reasons, we chose not to use these stacks to model the Smalltalk stack, but only for temporary storage within the microcode. When a microcoded primitive fails, or other exceptional condition arises, the microcode resets StkP to a standard state before continuing with the recovery code. As indicated in the earlier section on the memory cache, we believe this choice is better than using the processor stack for caching parts of Smalltalk contexts.

**Base Registers**

The Dorado memory system provides 32 base registers which hold full 28-bit virtual addresses; the microinstructions that reference memory normally provide 16-bit displacements relative to a current base register.
ter, switched under microprogram control. Consequently, the Smalltalk microcode dynamically maintains the following addresses in base registers at all times:

<table><tr><td>TS</td><td>The current context for accessing local variables (home context when executing a block, current context otherwise)</td></tr><tr><td>SS</td><td>The context used for execution and stack—always the current context, even when executing in a block</td></tr><tr><td>RS</td><td>The receiver in the current context (self)</td></tr><tr><td>CS</td><td>The currently executing method (code)</td></tr></table>

In addition, it loads the following addresses at system initialization:

<table><tr><td>OTBase</td><td>The base of the object table (OT)</td></tr><tr><td>FreeLists</td><td>The base of the table of free list heads</td></tr><tr><td>MCacheBase</td><td>The base of the message lookup cache</td></tr><tr><td>SpecialBase</td><td>The Special Selectors array, used to handle sends of special selectors (must also be reloaded after memory compactions)</td></tr></table>

It is interesting to observe that the memory system is so fast, and the indirect or indexed addressing of registers so awkward, that the system actually runs (slightly) faster by putting the free list heads in memory than by putting them in addressable registers.

This choice of base registers is fairly obvious, except for the issue of whether or not to maintain a pointer to the receiver. Maintaining such a pointer requires reloading it at each activation or return; not maintaining such a pointer requires indirect access through the OT at each reference to an instance variable. (More complicated schemes are also possible, such as a flag to indicate whether the base register has been reloaded since the last change of context.) Measurements indicate that references to instance variables are slightly more common than context switches, so we come out slightly ahead by always loading the base register at a context switch.

While the base register model works well for memory references, loading a base register is awkward for two relatively minor reasons:

* Base registers are 28 bits wide, but the Dorado's data paths are only 16 bits. Thus loading a base register takes at least 3 microinstructions (one to select the register, and one to load each half).

* Because the Dorado implementation packs flag bits into the OT along with the data address, exactly as described in the Smalltalk
virtual machine documentation, a masking operation is required. Also, again because of the 16-bit architecture, two memory references are required to fetch the OT entry.

As a result of these problems, the standard subroutine which loads a base register with the address of an object whose Oop is known (essentially the SETDS instruction described in the appendix below) takes 6 microinstructions; over 10% of execution time is spent in this subroutine (and various open-coded copies of it). By using 3 words per OT entry instead of 2, we could have eliminated the masking operation, saving 1 of the 6 microinstructions. However, besides adding 32K to the system's memory requirements, this design would have increased the cache working set size (and hence the wait time due to misses) significantly, so there might well have been no net speed improvement.

## Microcode Multiprocessing

The Dorado micro-architecture includes multiple processes at the microcode level. The Smalltalk-80 emulator itself makes no use of this capability, which is primarily designed to allow a single processor to function effectively as a controller for multiple high-speed I/O devices. However, one of these processes can be awakened periodically, at intervals as short as a few microseconds, to collect a histogram of the address of the next microinstruction to be executed by the instruction set emulator. This facility proved invaluable in analyzing performance bottlenecks in the Smalltalk microcode; essentially all the measurements reported in this paper were obtained from the micro-address histogram. One particularly interesting number was the amount of time spent waiting for cache misses; we computed this by looking at the number of samples at addresses of microinstructions that had to wait for memory data to arrive, compared to the instructions immediately preceding and following these.

## Appendix: Extended Alto Instructions

In the following descriptions of the extensions to the Alto instruction set, ACO-3 refer to four 16-bit registers which the Alto instruction set views as central registers, but which are addressable registers at the microcode level.

Many of these instructions are designed for use only from Altocode primitives, and consequently can cause "primitive failure" under cer-
tain circumstances. Primitive failure means that the execution of the primitive code is abandoned, and the Smalltalk method is executed instead.

The instructions are arranged below in groups, with the most heavily used groups listed first.

<table><tr><td>Access to Smalltalk Data</td><td><strong>LDSS n</strong><br>AC0 - word n relative to SS+SPR-Nargs, the location of receiver and arguments on the stack in the current context. N = 0 is the receiver, n = 1 is the first argument, etc.<br><strong>SETDS</strong><br>AC0 = an Oop. Sets the DS base register to the real memory address of the object, taken from the OT. Causes primitive failure if AC0 is a small integer rather than an Oop.<br><strong>LDFD n / LDF1</strong><br>AC0 - word n relative to DS; for LDF1, n is taken from AC1 rather than from the instruction itself. The parameters .LENGTH, .CLASS, and .FLDS define the offsets of the length word, class word, and first field of an object, e.g. the assembly-language instruction to load the second field of an object would be LDFD .FLDS+1.<br><strong>STFD n / STF1</strong><br>AC0 = a new Oop to be stored at word n relative to DS. This instruction does reference counting (increases the reference count of the object identified by AC0, decreases the reference count of the old contents): use STNFD (below) to store a non-Oop without reference counting.<br><strong>LDNFD n / LDNF1</strong><br>AC0 - word n relative to DS. Meant for use when the data being loaded are bits rather than Oops. Equivalent to LDFD in the current system, only provided for symmetry with STNFD.<br><strong>STNFD n / STNF1</strong><br>AC0 = a new value to store into word n relative to DS. Does not do reference counting (see STFD above).</td></tr></table>

<table><tr><td>Conversion of Integers</td><td><strong>IVAL</strong><br>AC0 = a small integer; AC0 - the value of the integer. Causes primitive failure if AC0 is not a small integer.<br><strong>WRDVAL</strong><br>AC0 = an Oop of a Smalltalk LargePositiveInteger, or a SmallInteger; AC0 - the value of the number. Causes primitive failure if the Oop is not a LargeInteger, or if the value does not fit in one word.<br><strong>MKINT</strong><br>AC0 = an unsigned integer; AC0 - the corresponding Smalltalk integer (small or large).</td></tr></table>
<table>
  <tbody>
    <tr>
      <td rowspan="2">Primitive Control</td>
      <td>PRET</td>
      <td>A primitive has completed successfully. AC0 = the value to return from the primitive.</td>
    </tr>
    <tr>
      <td>PFAIL</td>
      <td>Cause primitive failure.</td>
    </tr>
    <tr>
      <td rowspan="2">Access to OT</td>
      <td>READOT</td>
      <td>Read the OT entry for a given Oop. AC0 = an Oop. AC0 - address word from OT, AC1 - flag word from OT.</td>
    </tr>
    <tr>
      <td>SETOT</td>
      <td>Set the OT entry for a given Oop. AC0 = an Oop, AC1 = address word to store in OT, AC3 = flag word to store in OT.</td>
    </tr>
    <tr>
      <td rowspan="2">Access to Microcoded Primitives</td>
      <td>SIGNAL</td>
      <td>AC0 = a Semaphore. Does a "signal" operation on the semaphore. Used only by I/O interrupts and the low space notification mechanism.</td>
    </tr>
    <tr>
      <td>CINST</td>
      <td>AC0 = the Oop of a class, AC1 = the number of extra fields (for variable-length classes); AC0 - the Oop of a newly created instance. DS is also set as for SETDS.</td>
    </tr>
    <tr>
      <td rowspan="5">Compaction</td>
      <td>CLEANSTATE</td>
      <td>Store all of Smalltalk's state into memory in preparation for a compaction or a snapshot.</td>
    </tr>
    <tr>
      <td>ACOMPACT</td>
      <td>Start a compaction. AC0 = the Oop of the display bitmap.</td>
    </tr>
    <tr>
      <td>CSEG</td>
      <td>Prepare to compact the area of memory starting at AC0/1 and going up to an end marker which is the maximum legal Oop + 3.</td>
    </tr>
    <tr>
      <td>CLOOP</td>
      <td>Do the main compactor 1Oop. AC0/1 - the end of the occupied area after compaction. AC2/3 - the end of the occupied area just below the display bitmap, if the display bitmap was in the area being compacted.</td>
    </tr>
    <tr>
      <td>CRESUME</td>
      <td>Resume Smalltalk execution after a compaction.</td>
    </tr>
    <tr>
      <td rowspan="5">Miscellaneous</td>
      <td>RESUME</td>
      <td>Resume Smalltalk execution with the next bytecode. Used only during initialization, and for resuming after an interrupt. (All hardware interrupts cause control to go from the Smalltalk interpreter to Alto code.)</td>
    </tr>
    <tr>
      <td>SETCNT</td>
      <td>Set the low-space trap parameter to AC0.</td>
    </tr>
    <tr>
      <td>READCNT</td>
      <td>AC0 - the number of Oops left before a low-space trap will occur - 1.</td>
    </tr>
    <tr>
      <td>CONFIG</td>
      <td>AC0 - the size of (real) memory in units of 32K, e.g. for a 512K Dorado, AC0 - 16 decimal.</td>
    </tr>
    <tr>
      <td>Initialization and Post-mortem</td>
      <td>SETOTBASE</td>
      <td>Initializes the microcode base register that points to the OT. AC0 = low address of OT, AC1 = high address of OT.</td>
    </tr>
  </tbody>
</table>
## DEADSTART

Initializes the system. AC3 = a pointer to a block of memory laid out as follows:

0 base address of OT (low bits)

1 (high bits)

2 size of OT (# of OT entries)

3 the address of an 8K table for a microcode PC histogram, or 0 (low bits)

4 (high bits).

After initialization is done, Smalltalk execution begins, so control does not return to the instruction following the DEADSTART.

## READOUT

AC0 = a pointer to a readout area in memory, into which are stored the following values:

0 - Oop of current context (CONTEXT register)

1 - current stack pointer (SPR register)

2 - byte PC of current instruction (PCX register)

3 - unused but reserved for future use

4 - micro-PC from which crash occurred (LINK register)

5-19 - unused but reserved for future use.

## References

1. Lampson, Butler W., "The Dorado: A High-Performance Personal Computer", Xerox PARC Technical Report CSL-81-1, Jan. 1981.

2. 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 Report CSL-79-11 Aug. 1979).

3. Mitchell, James G., et. al., "Mesa Language Manual," Xerox PARC Report CSL-79-3, Apr. 1979.

4. 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).

5. See reference 1.

6. Markoff, John, "Smalltalk: A Language for the 80s", *InfoWorld*, cover story, Jan. 24, 1983.

7. See reference 1.
# The Design and Implementation of VAX/Smalltalk-80*

Stoney Ballard

Three Rivers Computer Corporation
Pittsburgh, Pennsylvania

Stephen Shirron

Digital Equipment Corporation
Marlboro, Massachusetts

## Introduction

VAX/Smalltalk-80 is an implementation of the Smalltalk-80 system written for the VAX family of computers running with the VMS operating system. This version differs from standard Smalltalk-80 implementations by using a basic word size of 32 bits and an incremental compacting garbage collector. This paper describes the rationale for these changes, their implementation, and various tricks that were developed to enhance the performance of this version of the Smalltalk-80 virtual machine. We also discuss some ideas for future work aimed at improving the performance of paged virtual object systems.

## Some History

Our group at DEC (the Corporate Research Group) was involved in studying issues relating to personal workstations and graphics. We had been interested in the Smalltalk-72 and Smalltalk-76 systems for several years because they were the best examples of powerful personal workstation environments that we had seen. Consequently, we jumped at the chance to participate in the Smalltalk-80 review.

<footnote>*The work described in this paper was done at Digital Equipment Corp. Copyright © Stoney Ballard and Stephen Shirron 1982. All rights reserved.</footnote>
The VAX Smalltalk-80 implementation was our second, the first hav-
ing been done for the PDP-11/23. The PDP-11 version was implemented
as closely as possible to the virtual machine specification published in
*Smalltalk-80: The Language and Its Implementation*. This version was
notable primarily for its execution speed, which resembled molasses in
December. By the time we were out of ideas to speed it up, the PDP-11
was executing about 5K bytecodes/second.

The PDP-11 version exhibited three major performance bottlenecks: the PDP-11 memory manager, the lack of writable microcode hardware, and the reference counter.

The memory management hardware on the PDP-11/23 was designed
to map a 64Kbyte virtual space into physical space by using eight sepa-
rate 8Kbyte segments. Our problem however, was not to map virtual
space to physical, but rather to directly access the full 256Kbyte physi-
cal space of the PDP-11/23. This involved adjusting the map for every
object access (as well as every object table access) to map it into the
64Kbyte directly addressable range. Since some Smalltalk-80 objects
are larger than 8Kbytes, we had to adjust the map to point at the par-
ticular field we wanted. This was particularly painful since it took
about 30 instructions to adjust the map. By setting up map segments
for the objects commonly used by the interpreter (e.g. the context,
method, self) at context switch and process switch, we eliminated most
of this overhead. Nevertheless, the interpreter spent about half of its
time with map box adjustment.

The PDP-11/23 had no writable microstore, so we wrote the bytecode interpreter and all the primitives in assembly language. If we had been able to write microcode, we could have achieved about a factor of two to four improvement in speed. The PDP-11 is not suitable for microcoding a Smalltalk-80 interpreter because the hardware is designed specifically for fetching and decoding its native instruction set.

The reference-counting scheme caused serious performance problems. Updating the reference counts of objects and tracing objects whose counts had gone to zero was the primary source of memory management overhead. Mapping problems aside, we felt that reference counting was inherently inefficient anyway because of the many places in the code that were required to update reference counts. Reference counting is probably the best scheme to use for small machines since it reclaims space immediately as it becomes garbage. All other garbage collection schemes leave a relatively large amount of garbage lying around between collections.

The space compactor was annoying since it caused the system to
pause for several seconds whenever it ran. Our compactor was slow
bqth because we compacted the whole memory at once, and because the
memory map had to be constantly adjusted as it ran.

After playing with the PDP-11 version for a while we came to sever-
al conclusions about the Smalltalk-80 system:
1. A maximum of 32K objects is insufficient for a system that supposedly integrates the whole environment into one object space. We felt that 10 to 100 times that number of objects would be needed to properly support a rich environment. Even the base Smalltalk-80 system suffers from the small object name space as seen in the non-uniform handling of methods. These objects should be broken into a literal vector and a bytecode vector, but weren't for performance reasons and because that would have added about 6K objects to the base system. This non-uniformity requires a great deal of the code to handle methods specially.

2. The performance we achieved was clearly inadequate for real work. Compilation and browsing were far too slow to support rapid development work. Touch typing was virtually impossible since we could type faster than the input process could accept characters. We felt that a tenfold increase in speed would be needed before we would feel comfortable with the system.

3. Fifteen-bit SmallIntegers are too small. Although this is somewhat of a minor problem, it would clean up the array indexing code substantially if a SmallInteger was sufficient to index the largest possible array.

4. The reference-counting scheme should be discarded in favor of an incremental compacting garbage collector. Not only would this eliminate the problem of reclaiming circular garbage (which required us to implement a separate mark/sweep garbage collector), but would also reduce the work required when storing object pointers into other objects, especially contexts. Additionally, an incremental compacting garbage collector eliminates the pauses due to compacting space.

5. Some sort of virtual object storage is necessary to support large applications or sets of applications where millions of objects would be needed. Paging systems are commonly available and easy to use. We were interested in determining the performance of paging for a system like the Smalltalk-80 system, where the locality of reference between adjacent objects is much smaller than in traditional language environments.

These considerations led to our decision to implement a modified version of the Smalltalk-80 virtual machine on a VAX-11/780. The VAX was an obvious choice for us since most groups at DEC had one, and it would be much easier for people to use the Smalltalk-80 system if it ran on computers accessible to them. To this end we decided to implement a portable system that could be used on any VAX running VMS. We realized, of course, that we would be giving up a fair amount of performance by using a timesharing system. Our plan was to build a ver-
sion for VMS, written in assembly code, and then convert it to run stand-alone with microcode assist. This latter phase has not yet been performed.

The following sections give details of the characteristics of our Smalltalk-80 implementation (which we call VAX/Smalltalk-80) and some suggestions for future work.

## Word Size Changes

We reformatted the Smalltalk-80 image to use 31 bit object names and SmallIntegers, using the 32nd bit as a tag bit to distinguish between them. Object headers increased from 4 to 8 bytes. Non-Oop fields, such as those of BitMaps and Strings, were not changed. This reformatting increased the size of the base image by about 50%. After reformatting, the average object size in the base image was 40 bytes. Fig. 8.1 shows typical object formats.

A 4 byte size field allows objects up to $2^{24}$ bytes long, leaving a byte for various flags and an age field (described below). Our size field was a byte count of the object, eliminating the "odd" bit from the object table entry. Objects were stored on longword (4 byte) boundaries because longword fetches are faster on the VAX if naturally aligned. Fig. 8.2 shows the layout of the size field.

The object name space is vastly larger than the 32K objects supported by the standard Smalltalk-80 virtual machine. This not only allows keeping such things as the source code for the methods in the object space, but also allows us to use an incremental, compacting garbage collector. Unlike reference-counting schemes, an incremental compacting garbage collector does not reclaim either the names of objects or the space they take as soon as they become inaccessible. This requires that the name space be substantially larger than the maximum number of names otherwise needed. Although we could support two billion objects with a 31-bit name, we are limited to a much smaller number by the size of the virtual space allocated by VMS to the Smalltalk-80 process.

Although our version allocates 31 bits in an object reference for the name space, it is certainly feasible to allocate fewer (say 24) for the name reference and use the rest for tagging. Having tag bits in a reference can be useful when one object needs to appear in different guises depending on who references it. This would allow a "monitor" object to trap all messages from objects who refer to it as a monitor, but allow its "owner" to send messages to it directly, bypassing the monitoring. These tag bits could also be used to mark objects as being, for example, usable by the interpreter as CompiledMethods even if they are subclasses of CompiledMethod. Currently, the interpreter does not check
Word Size Changes

<table><thead><tr><th></th><th>MSB</th><th>LSB</th></tr></thead><tbody><tr><td rowspan="4">Pointer Fields</td><td>Flags</td><td>Size</td><td>0</td></tr><tr><td></td><td>Class</td><td>4</td></tr><tr><td></td><td>Pointer Field 0</td><td>8</td></tr><tr><td></td><td>Pointer Field 1</td><td>12</td></tr></tbody></table>

<table><thead><tr><th></th><th>MSB</th><th>LSB</th></tr></thead><tbody><tr><td rowspan="4">Word Fields</td><td>Flags</td><td>Size</td><td>0</td></tr><tr><td></td><td>Class</td><td>4</td></tr><tr><td>Word 1</td><td>Word 0</td><td>8</td></tr><tr><td>Word 3</td><td>Word 2</td><td>12</td></tr></tbody></table>

<table><caption>Figure 8.1</caption><thead><tr><th></th><th>MSB</th><th>LSB</th></tr></thead><tbody><tr><td rowspan="4">Byte Fields</td><td>Flags</td><td>Size</td><td>0</td></tr><tr><td></td><td>Class</td><td>4</td></tr><tr><td>Byte 3</td><td>Byte 2</td><td>Byte 1</td><td>Byte 0</td><td>8</td></tr><tr><td>Byte 7</td><td>Byte 6</td><td>Byte 5</td><td>Byte 4</td><td>12</td></tr></tbody></table>
<table><thead><tr><th>31</th><th>30</th><th>29</th><th>28</th><th>27</th><th>26</th><th>25</th><th>24</th><th>23</th><th>22</th><th>21</th><th>20</th><th>19</th><th>18</th><th>17</th><th>16</th></tr></thead><tbody><tr><td>Age</td><td></td><td>X</td><td>P</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td colspan="16">Size (23:16)</td></tr><tr><td>15</td><td>14</td><td>13</td><td>12</td><td>11</td><td>10</td><td>9</td><td>8</td><td>7</td><td>6</td><td>5</td><td>4</td><td>3</td><td>2</td><td>1</td><td>0</td></tr><tr><td colspan="16">Size (15:0)</td></tr></tbody></table>

Age - Age of the object in Flips

P - Set if object has pointer fields*

X - Unused

Size - Size in bytes of the object

*The P field is duplicated here so that the scanner need not refer to the OTE (Object Table Entry) to see if the object has pointer fields.

the class of objects such as CompiledMethods both for reasons of efficiency, and to allow using subclasses of these classes. Having tag bits that assert the compatibility of such objects with the ones expected would lead to greater safety in the interpreter.

In the standard virtual machine, only 15 bits are allocated for literal SmallIntegers. This is inadequate to index large arrays, so the indexing code must be able to use LargePositiveIntegers as indices. Since a 31-bit SmallInteger can index any array, our array primitives are simpler and faster.

Converting Smalltalk-80 to use 32-bit words was surprisingly painless. We found few places in the Smalltalk-80 code that depended on the word size. The worst one was that the decompiler found the first bytecode of a method by taking twice the number of literals and adding three (for the header and index origin). This prevented us from editing any of the methods to fix them, especially this one. We fixed this by creating a primitive that determined the initial PC of a method, and patching the initialPC method by hand to call this primitive. We recommend that these dependencies be removed from Smalltalk-80 systems by adding a primitive that returns information about the field size.

Garbage
Collection

This is perhaps the most interesting aspect of our version, it is certainly where most of our effort went. The PDP-11 version (and prior experience with Lisp implementations) showed us that it is vitally important
to have a reliable garbage collector early in the game. A buggy garbage collector has a tendency to randomly smash parts of objects in such a way that the damage does not come to light until much later. This makes the whole virtual machine rather difficult to debug, as you are not sure just which piece of code was responsible for the error. Since mark/sweep collectors can be simple enough to debug easily, we started out by using one.

After debugging the virtual machine with the simple mark/sweep collector, we turned our attention to the implementation of an incremental garbage collector. There were two candidates to choose from, the Baker¹ and the Lieberman-Hewitt². Since the Lieberman-Hewitt garbage collector was an elaboration of the Baker, and significantly more complicated, we decided to implement the Baker first.

## The Baker Garbage Collector

To gain a full understanding of this garbage collector, you should read Baker's work on the subject³. For those readers unfamiliar with this garbage collector, we present a brief description of it here.

The Baker garbage collector is an incremental, compacting garbage collector. By incremental, we mean that the process of collecting garbage is interleaved with the process of allocating space in such a way that the time required for collecting the garbage and compacting space is distributed fairly smoothly over time. The individual incremental executions of the collector have an upper bound on their time consumption proportional to the size of the largest object. This corresponds to the time it takes to move an object from one place to another. Under normal circumstances, no pauses in execution due to the garbage collector operating are perceptible.

The Baker garbage collector divides the virtual space into two equal-sized regions, or semispaces, called Fromspace and Tospace. Objects are copied from Fromspace to Tospace (hence the names) as they are found to be accessible. These copied objects are compacted sequentially at one end of Tospace. A scanning pointer starts at the base of this region, and moves field by field through the objects that were copied previously to Tospace, copying objects in Fromspace that are referenced by them. In this way, the objects in Tospace act like the stack commonly used by a mark/sweep collector. This scanning and copying continues until the scanning pointer runs out of objects. Newly created objects are placed at the far end of Tospace, so that they are not scanned. Fig. 8.3 shows the layout of Tospace.

In the original Baker scheme, whenever an object is copied, its old location (in Fromspace) is marked as a "forwarding pointer," and the new address is placed there. An access to a copied object is redirected to the new copy, and the reference is changed to point to the new location.
<figure><img src="image_14.png" /></figure>

This is necessary for systems (such as Lisp) where objects are referenced by virtual address.

The whole process is started by an operation called a "flip", which switches the identity of Fromspace and Tospace, and immediately copies all the objects known to the interpreter (the "roots" of the world) to the bottom of the new Tospace. Flips may occur any time after the scanning pointer has reached the end.

We took the simplistic approach of flipping when there was insufficient space to satisfy an allocation request. This minimizes the copying activity at the expense of maximizing page faulting. Flipping when the scanning pointer runs out of objects to scan will minimize the number of pages needed for both semispaces by keeping the accessible objects as compacted as possible. It appears that the optimal time to flip should be dependent on the average lifetime of newly created objects, so that a flip will occur when the expected density of accessible objects falls below a reasonable value. The object of this tradeoff is to minimize the sum of the page faults due to accessing and creating objects and those due to copying objects.

Objects that must be copied as roots are those objects that may not be transitively accessible from any other object copied as a root. It is a
good idea to copy all the objects that are "wired into" the virtual machine to insure that they never get deleted under any circumstances. The registers of the virtual machine are defined to always be in Tospace, so any objects referred to by them must also be copied at flip time. The objects that must be copied include the current context, all the objects it refers to that are cached by the interpreter (e.g. the method, receiver, self), any semaphores waiting for external events, the ProcessorScheduler object, the current DisplayBitMap (if it is not in a special location), and all the objects used by the interpreter such as nil and the selector doesNotUnderstand. If a list of these objects other than those relating to the current context is maintained, the list can be scanned incrementally to reduce the time required to perform the flip. It is not necessary to copy the object Smalltalk (the symbol table) at this time, although it is known to the interpreter, because the interpreter never uses it. If it is live, then it must be reachable from at least one of the objects which are actually used by the interpreter.

Whenever a reference to an object in Fromspace is stored into an object in Tospace, the Fromspace object must be copied to Tospace. This is necessary because the scanner may have already passed the Tospace object, or it is new. The interpreter registers are considered to always be in Tospace, since they are the first things scanned, so that object references stored in them must be checked and the objects copied if necessary. Although at first glance this seems to require more overhead than reference counting, it is actually much faster to test a flag than to increment a reference count and handle overflows. In practice, only a small number of objects need to be copied when their references are stored, and this copying would have been done by the scanner anyway.

The garbage collector is run (incrementally) every time an object is allocated. The amount of space to copy whenever a new object is created should be adjusted so that the scanning pointer finishes at the time a flip is desired (as per the above discussion). This will tend to distribute the copying activity as smoothly as possible. The semispaces must be large enough so that the probability of running out of room before the scanning pointer finishes is negligible. In practice, the largest semispaces possible should be allocated, as the middle pages of the semispaces will never be used, and will only contribute to page table overhead. Our implementation was not tuned in this fashion. Our system was set to copy four times as much space as we allocated so that we did not run out of room.

The net effect of this garbage collector is to copy all the objects which are live by virtue of being accessible (transitively) by the interpreter, from one space to another, leaving behind all the garbage. This old space can then be reused starting at the next flip.

With the Baker garbage collector objects are copied in a breadth-first order. This ordering has been shown to be substantially better than a
random ordering for reducing page faults, though not as good as depth-first⁴. This ordering is largely invariant from one flip to the next, so that the copying will tend to proceed linearly through Fromspace, minimizing the page faulting due to the copying.

It is difficult to compare the performance of this garbage collector with reference counting schemes. There is no suitable analytical approach to this problem. We have not directly compared the two schemes in the same environment, but we can offer some observations based on our experience:

1. Reference counting uses less space (virtual or physical) than any other incremental scheme, as long as circular garbage is rarely created.

2. Smalltalk-80 systems would generate a fair amount of circular garbage if the programs did not explicitly unlink circular structures before deleting them. This manual intervention in what should be a completely automatic process of garbage collection is "unclean" because it prohibits easy sharing of circular data structures.

3. The Baker garbage collector is closer to a "real time" process because the time an activation takes is no more than the time to copy the largest object. A reference counter may take time that is proportional to the size of the largest network of objects.

4. Reference counting does not compact space incrementally. If objects are allocated from segments of limited size, the compaction time of a segment may be small enough to be unnoticeable. Segmentation may make it substantially more difficult to allocate large objects, such as bitmaps for high-resolution printers.

5. Reference counting is not sufficient by itself. An auxiliary mark/sweep garbage collector is needed to reclaim both circular garbage and objects whose reference counts have overflowed (if an overflow table is not used).

6. The Baker garbage collector traces accessible objects, while reference counters trace the inaccessible objects. Which is more efficient depends on the rate of garbage generation and of space flipping. The Lieberman-Hewitt garbage collector (see below) promises to radically reduce the amount of accessible storage that needs to be traced and copied, making it a clear winner in this category.

7. A detailed look at the implementation of both schemes shows that the virtual machine code has fewer places where the space checking for the Baker scheme must be performed, compared with the places where reference counts must be updated. In both schemes,
storing an object pointer usually requires that the stored pointer be checked, but reference counters require that the overwritten pointer be dereferenced, while the Baker does not.

For another comparison, it will be instructive to compare the processing necessary to perform a "store" with both reference counting and Baker. This is presented as a pseudo-Pascal code fragment in which the value of the ith field of object "objA" is stored into the jth field of the object "objB". The object table is expressed as an array of records containing the appropriate fields.

First, the reference-counting version.

### store: objA intoField: j of: objB

```pascal
temp := objB[j];          get the old value of objB[j]
if not isSmallInteger(temp) then
  if ot(temp).refCount <> overflow then
    begin                 decrement refCount
      ot(temp).refCount := ot(temp).refCount - 1;
      if ot(temp).refCount = 0 then
        deallocate(temp);  if 0 then delete it
                             recursive deallocation
    end;
  temp2 := objA[i];       get the object pointer to store
  if not isSmallInteger(temp2) then
    SmallIntegers have no reference count
  if ot(temp2).refCount <> overflow then
    if refCount hasn't overflowed
    ot(temp2).refCount := ot(temp2).refCount + 1;
    increment refCount
  objB[j] := temp2;        then store it
```

Next, the Baker version.

### store: objA intoField: j of: objB

```pascal
temp := objA[i];          get the object pointer to store
if ot(objB].space = Tospace then
  if the dest is in Tospace
  if not isSmallInteger(temp) then
    and the source is not a SmallInteger
    if ot(temp].space = FromSpace then
      and the source is in Fromspace
    moveObject(temp)      move source from Fromspace to Tospace
  objB[j] := temp;        then store it
```

Note that it is unnecessary to check if the destination object is in Tospace if it is the current context, since it would have either been created there or moved there when it became current.
Modifications
to the Baker
Garbage
Collector

One difference between Smalltalk-80 object spaces and those of Lisp-like systems is that Smalltalk-80 objects are referenced by name, whereas in Lisp, objects are typically referenced by virtual address. This allows us to eliminate the forwarding pointers needed in Lisp systems using the Baker garbage collector, since in Smalltalk-80 systems the object table is the only place that the actual address of an object is stored. We also use a flag in the object table entries to note in which semispace an object is stored. This could be done by comparing the virtual address of the object with the base addresses of the spaces, but would be slower.

The use of object names rather than virtual addresses is both a blessing and a curse. The elimination of forwarding pointers simplifies the object accessing code, since no check need be made for a forwarding pointer, but adds an extra indirection for object accesses (the other being the virtual to physical mapping), and the difficult problem of reclaiming the names of objects which have become garbage.

The indirect addressing caused by using object names rather than virtual addresses is not nearly as expensive as having to handle forwarding pointers. The use of forwarding pointers requires that the accessing code test the virtual address pointer to see if it is in Fromspace, and if so, read the object header to determine if it is a forwarding pointer. If it is, the source of the reference must be changed to point to the new location. This is more expensive (without special hardware) than accessing objects indirectly through the object table. Most object references in Smalltalk-80 systems are to objects whose virtual address is cached by the interpreter (the context, method, and receiver) so that indirection through the object table is minimized. "Pure" objects need never be changed if they reference other objects by name, allowing them to be stored on read-only media like videodisks. An object table will take up about 10-20% of the space of the whole world of objects, but we don't feel that that is excessive given the benefits of naming.

Garbage objects are reclaimed by virtue of not being seen by the garbage collector, so there is no direct way to reclaim their names. One way to deal with this is to defer name reclamation until some convenient time, such as overnight. Although a 31-bit name space is big enough to do this, the object table would become quite large and sparse. This would be difficult to manage, so we looked for a way of incrementally reclaiming names.

At first, we implemented a mechanism whereby a flag was set in the object table entry for objects that were either newly created or copied to Tospace. At flip time, we scanned the object table, freed those names without the flag set, and cleared the flags in those that were set. This resulted in a pause of several seconds at each flip, due to page faulting
in the object table. We could have just checked the pointers in the object table to find the ones that were still pointing at Fromspace, but we felt that the flag test was marginally faster.

Eventually, Steve Shirron developed a properly incremental method of reclaiming names that works in the following way.

Each object table entry has two flags, an "even" flag, and an "odd" flag. Each flip of the garbage collector alternates between being an "even" or an "odd" flip. As objects are created or copied to Tospace, the appropriate flag in the object table entry is set, without touching the other flag. A name reclaiming process is run incrementally every time a name is allocated. The name reclaimer scans the object table sequentially, starting over at each flip. For each object table entry, it checks to see if both flags are clear. If so, the object is dead and the name is reclaimed. If not, the flag corresponding to the previous cycle is cleared. In this way, names of objects that died in cycle N are reclaimed in cycle N+1.

The name reclaimer scans some number of entries each time it is activated. Since it is not fatal for the name reclaimer to not be done when a flip occurs (it merely finishes scanning the object table first), the number of entries to scan each time is not critical. The number of entries scanned per activation should dynamically depend on the amount of free space left, the average object allocation size, and the amount of object table left to scan, so that it will finish just before a flip occurs.

## The Lieberman-Hewitt Garbage Collector

Lieberman and Hewitt observe that with the Baker garbage collector the cost of creating objects and garbage collection is not related to the objects' lifetimes⁵. Traditional environments commonly use stack storage for temporary objects, especially activation records, because stack management is very inexpensive. Stacks have the nice property that they are always compacted, so that allocating and deallocating objects of varying sizes does not cause fragmentation of storage. Language environments such as C and Pascal follow a strict control hierarchy, and the lifetimes of their temporary objects (local variables and activation records) are directly related to this hierarchy. In these environments it is either illegal or impossible to pass a reference to a stacked object to a previous level. These restrictions allow traditional languages to manage space very efficiently.

Most Lisp systems allow only hierarchical control flow so that they can allocate activation records on a stack. Temporary objects can be declared to the compiler as "local" to a function activation, which allows
them to be deallocated when the function returns. Lisps which allow
multiprocessing, such as Interlisp, use either multiple stacks or a struc-
ture known as a "spaghetti stack". Multiple stacks are difficult to
manage because they may each grow to a potentially unbounded size.
With spaghetti stacks, activation records are allocated from a heap and
linked together. This facilitates the use of multiprocessing and environ-
ment closures. Even here, the cost of allocating activation records from
a heap is not inordinately expensive because the virtual machine can
deallocate them when they are deactivated.

Smalltalk-80 activation records (contexts) are objects just like any
other object in the environment. Since a method may hand a reference
to its context to any other object in the system, contexts may not be au-
tomatically deallocated when returning from a message send. Contexts
are created at a very high rate, which makes the Smalltalk-80 system
have pretty much the worst space management problems.

The Baker garbage collector is quite inefficient for Smalltalk-80 sys-
tems because the large number of contexts fill up free space rapidly,
causing frequent flips. Since each flip causes all the accessible objects to
be copied to the other semispace, the Baker garbage collector consumes
too much time to be practical.

The Lieberman-Hewitt garbage collector eliminates this problem by
dividing the world into a lot of little Baker spaces. These spaces are set
up so that objects of about the same age are in the same space. Newer
objects are more likely to die than older objects, so newer spaces are
collected more often than older spaces. Garbage collecting a small space
is quite a bit cheaper than garbage collecting the whole world at once.
The individual spaces are collected separately, allowing the use of small
Tospaces. Unfortunately, dealing with references that cross space
boundaries is complex.

This "generation" scheme is ideal for Smalltalk-80 systems. The
newest region will be filled with contexts rapidly, but when flipping the
region, very few of the contexts will survive. This drastically reduces
the amount of copying needed to maintain a compacted region. The
scheme can be arranged so that a new generation is created whenever
the newest region starts filling up with objects that have survived sev-
eral flips.

The Static
Object Region

We have not yet implemented the Lieberman-Hewitt garbage collector.
There are several open questions about the details of this scheme that
we want to answer before we try it. Instead, we implemented a scheme
that is somewhat halfway between the Baker and the Lieberman-Hewitt. This scheme involved the use of a separate region called the static object region.

We noticed that of the approximately 700Kbytes of objects in the base Smalltalk-80 system, about 600Kbytes of them are relatively permanent, and need not be subject to the continual scrutiny of the Baker garbage collector. By dividing the objects into two groups, static and dynamic, we can remove most of the objects from the Baker regions and compact them together into the static object region. This region is not garbage collected dynamically because the objects in it are expected to have very long lifetimes.

The Static Object Region and the Baker region are equivalent to the oldest and the newest generation in the Lieberman-Hewitt garbage collector. By leaving out all the middle generations, we simplify the scheme at the expense of causing inefficiencies when running applications that generate lots of medium lifetime objects.

Static objects are differentiated from dynamic objects by their age. Each object has a 6 bit (arbitrarily chosen) age field. This field is used to keep track of how many flips the object had survived. An object older than 63 flips was placed in the Static Object Region the next time the region was regenerated. Fig. 8.4 shows the resulting layout of each object table entry.

Whenever a snapshot is requested (which already causes a long pause) we scan through all objects looking for "old" ones. A space is created that is just big enough to hold them, and then they are copied to it. The object table entries for these objects are marked to indicate to the Baker collector that they should be ignored. This space is dumped to the snapshot file separately from the "dynamic" objects, so that it is easy to recreate when rolling in a snapshot.

Dynamic objects referred to only by static objects must be saved by the Baker garbage collector. Instead of scanning all the static objects for references to dynamics, we use an "exit table." This table is a list of those static objects which may contain references to dynamic objects. The static objects referred to by this table are scanned by the Baker scanner and all dynamic object references found in them are handled appropriately. Each static object has a flag, which when set indicates that the static object has an entry in the exit table. Whenever an object reference is stored in another object, the flags are checked. If they indicate that the destination is a static object without an entry in the exit table, and that the source is a dynamic object, an entry for that static object is placed in the table. If later, that static object ceases to have references to dynamic objects, it is not removed from the exit table. This does not appear to be the source of any inefficiency. Surprisingly, the exit table had fewer than 50 entries after running for several
An Object Table Entry is a 32 bit word

<table><tr><td>31</td><td>30</td><td>29</td><td>28</td><td>27</td><td>26</td><td>25</td><td>24</td><td>23</td><td>22</td><td>21</td><td>20</td><td>19</td><td>18</td><td>17</td><td>16</td></tr><tr><td>ST</td><td>NE</td><td>W</td><td>X</td><td>M</td><td>SO</td><td>SE</td><td>P</td><td colspan="10">Location (23:16)</td></tr></table>

<table><tr><td>15</td><td>14</td><td>13</td><td>12</td><td>11</td><td>10</td><td>9</td><td>8</td><td>7</td><td>6</td><td>5</td><td>4</td><td>3</td><td>2</td><td>1</td><td>0</td></tr><tr><td colspan="10">Location (15:2)</td><td>X</td><td>F</td></tr></table>

F - Set if OTE is free

P - Set if object has pointer fields

SE - Even flag for OTE sweeper

SO - Odd flag for OTE sweeper

M - Mark-used by Mark/Sweep GC

W - Set if object has word fields

NE - Set if object is Static and is not in exit table

ST - Set if object is static

X - Unused

<caption>**Figure 8.4** Location - Longword virtual address of object.</caption>

weeks, indicating that all but about 50 of the static objects only referred to other static objects.

The become: primitive causes problems because it switches the object pointers of two objects which may be in different spaces. A static object converted to a dynamic is the most difficult to manage. Rather than scan all the statics looking for those which refer to this new dynamic object (which would take a while), we add the new dynamic to a list called the "becomelist". This list is scanned by the garbage collector at flip time so that all the objects referred to by it are copied into Tospace. This insures that the new dynamic object is not deleted in case it is referred to only by static objects. It is fairly rare to convert a static object to a dynamic object, so we are not concerned by the possibility that it dies but is not seen as garbage. The exhaustive garbage collector that is run at snapshot time will get rid of it if it has died.

Converting a dynamic object to a static merely requires that the new static object be scanned for references to dynamic objects. If any are found, the new static is installed in the exit table. Only one object is scanned in this case, so no perceptible pause occurs.
Eventually, we have to collect the garbage that has accumulated in the static region. This is accomplished by an exhaustive mark/sweep garbage collector that is run at snapshot time. This same garbage collector also compacts the dynamic objects so that there is no wasted space in the snapshot image.

We found that the use of the static region resulted in a significant improvement in performance, more than doubling the apparent speed. Removing most of the objects from the Baker regions reduced page faulting substantially, because there were fewer objects to copy when a flip happened.

The implementation of this scheme was relatively simple compared to the full Lieberman-Hewitt. We acquired a lot of useful statistics from this that should allow us to do a good job of implementing the Lieberman-Hewitt garbage collector.

## Virtual Object Space

In order to support a very large number of objects, some "virtual object" mechanism must be used. The Software Concepts Group has used variants of "object swapping" to achieve this with their OOZE and LOOM virtual object systems[^7]. Since the VAX/VMS system supports a large paged virtual address space, we decided to use it directly to implement a virtual object scheme. This approach allowed us to defer issues relating to virtual memory performance until after we got the basic system running.

The virtual space is divided into several regions: two 1Mbyte "Baker" semispaces, 512Kbytes for the object table (ot), and approximately 600Kbytes for the static object region. The object table is set at 128K objects. This number was derived by doubling the size until we stopped running out of room. Although we do not know how much page faulting is due to accessing the object table, we suspect that it is substantial.

Ted Kaehler's paper (see Chapter 14) discusses the problems with straightforward paging systems (such as we used) and compares them with object swapping schemes. The gist of the argument against paging is that since there is a low locality of reference between adjacent objects in a page, and objects tend to be much smaller than pages, the majority of space in physical memory is taken up by useless objects that just happen to be on the same pages as useful objects. Object swapping schemes such as OOZE and LOOM compact the active objects into physical memory so that more active objects can fit at one time. This allows larger applications to run without faulting than with a paging system. Object swapping has two problems dealing with disks that like to trans-
fer whole pages at once. First, a faulted-in object must be copied from the disk page buffer to the object region in core. This is probably not serious compared to the time it takes to access the object on disk in the first place. The second problem is that when faulting-out an old object (when it has been modified), the disk page(s) it belongs in must first be read so that the adjacent objects are not trashed. Although it is possible to write all the objects you need to fault out compacted together and appended to the end of the file, this will not only cause problems dealing with the fragmentation of the disk image, but makes for extra work in updating the directory of the objects on disk.

The VAX/Smalltalk-80 system is more properly thought of as a "mapped real memory" than a true virtual object memory because of the excessive paging we encounter when we have less than about 3Mbytes of real core for our use. A proper system should provide adequate performance whenever the set of active objects fits into the available real memory. There may be more than a 100 to 1 ratio between all objects and the active objects in a production Smalltalk-80 system. A virtual object system should be able to support such a system with ease.

Our goal is to design a hybrid of object swapping and paging that gives us a low faulting rate, yet runs on paged systems. This would allow us to use commonly available computers that have hardware to support paging, as well as allowing Smalltalk-80 systems to co-exist with other language environments on the same machine.

Our approach is based on the observation that you can create a compact set of active objects in a paged system merely by copying them from wherever they happen to be in virtual space into a region which is locked into core. Faulting out objects is accomplished by just copying them back. The disk activity of the paging system caused by this scheme is virtually identical to that of the object swappers. In addition, objects larger than a page need not be copied at all, allowing much larger objects than would be possible with an object swapper. A large linear virtual address space is helpful when implementing garbage collectors such as the Baker. With a paged system, when Fromspace is empty the pages underlying it can be deleted completely. Pages needed for Tospace can be quickly created by using those released from Fromspace. If a large amount of garbage is collected in each pass, then the amount of physical memory required is much less than what both semispaces would ordinarily require. If you need more space than is available physically, paging will happen automatically.

The Lieberman-Hewitt garbage collector would be a natural candidate for use here. Newer objects are accessed more frequently than older objects, so by keeping the newest regions in core and copying objects from older regions into a cache, we would obtain the benefits of both object swapping and incremental garbage collection.
The cache could be managed by combining the "clock" procedure⁸ with a Baker-like semispace set. The clock procedure would repetitively scan a list of the cached objects. Those that had not been touched since the last scan would be copied back to their home (if they had been modified), those which had been touched would be copied to the other semispace. This would compact the cache incrementally. It is also possible to fault-out objects until a big enough hole is created to satisfy a faulted-in object, but this scheme may cause noticeable pauses whenever a flurry of objects are faulted out, as each will probably cause a page fault when written back. Fortunately, most of the objects would not have been modified and therefore need not be copied back. Some experimentation is called for here.

The object table should be implemented as a hash table in order to eliminate page faulting when accessing active objects. Objects in the cache, and those in the newer regions would have their names placed in the hash table.

## Paging Performance

The straightforward approach we have taken, although easy to implement, spends most of its time waiting in a page fault state when there are other users on the system. VMS allocates most unused core for faulted out pages, so when the Smalltalk-80 system is running by itself (on Sunday mornings) the performance improves several fold as disk accesses are usually unnecessary for page faults. A lot of the paging overhead is due to the Baker garbage collector and the object name reclaimer scanning their spaces. Since the pages touched by the name reclaimer, and many of the pages touched by the Baker scanner are completely predictable, a mechanism whereby the pager could be requested to fault-in a page without suspending the program would have a substantial impact on the performance. Unfortunately, VMS does not have such a hook. We are looking into using a separate VMS process, mapped into the same space as the Smalltalk-80 process, to fault-in pages so that it would be suspended instead of the Smalltalk-80 process.

Anything that reduces the rate at which garbage is created will have a favorable impact on paging rates because of the reduced garbage collection activity. Smalltalk-80 systems seem to be much worse than modern compiled Lisp systems in the rate at which garbage is generated. This is attributable primarily to contexts, which must be allocated from the heap, and secondarily to the fact that Smalltalk-80 methods tend to require arguments packed into objects such as points and rectangles, which are almost immediately discarded. Editing text also creates a
substantial amount of garbage as new strings are created for each modification. Some object-based systems allow variable-length objects to "grow" by allocating space for them that is larger than that actually needed. When an object such as a string needs more room, it can expand until it fills the contiguous chunk allocated for it by the memory system. If it needs more, it is automatically copied to a larger area. It may be worthwhile to use this technique in a Smalltalk-80 implementation.

## Context Reclamation

We noticed that we were generating about a megabyte per second of objects that did not survive even one space flip. We found that these objects were almost entirely contexts. Some method of reducing this garbage without compromising the flexibility of the context linkages had to be found. We could not just reclaim contexts when they were returned from, since a reference to a context could be handed to another object.

We found that there are only two occasions when a reference to the active context was handed out: the PushActiveContext bytecode, and when the context was placed on a process or semaphore queue. We assumed that if either of these events happened, the current context and all its ancestors could be accessible by any other object, so must be reclaimed only by the garbage collector. Fortunately, these cases happen infrequently. If neither of these events occurred, the context could be reclaimed immediately upon returning. By maintaining a counter that is incremented every time a non-primitive send happens and zeroed when either of the special events happens, we reclaim contexts (small only) whenever we return and the counter is non-zero (decrementing the counter as we return).

These reclaimed contexts are linked together on a free list, and are used instead of heap space if there is anything on the list. When the garbage collector does a space flip, this list is cleared because the contexts are then in the wrong space and it would be silly to copy them to the new Tospace.

This little trick reclaims about 85-90% of the contexts. Occasionally, it is much worse (40-50%), apparently due to executing tight loops that perform a lot of blockCopys.

## Dealing with a Timesharing System

The Smalltalk-80 system as distributed is not designed to either run background processes or co-exist on a timesharing system. This is due to the large number of places where the code loops waiting for a mouse
button. The system can be converted to one which is entirely event driven by inserting wait messages to an "any event" semaphore into the loops. We found these loops by noticing whenever the idle process was not running, yet nothing else seemed to be happening. We would then type control-C to interrupt the Smalltalk-80 system and find out who was responsible. The debugger was then used to edit and recompile the offending methods. Converting all the interaction to an event-driven style allowed background Smalltalk-80 processes to run whenever the user was not actively interacting with the Smalltalk-80 system.

It is generally considered uncivil to run programs that are not doing anything worthwhile on a timesharing system. To fix this, we replaced the Smalltalk-80 idle process with one that called two special primitives. The Smalltalk-80 code for this is as follows.

**idleLoop**

[true] whileTrue:
[[Smalltalk collectGarbage] whileTrue.
Smalltalk hibernate]

The collectGarbage primitive performed an incremental activation of the garbage collector, returning false if there was nothing left to do. The hibernate primitive suspended the Smalltalk-80 VMS process, letting other users run. The hibernate primitive returned whenever an external event happened. Since this loop runs at the lowest priority, it is preempted by any Smalltalk-80 process with something to do.

This made us more popular with the other users of the VAX, and also reduced the overhead of the garbage collector when interacting with the Smalltalk-80 system in a bursty manner (which is usually the case). The Smalltalk-80 process itself also benefited from this because the VMS scheduler assigns a lower priority to compute-bound processes. By hibernating often enough, the Smalltalk-80 process would preempt other users running compilers and the like, leading to a snappier response when browsing or editing.

**The Message Cache**

We implemented a message cache to speed up message lookup as recommended by the book. We found, however, that using a two-way set associative scheme was significantly better than the one-probe hash table described in the book. Our cache used a hash table where every key (constructed from the receiver's class and the selector Oop) had two possible locations in the cache, determined by the hash value and its complement. The location to store a message was determined by a ping-pong scheme in which a flag was toggled whenever a message was in-
serted into the cache. If the flag was set, the direct hash value was used, if cleared, the complement was used. This allowed two messages with the same hash value to co-exist in the cache. More elaborate caches using 4- and 8-way sets are feasible, but the payoff is less since all possible locations may have to be checked when looking up a message. In this cache we stored the full key for matching, the method's Oop, the fields of the method header and extension unpacked into bytes, and the address of the interpreter routine that handled that method. This latter information proved very helpful in speeding up the processing of message sends. Our hit rate was typically better than 90% with a 256 entry cache (two sets of 128 entries).

## The Image Preprocessor

The differences in word formats between the Xerox and DEC hardware forced us to write a program (in C on the VAX) that read the standard Smalltalk-80 image, massaged it, and wrote out an image in our format. This was done originally for the PDP-11 version, and was extensively modified for the VAX version. This preprocessor did the following conversions:

1. Converted object headers to 32-bit word format.

2. Converted the size fields to be bytecounts.

3. Initialized the flags in the object header and object table entry.

4. Converted all pointer fields to 32-bit words by sign extending SmallIntegers and zero extending Oops.

5. Byte-reversed all the objects with byte fields (e.g. CompiledMethods) so that we could use the byte-addressing capability of the VAX directly.

6. Bit-reversed all the words in bitmaps (our lsb is on the left of a scanline).

7. Converted the IEEE format floating point numbers to DEC format.

8. Converted LargePositiveIntegers to SmallIntegers where possible.

9. Patched CompiledMethod initialPC to call a primitive.

10. Patched the PCs in all the contexts to reflect the increased storage taken by the literals.
11. Reformatted the object table because of the different flags and addresses.

12. Formatted the image header to have the information about the static region that we needed.

This preprocessor also gathered information about the number and sizes of the various types of objects.

## Performance Measurements

It is difficult to come up with accurate performance figures for a system like this. Small changes in such things as the working set size have a major impact on the performance. Our performance monitoring software could not distinguish between time due to page faults and time due to other users preempting the Smalltalk-80 system (it left them both out). The page fault rate depended on the long-term history of the Smalltalk-80 session, and the time it took to handle faults varied according to the load on the VAX.

With that in mind, when using a working set of 512, 512 byte pages (the largest our system let us have), we observed that we were getting about 250 page faults/second during compiling or browsing. We seemed to get between 15K and 25K bytecodes/second (on Sunday mornings) when compiling or browsing.

We found that CPU time spent in the garbage collector code amounted to about 7% of the total when executing long tasks. Of course, the real time was substantially larger (except on Sunday mornings) due to page faulting in the garbage collector.

## Conclusions

After using this version of Smalltalk-80 implementation for a while, we can make some useful observations:

1. 32 bit fields are the way to go.

2. Paging systems are very easy to use, but a lot of work needs to be done to achieve adequate performance.

3. Incremental garbage collection is generally superior to reference counting, both in ease of implementation and performance.

4. The Smalltalk-80 system is marginally usable on a timesharing system with 40 users.
References

1. Baker, Henry G., "Actor Systems for Real-Time Computation," MIT Laboratory for Computer Science, MIT/LCS/TR-197, 1978.

2. Lieberman, Henry, and Hewitt, Carl, "A Real Time Garbage Collector Based on the Lifetimes of Objects," MIT AI Memo no. 569, 1981.

3. See reference 1.

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

5. See reference 1.

6. Bobrow, Daniel G., and Wegbreit, Ben, "A Model and Stack Implementation of Multiple Environments," *Communications of the ACM*, vol. 10, pp. 591-602, 1973.

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

<figure><img src="image_15.png" /></figure>
# The Smalltalk-80 Benchmarks

Kim McCall

Software Concepts Group

Xerox Palo Alto Research Center

Palo Alto, California

## Introduction

At the first Smalltalk-80 "implementors meeting" on September 24-25, 1981, several of the groups pursuing implementations expressed a desire for some system facilities to help them measure the efficiency of their interpreters. Such facilities, which were unavoidably labeled "benchmarks," would provide an objective means of comparing implementations, gauging the value of intended performance enhancements, and tracking the progress of individual implementations over time.

This author was given the responsibility of adding such facilities to the system, and thus was born the class Benchmark found in the Smalltalk-80 virtual image.

In this paper I:

1. Describe the general framework of the timing and reporting facilities in class Benchmark;

2. Describe various individual tests (hereafter referred to as "benchmarks");

3. Explain how to write a new benchmark;

4. Suggest ways benchmarks can be used, i.e., how to gain useful information from them; and
5. Present the results of running the standard system benchmarks in several different implementations.

## The Benchmark Framework

Class Benchmark contains a simple set of facilities for timing the execution of some block of code and reporting the result. The central message is

test: aBlock labeled: label repeated: nTimes.

aBlock must be a BlockContext that contains the code to be timed; and
label should be a string describing this code, i.e., describing the system
behavior that is being timed. Since timings are recorded in milliseconds,
it often happens (e.g., when testing atomic system functions such as
pushing a value onto the stack or popping it off) that a single execution
of aBlock would yield a value so small that it would be dwarfed by the
roundoff error. So the method allows us to specify the number of times
the block should be executed (nTimes).

For example,

### Benchmark new

test: [20 factorial]

labeled: 'testing 20 factorial'

repeated: 100

would time 100 executions of the block

[20 factorial]

and report the result, using the label 'testing 20 factorial' for purposes of
identification.

## Reporting

Class Benchmark contains various facilities for reporting its results in a
permanent, semi-permanent, or evanescent way.

A report consists of:

1. An *identification line*, giving the label, enclosed in square brackets.

2. A *total time line*, giving the number of times aBlock was executed and the total time (in seconds).

3. If the number of executions of aBlock is greater than one, a *single iteration line*, giving the time (in microseconds) taken to execute aBlock once.
For example, if it took 26133 milliseconds to run 100 repetitions of [20 factorial], the report would read

[testing 20 factorial]

100 repetitions timed at 26.133 seconds

261330.0 microseconds per repetition.

After each benchmark test, some feedback is printed in the SystemTranscript. The user can choose to print either the full report as described above or just the identification line. If she or he desires a more permanent record, the user may also elect to print a report on a file. For implementations that do not yet include a working file system, the report may be printed on a Stream.

The default reporting behavior will be to print the full report in the Transcript. To change the default, the user sends the message setOutputParameters to the instance of class Benchmark that is going to perform the test. In response to setOutputParameters, the instance of Benchmark will invite the user to select among the various reporting options.

In order to generate a file containing reports for a *series* of benchmarks, class Benchmark provides the message testList. The setOutputParameters message is sent automatically in response to testList. There are built-in facilities in class Benchmark for comparing two output files in order to chart progress over time or to compare two different implementations. These facilities are invoked by the message compareOldTimes:newTimes:outputTo:

The actual timing is done by the method

Timing

time: aBlock repeated: nTimes

This method times nTimes executions of aBlock and nTimes executions of an empty block (one that just returns nil), and then computes and returns the difference. This should report the actual time spent executing aBlock nTimes times, and subtract out the overhead of the counting and execution control structures. In the code for

time: aBlock repeated: nTimes

some care was taken to insure that the control structures for counting up to nTimes would not dominate the execution of aBlock. For example, rather than using timesRepeat: for looping, we use an open coded loop. We also use a doubly-nested iteration loop when nTimes is large, to insure that all the counting is done using SmallInteger arithmetic.
## The Standard System Benchmarks

The Smalltalk-80 virtual image includes two different kinds of benchmarks, those that measure specific parts of an interpreter and those that measure overall system performance. In order to be able to gauge the benefit of small changes to restricted parts of the interpreter, or to isolate specific areas in need of improvement, there is a set of benchmarks that test the efficiency of each of the most basic, simple operations of the interpreter. These test the basic bytecodes and the primitives. There is also a set of more global benchmarks that test the performance of the system at the higher-level activities invoked by a typical Smalltalk-80 programmer, such as compiling, decompiling, using browser facilities, and inserting, formatting, and displaying text. We call these the *micro-benchmarks* and the *macro-benchmarks* respectively.

### The Micro-Benchmarks

Most of the micro-benchmarks consist of several repetitions of the particular bytecode or primitive to be tested. We need several repetitions of the very fast bytecodes in order to make the execution time of a block be so much greater than the execution time of the empty block that the rounded-off results will be meaningful. To keep the stack from overflowing, and to satisfy the demands of the compiler, the repetitions of the operation we intend to test are interspersed with pops or quick sends of the message `==`. The micro-benchmarks all end with `↑nil`. This makes a block's execution speed more directly comparable to the execution time of an "empty" block (which just returns `nil`). In the descriptions of the individual micro-benchmarks below, I generally give the percentage of bytes in the block (ignoring the `↑nil`) that actually execute the behavior we are trying to test. I will present the standard system benchmarks in the order in which they occur in the method for `setStandardTests` in class `Benchmark` class. This list is intended to serve as a documentation reference, and the casual reader is invited to skip or skim it.

Please note that the inclusion in the benchmarks of the `==` message or other byte codes that we really didn't want to test may greatly alter the execution speed of the block and compromise the meaningfulness of the results. For example, I thought that I had implemented the quick push of a constant (like `1`) onto the stack about as efficiently as possible, and I was perplexed to learn that a machine-coded MC68000 implementation performed the `testLoadQuickConstant` benchmark faster than my own microcoded implementation. After looking at the code that actually implements the Smalltalk-80 virtual machine instruction `16r76` (118 decimal), I was even more perplexed, since my implementation looked considerably *more* efficient. Finally, I realized that most of the time reported by the benchmark was going into the execution of (and return from) the `==` message which I had included just to satisfy the compil-
er. (This MC68000 implementation gave better results because it uses a delayed reference-counting scheme that greatly expedites pushes, pops, and simple primitive operations.)

<table><tr><td>testLoadInstVar</td><td>This benchmark measures how quickly an instance variable of the receiver can be pushed onto the stack. Because this variable is set to 1, there is little reference-counting overhead on the push (although there may be more on the other operations in the block). 50% of the bytes in the block are 16r0, a push of the receiver's first instance variable.</td></tr><tr><td>testLoadTempNRef</td><td>This benchmark measures how quickly a variable that is local to a method can be pushed onto the stack. Setting this variable to 1 avoids most reference-counting overhead on the push. 50% of the bytes in the block are 16r10, a push of the method's first local variable.</td></tr><tr><td>testLoadTempRef</td><td>This benchmark also measures how quickly a variable that is local to a method can be pushed onto the stack, but because the variable is set to some newly created point, the implementation's reference-counting mechanism (if any) will be fully exercised. Again, 50% of the bytes in the block are 16r10, a push of the receiver's first instance variable.</td></tr><tr><td>testLoadQuickConstant</td><td>This benchmark measures how quickly one of the "quick constants" (-1, 0, 1, 2, nil, true, false) can be pushed onto the stack. There is little reference-counting overhead on the push. 50% of the bytes in the block are 16r76, a push of the constant 1.</td></tr><tr><td>testLoadLiteralNRef</td><td>This benchmark measures how quickly an ordinary literal (a constant generated at compile time) can be pushed onto the stack. Because we have used the constant 3, there is little reference-counting overhead on the push. 50% of the bytes in the block are 16r21, a push of the method's second literal.</td></tr><tr><td>testLoadLiteralIndirect</td><td>This benchmark measures how quickly the contents of an indirectly accessed variable (such as a class variable or a global variable) can be pushed onto the stack. Because our variable refers to class Point, there is little reference-counting overhead on the push. 50% of the bytes in the block are 16r41, an indirect push of the method's second literal.</td></tr><tr><td>testPopStoreInstVar</td><td>This benchmark measures how quickly a value can be popped off the stack and stored in an instance variable of the receiver. Because this value is the SmallInteger 1, there is little reference-counting overhead on the push or the store. 50% of the bytes in the block are 16r60, a pop of the top of the stack into the receiver's first instance variable.</td></tr></table>
<table><tr><td>testPopStoreTemp</td><td>This benchmark measures how quickly a value can be popped off the stack and stored in a local variable of the method. Again, since this value is 1, there is little reference-counting overhead. 50% of the bytes in the block are 16r68, a pop of the top of the stack into the method's first local variable.</td></tr><tr><td>test3plus4</td><td>This benchmark measures the speed of SmallInteger addition. Because all values are SmallIntegers, there is little reference-counting overhead. 25% of the bytes in the block are 16rB0, a quick send of the message +.</td></tr><tr><td>test3lessThan4</td><td>This benchmark measures the speed of SmallInteger comparison. Because all values are SmallIntegers, there is little reference-counting overhead. 25% of the bytes in the block are 16rB2, a quick send of the message &lt;.</td></tr><tr><td>test3times4</td><td>This benchmark measures the speed of SmallInteger multiplication. Because all values are SmallIntegers, there is little reference-counting overhead. 25% of the bytes in the block are 16rB8, a quick send of the message *.</td></tr><tr><td>test3div4</td><td>This benchmark measures the speed of SmallInteger division. Because all values are SmallIntegers, there is little reference-counting overhead. 25% of the bytes in the block are 16rBD, a quick send of the message //.</td></tr><tr><td>test16bitArith</td><td>This benchmark measures the speed of 16-bit integer arithmetic. Since some implementations use more than 15 bits to represent SmallIntegers (see Chapter 8), the reference-counting overhead will depend on the representation chosen for 16-bit integers. 25% of the bytes in the block are 16rB0, a quick send of the message +.</td></tr><tr><td>testLargeIntArith</td><td>This benchmark measures the speed of arithmetic on integers greater than 2<sup>16</sup>. The reference-counting overhead will depend on the exact representation chosen for these integers. 25% of the bytes in the block are 16rB0, a quick send of the message +.</td></tr><tr><td>testActivationReturn</td><td>This very important benchmark uses a call on a doubly-recursive method to measure the speed of method activation and return. There is little reference-counting overhead associated with knowing when to end the recursion, but there may be a great deal in managing the contexts that represent the activations. About 12.5% of the bytes executed during this benchmark are 16rE0, a send of the method's first literal (in this case, the symbol recur!), and about 12.5% are returns, split evenly between 16r78, a quick return of the receiver, and 16r7C, a return of the value on the top of the stack.</td></tr><tr><td>testShortBranch</td><td>This benchmark times the short jump to the false branch of a conditional. Although there</td></tr></table>
<table><tr><td>testWhileLoop</td><td>This benchmark measures the speed of executing a simple "while loop." All loop-counting uses SmallInteger arithmetic. About 9% of the bytes in the block are 16rA3, long jump, and about 9% are 16r9D, a short conditional branch.</td></tr><tr><td>testArrayAt</td><td>This benchmark measures how quickly a value can be read from an Array. 25% of the bytes in the block are 16rC0, a quick send of the message at..</td></tr><tr><td>testArrayAtPut</td><td>This benchmark measures how quickly a value can be stored into an Array. 20% of the bytes in the block are 16rC1, a quick send of the message at:put..</td></tr><tr><td>testStringAt</td><td>This benchmark measures how quickly a value can be read from a String. 25% of the bytes in the block are 16rC0, a quick send of the message at..</td></tr><tr><td>testStringAtPut</td><td>This benchmark measures how quickly a value can be stored into a String. 20% of the bytes in the block are 16rC1, a quick send of the message at:put..</td></tr><tr><td>testSize</td><td>This benchmark measures how quickly a String can return its size. The String will be reference counted in reference-counting implementations. 33% of the bytes in the block are 16rC2, a quick send of the message size.</td></tr><tr><td>testPointCreation</td><td>This benchmark measures how quickly a Point can be created from two SmallIntegers. 25% of the bytes in the block are 16rBB, a quick send of the message @.</td></tr><tr><td>testStreamNext</td><td>This benchmark measures how quickly the next value can be read from a Stream. About 33% of the bytes in the block are 16rC3, a quick send of the message next.</td></tr><tr><td>testStreamNextPut</td><td>This benchmark measures how quickly the next value can be stored into a Stream. About 25% of the bytes in the block are 16rC4, a quick send of the message nextPut..</td></tr><tr><td>testEQ</td><td>This benchmark measures how quickly two objects can be compared for identity. About 50% of the bytes in the block are 16rC6, a quick send of the message ==.</td></tr><tr><td>testClass</td><td>This benchmark measures how quickly an object can return its class. 33% of the bytes in the block are 16rC7, a quick send of the message class.</td></tr><tr><td>testBlockCopy</td><td>This benchmark measures how quickly a BlockContext can be created that has the current context as its "home context." 25% of</td></tr></table>
The Smalltalk-80 Benchmarks

<table><tr><td>testValue</td><td>the bytes in the block are 16rC8, a quick send of the message blockCopy..</td></tr><tr><td>testCreation</td><td>This benchmark measures how quickly a simple BlockContext can be evaluated. 33% of the bytes in the block are 16rC9, a quick send of the message value.</td></tr><tr><td>testPointX</td><td>This benchmark measures how quickly one coordinate can be extracted from a Point. 33% of the bytes in the block are 16rCE, a quick send of the message x.</td></tr><tr><td>testLoadThisContext</td><td>This benchmark measures how quickly the current context can be pushed onto the stack. 50% of the bytes in the block are 16r89, a quick push of the current context.</td></tr><tr><td>testBasicAt</td><td>This benchmark measures how quickly the value can be read from an unnamed (but indexed) field of a variable-length object. 25% of the bytes in the block are 16rE4, a send of the method's fifth literal, in this case the message basicAt..</td></tr><tr><td>testBasicAtPut</td><td>This benchmark measures how quickly a value can be stored into an unnamed (but indexed) field of a variable-length object. 20% of the bytes in the block are 16rF5, a send of the method's sixth literal, in this case the message basicAt:put..</td></tr><tr><td>testPerform</td><td>This benchmark measures the speed of the perform: primitive. 20% of the bytes in the block are 16rF1, a send of the method's second literal, in this case the message perform:with..</td></tr><tr><td>testStringReplace</td><td>This benchmark measures the speed of the String replacement primitive.</td></tr><tr><td>testAsFloat</td><td>This benchmark measures the speed of the SmallInteger to Float conversion. 33% of the bytes in the block are 16rD1, a send of the method's second literal, in this case the message asFloat.</td></tr><tr><td>testFloatingPointAddition</td><td>This benchmark measures the speed of the floating point number arithmetic. 25% of the bytes in the block are 16rB0, a quick send of the message + which must be looked up in class Float.</td></tr><tr><td>testBitBLT</td><td>This benchmark measures the speed of the BitBlt primitive. 33% of the bytes in the block are 16rD2, a send of the method's third literal, in this case the message copyBits.</td></tr><tr><td>testTextScanning</td><td>This benchmark measures the speed of the primitive method that displays characters on the screen.</td></tr></table>
The Macro-Benchmarks

The macro-benchmarks provide examples of the main activities in which a Smalltalk programmer is typically engaged. Since the Smalltalk-80 virtual image does not contain many applications besides the programming environment as a whole, most of the macro-benchmarks test system support for programming activities.

<table><tr><td>testClassOrganizer</td><td>This benchmark measures the speed of conversion between the textual and the structural representations of a class organization. The example chosen is class Benchmark because its organization contains many categories.</td></tr><tr><td>testPrintDefinition</td><td>This benchmark measures how quickly a class definition, as it appears in the system browser, can be generated. The example chosen is an instance of class Compiler because it has a moderate number of instance variables.</td></tr><tr><td>testPrintHierarchy</td><td>This benchmark times the printing of a portion of the Smalltalk-80 class hierarchy. The example chosen is class InstructionStream because it has several subclasses.</td></tr><tr><td>testAllCallsOn</td><td>This benchmark measures how quickly all the methods in which a given selector is referenced can be found. The example chosen is the selector printStringRadix: because it has a moderate number of senders.</td></tr><tr><td>testAllImplementors</td><td>This benchmark measures how quickly all the implementors of a given selector can be found. The example chosen is the selector next because it has a moderate number of implementors.</td></tr><tr><td>testInspect</td><td>This benchmark measures how quickly a standard inspect window can be created. The example chosen is an instance of class Compiler because it has a moderate number of instance variables.</td></tr><tr><td>testCompiler</td><td>This benchmark measures the speed of the compiler on a slightly longer than normal method, one containing 87 tokens and compiling into 73 bytecodes.</td></tr><tr><td>testDeccompiler</td><td>This benchmark measures the speed of the Deccompiler by decompiling all the methods in class InputSensor.</td></tr><tr><td>testKeyboardLookAhead</td><td>This benchmark gauges keyboard response, simulating a typist who is able to type ahead.</td></tr><tr><td>testKeyboardSingle</td><td>This benchmark measures keyboard handling by simulating a typist who waits until each keystroke appears on the screen before typing the next one.</td></tr><tr><td>testTextDisplay</td><td>This benchmark measures how quickly a paragraph can display itself. The paragraph chosen contains 13 lines with no font or emphasis changes.</td></tr></table>
testTextFormatting
This benchmark measures the system facilities required to display a piece of source code in the system browser. First, the message pattern is discovered and highlighted (by making it bold). Next, the line breaks are determined which will allow it to be displayed between certain margins. Finally, the text is displayed.

testTextEditing
This benchmark measures text-editing speed by repeatedly inserting characters into a string and redisplaying the string.

## Writing Your Own Benchmarks

Suppose you want to use the general benchmark facilities to test and record your system's performance of some tasks that are not already tested by class Benchmark. This is quite straightforward if you are testing some large system function, such as compilation, that does not require user interaction. As explained above, you send an instance of Benchmark the message

test: aBlock labeled: label repeated: nTimes

where aBlock invokes the function whose speed you want to measure. But if you want to test a more atomic system facility, such as a primitive specific to your implementation or a simple system facility, primitive, or byte code for which I have not included a test (such as the performance of your low-level disk code), or if you want to test your system's behavior at a task that involves user input, I have a few words of advice.

First, advice for macro-benchmarks that require user input: It should be obvious that if the benchmark ever has to wait for input, the results will depend on the behavior of the user rather than that of the system. This is unacceptable. So unless you can be sure of feeding your benchmark all the input you need ahead of time (by "type ahead" for example), you will need to figure out a more creative way to discover the results you want. The implementors at University of California, Berkeley, (see Chapter 11), have developed a "script" facility in which the input events required to drive some application can be recorded and then played back later. This allows a script to drive an application or a benchmark, and thus avoids uneven waiting.

Next, advice for the designers of new micro-benchmarks: The main problem in defining a benchmark is being sure that the benchmark actually tests what you mean it to test. The main problem here is making sure that that operation is not swamped by other extraneous computa-
tion. For example, if you want to test the speed of your BitBlt primitive, you might think of a simple way of getting a BitBlt to occur, such as

Display reverse: (100@100 corner: 400@400)

which uses BitBlt to complement the bits in a rectangle on the screen. But this would probably be a mistake, because several (costly) message sends are required to turn this high-level description of a particular BitBlt into a completely specified call on the primitive. The Smalltalk-80 "spy" facilities contained in class MessageTally can help you discover whether your proposed benchmark times primitive or higher-level execution.

To solve this problem you need to find a much lower-level way of invoking the desired behavior. But sometimes you have to be very careful. For example, consider my original code for testing the speed of BlockContext creation. Smalltalk methods often call for unevaluated blocks of code to be passed as arguments. This happens, for example, in all code of the general form

1 to: 10 do: [:i | array at: i put: true].

When it sees something like this, the compiler realizes that it needs to create a BlockContext to serve as the second argument of the to:do: message. So it generates the following sequence of byte codes

pushThisContext push0 (or 1 or 2, etc.) sendMsg: blockCopy:

Now, I was interested in testing the speed of execution of this blockCopy: message. Since I wanted to follow my general rule of making sure that this operation was not swamped by other computation, I thought it would be smart to store the current context in a temporary variable and thus be able to get it onto the stack by a simple pushTemp instruction rather than a (at least in some implementation strategies) potentially more complicated pushThisContext instruction. The problem is that since the code that the benchmark repeatedly executes is itself passed as an unevaluated block, by the time this code is executed, my clever temporary variable no longer points at the current context, but rather at one further down the stack. This resulted in my benchmark testing an operation that would literally *never* be performed in any normal Smalltalk-80 system and that might go much slower (in certain very highly optimized implementations) than the behavior I had meant to test.

The micro-benchmark designer should also be careful to consider the effect of other "filler" bytes, as discussed above.
## How to Use Your Results

What can you learn from the results of your tests? The micro-benchmarks can, of course, suggest parts of an implementation that need additional work. They will often help identify local gross inefficiencies. They can also serve to confirm that a simple local modification was, in fact, an improvement. But I think it is a mistake to place a great deal of emphasis on micro-benchmark performance. It seems that there are only a few micro-benchmarks whose performance correlates strongly with global (macro-benchmark) performance. Microcoded machines with stringent control store limits would be especially ill-advised to spend micro-instruction space speeding up the relatively insignificant micro-benchmarks.

The macro-benchmarks appear to be a good measure of overall system performance. Improvement in their performance correlates well with user-perceived system performance. I have found them very useful in gauging the effect of both small and large changes to my interpreter and in tracking my progress over time. For example, columns A and B of Table 9.1 compare the Dolphin interpreter before and after a change to the handling of the display that had a significant effect on performance. At other times however, testing the macro-benchmarks has served primarily to quell my enthusiastic anticipation of the value of some intended enhancement.

## A Brief Analysis of Early Results

As this book attests, there are now several successful Smalltalk-80 implementations. The standard system benchmarks have been run in each of these implementations, and the reports are presented below. There are several interesting lessons to be gleaned from these results, which I will explore here.

It should be stressed that the figures we will be comparing were achieved on machines of vastly different speeds and hardware configurations. Some of our figures are very early results. Some come from implementations that were intended to teach the implementors about the structure of the interpreter and that placed very low priority on execution speed. Some implementations were written in high-level languages while others were written in microcode. None of these results is final, and none indicates the expected performance of any future products.

I include these figures because the fact that they were achieved on vastly different machines and in pursuit of different goals allows us to do interesting cross-correlations. We can learn which of the micro-benchmarks seem to be good predictors of the speed of the macro-
benchmarks (which is what we really care about). And we can glimpse
the results of various strategies such as reference counting versus gar-
bage collecting.

I will present the results in two tables. Table 9.1 gives raw times for each of the benchmarks, and Table 9.2 gives times as a proportion of the average (geometric mean) time across all implementations. The time reported for each benchmark is the execution time for the entire benchmark (rather than for a single repetition), i.e., that given in the report's "total time line."

<table><caption>Table 9.1 The Benchmarks, Raw Times</caption><thead><tr><th>A</th><th>B</th><th>C</th><th>D</th><th>E</th><th>F</th><th>G</th><th>H</th><th>I</th><th>J</th></tr></thead><tbody><tr><td colspan="10"><em>Micro Tests</em></td></tr><tr><td colspan="10"><em>testLoadInstVar</em></td></tr><tr><td>4.47</td><td>3.72</td><td>0.28</td><td>5.85</td><td>27.6</td><td>3.85</td><td>23.41</td><td>10.62</td><td>5.89</td><td>10.02</td></tr><tr><td colspan="10"><em>testLoadTempNRef</em></td></tr><tr><td>4.37</td><td>3.07</td><td>0.28</td><td>5.97</td><td>26.2</td><td>2.78</td><td>23.3</td><td>10.62</td><td>5.92</td><td>9.71</td></tr><tr><td colspan="10"><em>testLoadTempRef</em></td></tr><tr><td>6.42</td><td>4.53</td><td>0.4</td><td>5.85</td><td>31.16</td><td>2.78</td><td>26.7</td><td>13.89</td><td>7.53</td><td>11.1</td></tr><tr><td colspan="10"><em>testLoadQuickConstant</em></td></tr><tr><td>7.31</td><td>5.14</td><td>0.5</td><td>11.7</td><td>46.19</td><td>5.37</td><td>38.58</td><td>19.65</td><td>11.89</td><td>17.9</td></tr><tr><td colspan="10"><em>testLoadLiteralNRef</em></td></tr><tr><td>4.46</td><td>3.11</td><td>0.28</td><td>6.03</td><td>25.51</td><td>2.88</td><td>19.22</td><td>10.62</td><td>6.02</td><td>10.9</td></tr><tr><td colspan="10"><em>testLoadLiteralIndirect</em></td></tr><tr><td>7.33</td><td>5.06</td><td>0.49</td><td>6.6</td><td>29.0</td><td>3.92</td><td>24.49</td><td>15.41</td><td>8.13</td><td>11.9</td></tr><tr><td colspan="10"><em>testPopStoreInstVar</em></td></tr><tr><td>3.12</td><td>2.81</td><td>0.18</td><td>6.75</td><td>27.68</td><td>5.62</td><td>20.63</td><td>7.98</td><td>10.49</td><td>6.95</td></tr><tr><td colspan="10"><em>testPopStoreTemp</em></td></tr><tr><td>3.58</td><td>2.51</td><td>0.18</td><td>4.67</td><td>27.69</td><td>2.48</td><td>22.87</td><td>7.99</td><td>9.79</td><td>8.22</td></tr><tr><td colspan="10"><em>test3plus4</em></td></tr><tr><td>3.48</td><td>2.42</td><td>0.16</td><td>7.43</td><td>24.56</td><td>3.1</td><td>25.97</td><td>8.7</td><td>10.52</td><td>8.04</td></tr><tr><td colspan="10"><em>test3lessThan4</em></td></tr><tr><td>3.47</td><td>2.41</td><td>0.18</td><td>7.33</td><td>24.84</td><td>3.25</td><td>26.36</td><td>9.34</td><td>10.12</td><td>12.8</td></tr><tr><td colspan="10"><em>test3times4</em></td></tr><tr><td>6.58</td><td>4.59</td><td>0.4</td><td>8.38</td><td>25.43</td><td>3.98</td><td>28.83</td><td>10.22</td><td>7.41</td><td>10.8</td></tr><tr><td colspan="10"><em>test3div4</em></td></tr><tr><td>4.22</td><td>3.08</td><td>0.57</td><td>1.25</td><td>2.67</td><td>0.48</td><td>3.45</td><td>1.29</td><td>0.75</td><td>1.43</td></tr><tr><td colspan="10"><em>test16bitArith</em></td></tr><tr><td>5.55</td><td>5.57</td><td>0.65</td><td>0.88</td><td>11.75</td><td>2.07</td><td>405.6</td><td>133.45</td><td>0.59</td><td>135.7</td></tr><tr><td colspan="10"><em>testLargeIntArith</em></td></tr><tr><td>6.38</td><td>0.65</td><td>0.08</td><td>0.08</td><td>1.17</td><td>0.27</td><td>43.1</td><td>14.31</td><td>0.06</td><td>14.3</td></tr><tr><td colspan="10"><em>testActivationReturn</em></td></tr><tr><td>11.07</td><td>7.39</td><td>1.01</td><td>16.2</td><td>55.38</td><td>8.68</td><td>73.41</td><td>26.38</td><td>16.84</td><td>21.5</td></tr></tbody></table>
<table><caption>Table 9.1 (Cont.)</caption><thead><tr><th>A</th><th>B</th><th>C</th><th>D</th><th>E</th><th>F</th><th>G</th><th>H</th><th>I</th><th>J</th></tr></thead><tbody><tr><td colspan="10">testShortBranch</td></tr><tr><td>2.04</td><td>1.43</td><td>0.12</td><td>6.65</td><td>21.6</td><td>2.63</td><td>13.82</td><td>7.35</td><td>6.14</td><td>6.74</td></tr><tr><td colspan="10">testWhileLoop</td></tr><tr><td>7.04</td><td>4.92</td><td>0.44</td><td>16.3</td><td>57.43</td><td>7.33</td><td>64.95</td><td>18.77</td><td>12.45</td><td>21.4</td></tr><tr><td colspan="10">testArrayAt</td></tr><tr><td>2.48</td><td>1.7</td><td>0.19</td><td>4.03</td><td>30.71</td><td>1.65</td><td>13.74</td><td>5.73</td><td>2.51</td><td>5.85</td></tr><tr><td colspan="10">testArrayAtPut</td></tr><tr><td>2.93</td><td>2.02</td><td>0.22</td><td>4.63</td><td>32.12</td><td>2.13</td><td>16.1</td><td>6.71</td><td>3.08</td><td>6.94</td></tr><tr><td colspan="10">testStringAt</td></tr><tr><td>2.45</td><td>1.69</td><td>0.19</td><td>4.0</td><td>11.91</td><td>1.6</td><td>14.63</td><td>5.61</td><td>2.65</td><td>4.72</td></tr><tr><td colspan="10">testStringAtPut</td></tr><tr><td>3.16</td><td>2.2</td><td>0.23</td><td>4.92</td><td>14.44</td><td>1.92</td><td>16.95</td><td>6.23</td><td>2.8</td><td>5.01</td></tr><tr><td colspan="10">testSize</td></tr><tr><td>1.79</td><td>1.23</td><td>0.15</td><td>3.03</td><td>8.52</td><td>1.45</td><td>11.14</td><td>4.76</td><td>2.15</td><td>4.59</td></tr><tr><td colspan="10">testPointCreation</td></tr><tr><td>1.66</td><td>1.17</td><td>0.37</td><td>1.67</td><td>5.52</td><td>1.4</td><td>6.29</td><td>4.3</td><td>1.28</td><td>3.37</td></tr><tr><td colspan="10">testStreamNext</td></tr><tr><td>10.15</td><td>7.17</td><td>0.91</td><td>4.97</td><td>15.67</td><td>6.5</td><td>21.98</td><td>7.2</td><td>4.01</td><td>8.18</td></tr><tr><td colspan="10">testStreamNextPut</td></tr><tr><td>12.32</td><td>8.77</td><td>1.05</td><td>5.88</td><td>28.71</td><td>7.58</td><td>26.26</td><td>9.33</td><td>5.18</td><td>9.84</td></tr><tr><td colspan="10">testEQ</td></tr><tr><td>5.71</td><td>3.93</td><td>0.37</td><td>6.75</td><td>28.76</td><td>3.15</td><td>29.51</td><td>13.71</td><td>7.13</td><td>12.2</td></tr><tr><td colspan="10">testClass</td></tr><tr><td>1.62</td><td>1.11</td><td>0.13</td><td>0.9</td><td>4.79</td><td>0.5</td><td>3.95</td><td>2.23</td><td>1.05</td><td>1.56</td></tr><tr><td colspan="10">testBlockCopy</td></tr><tr><td>15.59</td><td>10.8</td><td>0.53</td><td>13.7</td><td>22.54</td><td>4.18</td><td>20.85</td><td>16.57</td><td>13.09</td><td>11.2</td></tr><tr><td colspan="10">testValue</td></tr><tr><td>4.25</td><td>2.81</td><td>0.25</td><td>4.08</td><td>23.81</td><td>3.4</td><td>28.51</td><td>8.85</td><td>6.91</td><td>8.21</td></tr><tr><td colspan="10">testCreation</td></tr><tr><td>4.03</td><td>2.78</td><td>0.35</td><td>6.65</td><td>32.58</td><td>3.82</td><td>16.37</td><td>11.04</td><td>4.13</td><td>7.33</td></tr><tr><td colspan="10">testPointX</td></tr><tr><td>4.84</td><td>3.38</td><td>0.35</td><td>11.78</td><td>35.93</td><td>5.03</td><td>35.43</td><td>17.49</td><td>12.24</td><td>13.2</td></tr><tr><td colspan="10">testLoadThisContext</td></tr><tr><td>6.04</td><td>4.19</td><td>0.4</td><td>5.9</td><td>29.76</td><td>3.05</td><td>33.72</td><td>14.21</td><td>5.36</td><td>10.6</td></tr><tr><td colspan="10">testBasicAt</td></tr><tr><td>2.31</td><td>1.58</td><td>0.19</td><td>3.32</td><td>19.96</td><td>1.62</td><td>11.24</td><td>5.76</td><td>2.65</td><td>6.46</td></tr><tr><td colspan="10">testBasicAtPut</td></tr><tr><td>2.79</td><td>1.91</td><td>0.22</td><td>3.85</td><td>31.89</td><td>2.15</td><td>13.91</td><td>6.44</td><td>2.76</td><td>6.63</td></tr><tr><td colspan="10">testPerform</td></tr><tr><td>2.02</td><td>1.39</td><td>0.3</td><td>6.12</td><td>29.5</td><td>2.25</td><td>18.24</td><td>7.43</td><td>31.28</td><td>7.0</td></tr></tbody></table>
<table><caption>Table 9.1 (Cont.)</caption><thead><tr><th>A</th><th>B</th><th>C</th><th>D</th><th>E</th><th>F</th><th>G</th><th>H</th><th>I</th><th>J</th></tr></thead><tbody><tr><td colspan="10"><em>testStringReplace</em></td></tr><tr><td>0.88</td><td>0.61</td><td>1.06</td><td>0.17</td><td>2.24</td><td>0.183</td><td>0.62</td><td>0.38</td><td>19.38</td><td>0.23</td></tr><tr><td colspan="10"><em>testAsFloat</em></td></tr><tr><td>2.4</td><td>1.68</td><td>0.26</td><td>0.62</td><td>25.13</td><td>1.12</td><td>1.47</td><td>1.44</td><td>0.26</td><td>0.71</td></tr><tr><td colspan="10"><em>testFloatingPointAddition</em></td></tr><tr><td>2.81</td><td>1.96</td><td>0.25</td><td>0.73</td><td>18.86</td><td>0.88</td><td>2.57</td><td>1.63</td><td>0.38</td><td>1.04</td></tr><tr><td colspan="10"><em>testBitBLT</em></td></tr><tr><td>2.32</td><td>1.65</td><td>0.4</td><td>209.05</td><td>33.69</td><td>25.83</td><td>194.87</td><td>5.24</td><td>21.73</td><td>57.4</td></tr><tr><td colspan="10"><em>testTextScanning</em></td></tr><tr><td>1.65</td><td>1.16</td><td>0.32</td><td>21.78</td><td>3.44</td><td>4.0</td><td>7.17</td><td>1.01</td><td>2.2</td><td>2.29</td></tr><tr><td colspan="10"><em>Macro Tests</em></td></tr><tr><td colspan="10"><em>testClassOrganizer</em></td></tr><tr><td>12.3</td><td>8.51</td><td>1.25</td><td>16.03</td><td>80.79</td><td>8.58</td><td>65.02</td><td>24.53</td><td>16.82</td><td>27.4</td></tr><tr><td colspan="10"><em>testPrintDefinition</em></td></tr><tr><td>8.49</td><td>5.58</td><td>0.84</td><td>10.43</td><td>47.37</td><td>6.0</td><td>48.21</td><td>15.61</td><td>11.66</td><td>15.9</td></tr><tr><td colspan="10"><em>testPrintHierarchy</em></td></tr><tr><td>8.28</td><td>5.75</td><td>1.0</td><td>9.82</td><td>44.44</td><td>5.87</td><td>37.69</td><td>14.39</td><td>12.05</td><td>15.5</td></tr><tr><td colspan="10"><em>testAllCallsOn</em></td></tr><tr><td>19.06</td><td>13.2</td><td>1.57</td><td>24.38</td><td>92.45</td><td>10.73</td><td>102.72</td><td>33.95</td><td>21.41</td><td>34.2</td></tr><tr><td colspan="10"><em>testAllImplementors</em></td></tr><tr><td>6.13</td><td>4.3</td><td>0.61</td><td>7.95</td><td>34.33</td><td>4.22</td><td>36.11</td><td>12.33</td><td>8.55</td><td>12.7</td></tr><tr><td colspan="10"><em>testInspect</em></td></tr><tr><td>15.55</td><td>10.6</td><td>1.83</td><td>19.08</td><td>69.23</td><td>10.65</td><td>91.81</td><td>30.09</td><td>19.32</td><td>26.6</td></tr><tr><td colspan="10"><em>testCompiler</em></td></tr><tr><td>19.9</td><td>13.7</td><td>2.17</td><td>27.25</td><td>134.09</td><td>15.15</td><td>127.42</td><td>50.54</td><td>27.11</td><td>58.2</td></tr><tr><td colspan="10"><em>testDeccompiler</em></td></tr><tr><td>12.29</td><td>8.45</td><td>1.34</td><td>17.38</td><td>68.5</td><td>9.8</td><td>73.53</td><td>24.21</td><td>17.4</td><td>25.5</td></tr><tr><td colspan="10"><em>testKeyboardLookAhead</em></td></tr><tr><td>3.37</td><td>2.34</td><td>0.49</td><td>23.08</td><td>13.07</td><td>3.7</td><td>25.13</td><td>5.28</td><td>4.85</td><td>8.99</td></tr><tr><td colspan="10"><em>testKeyboardSingle</em></td></tr><tr><td>10.12</td><td>7.0</td><td>1.47</td><td>116.12</td><td>43.92</td><td>10.95</td><td>76.58</td><td>18.55</td><td>16.27</td><td>42.1</td></tr><tr><td colspan="10"><em>testTextDisplay</em></td></tr><tr><td>9.28</td><td>6.5</td><td>1.2</td><td>41.43</td><td>32.8</td><td>12.92</td><td>47.44</td><td>11.95</td><td>13.88</td><td>23.8</td></tr><tr><td colspan="10"><em>testTextFormatting</em></td></tr><tr><td>8.64</td><td>6.02</td><td>1.11</td><td>9.0</td><td>35.29</td><td>4.87</td><td>83.81</td><td>18.53</td><td>10.57</td><td>11.2</td></tr><tr><td colspan="10"><em>testTextEditing</em></td></tr><tr><td>24.83</td><td>17.3</td><td>4.07</td><td>135.2</td><td>95.23</td><td>28.03</td><td>186.39</td><td>37.1</td><td>37.03</td><td>60.3</td></tr></tbody></table>