<table><caption>Table 9.2 The Benchmarks Normalized to the Average</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>0.772</td><td>0.642</td><td>0.0483</td><td>1.01</td><td>4.77</td><td>0.665</td><td>4.04</td><td>1.83</td><td>1.02</td><td>1.73</td></tr><tr><td colspan="10"><em>testLoadTempNRef</em></td></tr><tr><td>0.801</td><td>0.563</td><td>0.0514</td><td>1.09</td><td>4.8</td><td>0.51</td><td>4.27</td><td>1.95</td><td>1.09</td><td>1.78</td></tr><tr><td colspan="10"><em>testLoadTempRef</em></td></tr><tr><td>0.958</td><td>0.676</td><td>0.0597</td><td>0.873</td><td>4.65</td><td>0.415</td><td>3.98</td><td>2.07</td><td>1.12</td><td>1.66</td></tr><tr><td colspan="10"><em>testLoadQuickConstant</em></td></tr><tr><td>0.74</td><td>0.521</td><td>0.0506</td><td>1.19</td><td>4.68</td><td>0.544</td><td>3.91</td><td>1.99</td><td>1.2</td><td>1.81</td></tr><tr><td colspan="10"><em>testLoadLiteralNRef</em></td></tr><tr><td>0.819</td><td>0.571</td><td>0.0514</td><td>1.11</td><td>4.68</td><td>0.529</td><td>3.53</td><td>1.95</td><td>1.1</td><td>2.0</td></tr><tr><td colspan="10"><em>testLoadLiteralIndirect</em></td></tr><tr><td>0.989</td><td>0.683</td><td>0.0661</td><td>0.891</td><td>3.91</td><td>0.529</td><td>3.31</td><td>2.08</td><td>1.1</td><td>1.61</td></tr><tr><td colspan="10"><em>testPopStoreInstVar</em></td></tr><tr><td>0.581</td><td>0.523</td><td>0.0335</td><td>1.26</td><td>5.16</td><td>1.05</td><td>3.84</td><td>1.49</td><td>1.95</td><td>1.29</td></tr><tr><td colspan="10"><em>testPopStoreTemp</em></td></tr><tr><td>0.734</td><td>0.515</td><td>0.0369</td><td>0.957</td><td>5.68</td><td>0.508</td><td>4.69</td><td>1.64</td><td>2.01</td><td>1.69</td></tr><tr><td colspan="10"><em>test3plus4</em></td></tr><tr><td>0.669</td><td>0.465</td><td>0.0307</td><td>1.43</td><td>4.72</td><td>0.596</td><td>4.99</td><td>1.67</td><td>2.02</td><td>1.54</td></tr><tr><td colspan="10"><em>test3lessThan4</em></td></tr><tr><td>0.624</td><td>0.433</td><td>0.0324</td><td>1.32</td><td>4.46</td><td>0.584</td><td>4.74</td><td>1.68</td><td>1.82</td><td>2.3</td></tr><tr><td colspan="10"><em>test3times4</em></td></tr><tr><td>0.955</td><td>0.666</td><td>0.058</td><td>1.22</td><td>3.69</td><td>0.578</td><td>4.18</td><td>1.48</td><td>1.08</td><td>1.57</td></tr><tr><td colspan="10"><em>test3div4</em></td></tr><tr><td>2.82</td><td>2.06</td><td>0.381</td><td>0.835</td><td>1.78</td><td>0.321</td><td>2.3</td><td>0.862</td><td>0.501</td><td>0.955</td></tr><tr><td colspan="10"><em>test16bitArith</em></td></tr><tr><td>0.657</td><td>0.659</td><td>0.0769</td><td>0.104</td><td>1.39</td><td>0.245</td><td>48.0</td><td>15.8</td><td>0.0698</td><td>16.1</td></tr><tr><td colspan="10"><em>testLargeIntArith</em></td></tr><tr><td>5.5</td><td>0.56</td><td>0.0689</td><td>0.0689</td><td>1.01</td><td>0.233</td><td>37.1</td><td>12.3</td><td>0.0517</td><td>12.3</td></tr><tr><td colspan="10"><em>testActivationReturn</em></td></tr><tr><td>0.756</td><td>0.505</td><td>0.069</td><td>1.11</td><td>3.78</td><td>0.593</td><td>5.02</td><td>1.8</td><td>1.15</td><td>1.47</td></tr><tr><td colspan="10"><em>testShortBranch</em></td></tr><tr><td>0.543</td><td>0.381</td><td>0.032</td><td>1.77</td><td>5.75</td><td>0.701</td><td>3.68</td><td>1.96</td><td>1.64</td><td>1.8</td></tr><tr><td colspan="10"><em>testWhileLoop</em></td></tr><tr><td>0.623</td><td>0.435</td><td>0.0389</td><td>1.44</td><td>5.08</td><td>0.649</td><td>5.75</td><td>1.66</td><td>1.1</td><td>1.89</td></tr><tr><td colspan="10"><em>testArrayAt</em></td></tr><tr><td>0.736</td><td>0.504</td><td>0.0564</td><td>1.2</td><td>9.11</td><td>0.49</td><td>4.08</td><td>1.7</td><td>0.745</td><td>1.74</td></tr><tr><td colspan="10"><em>testArrayAtPut</em></td></tr><tr><td>0.74</td><td>0.51</td><td>0.0555</td><td>1.17</td><td>8.11</td><td>0.538</td><td>4.06</td><td>1.69</td><td>0.777</td><td>1.75</td></tr><tr><td colspan="10"><em>testStringAt</em></td></tr><tr><td>0.813</td><td>0.561</td><td>0.0631</td><td>1.33</td><td>3.95</td><td>0.531</td><td>4.86</td><td>1.86</td><td>0.88</td><td>1.57</td></tr></tbody></table>
<table><caption>Table 9.2 (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">testStringAtPut</td></tr><tr><td>0.889</td><td>0.619</td><td>0.0647</td><td>1.38</td><td>4.06</td><td>0.54</td><td>4.77</td><td>1.75</td><td>0.787</td><td>1.41</td></tr><tr><td colspan="10">testSize</td></tr><tr><td>0.744</td><td>0.511</td><td>0.0624</td><td>1.26</td><td>3.54</td><td>0.603</td><td>4.63</td><td>1.98</td><td>0.894</td><td>1.91</td></tr><tr><td colspan="10">testPointCreation</td></tr><tr><td>0.825</td><td>0.582</td><td>0.184</td><td>0.83</td><td>2.74</td><td>0.696</td><td>3.13</td><td>2.14</td><td>0.636</td><td>1.68</td></tr><tr><td colspan="10">testStreamNext</td></tr><tr><td>1.52</td><td>1.08</td><td>0.136</td><td>0.745</td><td>2.35</td><td>0.975</td><td>3.3</td><td>1.08</td><td>0.601</td><td>1.23</td></tr><tr><td colspan="10">testStreamNextPut</td></tr><tr><td>1.46</td><td>1.04</td><td>0.125</td><td>0.697</td><td>3.41</td><td>0.899</td><td>3.11</td><td>1.11</td><td>0.614</td><td>1.17</td></tr><tr><td colspan="10">testEQ</td></tr><tr><td>0.854</td><td>0.588</td><td>0.0553</td><td>1.01</td><td>4.3</td><td>0.471</td><td>4.41</td><td>2.05</td><td>1.07</td><td>1.82</td></tr><tr><td colspan="10">testClass</td></tr><tr><td>1.33</td><td>0.91</td><td>0.107</td><td>0.738</td><td>3.93</td><td>0.41</td><td>3.24</td><td>1.83</td><td>0.861</td><td>1.28</td></tr><tr><td colspan="10">testBlockCopy</td></tr><tr><td>1.65</td><td>1.14</td><td>0.0559</td><td>1.45</td><td>2.38</td><td>0.441</td><td>2.2</td><td>1.75</td><td>1.38</td><td>1.18</td></tr><tr><td colspan="10">testValue</td></tr><tr><td>0.819</td><td>0.542</td><td>0.0482</td><td>0.786</td><td>4.59</td><td>0.655</td><td>5.5</td><td>1.71</td><td>1.33</td><td>1.58</td></tr><tr><td colspan="10">testCreation</td></tr><tr><td>0.759</td><td>0.524</td><td>0.0659</td><td>1.25</td><td>6.14</td><td>0.72</td><td>3.08</td><td>2.08</td><td>0.778</td><td>1.38</td></tr><tr><td colspan="10">testPointX</td></tr><tr><td>0.597</td><td>0.417</td><td>0.0432</td><td>1.45</td><td>4.43</td><td>0.621</td><td>4.37</td><td>2.16</td><td>1.51</td><td>1.63</td></tr><tr><td colspan="10">testLoadThisContext</td></tr><tr><td>0.921</td><td>0.639</td><td>0.061</td><td>0.899</td><td>4.54</td><td>0.465</td><td>5.14</td><td>2.17</td><td>0.817</td><td>1.62</td></tr><tr><td colspan="10">testBasicAt</td></tr><tr><td>0.745</td><td>0.509</td><td>0.0612</td><td>1.07</td><td>6.43</td><td>0.522</td><td>3.62</td><td>1.86</td><td>0.854</td><td>2.08</td></tr><tr><td colspan="10">testBasicAtPut</td></tr><tr><td>0.75</td><td>0.513</td><td>0.0591</td><td>1.03</td><td>8.57</td><td>0.578</td><td>3.74</td><td>1.73</td><td>0.742</td><td>1.78</td></tr><tr><td colspan="10">testPerform</td></tr><tr><td>0.402</td><td>0.277</td><td>0.0598</td><td>1.22</td><td>5.88</td><td>0.448</td><td>3.63</td><td>1.48</td><td>6.23</td><td>1.39</td></tr><tr><td colspan="10">testStringReplace</td></tr><tr><td>1.21</td><td>0.838</td><td>1.46</td><td>0.234</td><td>3.08</td><td>0.251</td><td>0.852</td><td>0.522</td><td>26.6</td><td>0.316</td></tr><tr><td colspan="10">testAsFloat</td></tr><tr><td>1.97</td><td>1.38</td><td>0.214</td><td>0.509</td><td>20.6</td><td>0.92</td><td>1.21</td><td>1.18</td><td>0.214</td><td>0.583</td></tr><tr><td colspan="10">testFloatingPointAddition</td></tr><tr><td>2.02</td><td>1.41</td><td>0.179</td><td>0.524</td><td>13.5</td><td>0.631</td><td>1.84</td><td>1.17</td><td>0.273</td><td>0.746</td></tr><tr><td colspan="10">testBitBLT</td></tr><tr><td>0.162</td><td>0.115</td><td>0.028</td><td>14.6</td><td>2.36</td><td>1.81</td><td>13.6</td><td>0.367</td><td>1.52</td><td>4.02</td></tr><tr><td colspan="10">testTextScanning</td></tr><tr><td>0.684</td><td>0.481</td><td>0.133</td><td>9.03</td><td>1.43</td><td>1.66</td><td>2.97</td><td>0.419</td><td>0.912</td><td>0.949</td></tr></tbody></table>
<table><caption>Table 9.2 (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>Macro Tests</em></td></tr><tr><td colspan="10"><em>testClassOrganizer</em></td></tr><tr><td>0.771</td><td>0.533</td><td>0.0783</td><td>1.0</td><td>5.06</td><td>0.538</td><td>4.08</td><td>1.54</td><td>1.05</td><td>1.72</td></tr><tr><td colspan="10"><em>testPrintDefinition</em></td></tr><tr><td>0.808</td><td>0.531</td><td>0.0799</td><td>0.992</td><td>4.51</td><td>0.571</td><td>4.59</td><td>1.49</td><td>1.11</td><td>1.51</td></tr><tr><td colspan="10"><em>testPrintHierarchy</em></td></tr><tr><td>0.811</td><td>0.563</td><td>0.0979</td><td>0.961</td><td>4.35</td><td>0.575</td><td>3.69</td><td>1.41</td><td>1.18</td><td>1.52</td></tr><tr><td colspan="10"><em>testAllCallsOn</em></td></tr><tr><td>0.874</td><td>0.605</td><td>0.072</td><td>1.12</td><td>4.24</td><td>0.492</td><td>4.71</td><td>1.56</td><td>0.981</td><td>1.57</td></tr><tr><td colspan="10"><em>testAllImplementors</em></td></tr><tr><td>0.78</td><td>0.547</td><td>0.0776</td><td>1.01</td><td>4.37</td><td>0.537</td><td>4.6</td><td>1.57</td><td>1.09</td><td>1.62</td></tr><tr><td colspan="10"><em>testInspect</em></td></tr><tr><td>0.82</td><td>0.559</td><td>0.0965</td><td>1.01</td><td>3.65</td><td>0.562</td><td>4.84</td><td>1.59</td><td>1.02</td><td>1.4</td></tr><tr><td colspan="10"><em>testCompiler</em></td></tr><tr><td>0.702</td><td>0.484</td><td>0.0766</td><td>0.962</td><td>4.73</td><td>0.535</td><td>4.5</td><td>1.78</td><td>0.957</td><td>2.05</td></tr><tr><td colspan="10"><em>testDecompiler</em></td></tr><tr><td>0.756</td><td>0.52</td><td>0.0825</td><td>1.07</td><td>4.22</td><td>0.603</td><td>4.53</td><td>1.49</td><td>1.07</td><td>1.57</td></tr><tr><td colspan="10"><em>testKeyboardLookAhead</em></td></tr><tr><td>0.614</td><td>0.426</td><td>0.0892</td><td>4.2</td><td>2.38</td><td>0.674</td><td>4.58</td><td>0.961</td><td>0.883</td><td>1.64</td></tr><tr><td colspan="10"><em>testKeyboardSingle</em></td></tr><tr><td>0.537</td><td>0.371</td><td>0.078</td><td>6.16</td><td>2.33</td><td>0.581</td><td>4.06</td><td>0.984</td><td>0.863</td><td>2.23</td></tr><tr><td colspan="10"><em>testTextDisplay</em></td></tr><tr><td>0.676</td><td>0.473</td><td>0.0874</td><td>3.02</td><td>2.39</td><td>0.941</td><td>3.46</td><td>0.87</td><td>1.01</td><td>1.73</td></tr><tr><td colspan="10"><em>testTextFormatting</em></td></tr><tr><td>0.822</td><td>0.573</td><td>0.106</td><td>0.856</td><td>3.36</td><td>0.463</td><td>7.98</td><td>1.76</td><td>1.01</td><td>1.07</td></tr><tr><td colspan="10"><em>testTextEditing</em></td></tr><tr><td>0.625</td><td>0.436</td><td>0.103</td><td>3.4</td><td>2.4</td><td>0.706</td><td>4.69</td><td>0.934</td><td>0.933</td><td>1.52</td></tr></tbody></table>

Here is a brief description of each implementation, with references to the related chapters in this book.

A. Xerox (see Chapter 7). Implementation written in microcode and machine code running on a 40Mhz Xerox Dolphin.

B. Xerox (see Chapter 7). Implementation written in microcode and machine code running on a 44.5Mhz Xerox Dolphin with special display alignment.

C. Xerox (see Chapter 7). Implementation written in microcode and machine code running on a Xerox Dorado.

D. U.C. Berkeley (see Chapter 11). Implementation written in C run-
ning on a DEC VAX-11/780, under 4.1BSD UNIX. Uses AED-512 over a RS-232 link for the display. Uses 32-bit Oops.

E. Tektronix (see Chapter 5). Implementation written in Pascal and assembly language running on an 8Mhz MC68000.

F. Tektronix (see Chapter 4). Implementation written in assembly language running on a 10Mhz MC68000.

G. Hewlett-Packard (see Chapter 6). Implementation written in high-level language (C) running on a DEC VAX-11/780 with 4 megabyte main memory running 4.1BSD UNIX. Portable among UNIX systems. "By the book" implementation; limited optimization. 16-bit and `LARGEINTEGER` arithmetic performed with Smalltalk-80 code (no primitives); Float arithmetic using VAX format (not IEEE); some additional class and argument checking in primitives; standard reference-count management with 8-bit counts (contexts are reference counted); recursive marking garbage collector.

H. Apple (see Chapter 10). Implementation written in assembly language running on a 5Mhz MC68000. Synchronization of CPU memory accesses and display memory accesses reduces the effective processor speed to about 4.5Mhz.

I. Digital Equipment Corp. (see Chapter 8). Implementation written in assembly language, running on a DEC VAX-11/780 with 4 megabyte main memory, under VMS. `SmallInteger` and `Float` primitives implemented; `LARGEInteger` primitives not implemented. All primitives do class and argument checking. Incremental compacting garbage collector.

J. Digital Equipment Corp. (see Chapter 8). Implementation written in `Bliss-32`, running on a DEC VAX-11/780 with 4 megabyte main memory, under VMS. "By the book" implementation using reference counting; moderately optimized. All arithmetic primitives implemented. All primitives do class and argument checking.

One can see from the above data that some micro-benchmarks matter very little to overall performance. Performance on the division and `LARGEInteger` benchmarks for example, does not seem to be a very good predictor of overall performance. As might be expected, performance on the `String replace` benchmark correlates strongly with performance on the text editing macro-benchmark, but not for example, with compiler performance.

Another observation is that performance on the micro-benchmarks varies much more widely than performance on the macro-benchmarks. While this was to be expected, since the macro-benchmarks test perfor-
mance over a much broader range of activities than do the micro-benchmarks (thus smoothing out peaks and valleys), I was surprised at the magnitude of this difference between the smoothness of the macro-benchmarks and the variations among the micro-benchmarks. (For the Dolphin implementation, the standard deviation for the micro-benchmark results is 0.86 while the standard deviation for the macro-benchmarks is only 0.087.) This leads me to the hypothesis that, for any reasonably efficient interpreter, virtually all macro-level performance is determined by a very few micro-level factors. This hypothesis is supported by the observation that while the Dorado performance on most of the micro-benchmarks is on the order of 15-20 times as fast as the Dolphin, performance on the macro-benchmarks is only approximately 10 times as fast. This appears to be due primarily to the relative speeds of activation and return in the two implementations. The activation/return benchmark correlates much more strongly with macro-level performance than do most other micro-benchmarks. So it appears that general system behavior is most strongly influenced by the speed of method activation and return. (This may be less true of machines with special stack hardware or other special hardware that would affect Smalltalk-80 bytecode performance in a non-uniform way.)

From an analytic point of view, this hypothesis, that (within reasonable bounds) overall system performance is most strongly determined by the speed of method activation and return, can be supported by two other general facts: method activation and return are by far the most expensive atomic operations the interpreter must perform; and a fairly high proportion of the byte codes encountered by a running interpreter cause activation or return. Of course, neither of these "facts" is universally true. The String replacement and BitBlt primitives can be much more expensive than an activation, so code that is very rich in these, such as text editing, can be expected to perform more like the relevant micro-benchmarks. Also, highly optimized code (such as that invoked by Smalltalk allCallsOn:) will "open code" important message calls rather than incurring the activation and return overhead and can therefore be expected to perform closer to the level predicted by the other benchmarks.

Exceptions to the general rule that macro-behavior is best predicted by the testActivationReturn benchmark are illustrated by the performance of implementation D on the testTextEditing and testKeyboardSingle macro-benchmarks. Most of D's normalized micro-benchmark scores fall in the range 0.8 to 1.6, but the scores for the display-intensive micro-benchmarks testBitBLT and testTextScanning are much worse. The display configuration that D uses is much slower than other implementations and accounts for these low scores. While performance on most macro-benchmarks is very near 1.0, as predicted by the majority of the micro-benchmarks, the scores for testTextEditing and
testKeyboardSingle are much worse (3.4 and 6.16) due to the fact that these are display-intensive macro-benchmarks. It is also worth noting that these particular macro-benchmarks seem to correlate strongly with user satisfaction. While D appears to be computationally acceptable in other respects, its users are generally not satisfied with its responsiveness.

**Concluding Summary**

Discoveries and warnings have been sprinkled throughout this paper; here is my chance to put them in one place.

Many of the micro-benchmarks contain operations that I had not meant to test, but that I included simply to satisfy the demands of the compiler or stack management discipline. These operations, although fairly fast, may be slower than the operations being tested and this may distort somewhat the meaningfulness of these benchmarks.

In writing your own benchmarks, you must be very careful to make sure that the operations you are trying to time are not swamped by other computation. For micro-benchmarks, it is good to look at the compiled code to see whether you have created the test you thought you had.

Most of the micro-benchmarks are not very good predictors of overall system performance. The speed of certain specialized applications may correlate well with some specific micro-benchmarks, such as BitBlt or String replacement, but it appears from our data that the efficiency of activation and return is the overriding determinant of system performance.

Finally, let me stress again that the data I presented in the analysis section represent early or interim results, designed for very different purposes, written in different level languages, and running on vastly different hardware. None of these are final, and none indicate the expected performance of any future systems. We thank the implementors for their courage in allowing us to publish such preliminary measurements.
<figure><img src="image_16.png" /></figure>
# An MC68000-Based Smalltalk-80 System

Richard Meyers

David Casseres

Apple Computer Inc.

Cupertino, California

## Introduction

This paper describes some preliminary results of an MC68000-based implementation of the Smalltalk-80 system. The implementation was conducted as a research project by Apple Computer Inc. Our purpose in presenting this data is to provide to other implementors some of the information we wish we had known when we first set out to implement Smalltalk.

## History

Apple Computer began its Smalltalk-80 research project in early October 1980. The project has been staffed by one engineer (Rick Meyers) and, for about half of the last 18 months, by a technical writer (David Casseres). Apple has consistently viewed Smalltalk as a research effort, and has afforded the project the freedom from schedules and from marketing considerations that allows research efforts to thrive.

Our Smalltalk-80 implementation has been running since April 1981 on a series of experimental Motorola MC68000-based computer systems. The Smalltalk-80 virtual machine described in this paper is a straightforward translation of the Xerox virtual machine specification to 68000 assembly language. The bytecode interpreter, object memory system,
and primitive routines were written slowly and carefully by a single engineer. Other engineers contributed the BitBlt (screen display), text scanning (textual display), and floating-point arithmetic routines. To date, only about three weeks of effort have been devoted specifically to optimizing the virtual machine, and the only major optimization is the message lookup cache described later in the paper.

This paper reports on work in progress. The measurements reported were first made in June 1981 and were repeated in June and July 1982.

## Memory Layout

The measurements were made on a Smalltalk-80 system configured to use about 793K bytes of memory. Estimates of the sizes of major system components are shown in Table 10.1. The virtual machine size includes BitBlt, text scanning, and the floating-point routines. The data does not include the program development system used to host Smalltalk, the file system and the device drivers, the system debugger, or the data areas used by program analysis tools.

<table><caption>Table 10.1 Memory Layout</caption><thead><tr><td>Area</td><td>Bytes</td></tr></thead><tbody><tr><td>virtual machine data</td><td>4K</td></tr><tr><td>virtual machine code</td><td>21K</td></tr><tr><td>display memory</td><td>32K</td></tr><tr><td>object table (24K objects)</td><td>96K</td></tr><tr><td>15K system-supplied objects (60K)</td><td></td></tr><tr><td>9K user objects (36K)</td><td></td></tr><tr><td>heap storage (10 heaps, 64K/heap)</td><td>640K</td></tr><tr><td>system supplied objects (407K)</td><td></td></tr><tr><td>user objects (233K)</td><td></td></tr><tr><td>Total</td><td>793K</td></tr></tbody></table>

## Virtual Machine Structure and Size

At the time of this writing, our Smalltalk-80 virtual machine consists of 21,088 bytes of Motorola 68000 assembly-language code. The major system components have the following functions:

* Initialization and Utilities: Global initialization, memory image input, I/O operations, utilities
* Fetch Loop: Bytecode fetch and dispatch

* Bytecode and Primitive Tables: Addresses of bytecode and primitive routines

* Bytecode Interpreter: Bytecode interpretation, except the major activities such as send, return, and memory allocation

* Send/Return: Send and superclass send, primitive dispatch, context switch, argument transfer and return

* Multiprocessing: Process switch, semaphores, keyboard and time events

* Memory Management: Memory allocation, reference counting, heap compaction, and garbage collection

* Primitives: All primitives except for floating-point package, BitBlt and text scanning

* BitBlt: Class BitBlt, method copyBits

* Text Scanning: Class TextScanner, method scanCharactersFrom:to:-last:in:rightX:stopConditions:displaying:

* Analysis: Reference-count validation, statistics gathering and reporting

Table 10.2 shows a breakdown of the virtual machine into its major components. The file system and device drivers are excluded from these measurements. The table also indicates time spent in each component of the virtual machine.

<table><caption>Table 10.2 Virtual Machine Structure and Size</caption><thead><tr><td>Function</td><td>Bytes</td><td>Size</td><td>% Time</td></tr></thead><tbody><tr><td>initialization & utilities</td><td>2,274</td><td>10.8%</td><td>1.9%</td></tr><tr><td>fetch loop</td><td>18</td><td>0.1%</td><td>10.2%</td></tr><tr><td>bytecode & primitive tables</td><td>802</td><td>3.8%</td><td>--</td></tr><tr><td>bytecode interpreter</td><td>1,476</td><td>7.0%</td><td>16.0%</td></tr><tr><td>send & return</td><td>1,132</td><td>5.4%</td><td>39.2%</td></tr><tr><td>multiprocessing</td><td>1,338</td><td>6.3%</td><td>--</td></tr><tr><td>memory management</td><td>1,650</td><td>7.8%</td><td>22.6%</td></tr><tr><td>primitives (except those below)</td><td>5,128</td><td>24.3%</td><td>8.8%</td></tr><tr><td>floating-point</td><td>3,162</td><td>15.0%</td><td>0.0%</td></tr><tr><td>BitBlt</td><td>1,956</td><td>9.3%</td><td>0.5%</td></tr><tr><td>text scanning</td><td>1,258</td><td>6.0%</td><td>0.7%</td></tr><tr><td>analysis</td><td>894</td><td>4.2%</td><td>--</td></tr></tbody></table>
## Virtual Machine Code Utilization

A sampling technique was used to measure the approximate percentage of the total time spent executing each instruction of the virtual machine. The virtual machine program counter was sampled every 10 milliseconds to construct a histogram of relative utilization for each possible program counter value. It should be noted that this technique fails to measure periodic activities which are based on interrupts, such as multiprocessing activity.

The Smalltalk-80 memory image supplied by Xerox Palo Alto Research Center contained a set of 35 benchmarks, included as methods in class Benchmark. The benchmarks test a number of individual bytecodes, common primitive operations, and several "macro" operations such as compilation and text formatting. The results of running Benchmark testStandardTests are reported in Chapter 9. The results reported in this section were gathered during execution of the Benchmark "macro" operations

Benchmark new testCompiler

Benchmark new testDecompile

Benchmark new testInspect

Benchmark new testTextEditing

Benchmark new testTextFormatting

Each of these tests was run five times in a period of just over 28 minutes; 170,922 samples were taken, one every 10 milliseconds. The time spent in each of the major system components is summarized in Table 10.2 above and in Fig. 10.1.

Several sections of the virtual machine deserve special attention. The bytecode fetch and dispatch, which usually requires five instructions, accounts for 10.2% of the total execution time. The relatively small (1132 bytes, 5.4% of total) send/return component of the system accounts for 39.2% of the execution time. Prior to implementation of a method lookup cache, this percentage was 52.5%.

The countDownOthers routine, which recursively decrements the reference counts for the fields of deallocated objects, requires 11.8% of the execution time. This fact, and the time spent in countDown, suggests that implementation strategies which avoid reference counting of contexts may yield substantial performance improvements.

Overall patterns of utilization indicate the value of *time* optimization for send/return and the memory management functions, and *space* optimization for most of the primitive operations, especially the floating-point routines. Fig. 10.1 shows the space and time used by each major system component.
<figure><img src="image_17.png" /><figcaption>Figure 10.1</figcaption></figure>
## Bytecode and Primitive Frequencies

The Smalltalk-80 virtual machine implements 256 individual bytecodes (instructions) and approximately 100 primitive operations. In designing and optimizing an implementation, it is vital to know which bytecodes and primitives occur most frequently, and which are rarely used.

<table><thead><tr><th></th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>A</th><th>B</th><th>C</th><th>D</th><th>E</th><th>F</th></tr></thead><tbody><tr><td>0</td><td colspan="20">Push Instance Variable (0 to F)</td></tr><tr><td>1</td><td colspan="20">Push Temporary Variable (0 to F)</td></tr><tr><td>2</td><td colspan="20">Push Literal Constant (0 to 1F)</td></tr><tr><td>3</td><td colspan="20">Push Literal Variable (0 to 1F)</td></tr><tr><td>4</td><td colspan="20"></td></tr><tr><td>5</td><td colspan="20"></td></tr><tr><td>6</td><td colspan="8">Pop Instance Variable (0 to 7)</td><td colspan="12">Pop Temporary Variable (0 to 7)</td></tr><tr><td>7</td><td colspan="20">Push</td></tr><tr><td>8</td><td>self</td><td>true</td><td>false</td><td>nil</td><td>-1</td><td>0</td><td>1</td><td>2</td><td colspan="2">return from message</td><td>self</td><td>true</td><td>false</td><td>nil</td><td>ret. msg.</td><td>TOS block</td><td></td></tr><tr><td>9</td><td>Push</td><td>store</td><td>pop</td><td>send</td><td>send</td><td>send</td><td>send</td><td>pop</td><td>dup.</td><td>push</td><td>c'txt</td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>9</td><td colspan="8">Jump (1 to 8)</td><td colspan="8">Jump on False (1 to 8)</td></tr><tr><td>A</td><td colspan="8">Jump (iii-4)*256+<i>iiiiiii</i></td><td colspan="4">Jump on True</td><td colspan="4">Jump on False</td></tr><tr><td>B</td><td>+</td><td>-</td><td>&lt;</td><td>&gt;</td><td>&lt;=</td><td>&gt;=</td><td>=</td><td>~=</td><td>*</td><td>/</td><td>\</td><td>@</td><td>bit Shift:</td><td>//</td><td>bit And:</td><td>bit Or:</td></tr><tr><td>C</td><td colspan="8">Send Special Selector</td><td>=</td><td>class</td><td>block Copy:</td><td>value</td><td>value:</td><td colspan="4">Send Special Selector</td></tr><tr><td>D</td><td colspan="8">Send Literal Selector (0 to F) with No Arguments</td><td colspan="8"></td></tr><tr><td>E</td><td colspan="8">Send Literal Selector (0 to F) with 1 Argument</td><td colspan="8"></td></tr><tr><td>F</td><td colspan="8">Send Literal Selector (0 to F) with 2 Arguments</td><td colspan="8"></td></tr></tbody></table>

### Notes:

To look up a hex bytecode, find the high-order digit on the left and low-order digit at the top.

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

indicates a bytecode that is followed by one extension byte.

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

indicates a bytecode that is followed by two extension bytes.

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

indicates a bytecode that is not used.

<caption>Figure 10.2</caption>
Our implementation was instrumented to tally every bytecode and primitive executed. This instrumentation imposed a time overhead of about 22%, low enough to allow execution of reasonably large methods during analysis.

Bytecode and primitive frequencies are both directly dependent on the methods being executed while data is collected. Two separate measurements are reported here. In the first test we ran each of the Benchmark "macro" operations, listed above. Measurements continued through both the data collection and data reporting phases of the benchmarks. The second test consisted of browsing as rapidly as possible for about two minutes; it demonstrates the degree of variation involved.

Figure 10.2 is a bytecode summary matrix to aid in the interpretation of the bytecode frequency data.

Table 10.3 lists the percentage of total bytecodes executed in each major bytecode category, while executing the "macro" operations. A total of 3,750,200 bytecodes were executed while collecting this data.

<table><caption>Table 10.3 Bytecode Frequencies by Category in Benchmark Macro Tests</caption><thead><tr><td>Hex Code</td><td>Operation</td><td>Percentage</td></tr></thead><tbody><tr><td>00-0F</td><td>push instance variable</td><td>7.3%</td></tr><tr><td>10-1F</td><td>push temporary variable</td><td>19.1%</td></tr><tr><td>20-3F</td><td>push literal constant</td><td>2.3%</td></tr><tr><td>40-5F</td><td>push literal variable</td><td>1.1%</td></tr><tr><td>50-67</td><td>pop instance variable</td><td>1.9%</td></tr><tr><td>68-6F</td><td>pop temporary variable</td><td>3.9%</td></tr><tr><td>70-77</td><td>push self, true, false, nil, -1, 0, 1, 2</td><td>14.4%</td></tr><tr><td>78-7B</td><td>return from message self, true, false, nil</td><td>1.8%</td></tr><tr><td>7C-7D</td><td>return TOS from message/block</td><td>4.7%</td></tr><tr><td>80</td><td>extended push</td><td>1.3%</td></tr><tr><td>81</td><td>extended store</td><td>1.4%</td></tr><tr><td>82</td><td>extended pop</td><td>0.9%</td></tr><tr><td>83</td><td>extended send</td><td>0.6%</td></tr><tr><td>84</td><td>double extended send</td><td>0.0%</td></tr><tr><td>85</td><td>superclass send</td><td>0.2%</td></tr><tr><td>86</td><td>double extended superclass send</td><td>0.0%</td></tr><tr><td>87</td><td>pop stack</td><td>3.7%</td></tr><tr><td>88</td><td>duplicate TOS</td><td>0.1%</td></tr><tr><td>89</td><td>push context</td><td>0.3%</td></tr><tr><td>90-97</td><td>jump (1-8)</td><td>0.2%</td></tr></tbody></table>
<table><caption>Table 10.3 (Cont.)</caption><thead><tr><th>Hex Code</th><th>Operation</th><th>Percentage</th></tr></thead><tbody><tr><td>98-9F</td><td>jump on false (1-8)</td><td>4.8%</td></tr><tr><td>A0-A7</td><td>jump (iii-4)*256+jjjjjjj</td><td>2.1%</td></tr><tr><td>A8-AB</td><td>jump on true ii*256+jjjjjjj</td><td>0.0%</td></tr><tr><td>AC-AF</td><td>jump on false ii*256+jjjjjjj</td><td>2.2%</td></tr><tr><td>B0-BF</td><td>send +, -, &lt;, &gt;, &lt;=, &gt;=, =, ~=, *, /, \, @, bitShift;, //, bitAnd;, bitOr:</td><td>11.2%</td></tr><tr><td>C0-CF</td><td>send special selector, ==, class, blockCopy:, value, value:</td><td>7.1%</td></tr><tr><td>D0-DF</td><td>send literal selector with no arguments</td><td>3.4%</td></tr><tr><td>E0-EF</td><td>send literal selector with 1 argument</td><td>2.5%</td></tr><tr><td>F0-FF</td><td>send literal selector with 2 arguments</td><td>1.4%</td></tr></tbody></table>

In both of the tests, 18 of the 256 bytecodes accounted for over half of the bytecodes executed, as shown in Tables 10.4 and 10.5. Simple push operations (push self, push temporary variable, push 0, push 1) top both lists and account for over 30% of all bytecodes executed.

<table><caption>Table 10.4 Most Frequent Bytecodes in Benchmark Macro Tests</caption><thead><tr><th>Hex Code</th><th>Operation</th><th>Percentage</th></tr></thead><tbody><tr><td>70</td><td>push self</td><td>6.7%</td></tr><tr><td>10</td><td>push temporary variable 0</td><td>6.1%</td></tr><tr><td>11</td><td>push temporary variable 1</td><td>4.6%</td></tr><tr><td>12</td><td>push temporary variable 2</td><td>4.5%</td></tr><tr><td>76</td><td>push 1</td><td>4.4%</td></tr><tr><td>7C</td><td>return TOS from message</td><td>3.9%</td></tr><tr><td>87</td><td>pop stack top</td><td>3.7%</td></tr><tr><td>B0</td><td>send +</td><td>3.7%</td></tr><tr><td>01</td><td>push instance variable 1</td><td>2.4%</td></tr><tr><td>AC</td><td>jump on false (range 0 to 256)</td><td>2.2%</td></tr><tr><td>C0</td><td>send special selector 0</td><td>2.0%</td></tr><tr><td>B6</td><td>send =</td><td>1.9%</td></tr><tr><td>B1</td><td>send -</td><td>1.7%</td></tr><tr><td>A3</td><td>jump (range -256 to -1)</td><td>1.7%</td></tr><tr><td>B4</td><td>send &lt;=</td><td>1.5%</td></tr><tr><td>75</td><td>push 0</td><td>1.4%</td></tr><tr><td>81</td><td>extended store</td><td>1.4%</td></tr><tr><td>78</td><td>return self</td><td>1.4%</td></tr><tr><td></td><td><strong>Total</strong></td><td><strong>55.2%</strong></td></tr></tbody></table>
<table><caption>Table 10.5 Most Frequent Bytecodes in Browsing Test</caption><thead><tr><th>Hex Code</th><th>Operation</th><th>Percentage</th></tr></thead><tbody><tr><td>10</td><td>push temporary variable 0</td><td>6.9%</td></tr><tr><td>70</td><td>push self</td><td>5.4%</td></tr><tr><td>7C</td><td>return TOS from message</td><td>5.4%</td></tr><tr><td>11</td><td>push temporary variable 1</td><td>4.9%</td></tr><tr><td>12</td><td>push temporary variable 2</td><td>3.3%</td></tr><tr><td>B0</td><td>send +</td><td>3.3%</td></tr><tr><td>76</td><td>push 1</td><td>2.9%</td></tr><tr><td>00</td><td>push instance variable 0</td><td>2.4%</td></tr><tr><td>01</td><td>push instance variable 1</td><td>2.4%</td></tr><tr><td>87</td><td>pop stack top</td><td>2.3%</td></tr><tr><td>B1</td><td>send -</td><td>2.2%</td></tr><tr><td>D0</td><td>send literal selector 0 (no arguments)</td><td>2.1%</td></tr><tr><td>80</td><td>extended push</td><td>1.9%</td></tr><tr><td>C0</td><td>send special selector 0</td><td>1.8%</td></tr><tr><td>78</td><td>return self</td><td>1.6%</td></tr><tr><td>75</td><td>push 0</td><td>1.5%</td></tr><tr><td>AC</td><td>jump on false (range 0 to 256)</td><td>1.5%</td></tr><tr><td>82</td><td>extended pop and store</td><td>1.5%</td></tr><tr><td></td><td><strong>Total</strong></td><td><strong>53.3%</strong></td></tr></tbody></table>

Primitive executions were tallied during execution of the Benchmark "macro" operations. Primitive executions resulting from "send special selector" bytecodes and those resulting from normal send operations are included in the tally. Primitive failures are also included. The 20 most frequent primitives are listed in Table 10.6. The top five primitives account for over 50% of all primitive executions, and the top 20 account for almost 95%. As expected, all of the most common primitives are invoked directly from "send special selector" bytecodes.

<table><caption>Table 10.6 Most Frequent Primitives in Benchmark Macro Tests</caption><thead><tr><th>Decimal #</th><th>Class</th><th>Method</th><th>Count</th><th>Percentage</th></tr></thead><tbody><tr><td>1</td><td>SmallInteger</td><td>+</td><td>138,803</td><td>18.2%</td></tr><tr><td>7</td><td>SmallInteger</td><td>=</td><td>73,339</td><td>9.7%</td></tr><tr><td>60</td><td>Object</td><td>at:</td><td>72,429</td><td>9.5%</td></tr><tr><td>2</td><td>SmallInteger</td><td>-</td><td>65,399</td><td>8.5%</td></tr><tr><td>5</td><td>SmallInteger</td><td>&lt;=</td><td>58,746</td><td>7.7%</td></tr><tr><td>110</td><td>Object</td><td>=</td><td>48,784</td><td>6.4%</td></tr></tbody></table>
<table><caption>Table 10.6 (Cont.)</caption><thead><tr><th>Decimal #</th><th>Class</th><th>Method</th><th>Count</th><th>Percentage</th></tr></thead><tbody><tr><td>61</td><td>Object</td><td>at:put:</td><td>38,657</td><td>5.0%</td></tr><tr><td>62</td><td>Object</td><td>size</td><td>36,075</td><td>4.7%</td></tr><tr><td>81</td><td>BlockContext</td><td>value/value:</td><td>35,092</td><td>4.6%</td></tr><tr><td>4</td><td>SmallInteger</td><td>&gt;</td><td>34,170</td><td>4.4%</td></tr><tr><td>63</td><td>String</td><td>at:</td><td>27,256</td><td>3.3%</td></tr><tr><td>66</td><td>ReadStream</td><td>next</td><td>25,259</td><td>3.3%</td></tr><tr><td>6</td><td>SmallInteger</td><td>&gt;=</td><td>13,010</td><td>1.7%</td></tr><tr><td>3</td><td>SmallInteger</td><td>&lt;</td><td>11,724</td><td>1.5%</td></tr><tr><td>80</td><td>ContextPart</td><td>blockCopy:</td><td>9,894</td><td>1.3%</td></tr><tr><td>70</td><td>Behavior</td><td>new</td><td>8,695</td><td>1.1%</td></tr><tr><td>111</td><td>Object</td><td>class</td><td>8,402</td><td>1.1%</td></tr><tr><td>71</td><td>Behavior</td><td>new:</td><td>7,781</td><td>1.0%</td></tr><tr><td>11</td><td>SmallInteger</td><td>\</td><td>6,039</td><td>0.7%</td></tr><tr><td>12</td><td>SmallInteger</td><td>//</td><td>5,594</td><td>0.7%</td></tr><tr><td></td><td>Total</td><td></td><td></td><td>94.4%</td></tr></tbody></table>

## Send Characteristics

Message sends play a key role conceptually in the Smalltalk-80 language, and have a major impact on the performance of Smalltalk-80 implementations. Three categories of bytecodes initiate send operations:

* Integer and common primitive bytecodes

* Special selector bytecodes

* Send and superclass-send bytecodes.

The final action taken as the result of a send can be any of the following:

* Primitive return of self

* Primitive return of an instance variable

* Successful execution of a primitive

* Activation of a CompiledMethod.

Sends involving primitives can either succeed or fail (usually because of improper argument classes). Our interpreter was modified to tally the various attributes of sends. The data in Table 10.7 was collected while executing the Benchmark "macro" operations.
<table><caption>Table 10.7 Analysis of Send Characteristics</caption><thead><tr><th>Bytecode Initiating Send</th><th>Counts</th><th>Percent</th></tr></thead><tbody><tr><td>Integer & common primitive bytecodes</td><td>515,099</td><td>51.9%</td></tr><tr><td>Special selector bytecodes</td><td>173,164</td><td>17.4%</td></tr><tr><td>Send and superclass-send bytecodes</td><td>305,065</td><td>30.7%</td></tr><tr><td><em>Final Action Taken</em></td><td></td><td></td></tr><tr><td>Primitive return of self</td><td>1,673</td><td>0.2%</td></tr><tr><td>Primitive return of an instance variable</td><td>40,585</td><td>4.1%</td></tr><tr><td>Successful execution of a primitive</td><td>733,779</td><td>73.9%</td></tr><tr><td>Activation of a CompiledMethod</td><td>217,291</td><td>21.9%</td></tr><tr><td><em>Primitives</em></td><td></td><td></td></tr><tr><td>Primitive successes</td><td>733,779</td><td>96.8%</td></tr><tr><td>Primitive failures</td><td>23,969</td><td>3.2%</td></tr></tbody></table>

## Number of Arguments

In optimizing the activation code within the virtual machine, it may be helpful to know the distribution of the number of arguments passed by sends. The virtual machine was instrumented to construct the histogram shown in Fig. 10.3. Only sends resulting in activation of a CompiledMethod were considered. The data below is for the Benchmark "macro" operations. Zero-argument and one-argument sends occur with nearly equal frequency, and account for over 80% of all reported messages.

<figure><img src="image_21.png" /><figcaption>Figure 10.3</figcaption></figure>
## Message Lookup Chaining

The message lookup routines begin their search in the class of the receiver. If the message being sent is not in this class, the search continues up the superclass chain until an inherited message is found. Our interpreter was modified to gather statistics on the depth of search required. The method lookup cache was not in use when these statistics were collected. The data in Fig. 10.4 was gathered while executing the "macro" operations in class Benchmark.

About half of all sends are to methods defined in the class of the receiver, requiring 0 depth of search. Searches of depth 1, 2, 3, and 4 occur with roughly equal frequencies of about 7.5% to 15%. Relatively few messages require a search of depth 5 or more, but one search of depth 9 did occur.

<figure><img src="image_22.png" /><figcaption>Figure 10.4</figcaption></figure>

## Performance Measurements

Performance measurements are included here to allow comparisons with other Smalltalk-80 implementations. These measurements were made on a single-user Motorola MC68000-based system with the system clock running at 5 MHz. (A 4-byte register-to-register add takes 1.6 microseconds. A 4-byte move from an absolute memory location to a register takes 3.2 microseconds. CPU memory accesses and display memory accesses are synchronized, slowing the CPU by 10-15%). The measure-
ments are a snapshot of work in progress as of July 1982. The only major optimization in use was a 256-entry message lookup cache. The uninterpreted results of running Benchmark testStandardTests are reported in Chapter 9.

A traditional test of system performance is the number of bytecodes per second the system can execute. Bytecodes vary tremendously in complexity, from simple operations such as pushing a literal zero on the stack or branching to another bytecode to very complex primitive operations such as floating-point divide, string-to-string copy, or BitBlt operations. Therefore, bytecode-per-second measurements are extremely dependent on the methods being executed. We had no trouble collecting measurements ranging from 5000 to about 30,000 bytecodes per second.

Our analysis was done by modifying the virtual machine to count the actual number of bytecodes executed. This introduced an overhead of about 5%, which is compensated for in the final column of Table 10.8. Class Benchmark, method test:labeled:repeated: was also modified to allow collection of the bytecode counts. We have chosen to report data collected for each of the "macro" operations in class Benchmark. Measurements reported are the average of three trials. The message lookup cache was in use when these measurements were taken.

<table><caption>Table 10.8 Bytecodes/Second for Benchmark Macro Tests</caption><thead><tr><th>Activity</th><th>Counts</th><th>ms Elapsed</th><th>Bytecodes/sec</th><th>+5%</th></tr></thead><tbody><tr><td>compile dummy method</td><td>550,061</td><td>49,440</td><td>11,126</td><td>11,682</td></tr><tr><td>decompile Form & Class</td><td>2,391,154</td><td>203,440</td><td>11,753</td><td>12,341</td></tr><tr><td>create an Inspector</td><td>33,959</td><td>3,430</td><td>9,901</td><td>10,396</td></tr><tr><td>format a bunch of text</td><td>258,750</td><td>20,880</td><td>12,396</td><td>13,012</td></tr><tr><td>replace & redisplay test</td><td>350,985</td><td>38,580</td><td>9,098</td><td>9,552</td></tr></tbody></table>

## Acknowledgments

The authors wish to thank the management of Apple Computer, and especially John Couch, Wayne Rosing, Nellie Connors, and Ron Johnston for providing the equipment, the environment and the freedom needed to implement the Smalltalk-80 system successfully on the MC68000. Thanks also go to Bill Atkinson and David Hough, who helped with the engineering effort.
# Berkeley Smalltalk: Who Knows Where the Time Goes?

David M. Ungar

David A. Patterson

Computer Science Division

Department of Electrical Engineering

and Computer Sciences

University of California, Berkeley

Sad deserted shore,
Your fickle friends are leaving.
Ah but then you know
It's time for them to go.
But I will still be here
I have no thought of leaving.
I do not count the time.
Who knows where the time goes?
Who knows where the time goes?
"Who Knows Where the Time Goes"*

We have implemented the Smalltalk-80 virtual machine in the C programming language for the Digital Equipment Corp. VAX-11/780 under Berkeley Unix. We call this system Berkeley Smalltalk (BS). An AED-512 terminal connected over a 9600-baud serial link serves as the display device. In four months one person wrote BS in about 9000 lines

*[Denny, Sandy, "Who Knows Where the Time Goes?" (BMI) Winckler Music, Judy Collins (BMI), Irving Music, used by permission]

Copyright © David M. Ungar, David A. Patterson, 1982. All rights reserved.
of source code. Other Smalltalk-80 implementations on non-micropro-
grammable computers have suffered from poor performance. We believe
that a straightforward, literal implementation of the specification can-
not achieve acceptable performance. This paper explains how the opti-
mizations in BS have increased performance fourfold.

**Introduction**

The Smalltalk-80 book¹ includes a clear and intelligible definition of
the Smalltalk-80 virtual machine. To learn about the performance con-
sequences of following this definition, we have measured key compo-
nents of:

1. An interpreter that follows the book exactly; and

2. Berkeley Smalltalk (BS), which meets the specification but does not mimic the definition in the book.

The results of this study are shown in Table 11.1 below. Berkeley Smalltalk is 4.8 times faster than a straight-forward implementation. The rest of this paper details the steps behind this result.

<table><caption>Table 11.1 Summary of All Optimizations
(all times are in microseconds per bytecode)</caption><thead><tr><th>Activity</th><th>By-the-book</th><th>BS</th><th>By-the-book/BS</th></tr></thead><tbody><tr><td>reference counting</td><td>50 (12%)</td><td>9.5 (11%)</td><td>5.3</td></tr><tr><td>dispatching bytecodes</td><td>124 (31%)</td><td>10 (12%)</td><td>12</td></tr><tr><td>BitBlt</td><td>0—100 (0—25%)</td><td>0—8.3 (0—10%)</td><td>12</td></tr><tr><td>allocation and freeing</td><td>19 (5%)</td><td>5.2 (6%)</td><td>3.7</td></tr><tr><td>OT indirection</td><td>29 (7%)</td><td>2.4 (3%)</td><td>12</td></tr><tr><td>method lookup</td><td>36 (9%)</td><td>3.8 (5%)</td><td>9.4</td></tr><tr><td><strong>Subtotal</strong></td><td><strong>358 (89%)</strong></td><td><strong>39 (47%)</strong></td><td></td></tr><tr><td>other activities</td><td>44 (11%)</td><td>44 (53%)</td><td></td></tr><tr><td><strong>Total</strong></td><td><strong>402µs (100%)</strong></td><td><strong>83µs (100%)</strong></td><td><strong>4.8</strong></td></tr></tbody></table>

**Methodology**

First, we identified the activities or operations that distinguish a Smalltalk-80 system from a conventional non-interpreted language. These include:
* Automatic free space reclamation (realized with reference counts),

* Bytecode decoding,

* Bitmap manipulation (BitBlt)²,

* Allocating and freeing objects,

* Object table (OT) indirections, and

* Method lookup.

We measured the cost of each activity by writing test programs in C³ that simply looped and performed the operations as defined by the book. The CPU execution times of these programs were compared with dummy programs that looped without performing the measured operation. Although we never implemented a complete interpreter by-the-book, we coded these key operations with as much ingenuity as those in BS. In this way, we hoped to measure only differences caused by underlying data structures rather than those attributable to clever "hacks" in the code.

Next, we derived a bytecode mix from a profile of a typical interactive session of seven million bytecodes⁴. This mix is shown in Table 11.2 below.

<table><caption>Table 11.2 A Typical Dynamic Bytecode Distribution</caption><thead><tr><td>Instruction Type</td><td>Frequency</td><td>Explanation</td></tr></thead><tbody><tr><td>push</td><td>43%</td><td>typically instance or temporary variable</td></tr><tr><td>full sends</td><td>11%</td><td>causes context switch</td></tr><tr><td>direct arith prims</td><td>8%</td><td>successful; another 2% fail</td></tr><tr><td>short circuit sends</td><td>5%</td><td></td></tr><tr><td>direct special prims</td><td>3%</td><td>successful</td></tr><tr><td>primitives</td><td>3%</td><td>0.3% fail</td></tr><tr><td>return stack top</td><td>9%</td><td>assume 1 entry on stack</td></tr><tr><td>other returns</td><td>2%</td><td>assume 1 entry on stack</td></tr><tr><td>pop and store</td><td>5%</td><td>typically instance or temporary variable</td></tr><tr><td>pop</td><td>2%</td><td></td></tr><tr><td>jump conditional</td><td>6%</td><td>from Baden's measurements⁵</td></tr><tr><td>jump unconditional</td><td>2%</td><td>from Baden's measurements⁶</td></tr><tr><td>store</td><td>1%</td><td></td></tr><tr><td>unaccounted</td><td>1%</td><td></td></tr><tr><td>Total</td><td>100%</td><td></td></tr></tbody></table>

The Smalltalk-80 book and the BS source code gave us the types and numbers of key operations for each type of bytecode. Finally, we calcu-
lated a weighted average for the mean number of key operations per bytecode.

Multiplying the time per operation by the number of operations per bytecode gave us the time spent per bytecode on each operation (except BitBt). To measure individual optimizations, we also computed the time spent by an implementation that performed all the optimizations *but* the one in question. Table 11.1 summarizes effects of optimizing these areas. We'll examine these areas individually in the following sections, discuss other optimizations, and draw some conclusions.

## Reference Counting

Smalltalk-80 implementations, including BS, reclaim space by maintaining a reference count for every object. Two reference-count operations are required when the virtual machine stores an object pointer (Oop): one to account for the destruction of the word's former contents, and one to account for the creation of a new reference. Each reference-count operation must first verify that its operand represents a reference-counted object and not a small integer. Then it must increment or decrement the appropriate count and check for over- and underflow. When an object's reference count diminishes to zero, all of its references must be destroyed by recursively decrementing the counts of the referenced objects. Only then can the virtual machine reuse the space. Although each reference-count operation is not expensive, the cumulative time counting references threatens to throttle by-the-book implementations.

We designed the Oop and OT structures to speed up reference counting. We enlarged the book's reference-count variables from 8 to 32 bits to obviate overflow checking. The object table was split into separate arrays of reference counts, addresses, and flags to eliminate the multiplication needed to index an array whose elements are not a power of 2 long. The SmallInteger tag bit was moved to the high order bit of the Oop from the low order bit to avoid the right shift required to convert an Oop to an array index.

### *Oops by-the-book.*

```
15 ... 1      0
<OT Index>    0
<Integer>      1
```

### *Berkeley Oops*

```
15 14 ...     0
0 <OTIndex >
1 <Integer >
```
The Berkeley Oop format also reduced the overhead of reference counting by hastening the check to decide whether an object must be reference counted. Since the integers all have negative Oops, and the Oop not needing reference counting (invalid Oop, nil, true, false) have values 0 through 3; a single signed comparison can ferret out nonreference-counted Oops. A typical BS count operation became 25% faster—8.2µs to 6.3µs.

Reference-Counting
Operations Per
Bytecode

BS incorporated many strategies from the Xerox Dorado⁷ and Dolphin implementations⁸ that reduce the number of reference-count operations. For example, when returning the top of stack, the result's Oop must be pushed onto the caller's stack. A straightforward implementation would *copy* the Oop into the new context and increment its reference count. Later, when freeing the callee's context, the implementation would decrement the result's reference count. Instead, *destructively moving* the Oop obviates these two reference-count operations. After storing the Oop in the caller's context, BS destroys the old reference from the callee's context by nilling it out. Since the net number of references does not change, the reference count stays the same. An implementation can also avoid a decrement operation when it can guarantee that the target field contains a nonreference-counted object (e.g. nil). If the implementation can count on the new contexts of a field to be nonreference counted, it can avoid the increment.

Perhaps the single most significant trick for optimizing reference counting is the stack management strategy we adopted from the Dorado implementation. A Smalltalk-80 interpreter must free a context on almost every return. Since the context may contain references to objects, a conventional implementation must sweep the entire context to free it. The stack occupies two-thirds of a context; most of the stack is never used. BS avoids sweeping the area above the top of the stack (TOS) by banishing references to objects from that area. Only nil, SmallIntegers, true, and false may reside there. Performing context freeing as part of the return operation whenever possible is another important optimization. In addition to saving the overhead of invoking the recursive freeing routine, many other fields in a context are sure to be nonreference counted and are thus ignored. With these changes, recursive freeing accounts for less than 2%⁹ of the execution time. Moving the sender Oop and result Oop instead of copying them saved four more count operations in the return bytecode. Tables 11.3 and 11.4 enumerate the reference-count operations required for a full send and return.

Be warned: explicitly altering either the stack pointer or the fields above the top of stack (both pointless actions) can compromise the integrity of an implementation with this optimization. This hazard has not posed a problem for BS or the Dorado implementation.
<table><caption>Table 11.3 Reference-Count Operations for Full Sends</caption><thead><tr><td>Operation</td><td>By-the-book</td><td>BS</td></tr></thead><tbody><tr><td>decrement sender in new context</td><td>1</td><td>0</td></tr><tr><td>increment new sender</td><td>1</td><td>0</td></tr><tr><td>decrement old active context</td><td>1</td><td>0</td></tr><tr><td>increment new active context</td><td>1</td><td>1</td></tr><tr><td>decrement IP in old context</td><td>1</td><td>0</td></tr><tr><td>increment IP in old context</td><td>1</td><td>0</td></tr><tr><td>decrement SP in old context</td><td>1</td><td>0</td></tr><tr><td>increment SP in old context</td><td>1</td><td>0</td></tr><tr><td>increment context class</td><td>1</td><td>0</td></tr><tr><td>decrement method in new context</td><td>1</td><td>0</td></tr><tr><td>increment method in new context</td><td>1</td><td>1</td></tr><tr><td>decrement receiver in new context</td><td>1</td><td>0</td></tr><tr><td>increment receiver in new context</td><td>1</td><td>0</td></tr><tr><td>decrement argument in new context</td><td>1</td><td>0</td></tr><tr><td>increment argument in new context</td><td>1</td><td>0</td></tr><tr><td><strong>Total for full send</strong></td><td><strong>15</strong></td><td><strong>2</strong></td></tr></tbody></table>

<table><caption>Table 11.4 Reference-Count Operations for Returns</caption><thead><tr><td>Operation</td><td>By-the-book</td><td>BS</td></tr></thead><tbody><tr><td>decrement old active context</td><td>1</td><td>1</td></tr><tr><td>increment new active context</td><td>1</td><td>0</td></tr><tr><td>increment result</td><td>1</td><td>0</td></tr><tr><td>decrement result</td><td>1</td><td>0</td></tr><tr><td>increment old IP</td><td>1</td><td>0</td></tr><tr><td>increment old SP</td><td>1</td><td>0</td></tr><tr><td><strong>Total to switch contexts</strong></td><td><strong>6</strong></td><td><strong>1</strong></td></tr><tr><td>decrement old sender</td><td>1</td><td>0</td></tr><tr><td>decrement old IP</td><td>1</td><td>0</td></tr><tr><td>decrement old SP</td><td>1</td><td>0</td></tr><tr><td>decrement old unused field</td><td>1</td><td>0</td></tr><tr><td>decrement old receiver</td><td>1</td><td>1</td></tr><tr><td>decrement old method</td><td>1</td><td>1</td></tr><tr><td>decrement old stack contents</td><td>12</td><td>1</td></tr><tr><td>decrement context class</td><td>1</td><td>0</td></tr><tr><td><strong>Total to free old context</strong></td><td><strong>19</strong></td><td><strong>3</strong></td></tr><tr><td><strong>Grand total for return</strong></td><td><strong>25</strong></td><td><strong>4</strong></td></tr></tbody></table>
This stack management strategy also reduced the number of reference-count operations for pushes and pops. It saved a decrement for each push and saved two reference-count operations per pop and store. It did force pop operations to nil out the old Oop. Three reference-count operations were saved for each integer primitive since they can succeed only with nonreference-counted Oops. Table 11.5 lists the number of counts for each type of bytecode. The optimizations removed 70% of the reference counting.

<table><caption>Table 11.5 Reference-Count Operations by Bytecode</caption><thead><tr><th>Instruction type</th><th>By-the-book</th><th>BS</th><th>By-the-book/BS</th></tr></thead><tbody><tr><td>push</td><td>2</td><td>1</td><td>2.0</td></tr><tr><td>full sends</td><td>15</td><td>2</td><td>7.5</td></tr><tr><td>direct arith prims</td><td>4</td><td>0</td><td>(infinite)</td></tr><tr><td>special primitives</td><td>4</td><td>3</td><td>.67</td></tr><tr><td>short circuit sends</td><td>2</td><td>2</td><td>1.0</td></tr><tr><td>primitives</td><td>4</td><td>4</td><td>1.0</td></tr><tr><td>return stack top</td><td>25</td><td>4</td><td>6.3</td></tr><tr><td>other returns</td><td>26</td><td>5</td><td>5.2</td></tr><tr><td>pop and store</td><td>2</td><td>1</td><td>2</td></tr><tr><td>pop</td><td>0</td><td>1</td><td>0</td></tr><tr><td>jump conditional</td><td>0</td><td>0</td><td></td></tr><tr><td>jump unconditional</td><td>0</td><td>0</td><td></td></tr><tr><td>store</td><td>3</td><td>2</td><td>1.5</td></tr><tr><td><strong>Mean counts per bytecode</strong></td><td><strong>6.1</strong></td><td><strong>1.5</strong></td><td><strong>4.1</strong></td></tr></tbody></table>

Multiplying the time per count by the number of counts per bytecode gave us the total time spent for each bytecode on reference counting. Table 11.6 presents these data and reinforces the importance of the reference-count optimizations; if BS did not include them, it would run 1.5 times slower.

<table><caption>Table 11.6 Cost of Reference Counting</caption><thead><tr><th>Measurement</th><th>By-the-book</th><th>BS</th><th>By-the-book/BS</th></tr></thead><tbody><tr><td>mean counts per bytecode</td><td>6.1</td><td>1.5</td><td>4.1</td></tr><tr><td>mean time per count</td><td>8.2µs</td><td>6.3µs</td><td>1.3</td></tr><tr><td>mean count time per bytecode</td><td>50µs</td><td>9.5µs</td><td>5.3</td></tr><tr><td>mean time per bytecode</td><td>124µs</td><td>83µs</td><td>1.5</td></tr><tr><td><strong>Fraction spent counting</strong></td><td><strong>40%</strong></td><td><strong>11%</strong></td><td><strong>3.6</strong></td></tr></tbody></table>
## Bytecode Decoding

The definition of bytecode decoding encompasses the computation performed identically for each bytecode. Both Dolphin and Dorado contain fast hardware to decode bytecodes, a luxury absent from a conventional computer like our VAX. In addition to the decoding itself, we included checking for process switches, fetching bytecodes, updating the virtual instruction pointer, and for BS, counting bytecodes. BS uses a 256-way branch table to decode single-byte bytecodes completely. We combined the check for process switching and input polling into a single counter that is decremented and tested for each bytecode executed. Although we did not measure this optimization by itself, we did duplicate the code for the directly executed primitives so they could be executed in-line. Open coding minimizes the number of subroutine calls; the most common bytecodes and primitives use none. We timed bytecode decoding for both BS and a by-the-book implementation. As Table 11.7 shows, fast dispatching is critical—BS would be 2.5 times slower without it.

<table><caption>Table 11.7 Bytecode Dispatching</caption><thead><tr><th>Measurement</th><th>By-the-book</th><th>BS</th><th>By-the-book/BS</th></tr></thead><tbody><tr><td>time to dispatch one bytecode</td><td>124µs</td><td>10µs</td><td>12</td></tr><tr><td>mean time per bytecode</td><td>207µs</td><td>83µs</td><td>2.5</td></tr><tr><td>% of time spent dispatching</td><td>60%</td><td>12%</td><td>5</td></tr></tbody></table>

## BitBlt

BitBlt¹⁰ is the workhorse of the Smalltalk-80 graphics system. It performs all bitmap manipulation and text composition. The large amount of computation for this operation makes it a prime target for optimization. BS uses an external display, and must pay communication costs for bitmaps as well as the computation costs.

## Coping With an External Display

We found three techniques to cut communication costs to our external display: fill recognition, delayed output, and reordered output.

☐ **Fill Recognition** The bulk of the computation on bitmaps fills a rectangular area with all ones or all zeroes¹¹. These area fill operations involve 21 times more bits than other, more complex copying operations. BS determines which invocations of BitBlt merely fill areas and sends rectangle fill commands to the display for them. (BitBlt itself is optimized for this case with special-purpose routines.)
☐ *Delayed Output* Second, borrowing an idea from an HP version of Smalltalk¹², when displaying text, our output routine does not send individual character-sized blocks of pixels until the completion of an invocation of the text composition primitive, `scanCharacters`. At that point `BS` sends a complete word-sized block.

☐ *Reordered Output* Third, when sending a bitmap to the display device, the middle goes separately from the left and right edges. Since the middle is an integral number of bytes, no shifting is needed to align the pixels for the display device. Each row in the middle of the bitmap is sent as bytes, not bits.

*Measuring the BitBlt Optimization*

The only display optimization that can be easily compared to the specification in the book is the special purpose code for area fill. We measured the time to fill a 1000 by 1000 bitmap with the slow, general code, and the time to fill the same bitmap with the fast code for zero and one fill. The data in¹³ supplied the proportion of work done by BitBlt (number of bits) that could be done with the special-purpose fast code. A weighted average of the times then yields the mean time to fill a 1000 by 1000 bitmap. Profile data supplied the midpoint proportion of total time spent per bytecode on BitBlt. To derive the time spent in BitBlt per bytecode for `BS`, we multiplied the time per bytecode by this percentage. We obtained the BitBlt time per bytecode of the unoptimized version by multiplying this time by the ratio of the unoptimized time to fill a megabit to the `BS` time to fill a megabit. Table 11.8 shows the results of this calculation. We conclude that this optimization is important for sessions that involve graphics and text composition, it doubled the speed of the interpreter.

<table><caption>Table 11.8 BitBlt Area Fill Optimization</caption><thead><tr><th>Measurement</th><th>By-the-book</th><th>BS</th><th>By-the-book/BS</th></tr></thead><tbody><tr><td>time to fill 1000 x 1000 zeroes</td><td>2100ms</td><td>92ms</td><td>23</td></tr><tr><td>time to fill 1000 x 1000 ones</td><td>2100ms</td><td>97ms</td><td>22</td></tr><tr><td>time to fill 1000 x 1000 mixed bits</td><td>2100ms</td><td>2100ms</td><td>1</td></tr><tr><td>ratio of zero/one fill to mixed bits</td><td>21</td><td>21</td><td>1</td></tr><tr><td>avg. time per 1M bits</td><td>2100ms</td><td>180ms</td><td>12</td></tr><tr><td>% time copying</td><td>0—57%</td><td>0—10%</td><td>1—5.7</td></tr><tr><td>copybits time per bytecode</td><td>0—100µs</td><td>0—8.3µs</td><td>1—12</td></tr><tr><td>Mean time per bytecode</td><td>75µs—175µs</td><td>83µs</td><td>1—2.1</td></tr></tbody></table>
## Allocation and Freeing

Unix includes a library package for allocating and freeing areas of memory¹⁴, but it might be too general to be fast enough for a Smalltalk-80 system. The proliferation of dynamic objects in a Smalltalk-80 environment strains conventional memory allocators. In particular, every message send and return pair results in allocating and freeing a context object. Many Points are created and discarded in the graphics routines. The popularity of these two classes is shown in Table 11.9, the percentage of allocation frequency by size based on measurements¹⁵.

<table><caption>Table 11.9 Sizes of Frequently Allocated Objects</caption><thead><tr><td>Size</td><td>Allocation Frequency</td><td>Comments</td></tr></thead><tbody><tr><td>18</td><td>84%</td><td>size of small context</td></tr><tr><td>2</td><td>9%</td><td>size of point object</td></tr><tr><td>28</td><td>1%</td><td>size of large context</td></tr><tr><td>other</td><td>6%</td><td></td></tr></tbody></table>

BS exploits this pattern with an algorithm outlined in the specification¹⁶. We observed that when a small object such as a context is freed, the probability of an allocation request for an object of the same size in the near future is high. The obvious strategy then is to hold onto the space and OT entry for the freed object, and to recycle it for the expected allocation. Although the specification defines a small object as one with 20 or fewer fields, we extended it to 40 to cover large contexts as suggested by Peter Deutsch. For each size of small object (0-40), BS maintains a pool of free objects on a linked list. Thus BS can allocate a small object by removing one from the appropriate list, setting its class and reference count, and nilling out the object's fields. If a pool runs dry, the Unix storage allocator is invoked to obtain a chunk of memory 10 times the desired size. BS then divides the chunk into 10 free objects, and tosses them into the pool. If too many objects end up in the free pools, it is possible to run out of available OT slots. When this happens, OT entries must be released from the free objects. The memory space for large objects is obtained from the Unix allocator.

We measured the cost of an allocation with a test program that repeatedly allocated and freed 100 context-sized objects with a LIFO discipline. Both the Unix allocator and the BS allocator were measured. It will be useful for the analysis to trichotomize sends:

1. We call sends to methods that simply return self or an instance variable short-circuit sends. The method header names the field to be returned.
2. Other sends result in the invocation of runtime interpreter sub-routines. These are the *primitives*.

3. The longest sends activate a new context and transfer control to the target method. We call these *full sends*.

The frequency of full sends provided the context allocation frequency, and the total allocation frequency was obtained by dividing the number of contexts allocated per bytecode by the fraction of context allocations. The allocate, free, and nilling out time is just the product of the allocations per bytecode and the time per allocation. Table 11.10 shows this calculation. Our object allocation strategy bought only a modest improvement in overall performance. The Unix allocator is well-tuned, and the time allocating and freeing objects is amortized over the time spent using the objects.

<table><caption>Table 11.10 Cost to Allocate and Free Object</caption><thead><tr><th>Measurement</th><th>Unix allocator</th><th>BS allocator</th><th>Unix/BS</th></tr></thead><tbody><tr><td>time to allocate and free</td><td>130µs</td><td>21µs</td><td>6.2</td></tr><tr><td>time to nil out object</td><td>19µs</td><td>19µs</td><td>1.0</td></tr><tr><td><strong>Total</strong></td><td><strong>149µs</strong></td><td><strong>40µs</strong></td><td><strong>3.7</strong></td></tr><tr><td>allocations per bytecode</td><td>.13</td><td>.13</td><td>1</td></tr><tr><td>alloc/free/nil time per bytecode</td><td>19µs</td><td>5.2µs</td><td>3.7</td></tr><tr><td>mean time per bytecode</td><td>97µs</td><td>83µs</td><td>1.2</td></tr><tr><td><strong>Fraction of time spent allocating</strong></td><td><strong>20%</strong></td><td><strong>6%</strong></td><td><strong>3.2</strong></td></tr></tbody></table>

There are more tasks involved in storage management than just allocating and freeing, but the large address space and physical memory of the VAX reduce the importance of most of them. BS usually needs about half a megabyte of physical memory, and fits comfortably on our 4 megabyte time-shared VAX. In particular, we have not observed any thrashing, and thus have ignored dynamic compaction. Garbage collection flashes by so quickly on a 32-bit computer with plentiful memory that it can be hidden in the time needed to save an image on disk.

## Object Table Indirection

To read or write a field of an object, the Smalltalk-80 virtual machine must first determine the object's memory address from the Object Table. We optimized this object table indirection just as we optimized reference counting. Addresses, like counts, are stored in a separate array,
and the same Oop format that facilitates indexing the reference array speeds accesses to the object address array. We used test programs to time the cost of an indirection. Indirection is so simple that the array access costs dominates; the data structures in the book would double the time for each object table indirection on a VAX.

Close scrutiny of the book and the BS source code yielded the number of indirections. BS avoids object table indirections by saving memory addresses of some objects in registers. In particular, it keeps the current receiver, active and home contexts, current method, top of stack, and next bytecode addresses in registers or local variables. Those primitives and bytecodes that do multiword transfers or read-modify-write operations also keep addresses in registers. Scattering addresses around in registers complicates compaction, but except for garbage collection, BS does not compact. Tables 11.11 and 11.12 enumerate the indirections performed for a full send and a return, respectively. The need to recursively free the old context increases the number of indirections for a by-the-book return.

<table><caption>Table 11.11 Object Table Indirections for Full Sends</caption><thead><tr><td>Operation</td><td>By-the-book</td><td>BS</td></tr></thead><tbody><tr><td>fetch send</td><td>1</td><td>0</td></tr><tr><td>copy receiver and argument</td><td>4</td><td>0</td></tr><tr><td>initialize new context</td><td>5</td><td>0</td></tr><tr><td>store old IP</td><td>1</td><td>0</td></tr><tr><td>store old SP</td><td>1</td><td>0</td></tr><tr><td>store new IP</td><td>1</td><td>0</td></tr><tr><td>store new SP</td><td>1</td><td>0</td></tr><tr><td>get address of new context</td><td>0</td><td>1</td></tr><tr><td>get address of new method</td><td>0</td><td>2</td></tr><tr><td>get address of new receiver</td><td>0</td><td>1</td></tr><tr><td>Total</td><td>14</td><td>4</td></tr></tbody></table>

Computing the indirections for the other operations was straightforward, except for the nonarithmetic primitives, where we cheated by assuming three indirections each. (These are only 6% of the bytecodes executed.) Table 11.13 gives the number of indirections required for each type of bytecode. A by-the-book implementation performs an indirection for every bytecode simply to fetch it; caching this address of the next bytecode is every implementor's favorite optimization. The optimizations are successful, they remove three-quarters of the indirections.
<table><caption>Table 11.12 Object Table Indirections for Returns</caption><thead><tr><th>Operation</th><th>By-the-book</th><th>BS</th></tr></thead><tbody><tr><td>fetch bytecode</td><td>1</td><td>0</td></tr><tr><td>pop result</td><td>1</td><td>0</td></tr><tr><td>push result</td><td>1</td><td>0</td></tr><tr><td>store old IP</td><td>1</td><td>0</td></tr><tr><td>store old SP</td><td>1</td><td>0</td></tr><tr><td>load new SP</td><td>1</td><td>0</td></tr><tr><td>load new IP</td><td>1</td><td>0</td></tr><tr><td>load new method register</td><td>1</td><td>0</td></tr><tr><td>load new receiver register</td><td>1</td><td>0</td></tr><tr><td>load active context</td><td>1</td><td>0</td></tr><tr><td>get address of new method</td><td>0</td><td>1</td></tr><tr><td>get address of new context</td><td>0</td><td>1</td></tr><tr><td>get address of new receiver</td><td>0</td><td>1</td></tr><tr><td>free context</td><td>2</td><td>2</td></tr><tr><td>recursive free of context</td><td>18</td><td>0</td></tr><tr><td><strong>Total</strong></td><td><strong>30</strong></td><td><strong>5</strong></td></tr></tbody></table>

<table><caption>Table 11.13 Object Table Indirections per Bytecode</caption><thead><tr><th>Instruction Type</th><th>By-the-book</th><th>BS</th><th>By-the-book/BS</th></tr></thead><tbody><tr><td>push</td><td>3</td><td>0</td><td>(infinite)</td></tr><tr><td>full sends</td><td>14</td><td>4</td><td>3.5</td></tr><tr><td>arith prim</td><td>4</td><td>0</td><td>(infinite)</td></tr><tr><td>special prim</td><td>4</td><td>1.5</td><td>2.6</td></tr><tr><td>primitives</td><td>5</td><td>3</td><td>1.7</td></tr><tr><td>short circuit sends</td><td>3</td><td>0</td><td>(infinite)</td></tr><tr><td>return stack top</td><td>28</td><td>5</td><td>5.6</td></tr><tr><td>other returns</td><td>30</td><td>5</td><td>6.0</td></tr><tr><td>pop and store</td><td>3</td><td>0</td><td>(infinite)</td></tr><tr><td>pop</td><td>2</td><td>0</td><td>(infinite)</td></tr><tr><td>jump conditional</td><td>2</td><td>0</td><td>(infinite)</td></tr><tr><td>jump unconditional</td><td>1</td><td>0</td><td>(infinite)</td></tr><tr><td>store</td><td>3</td><td>0</td><td>(infinite)</td></tr><tr><td><strong>Mean indirections per bytecode</strong></td><td><strong>7.0</strong></td><td><strong>1.2</strong></td><td><strong>5.8</strong></td></tr></tbody></table>

Finally, to obtain the time spent on object table indirection per bytecode, we multiplied by the number of indirections per bytecode. Table 11.14 shows these results. These optimizations reduce indirection
from a major cost of the interpreter to merely 4% of the total cost. There have been proposals to use 32-bit Oops and eliminate the object table. Table 11.14 implies that eliminating the speed penalty of the indirection is a poor justification for abolishing the object table. There may of course, be other, more compelling reasons.

<table><caption>Table 11.14 Cost of Object Table Indirection</caption><thead><tr><th>Measurement</th><th>By-the-book</th><th>BS</th><th>By-the-book/BS</th></tr></thead><tbody><tr><td>mean indirections per bytecode</td><td>7.0</td><td>1.2</td><td>5.8</td></tr><tr><td>time per indirection</td><td>4.2µs</td><td>2.0µs</td><td>1.2</td></tr><tr><td>mean indirection time per bytecode</td><td>29µs</td><td>2.4µs</td><td>12</td></tr><tr><td>mean time per bytecode</td><td>110µs</td><td>83µs</td><td>1.3</td></tr><tr><td><strong>Fraction spent indirecting</strong></td><td><strong>26%</strong></td><td><strong>3%</strong></td><td><strong>9.0</strong></td></tr></tbody></table>

## Method Lookup

Runtime type checking is a fundamental innovation of the Smalltalk-80 language. Every message send (procedure call) looks up the message's selector in the method dictionaries for the receiver's class (and superclasses). The Smalltalk-80 book recommends reducing the time spent for lookups with a cache. BS incorporates such a method lookup cache with 1024 entries. The cache slot is computed from the low-order 10 bits of the result of performing an exclusive-or (the book uses and) of the receiver's class and the selector. Conroy and Pelegri (see Chapter 13) have conducted a thorough study of Smalltalk-80 method cache behavior; Table 11.15 merely summarizes their findings for BS. The wisdom in the book is borne out, as BS would be 40% slower without the cache.

<table><caption>Table 11.15 Method Caching</caption><thead><tr><th>Measurement</th><th>Without Cache</th><th>With Cache</th><th>Ratio</th></tr></thead><tbody><tr><td>measured hit time</td><td></td><td>4.4µs</td><td></td></tr><tr><td>measured miss time</td><td>187µs</td><td>284µs</td><td></td></tr><tr><td>measured hit %</td><td>0%</td><td>94%</td><td></td></tr><tr><td>mean lookup time</td><td>187µs</td><td>20µs</td><td>9.4</td></tr><tr><td>mean lookups per bytecode</td><td>.19</td><td>.19</td><td>1.0</td></tr><tr><td>mean lookup time per bytecode</td><td>36µs</td><td>3.8µs</td><td>9.4</td></tr><tr><td>mean time per bytecode</td><td>115µs</td><td>83µs</td><td>1.4</td></tr><tr><td><strong>Fraction of time for lookup</strong></td><td><strong>31%</strong></td><td><strong>5%</strong></td><td><strong>6.2</strong></td></tr></tbody></table>
## Other Optimizations

Many other optimizations exist in BS. Standard programming tricks speed recursive freeing and garbage collection for certain popular classes. Subroutine calls and other overhead are trimmed in sends and returns. Floating point arithmetic is performed in hardware. Most of these optimizations are easily discovered and are unrelated to the distinguishing characteristics of the Smalltalk-80 system.

## Other Interpreter Activities

As Table 11.1 shows, the activities we measured account for a total of 40µs per bytecode in BS. BS has been instrumented to measure the bytecodes executed per CPU-second; this is about 12000 for typical interactive sessions of browsing, editing, compiling, and so forth. Thus, BS spends 1/12000 second or 83µs per bytecode. That leaves 43µs unaccounted for. This represents the "useful work", in the sense that it contains no easy targets for optimization. It includes the execution of bytecodes and primitives.

Although we have optimized these activities in the obvious ways (e.g. open coding), these are the least interesting optimizations. We therefore made the conservative assumption that the unoptimized interpreter would be no slower.

## Comparative Execution Times

How close is BS to an optimal Smalltalk-80 implementation? The fastest Smalltalk-80 implementation is Deutsch's Dorado interpreter. The Dorado is a powerful personal computer¹⁷ with a microcycle time three times faster than the VAX-11/780. The Dolphin is a more modest machine; it is considered to be adequate but not comfortable. We decided to examine two test cases: our typical interactive session and Baden's Towers of Hanoi benchmark¹⁸. Peter Deutsch measured the performance of the Xerox implementations on the Hanoi benchmark. The numbers for the Xerox implementations for the typical interactive session reflect the best estimates of the Software Concepts Group. The execution rate for BS was measured as described above. Table 11.16

<table><caption>Table 11.16 Relative Performance (kilobycodes per second)</caption><thead><tr><td>Case</td><td>BS</td><td>Dolphin</td><td>Dorado</td></tr></thead><tbody><tr><td>Interactive use</td><td>12</td><td>30</td><td>400</td></tr><tr><td>Towers of Hanoi</td><td>23</td><td>33</td><td>420</td></tr></tbody></table>
compares BS execution speed for the two test cases. Although BS performs well for a conventional machine, it suffers in comparison to the Xerox personal computers.

## Conclusions

We have several minor reservations about the results in this paper. First, our methods yielded only rough approximations. We ignored the effects of the VAX hardware cache hit rate on the running times of our test programs. Bytecode frequencies can be expected to vary. Second, major optimizations often have synergistic effects on code complexity and execution time. Finally, we did not explore some important areas (e.g. context changing overhead). The intended value of this work lies in ranking the different optimizable areas and in quantifying the benefits of optimization. For instance, it clearly shows that reference counting remains a more promising target than allocation and freeing. These measurements and calculations do however, reinforce the need to optimize carefully and tune implementations of Smalltalk-80 virtual machines. When our optimizations in the measured areas were combined, they resulted in a fourfold improvement in performance.

## Acknowledgments

We would like to thank the Software Concepts Group for creating the Smalltalk-80 system and bringing it out into the light of day. In particular, we owe our gratitude to Peter Deutsch who has offered both quintessential and patient technical guidance, and to Adele Goldberg who issued our entry visa onto the "Isle of Smalltalk". We thank the students here at Berkeley involved with the Smalltalk project: Scott Baden, Ricki Blau, Dan Conde, Tom Conroy, Dan Halbert, Ed Pelegri, Richard Probst, and Steve Sargent have contributed hard work, data, and insight to the task of understanding where the time goes. We owe a debt of thanks to Jim Stinger, Ted Laliottis, Bob Ballance, and the rest of the Smalltalk-80 group at HP Labs, who by permitting us to study their unfinished implementation, furnished us with a working model to study. Paul McCullough provided thoughtful and constructive comments to help smooth out the rough spots in this paper.

This effort was funded in part by Apple Computer and the State of California through the Microelectronics Innovation and Computer Research Opportunities program, and sponsored by Defense Advance Research Projects Agency, Department of Defense, Order No. 3803,
monitored by Naval Electronic System Command under Contract No. N00039-81-K-0251.

References

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

2. Ingalls, Daniel H. H., "The Smalltalk Graphics Kernel", *Byte* vol. 6, no. 8, pp. 168-194, Aug. 1981.

3. Ritchie, Dennis M., Johnson, Stephen C., Lesk, Michael E., and Kernigham, Brian W., "UNIX Time-Sharing System: The C Programming Language", *Bell System Technical Journal* vol. 57, no. 6, pp. 1991-2019, 1978.

4. Conroy, Tom, and Pelegri-Llopart, Eduardo, "CPU Time Profile of Long Interactive BS Session", Private Communication, May 1982.

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

6. *Ibid.*

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

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

9. See reference 4.

10. See reference 2.

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

12. Stinger, Jim, et. al., Private Communications, 1981.

13. See reference 11.

14. Joy, William N., and Babaoglu, Ozalp, UNIX *Programmers Manual*, Computer Science Div., Dept. of E.E.C.S., Univ. of California, Berkeley, CA, Nov. 7, 1979.
15. See reference 5.

16. See reference 1.

17. See reference 7.

18. See reference 5.

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

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

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

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

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

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

<figure><img src="image_29.png" /></figure>
# The Analysis of the Smalltalk-80 System at Hewlett-Packard*

Joseph R. Falcone

Computer Research Center

Hewlett-Packard Laboratories

Palo Alto, California

## Introduction

The implementation of Smalltalk at Hewlett-Packard Laboratories was the principal component of an investigation into personal computing environments. As we developed the implementation, we continually analyzed its performance to achieve a better understanding of the system. This program began in earnest in March of 1981 when we embarked on the first implementation. By November, the entire project was winding down and we placed more emphasis on performance analysis to complete it before the end. When the project closed in February of 1982, we had developed a vast body of performance data, collected by both programs and people. Since then only the performance analysis has continued (as an unofficial part-time activity). The HP Smalltalk project is described in more detail in Chapter 6.

## Approach

The Smalltalk-80 system is difficult to measure, given the variability of user interaction which is fundamental to it. Repeating the identical test twice was nearly impossible so we designated a general collection of

<footnote>*The views expressed herein are those of the author, and do not necessarily represent the position of Hewlett-Packard or any commitment to products or services. Copyright © Joseph R. Falcone, 1982. All rights reserved.</footnote>
tasks as the *basic test*, touching all of the capabilities of the system at least once according to our view of personal computer usage patterns. During this test, the browser, compiler, decompiler, and window system are exercised in every conceivable way. With full performance monitoring, the test covers millions of bytecodes and takes over six hours. Our test should not be confused with the *testStandardTests* benchmarks. Early investigative work on our system used the *testStandardTests* benchmarks until we noticed that the results bore little relation to statistics gathered from normal usage. Hence we felt that it was not useful as a personal computing performance test.

In the following sections, we present measurements of the system compiled from many *basic test* experiments. The measurements cover a wide variety of system functions, from bytecode frequencies to memory access. These figures are probably accurate to within 10% for different mixes of Smalltalk-80 code. We conducted these tests on a pre-release version of the Smalltalk-80 system.

Bytecode
Measurements

<table><caption>Table 12.1 Smalltalk-80 Virtual Machine Bytecode Frequency</caption><thead><tr><th>SVM Bytecode</th><th>Static %</th><th>Dynamic %</th><th>Cumulative</th></tr></thead><tbody><tr><td>push temporary variable 0</td><td>6.25%</td><td>6.48%</td><td>6.48%</td></tr><tr><td>push self (receiver)</td><td>6.28%</td><td>5.73%</td><td>12.21%</td></tr><tr><td>return stack top from message</td><td>3.22%</td><td>4.94%</td><td>17.15%</td></tr><tr><td>push temporary variable 1</td><td>3.39%</td><td>4.74%</td><td>21.89%</td></tr><tr><td>send +</td><td>1.19%</td><td>3.65%</td><td>25.54%</td></tr><tr><td>push temporary variable 2</td><td>2.12%</td><td>3.46%</td><td>29.00%</td></tr><tr><td>push constant 1</td><td>2.61%</td><td>3.26%</td><td>32.26%</td></tr><tr><td>send literal 0 with no args</td><td>1.66%</td><td>2.57%</td><td>34.83%</td></tr><tr><td>pop stack top</td><td>7.03%</td><td>2.42%</td><td>37.25%</td></tr><tr><td>send at:</td><td>0.77%</td><td>2.06%</td><td>39.31%</td></tr><tr><td>jump on false 0*256 + next</td><td>0.86%</td><td>1.93%</td><td>41.24%</td></tr><tr><td>push receiver variable 1</td><td>0.97%</td><td>1.72%</td><td>42.96%</td></tr><tr><td>push receiver variable 0</td><td>0.97%</td><td>1.70%</td><td>44.66%</td></tr><tr><td>send ==</td><td>0.90%</td><td>1.62%</td><td>46.28%</td></tr><tr><td>send -</td><td>0.83%</td><td>1.61%</td><td>47.89%</td></tr><tr><td>extended pop and store (all)</td><td>1.09%</td><td>1.51%</td><td>49.40%</td></tr><tr><td>push constant nil</td><td>1.33%</td><td>1.48%</td><td>50.88%</td></tr><tr><td>return self (receiver)</td><td>2.55%</td><td>1.43%</td><td>52.31%</td></tr><tr><td>send &lt;=</td><td>0.18%</td><td>1.32%</td><td>53.63%</td></tr></tbody></table>
<table><caption>Table 12.1 (Cont.)</caption><thead><tr><th>SVM Bytecode</th><th>Static %</th><th>Dynamic %</th><th>Cumulative</th></tr></thead><tbody><tr><td>extended push (all)</td><td>0.68%</td><td>1.32%</td><td>54.95%</td></tr><tr><td>jump -1*256 + next</td><td>0.27%</td><td>1.29%</td><td>56.24%</td></tr><tr><td>pop and store temporary 1</td><td>0.87%</td><td>1.27%</td><td>57.51%</td></tr><tr><td>push constant 0</td><td>1.87%</td><td>1.26%</td><td>58.77%</td></tr><tr><td>push temporary variable 3</td><td>1.27%</td><td>1.18%</td><td>59.95%</td></tr><tr><td>extended store (all)</td><td>0.81%</td><td>1.17%</td><td>61.12%</td></tr><tr><td>pop and branch on false 2</td><td>0.76%</td><td>1.15%</td><td>62.27%</td></tr><tr><td>push temporary variable 6</td><td>0.42%</td><td>1.10%</td><td>63.37%</td></tr><tr><td>send literal 1 with no args</td><td>1.21%</td><td>1.05%</td><td>64.42%</td></tr><tr><td>push receiver variable 14</td><td>0.20%</td><td>1.05%</td><td>65.47%</td></tr><tr><td>pop and store temporary 2</td><td>0.71%</td><td>1.03%</td><td>66.50%</td></tr><tr><td>send ></td><td>0.32%</td><td>0.96%</td><td>67.46%</td></tr><tr><td>send =</td><td>0.91%</td><td>0.94%</td><td>68.40%</td></tr><tr><td>push temporary variable 4</td><td>0.82%</td><td>0.88%</td><td>69.28%</td></tr><tr><td>send literal 0 with 1 arg</td><td>1.63%</td><td>0.85%</td><td>70.13%</td></tr><tr><td>all others (213)</td><td>41.91%</td><td>29.87%</td><td>100.00%</td></tr></tbody></table>

Table 12.1 lists the static and dynamic frequencies of the Smalltalk-80 virtual machine instruction set. This distribution is remarkably uniform. Most dynamic instruction frequencies show at least one instruction at over 10%¹, but the highest in the Smalltalk-80 virtual machine is only 6.48% for pushing a temporary onto the stack, usually performed to work on an argument passed through the temporary variable area. However, as the following section will show, there is some regularity by category of bytecodes. The top 17 bytecodes consume more than 50% of execution and the top 34 are over 70% out of 247 designated bytecodes.

Pop stack top had the highest static frequency even though it was ninth in execution. The top three bytecodes in static frequency comprise one-fifth of all generated code. After that there is a steep drop and no bytecode rises above 3.39%. The less popular instructions tend to have higher static frequencies. Outside of the top 30, the bytecodes have a static/dynamic frequency ratio of 4 to 3.

There are 9 unused bytecodes in the Smalltalk-80 virtual machine instruction set, and the system never executed 18 other bytecodes in our tests. Twelve of these instructions were long jumps, and all were the longer varieties. The current Smalltalk compiler does not generate the pop and jump on true instructions. This is apparently to simplify the task of the decompiler. The other six untouched instructions were pushes and sends concerned with somewhat rare circumstances.
<table><caption>Table 12.2 Bytecode Frequency by Category</caption><thead><tr><td>Bytecode Category</td><td>Static %</td><td>Dynamic %</td><td>Cumulative</td></tr></thead><tbody><tr><td>stack push</td><td>44.01%</td><td>44.37%</td><td>44.37%</td></tr><tr><td>message send</td><td>29.00%</td><td>28.63%</td><td>73.00%</td></tr><tr><td>stack pop and store</td><td>13.32%</td><td>10.80%</td><td>83.80%</td></tr><tr><td>branch and jump</td><td>6.50%</td><td>8.59%</td><td>92.39%</td></tr><tr><td>return</td><td>7.17%</td><td>7.61%</td><td>100.00%</td></tr></tbody></table>

Table 12.2 groups the bytecodes into five categories for static and dynamic frequencies. The importance of message sends in Smalltalk is evident, but this can be misleading. The percentage of sends is so large because it includes both procedure calls and arithmetic and logical operations (note the absence of a computational instruction category). Also, because many of the sends are special or primitive operations which do not result in the execution of Smalltalk code, the percentage of return instructions is much lower.

Stack operations account for 55.17% of instructions executed, and 71.37% are instructions other than sends. The frequency of stack push and pop instructions points out the necessity of having an optimized independent path to the stack frame of the active context.

## Send Bytecodes

Although the message send is perhaps the most important part of Smalltalk, it comprises only about one-quarter of execution time. More importantly, nearly half are special sends which do not require a dictionary lookup for their selector. These special sends perform functions which are typically in the instruction set of a processor, such as arithmetic and logical operations for small integers.

Approximately every third instruction is a message send and sends requiring dictionary lookups occur every 6.67 bytecodes. Of the sends needing dictionary searches, 36.64% invoked primitives, and the rest resulted in the execution of a Smalltalk method which, along with process switches, accounted for a context switch every 6.50 bytecodes.

Of the special sends, 78.92% are arithmetic and logical operations. The remaining special sends fell further into the minority by a change in the third test image release which required 11 of the 16 cases to look up the selector in a special messages array rather than invoking a primitive directly. As a result, some of these special sends actually result in the execution of Smalltalk code if the selector in the array does not bind to a primitive for the receiver in question. Of course this allows one to dynamically modify system behavior or to change this set of primitives if future requirements should dictate. These other special sends include high level operations such as instantiation, indexing, length and class query, block evaluation, and point coordinates.
<table><caption>Table 12.3 Frequency of Message Sends by Flavor</caption><thead><tr><td>Flavor of Send</td><td>Percentage</td><td>Cumulative Percentage</td></tr></thead><tbody><tr><td>primitive</td><td>66.86%</td><td>66.86%</td></tr><tr><td>method</td><td>21.42%</td><td>88.28%</td></tr><tr><td>pseudo-primitive</td><td>11.72%</td><td>100.00%</td></tr></tbody></table>

There are three flavors of message sends:

* **Primitive** Those which invoke C or machine code routines.

* **Method** Those which activate Smalltalk code.

* **Pseudo-primitive** Those which return directly after performing an operation encoded in the header of the compiled method.

The method sends are the best known of those in Table 12.3. At about one-fifth of all sends executed, this indicates the amount of optimization possible through the proper choice of the set of primitives. The pseudo-primitives, which offer an inexpensive way to access instance fields, execute half as frequently as traditional method sends. In all, 78.58% of sends do not *immediately* result in the execution of Smalltalk code. This does not take into account those primitives which fail and then activate Smalltalk backup code (discussed later).

<table><caption>Table 12.4 Frequency of Primitive Method Invocations by Type</caption><thead><tr><td>Type of Primitive</td><td>Percentage</td><td>Cumulative Percentage</td></tr></thead><tbody><tr><td>arithmetic</td><td>56.30%</td><td>56.30%</td></tr><tr><td>selector</td><td>28.66%</td><td>84.96%</td></tr><tr><td>common</td><td>15.04%</td><td>100.00%</td></tr></tbody></table>

Primitive invocations also break down into three categories:

<table><tr><td>Arithmetic</td><td>Arithmetic and logical operations invoked with no lookup.</td></tr><tr><td>Common</td><td>Operations invoked without lookup in the special messages array.</td></tr><tr><td>Selector</td><td>Those sends where selector lookup associated a primitive with the method.</td></tr></table>

As one might expect, the arithmetic primitive invocations dominate the statistics in Table 12.4. Overall, 71.34% of primitive invocations are *direct* from bytecode dispatch and require no special handling.
<table><caption>Table 12.5 Failures of Primitive Methods by Type</caption><thead><tr><td>Type of Primitive</td><td>Percentage</td><td>Cumulative Percentage</td></tr></thead><tbody><tr><td>arithmetic</td><td>81.36%</td><td>81.36%</td></tr><tr><td>selector</td><td>15.93%</td><td>97.29%</td></tr><tr><td>common</td><td>2.71%</td><td>100.00%</td></tr></tbody></table>

Several interesting figures arise from Table 12.5 which shows primitive failures by type. Only 4.49% of primitive operations fail, and most of these are the result of small integer arithmetic range violations. In fact, arithmetic primitives are 2.6 times more likely to fail than selector primitives and 8 times more likely than common primitives. The true figure for arithmetic failures is probably even higher because we did not implement certain primitives in the selector category (e.g., large integer arithmetic) and an invocation of one of them leads directly to a primitive failure. Still the failure rate for arithmetic primitives is only 6.49%, a testament to the utility of signed 15-bit arithmetic.

<table><caption>Table 12.6 Frequency of Message Sends by Flavor (adjusted for primitive failures)</caption><thead><tr><td>Flavor of Send</td><td>Percentage</td><td>Cumulative Percentage</td></tr></thead><tbody><tr><td>successful primitive</td><td>63.86%</td><td>63.86%</td></tr><tr><td>method and primitive backup</td><td>24.42%</td><td>88.28%</td></tr><tr><td>pseudo-primitive</td><td>11.72%</td><td>100.00%</td></tr></tbody></table>

Comparing Table 12.6 with Table 12.3, we see that primitive failures account for only a three percent increase in the number of Smalltalk methods activated. This is a very small price to pay for significantly better performance than equivalent Smalltalk routines.

<table><caption>Table 12.7 Send Bytecode Frequency by Category</caption><thead><tr><td>Send Category</td><td>Static %</td><td>Dynamic %</td><td>Cumulative</td></tr></thead><tbody><tr><td>special arithmetic</td><td>19.00%</td><td>37.65%</td><td>37.65%</td></tr><tr><td>selector send</td><td>53.81%</td><td>32.71%</td><td>70.36%</td></tr><tr><td>common send</td><td>19.74%</td><td>27.21%</td><td>97.57%</td></tr><tr><td>extended selector</td><td>7.45%</td><td>2.43%</td><td>100.00%</td></tr></tbody></table>

The SVM send instructions fall into the four categories listed in Table 12.7.
1. *Special Arithmetic*. Arithmetic and logical operations invoked with no selector lookup. Their dynamic frequency is twice the static, indicating the popularity of these operations. Together with the common send instructions, these dominate dynamic frequency at over 64%.

2. *Common Send*. Special operations which either execute directly (five cases) or indirectly through the lookup of a selector in the special messages array. Although these bytecodes have a higher static frequency than special arithmetic sends, they execute 10% less of the time.

3. *Selector Send*. An instruction specifying where the selector is found in the literal frame of the compiled method. These sends can access the first 16 literal selectors in the compiled method, and they take 0, 1, or 2 arguments. The static frequency concurs with our flavor analysis as selector send bytecodes constitute more than 50% of all sends in methods, but less than one-third of execution.

4. *Extended Selector*. These are 2- and 3-byte extended versions of the regular selector sends for greater literal access range and/or larger numbers of arguments. They come in two flavors: one is an ordinary message send to receiver; the other starts message lookup in the superclass of the receiver. The 2-byte version can access the first 16 selectors with 0 to 7 arguments. The 3-byte version allocates a byte to the selector index and the argument count, with a range of 0 to 255 for each. These are rarely executed so their static frequency is triple the execution rate.

<table><caption>Table 12.8 Send Bytecode Frequency</caption><thead><tr><th>Send Bytecode</th><th>Static %</th><th>Dynamic %</th><th>Cumulative</th></tr></thead><tbody><tr><td>+</td><td>4.10%</td><td>12.74%</td><td>12.74%</td></tr><tr><td>selector 0, no args</td><td>5.84%</td><td>9.01%</td><td>21.75%</td></tr><tr><td>at:</td><td>2.67%</td><td>7.18%</td><td>28.93%</td></tr><tr><td>= =</td><td>3.11%</td><td>5.66%</td><td>34.59%</td></tr><tr><td>-</td><td>2.87%</td><td>5.64%</td><td>40.23%</td></tr><tr><td>&lt; =</td><td>0.64%</td><td>4.61%</td><td>44.84%</td></tr><tr><td>selector 1, no args</td><td>4.16%</td><td>3.66%</td><td>48.50%</td></tr><tr><td>&gt;</td><td>1.09%</td><td>3.38%</td><td>51.88%</td></tr><tr><td>=</td><td>3.13%</td><td>3.28%</td><td>55.16%</td></tr><tr><td>selector 0, 1 arg</td><td>5.61%</td><td>2.97%</td><td>58.13%</td></tr><tr><td>x</td><td>0.56%</td><td>2.73%</td><td>60.86%</td></tr><tr><td>y</td><td>0.45%</td><td>2.71%</td><td>63.57%</td></tr><tr><td>selector 0, 2 args</td><td>1.93%</td><td>2.42%</td><td>65.99%</td></tr></tbody></table>
<table><caption>Table 12.8 (Cont.)</caption><thead><tr><th>Send Bytecode</th><th>Static %</th><th>Dynamic %</th><th>Cumulative</th></tr></thead><tbody><tr><td>selector 1, 1 arg</td><td>3.10%</td><td>2.17%</td><td>68.16%</td></tr><tr><td>@</td><td>2.11%</td><td>2.07%</td><td>70.23%</td></tr><tr><td>all others (66)</td><td>58.63%</td><td>29.77%</td><td>100.00%</td></tr></tbody></table>

Table 12.8 is a closer look at the send bytecodes. Addition (+) is the most popular message sent, executing at triple its static frequency. However, a selector send follows closely revealing the importance of the more flexible versions in spite of all the special cases. The next two entries in the table are primitive sends for array access (at:) and object equivalence (==). The three other primitive sends in the table all deal with points—creation and access. The graphical nature of the Smalltalk-80 user interface increases the use of the coordinate point so that messages for point handling account for over 7.5% of all messages sent. Overall, the selector sends have much higher static frequencies than the rest.

<table><caption>Table 12.9 Special Arithmetic Send Bytecode Frequency</caption><thead><tr><th>Bytecode</th><th>Static %</th><th>Dynamic %</th><th>Cumulative</th></tr></thead><tbody><tr><td>+</td><td>21.56%</td><td>33.85%</td><td>33.85%</td></tr><tr><td>-</td><td>15.11%</td><td>14.96%</td><td>48.81%</td></tr><tr><td>&lt;=</td><td>3.35%</td><td>12.26%</td><td>61.07%</td></tr><tr><td>&gt;</td><td>5.74%</td><td>8.96%</td><td>70.03%</td></tr><tr><td>=</td><td>16.47%</td><td>8.71%</td><td>78.74%</td></tr><tr><td>@</td><td>11.12%</td><td>5.50%</td><td>84.24%</td></tr><tr><td>&lt;</td><td>4.92%</td><td>4.53%</td><td>88.77%</td></tr><tr><td>bitAnd:</td><td>2.01%</td><td>2.62%</td><td>91.39%</td></tr><tr><td>bitShift:</td><td>1.96%</td><td>2.42%</td><td>93.81%</td></tr><tr><td>&gt;=</td><td>1.94%</td><td>1.79%</td><td>95.60%</td></tr><tr><td>\</td><td>1.53%</td><td>1.57%</td><td>97.17%</td></tr><tr><td>//</td><td>3.35%</td><td>1.06%</td><td>98.23%</td></tr><tr><td>*</td><td>6.24%</td><td>0.86%</td><td>99.09%</td></tr><tr><td>~=</td><td>2.68%</td><td>0.63%</td><td>99.72%</td></tr><tr><td>bitOr:</td><td>0.29%</td><td>0.26%</td><td>99.98%</td></tr><tr><td>/</td><td>1.75%</td><td>0.02%</td><td>100.00%</td></tr></tbody></table>

The statistics for special arithmetic sends in Table 12.9 are comparable to those for the computational instructions of conventional languages and architectures². Additions occur over one-third of the time, and to-
gether with subtractions, comprise nearly half of arithmetic send execution. The sixth entry is a bit unusual—an instruction for creating a point from the receiver as the X value and the argument as the Y value. Multiplication and division account for only about 3.5% of special arithmetic sends. The static and dynamic frequencies show interesting differences. The execution frequency of <= is four times the static, while the opposite is true for @ and = where the static frequencies are twice the dynamic. The multiplication bytecode is fifth in static frequency with a rate eight times its execution percentage.

<table><caption>Table 12.10 Common Send Bytecode Frequency</caption><thead><tr><th>Bytecode</th><th>Static %</th><th>Dynamic %</th><th>Cumulative</th></tr></thead><tbody><tr><td>at:</td><td>13.51%</td><td>26.41%</td><td>26.41%</td></tr><tr><td>= =*</td><td>15.77%</td><td>20.81%</td><td>47.22%</td></tr><tr><td>x</td><td>2.85%</td><td>10.02%</td><td>57.24%</td></tr><tr><td>y</td><td>2.26%</td><td>9.95%</td><td>67.19%</td></tr><tr><td>value:*</td><td>2.09%</td><td>6.86%</td><td>74.05%</td></tr><tr><td>size</td><td>9.71%</td><td>4.91%</td><td>78.96%</td></tr><tr><td>blockCopy:*</td><td>19.29%</td><td>4.75%</td><td>83.71%</td></tr><tr><td>new</td><td>10.59%</td><td>4.57%</td><td>88.28%</td></tr><tr><td>at:put:</td><td>7.18%</td><td>3.38%</td><td>91.66%</td></tr><tr><td>class*</td><td>2.90%</td><td>3.05%</td><td>94.71%</td></tr><tr><td>nextPut:</td><td>4.95%</td><td>1.87%</td><td>96.58%</td></tr><tr><td>value*</td><td>2.67%</td><td>1.48%</td><td>98.06%</td></tr><tr><td>new:</td><td>4.40%</td><td>1.47%</td><td>99.53%</td></tr><tr><td>next</td><td>1.77%</td><td>0.47%</td><td>100.00%</td></tr><tr><td>atEnd</td><td>0.00%</td><td>0.00%</td><td>100.00%</td></tr></tbody></table>

Table 12.10 lists the frequencies for common send bytecodes. The selectors marked by an asterisk in the table are those messages which do not require any dictionary lookup before invoking a primitive. Those without the asterisk get their selectors from a special messages array and then proceed via the normal send process. Array access (at:) and object equivalence (==) constitute nearly one half of common send execution. Although array element loads (at:) are eight times more frequent than array element stores (at:put:), the opposite is true for streams. Writes on streams (nextPut:) are four times more frequent than reads (next). Nearly all of the common send instructions show significant differences between static and dynamic frequencies, ranging as high as a 4 to 1 ratio in both directions.
<table><caption>Table 12.11 Primitive Method Invocation Frequency
(excluding arithmetic primitives)</caption><thead><tr><td>Class &amp; Primitive</td><td>Percentage</td><td>Cumulative Percentage</td></tr></thead><tbody><tr><td>&lt;Object&gt; at:</td><td>25.89%</td><td>25.89%</td></tr><tr><td>&lt;Object&gt; ==</td><td>19.91%</td><td>45.80%</td></tr><tr><td>&lt;BlockContext&gt; value</td><td>8.10%</td><td>53.90%</td></tr><tr><td>&lt;Object&gt; size</td><td>7.78%</td><td>61.68%</td></tr><tr><td>&lt;String&gt; at:</td><td>5.76%</td><td>67.44%</td></tr><tr><td>&lt;Object&gt; at:put:</td><td>5.75%</td><td>73.19%</td></tr><tr><td>&lt;BlockContext&gt; blockCopy:</td><td>4.38%</td><td>77.57%</td></tr><tr><td>&lt;Behavior&gt; new</td><td>4.25%</td><td>81.82%</td></tr><tr><td>&lt;Object&gt; class</td><td>2.81%</td><td>84.63%</td></tr><tr><td>&lt;BitBlt&gt; copyBits</td><td>2.47%</td><td>87.10%</td></tr><tr><td>all others (31)</td><td>12.90%</td><td>100.00%</td></tr></tbody></table>

The 10 primitive methods in Table 12.11 total nearly 90% of all invocations. Array, string, and stream access account for nearly 40% of these. With a few exceptions, the leading non-arithmetic primitives perform very simple functions. The most notable exception is copyBits, a very complex primitive made even more so because of our external graphics display system. Two of the primitives manage block execution and account for over 12% by themselves.

<table><caption>Table 12.12 Superclass Chain Traversals by Length</caption><thead><tr><td>Length of Traversal</td><td>Percentage</td><td>Cumulative Percentage</td></tr></thead><tbody><tr><td>0 (receiver)</td><td>56.20%</td><td>56.20%</td></tr><tr><td>1 (superclass)</td><td>17.36%</td><td>73.56%</td></tr><tr><td>2</td><td>6.72%</td><td>80.28%</td></tr><tr><td>3</td><td>6.18%</td><td>86.46%</td></tr><tr><td>4</td><td>5.33%</td><td>91.79%</td></tr><tr><td>5</td><td>4.32%</td><td>96.11%</td></tr><tr><td>7</td><td>2.11%</td><td>98.22%</td></tr><tr><td>6</td><td>1.67%</td><td>99.89%</td></tr><tr><td>8, 9 &amp; 10</td><td>0.11%</td><td>100.00%</td></tr></tbody></table>

Table 12.12 gives the number of links traversed to look up messages in the dictionaries of superclasses. The zero category corresponds to messages understood by the class of their receiver and therefore no links are traversed. The average traversal distance is 1.18, but the majority of messages never go to the superclass. Nearly 14% search four or more dictionaries, thus skewing the figures in that direction.
<table><caption>Table 12.13 Message Dictionary Probes by Number</caption><thead><tr><th>Number of Probes</th><th>Percentage</th><th>Cumulative Percentage</th></tr></thead><tbody><tr><td>1 (direct hit)</td><td>61.16%</td><td>61.16%</td></tr><tr><td>2</td><td>11.97%</td><td>73.13%</td></tr><tr><td>4</td><td>4.71%</td><td>77.84%</td></tr><tr><td>3</td><td>4.08%</td><td>81.92%</td></tr><tr><td>5</td><td>2.54%</td><td>84.46%</td></tr><tr><td>9</td><td>1.45%</td><td>85.91%</td></tr><tr><td>8</td><td>1.41%</td><td>87.32%</td></tr><tr><td>12</td><td>1.34%</td><td>88.66%</td></tr><tr><td>23</td><td>1.28%</td><td>89.94%</td></tr><tr><td>6</td><td>1.19%</td><td>91.13%</td></tr><tr><td>all others (31)</td><td>8.87%</td><td>100.00%</td></tr></tbody></table>

The statistics in Table 12.13 for message lookup are for method cache misses. Our method cache hit rate is 93% for a 509 element cache. There is an average of 3.89 probes into each message dictionary after a cache miss. Combined with the superclass chain traversals, each send missing the cache requires an average of 8.48 probes of message dictionaries, searching the message dictionaries of the class and superclass of the receiver in the typical case. The appearance of figures over 10 in the table is the result of very long hash collision chains. If a message dictionary is nearly full this will happen, but it is more likely that the very simple hash function used by Smalltalk is causing many collisions.

<table><caption>Table 12.14 Push Bytecode Frequency by Category</caption><thead><tr><th>Push Category</th><th>Static %</th><th>Dynamic %</th><th>Cumulative</th></tr></thead><tbody><tr><td>temporary variable</td><td>35.45%</td><td>44.45%</td><td>44.45%</td></tr><tr><td>special</td><td>33.95%</td><td>29.57%</td><td>74.02%</td></tr><tr><td>receiver variable</td><td>11.30%</td><td>17.19%</td><td>91.21%</td></tr><tr><td>extended (all)</td><td>1.54%</td><td>2.97%</td><td>94.18%</td></tr><tr><td>literal variable</td><td>8.97%</td><td>2.96%</td><td>97.14%</td></tr><tr><td>literal constant</td><td>8.79%</td><td>2.86%</td><td>100.00%</td></tr></tbody></table>

Push and Pop Bytecodes

Push instructions can access four different memory areas in the Smalltalk-80 execution environment:

1. *Temporary Variable*. The area just above the stack in a method context is the temporary frame where the Smalltalk-80 language passes arguments and allocates local and temporary variables.
2. *Receiver Variable*. The instance variables of the receiver of the message.

3. *Literal Variable*. A variable accessed through a pointer to an association in the literal frame of a compiled method.

4. *Literal Constant*. A constant value in the literal frame of a compiled method.

Table 12.14 lists the frequencies of these plus the special push instructions for frequently used constants and environment values, such as self (the receiver of the current message). The extended category includes all four flavors of push instructions. The static frequencies for literal access are triple the execution rate, which is less than 6%. Literal constant access is particularly low because of the push constant instructions for 2, 1, 0, -1, false, true, and nil. These seven bytecodes alone constitute 15.71% of all pushes.

The access ranges of push instructions vary. The standard temporary and receiver variable push instructions can access the first 16 entries, while the literal frame pushes have a range of 32. The extended push instructions can access up to 64 entries. When this range is not enough, other tactics are necessary. For example, to access instance variable number 73 of the receiver, we can do the following:

1. Push self [the Oop of the receiver]

2. Push literal constant n [73]

3. Send at:

This takes two pushes and a primitive invocation, so one can appreciate the value of the extended push instructions.

<table><caption>Table 12.15 Push Bytecode Frequency</caption><thead><tr><td>Push Bytecode</td><td>Static %</td><td>Dynamic %</td><td>Cumulative</td></tr></thead><tbody><tr><td>temporary variable 0</td><td>14.19%</td><td>14.61%</td><td>14.61%</td></tr><tr><td>self (receiver)</td><td>14.26%</td><td>12.92%</td><td>27.53%</td></tr><tr><td>temporary variable 1</td><td>7.70%</td><td>10.70%</td><td>38.23%</td></tr><tr><td>temporary variable 2</td><td>4.81%</td><td>7.79%</td><td>46.02%</td></tr><tr><td>constant 1</td><td>5.92%</td><td>7.34%</td><td>53.36%</td></tr><tr><td>receiver variable 1</td><td>2.20%</td><td>3.88%</td><td>57.24%</td></tr><tr><td>receiver variable 0</td><td>2.19%</td><td>3.82%</td><td>61.06%</td></tr><tr><td>constant nil</td><td>3.03%</td><td>3.33%</td><td>64.39%</td></tr><tr><td>extended (all)</td><td>1.54%</td><td>2.96%</td><td>67.35%</td></tr><tr><td>constant 0</td><td>4.24%</td><td>2.84%</td><td>70.19%</td></tr></tbody></table>
<table><caption>Table 12.15 (Cont.)</caption><thead><tr><th>Push Bytecode</th><th>Static %</th><th>Dynamic %</th><th>Cumulative</th></tr></thead><tbody><tr><td>temporary variable 3</td><td>2.89%</td><td>2.67%</td><td>72.86%</td></tr><tr><td>temporary variable 6</td><td>0.95%</td><td>2.48%</td><td>75.34%</td></tr><tr><td>receiver variable 14</td><td>0.46%</td><td>2.35%</td><td>77.69%</td></tr><tr><td>temporary variable 4</td><td>1.87%</td><td>1.99%</td><td>79.68%</td></tr><tr><td>receiver variable 2</td><td>1.75%</td><td>1.65%</td><td>81.33%</td></tr><tr><td>temporary variable 7</td><td>0.59%</td><td>1.62%</td><td>82.95%</td></tr><tr><td>temporary variable 5</td><td>1.40%</td><td>1.49%</td><td>84.44%</td></tr><tr><td>literal variable 2</td><td>2.10%</td><td>1.30%</td><td>85.74%</td></tr><tr><td>all others (85)</td><td>27.91%</td><td>14.26%</td><td>100.00%</td></tr></tbody></table>

Pushes involving the receiver and the first three temporary slots account for nearly half of execution in Table 12.15. These top four entries correspond roughly to usage of the first four parameters or local variables in an ordinary language subroutine. After the special push of constant 1, there is a steep drop in execution percentage. There is little disagreement between static and dynamic frequencies for these instructions.

<table><caption>Table 12.16 Special Push Bytecode Frequency</caption><thead><tr><th>Special Push Bytecode</th><th>Static %</th><th>Dynamic %</th><th>Cumulative</th></tr></thead><tbody><tr><td>self (receiver)</td><td>42.00%</td><td>43.70%</td><td>43.70%</td></tr><tr><td>constant 1</td><td>17.45%</td><td>24.82%</td><td>68.52%</td></tr><tr><td>constant nil</td><td>8.92%</td><td>11.26%</td><td>79.78%</td></tr><tr><td>constant 0</td><td>12.50%</td><td>9.61%</td><td>89.39%</td></tr><tr><td>constant 2</td><td>4.02%</td><td>3.98%</td><td>93.37%</td></tr><tr><td>active context</td><td>7.59%</td><td>3.13%</td><td>96.50%</td></tr><tr><td>constant false</td><td>3.11%</td><td>1.91%</td><td>98.41%</td></tr><tr><td>constant true</td><td>1.97%</td><td>1.45%</td><td>99.86%</td></tr><tr><td>constant -1</td><td>0.53%</td><td>0.09%</td><td>99.95%</td></tr><tr><td>stack top</td><td>1.91%</td><td>0.05%</td><td>100.00%</td></tr></tbody></table>

The special pushes offer a shortcut for popular push operations. When it determines a value to be constant, the compiler can use the special push instructions to avoid additional memory accesses and to conserve space in the literal frame where it usually puts constants. However, in some cases the special pushes are the only mechanism for reaching cer-
tain environment values, such as the receiver of the current message and the active context. In Table 12.16, push self accounts for over 40% of special push execution, and the top four comprise nearly 90%. Both push -1 and duplicate stack top have a combined static frequency of nearly 2.5% (0.83% overall), but execute only once every 2400 pushes (or 5400 bytecodes).

<table><caption>Table 12.17 Pop and Store Bytecode Frequency by Category</caption><thead><tr><td>Pop & Store Category</td><td>Static %</td><td>Dynamic %</td><td>Cumulative</td></tr></thead><tbody><tr><td>pop and store temporary variable</td><td>25.16%</td><td>36.51%</td><td>36.51%</td></tr><tr><td>pop stack top</td><td>52.77%</td><td>22.36%</td><td>58.87%</td></tr><tr><td>pop and store receiver variable</td><td>7.84%</td><td>16.30%</td><td>75.17%</td></tr><tr><td>extended pop and store (all)</td><td>8.15%</td><td>13.96%</td><td>89.13%</td></tr><tr><td>extended store (all)</td><td>6.08%</td><td>10.87%</td><td>100.00%</td></tr></tbody></table>

The pop and store instructions in Table 12.17 roughly parallel the push operations, with a few differences. The SVM prohibits storing directly into the literal frame of compiled methods, but one can modify literal variables through their association in the literal frame via the extended pop and store instructions. In addition, the range of the regular pop and store instructions for temporary and receiver variables is 8 entries instead of 16. Because of these factors, the extended versions of the instructions total nearly 25% of all pop and stores executed. The pop stack top bytecode is also almost one-quarter, leaving regular temporary and receiver variable access at a little over half. The story is different for static frequencies where pop stack top leads at over 50%, more than double its dynamic rate. The other categories show dynamic frequencies from 40% to 100% higher than their static figures.

The difference in execution between loads and stores on this system is interesting. The figures for temporary and receiver variable operations are very similar. However, the extended pop and store instructions execute over eight times more frequently than extended pushes (24.83% vs. 2.97%). This is because the only way to modify literal variables is through the extended pop and store instructions, whereas there is a separate regular bytecode for pushing literal variables. In addition, as noted, the range of pop and store instructions is more limited, hence forcing the use of extended instructions more frequently. Finally, popping the stack top is almost 500 times more frequent than duplicating it (22.36% vs. 0.05%).
<table><caption>Table 12.18 Pop and Store Bytecode Frequency</caption><thead><tr><th>Pop & Store Bytecode</th><th>Static %</th><th>Dynamic %</th><th>Cumulative</th></tr></thead><tbody><tr><td>pop stack top</td><td>52.77%</td><td>22.36%</td><td>22.36%</td></tr><tr><td>extended pop and store (all)</td><td>8.15%</td><td>13.96%</td><td>36.32%</td></tr><tr><td>temporary variable 1</td><td>6.53%</td><td>11.76%</td><td>48.08%</td></tr><tr><td>extended store (all)</td><td>6.08%</td><td>10.87%</td><td>58.95%</td></tr><tr><td>temporary variable 2</td><td>5.36%</td><td>9.53%</td><td>68.48%</td></tr><tr><td>receiver variable 1</td><td>1.57%</td><td>4.36%</td><td>72.84%</td></tr><tr><td>receiver variable 0</td><td>1.61%</td><td>3.99%</td><td>76.83%</td></tr><tr><td>receiver variable 4</td><td>0.87%</td><td>3.44%</td><td>80.27%</td></tr><tr><td>temporary variable 6</td><td>1.50%</td><td>3.26%</td><td>83.53%</td></tr><tr><td>temporary variable 4</td><td>2.22%</td><td>3.11%</td><td>86.64%</td></tr><tr><td>temporary variable 3</td><td>3.23%</td><td>2.89%</td><td>89.53%</td></tr><tr><td>temporary variable 7</td><td>0.82%</td><td>2.82%</td><td>92.35%</td></tr><tr><td>all others (7)</td><td>9.29%</td><td>7.65%</td><td>100.00%</td></tr></tbody></table>

Table 12.18 provides a more detailed look at the pop and store bytecodes. Temporary variable 0 is not among the top 12, and in general, the frequency of variable access is not in numeric sequence. In fact, pop and store operations on temporary variable 1 are six times more frequent than those on variable 0 (11.76% vs. 1.82%). This indicates that methods manipulate temporary variables more than arguments, since temporary slot 0 is usually occupied by the first message parameter.

The system spends nearly one-sixth of execution on these transfer of control instructions. The return bytecodes are the most sophisticated of them, having to reset the sender as the active context upon leaving a method. The special case sends have diminished the importance of returns by relegating their use to the relatively small percentage of method sends. We divide the other control transfer bytecodes into branches for the single-byte short versions and jumps for the multiple-byte long ones. These are not very significant either because the tiny size of Smalltalk methods leaves precious little space for much transfer of control.

Return, Branch, and Jump Bytecodes

<table><caption>Table 12.19 Return Bytecode Frequency</caption><thead><tr><th>Return Bytecode</th><th>Static %</th><th>Dynamic %</th><th>Cumulative</th></tr></thead><tbody><tr><td>stack top from Method</td><td>44.90%</td><td>64.83%</td><td>64.83%</td></tr><tr><td>self</td><td>35.54%</td><td>18.82%</td><td>83.65%</td></tr><tr><td>stack top from Block</td><td>14.08%</td><td>8.10%</td><td>91.75%</td></tr></tbody></table>
<table><caption>**Table 12.19 (Cont.)**</caption><thead><tr><td>Return Bytecode</td><td>Static %</td><td>Dynamic %</td><td>Cumulative</td></tr></thead><tbody><tr><td>false</td><td>2.30%</td><td>5.59%</td><td>97.34%</td></tr><tr><td>true</td><td>1.78%</td><td>2.63%</td><td>99.97%</td></tr><tr><td>nil</td><td>1.40%</td><td>0.03%</td><td>100.00%</td></tr></tbody></table>

Nearly three-quarters of all methods and blocks return top of stack as shown in Table 12.19. Most of the rest return self, while a very tiny portion return nil. Although the default return for Smalltalk-80 code is self, such returns account for less than 20%. The static frequencies of return self and stack top from block are nearly double their execution. At the other end, only one of every 3300 methods returns nil, raising doubts as to the value of this variant, which is executed once every 43,802 bytecodes on average.

<table><caption>**Table 12.20 Branch and Jump Bytecode Frequency by Category**</caption><thead><tr><td>Branch & Jump Category</td><td>Static %</td><td>Dynamic %</td><td>Cumulative</td></tr></thead><tbody><tr><td>pop and branch on false</td><td>40.71%</td><td>49.50%</td><td>49.50%</td></tr><tr><td>pop and jump on false</td><td>13.21%</td><td>22.56%</td><td>72.06%</td></tr><tr><td>jump</td><td>27.46%</td><td>21.42%</td><td>93.48%</td></tr><tr><td>branch</td><td>18.62%</td><td>6.52%</td><td>100.00%</td></tr><tr><td>pop and jump on true</td><td>0.00%</td><td>0.00%</td><td>100.00%</td></tr></tbody></table>

Because Smalltalk-80 methods tend to be very short, one expects to find low execution frequencies for long jumps, and the data in Table 12.20 concurs. However, the most frequent unconditional transfers are the long jumps, outnumbering short branches by more than three to one. Overall, the conditional and unconditional short branches account for 57.02% of transfers. The conditional branches and jumps execute over two and a half times more frequently than the unconditional ones. As noted before, the current compiler does not use the pop and jump on true instruction.

<table><caption>**Table 12.21 Branch and Jump Bytecode Frequency**</caption><thead><tr><td>Branch & Jump Bytecode</td><td>Static %</td><td>Dynamic %</td><td>Cumulative</td></tr></thead><tbody><tr><td>jump 0*256 + next</td><td>13.21%</td><td>22.56%</td><td>22.56%</td></tr><tr><td>jump -1*256 + next</td><td>4.21%</td><td>15.01%</td><td>37.57%</td></tr><tr><td>pop and branch on false 2</td><td>11.63%</td><td>13.38%</td><td>50.95%</td></tr></tbody></table>
<table><caption>Table 12.21 (Cont.)</caption><thead><tr><td>Branch & Jump Bytecode</td><td>Static %</td><td>Dynamic %</td><td>Cumulative</td></tr></thead><tbody><tr><td>pop and branch on false 4</td><td>7.76%</td><td>8.53%</td><td>59.48%</td></tr><tr><td>pop and branch on false 3</td><td>6.65%</td><td>7.33%</td><td>66.81%</td></tr><tr><td>pop and branch on false 6</td><td>2.78%</td><td>6.59%</td><td>73.40%</td></tr><tr><td>jump 0*256 + next</td><td>23.20%</td><td>6.39%</td><td>79.79%</td></tr><tr><td>pop and branch on false 1</td><td>3.16%</td><td>5.10%</td><td>84.89%</td></tr><tr><td>pop and branch on false 5</td><td>4.60%</td><td>4.77%</td><td>89.66%</td></tr><tr><td>branch 1</td><td>8.15%</td><td>3.44%</td><td>93.10%</td></tr><tr><td>pop and branch on false 8</td><td>1.74%</td><td>2.81%</td><td>95.91%</td></tr><tr><td>all others (9)</td><td>12.91%</td><td>4.09%</td><td>100.00%</td></tr></tbody></table>

The first two entries in Table 12.21 comprise nearly 90% of all long jumps executed. The rest of the table is dominated by the short conditional branch instruction. There is little consistency to the static and dynamic measurements. For the two unconditional long jumps in the table, the backward jump executes at more than three times its static frequency while the forward jump has a greater static frequency by nearly four to one. The branches and jumps in the *others* category have a low execution frequency but appear statically more than three times as often.

## Memory System Measurements

The performance of the object memory system is vital to a Smalltalk-80 implementation. We recognized this early, and we were able to improve memory system performance substantially through regular analyses of profile data. The following tables are the culmination of this effort.

<table><caption>Table 12.22 Classes in the System by Number of Instances</caption><thead><tr><td>Class of Objects</td><td>Percentage</td><td>Cumulative Percentage</td></tr></thead><tbody><tr><td>CompiledMethod</td><td>25.83%</td><td>25.83%</td></tr><tr><td>Symbol</td><td>21.84%</td><td>47.67%</td></tr><tr><td>Array</td><td>15.45%</td><td>63.12%</td></tr><tr><td>String</td><td>9.11%</td><td>72.23%</td></tr><tr><td>Association</td><td>3.81%</td><td>76.04%</td></tr><tr><td>Point</td><td>2.91%</td><td>78.95%</td></tr><tr><td>ClassOrganizer</td><td>2.80%</td><td>81.75%</td></tr><tr><td>MethodDictionary</td><td>2.80%</td><td>84.55%</td></tr></tbody></table>
<table><caption>Table 12.22 (Cont.)</caption><thead><tr><td>Class of Objects</td><td>Percentage</td><td>Cumulative Percentage</td></tr></thead><tbody><tr><td>Character</td><td>1.66%</td><td>86.21%</td></tr><tr><td>LargePositiveInteger</td><td>1.44%</td><td>87.65%</td></tr><tr><td>RemoteString</td><td>1.40%</td><td>89.05%</td></tr><tr><td>Metaclass</td><td>1.40%</td><td>90.45%</td></tr><tr><td>Float</td><td>1.33%</td><td>91.78%</td></tr><tr><td>TextLineInterval</td><td>1.09%</td><td>92.87%</td></tr><tr><td>all others (296)</td><td>7.13%</td><td>100.00%</td></tr></tbody></table>

Table 12.22 ranks the classes in the system according to the number of extant instances of each. Compiled methods and symbols ( selectors ) comprise nearly half of the objects in the system, and over 75% of the objects are instances of the top five classes. With over 200 classes in the system, this indicates that many have very few instances. In fact, 56.48% of classes (excluding metaclasses) have no instances at all and exist mainly for the behavior inherited by their subclasses; 26.38% have exactly one instance (a system controller, object, or dictionary). In all, 76.38% of all classes have fewer than 10 instances. This is a result of a particular style of Smalltalk programming making extensive use of an existing set of basic classes and certain paradigms.

<table><caption>Table 12.23 Classes in the System by Memory Usage</caption><thead><tr><td>Class of Objects</td><td>Percentage</td><td>Cumulative Percentage</td></tr></thead><tbody><tr><td>CompiledMethod</td><td>34.69%</td><td>34.69%</td></tr><tr><td>Array</td><td>13.19%</td><td>47.88%</td></tr><tr><td>Symbol</td><td>11.72%</td><td>59.60%</td></tr><tr><td>DisplayBitmap</td><td>9.76%</td><td>69.36%</td></tr><tr><td>String</td><td>9.74%</td><td>79.10%</td></tr><tr><td>Bitmap</td><td>8.62%</td><td>87.72%</td></tr><tr><td>MethodDictionary</td><td>4.18%</td><td>91.90%</td></tr><tr><td>ClassOrganizer</td><td>0.88%</td><td>92.78%</td></tr><tr><td>Metaclass</td><td>0.77%</td><td>93.55%</td></tr><tr><td>Dictionary</td><td>0.62%</td><td>94.17%</td></tr><tr><td>Association</td><td>0.60%</td><td>94.77%</td></tr><tr><td>all others (296)</td><td>5.23%</td><td>100.00%</td></tr></tbody></table>

Table 12.23 lists the classes by the amount of memory used by their instances. Compiled methods and symbols occupy nearly half the object space. The percentage for DisplayBitmap depends on the size of the display screen currently in use. In our case, a 640 x 480 pixel bit map was
active. The leading classes result from code (CompiledMethod, Array, Symbol, MethodDictionary and Metaclass) at 64.55% and graphics (DisplayBitmap and Bitmap) at 18.38% for a total of 82.93%.

Object Memory
Access

<table><caption>Table 12.24 Object Memory Accesses by Type</caption><thead><tr><td>Type of Access</td><td>Percentage</td><td>Cumulative Percentage</td></tr></thead><tbody><tr><td>load pointer</td><td>72.45%</td><td>72.45%</td></tr><tr><td>store pointer</td><td>14.84%</td><td>87.29%</td></tr><tr><td>load word</td><td>7.59%</td><td>94.88%</td></tr><tr><td>store word</td><td>4.82%</td><td>99.70%</td></tr><tr><td>load byte</td><td>0.23%</td><td>99.93%</td></tr><tr><td>store byte</td><td>0.07%</td><td>100.00%</td></tr></tbody></table>

The *load pointer* and *store pointer* routines fetch and store object pointers in memory. The word and byte routines deal only with non-pointer 16- and 8-bit quantities. Because our interpreter caches the instruction and stack pointers, the memory access figures in Table 12.24 include neither stack push/pop operations nor bytecode instruction fetch. However, those aspects of execution have well-defined behavior and are easy to monitor. The bias introduced by such factors can be significant. For example, if we include bytecode fetches with the other memory accesses, the share of *load byte* operations increases from 0.23% to 16.90%. This bias tends to cloud the real issues (bytecode fetch, like death and taxes, is inevitable).

These figures show *load pointer* dominating the memory accesses. This is not surprising in an object-oriented memory system. Pointer object accesses accounted for over 87% of all memory traffic. The memory system must endure nearly five accesses per bytecode, a figure which is due partly to the experimental nature of the system. A better implementation of the interpreter could reduce the number of accesses, but that was not our goal.

Load and store operations occur 40 times more frequently for words than for bytes. At 12.41% word accesses seem relatively high since they are not used by the system for any common operations. Instead, the infrequent but massive bit map operations are responsible for this rate of access.

<table><caption>Table 12.25 Load Pointer Operations by Class</caption><thead><tr><td>Class of Object</td><td>Percentage</td><td>Cumulative Percentage</td></tr></thead><tbody><tr><td>MethodContext</td><td>27.55%</td><td>27.55%</td></tr><tr><td>MethodDictionary</td><td>25.06%</td><td>52.61%</td></tr><tr><td>CompiledMethod</td><td>15.70%</td><td>68.31%</td></tr><tr><td>Array</td><td>7.00%</td><td>75.31%</td></tr></tbody></table>
<table><caption>Table 12.25 (Cont.)</caption><thead><tr><td>Class of Object</td><td>Percentage</td><td>Cumulative Percentage</td></tr></thead><tbody><tr><td>Class Array</td><td>4.95%</td><td>80.26%</td></tr><tr><td>BlockContext</td><td>3.11%</td><td>83.37%</td></tr><tr><td>Class String</td><td>1.29%</td><td>84.66%</td></tr><tr><td>Class LargePositiveInteger</td><td>1.25%</td><td>85.91%</td></tr><tr><td>all others (258)</td><td>14.09%</td><td>100.00%</td></tr></tbody></table>

The breakdown of load pointer operations by classes in Table 12.25 points out the memory intensive nature of some operations. The method and block context loads are for receiver and argument passing as well as operations occurring while they are neither the active nor the home context (since access to those are through a cache). The hash probes to the selector portion of message dictionaries comprise part of the method dictionary figure. The compiled method loads are from the literal frame for constants, pointers, and selectors. The array accesses correspond to the method pointer portion of the message dictionary—in other words, the method Oop fetch after a successful cache hit or search.

<table><caption>Table 12.26 Store Pointer Operations by Class</caption><thead><tr><td>Class of Object</td><td>Percentage</td><td>Cumulative Percentage</td></tr></thead><tbody><tr><td>MethodContext</td><td>81.96%</td><td>81.96%</td></tr><tr><td>BlockContext</td><td>8.43%</td><td>90.39%</td></tr><tr><td>Point</td><td>1.95%</td><td>92.34%</td></tr><tr><td>CompositionScanner</td><td>1.85%</td><td>94.19%</td></tr><tr><td>DisplayScanner</td><td>1.23%</td><td>95.42%</td></tr><tr><td>all others (102)</td><td>4.58%</td><td>100.00%</td></tr></tbody></table>

Context initialization, including receiver and argument passing, dominates store pointer operations in Table 12.26. Again this does not include operations on home or active contexts. Graphics and text manipulation consumes the remainder of the stores.

<table><caption>Table 12.27 Load Word Operations by Class</caption><thead><tr><td>Class of Object</td><td>Percentage</td><td>Cumulative Percentage</td></tr></thead><tbody><tr><td>DisplayBitmap</td><td>69.30%</td><td>69.30%</td></tr><tr><td>Bitmap</td><td>30.22%</td><td>99.52%</td></tr><tr><td>Float</td><td>0.40%</td><td>99.92%</td></tr><tr><td>Array</td><td>0.08%</td><td>100.00%</td></tr></tbody></table>
Bit map access constitutes over 99% of word object loads and stores. These bit maps come in two flavors: the bit map associated with the display and subsidiary bit maps used as graphics workspaces to prepare material for BitBlt to the display bit map. In Table 12.27 the relatively high percentage for Bitmap loads results from the transfer of their contents to the display bit map. Accordingly, Table 12.28 shows that store word operations are almost completely devoted to the display bit map, the eventual recipient of all words loaded. This indicates that the majority of graphics operations do not warrant the use of subsidiary bit maps, but rather operate directly on the display bit map.

<table><caption>Table 12.28 Store Word Operations by Class</caption><thead><tr><td>Class of Object</td><td>Percentage</td><td>Cumulative Percentage</td></tr></thead><tbody><tr><td>DisplayBitmap</td><td>97.41%</td><td>97.41%</td></tr><tr><td>Bitmap</td><td>2.06%</td><td>99.47%</td></tr><tr><td>Float</td><td>0.31%</td><td>99.78%</td></tr><tr><td>Array</td><td>0.11%</td><td>99.89%</td></tr><tr><td>LargePositiveInteger</td><td>0.11%</td><td>100.00%</td></tr></tbody></table>

String processing accounts for nearly 75% of all byte loads in Table 12.29. This is a result of the actions of the compiler, decompiler, and text editor. For byte stores, string processing declines by one-third as operations on large integer objects double their share to lead Table 12.30. Compiled methods are rarely the subject of byte accesses, and in general, byte accesses account for a tiny fraction of all types, mainly because the bytecode instruction fetches have direct access to the current compiled method.

<table><caption>Table 12.29 Load Byte Operations by Class</caption><thead><tr><td>Class of Object</td><td>Percentage</td><td>Cumulative Percentage</td></tr></thead><tbody><tr><td>String</td><td>67.96%</td><td>67.96%</td></tr><tr><td>LargePositiveInteger</td><td>25.46%</td><td>93.42%</td></tr><tr><td>Symbol</td><td>6.50%</td><td>99.92%</td></tr><tr><td>CompiledMethod</td><td>0.08%</td><td>100.00%</td></tr></tbody></table>
<table><caption>Table 12.30 Store Byte Operations by Class</caption><thead><tr><td>Class of Object</td><td>Percentage</td><td>Cumulative Percentage</td></tr></thead><tbody><tr><td>LargePositiveInteger</td><td>52.26%</td><td>52.26%</td></tr><tr><td>String</td><td>46.69%</td><td>98.95%</td></tr><tr><td>CompiledMethod</td><td>0.66%</td><td>99.61%</td></tr><tr><td>Symbol</td><td>0.39%</td><td>99.92%</td></tr></tbody></table>

Allocation and
Instantiation

<table><caption>Table 12.31 Object Instantiation Types by Number</caption><thead><tr><td>Type of Instantiation</td><td>Percentage</td><td>Cumulative Percentage</td></tr></thead><tbody><tr><td>pointer object</td><td>98.34%</td><td>98.34%</td></tr><tr><td>byte object</td><td>1.20%</td><td>99.54%</td></tr><tr><td>word object</td><td>0.46%</td><td>100.00%</td></tr></tbody></table>

Pointer objects dominate the instantiation statistics in Table 12.31. Byte objects show a relatively higher rate of instantiation than word objects, probably because of the fine granularity of string processing. Such extremely lopsided statistics lead one to seriously question the need for type distinctions between pointer and non-pointer objects.

<table><caption>Table 12.32 Object Instantiation Types by Amount</caption><thead><tr><td>Type of Instantiation</td><td>Percentage</td><td>Cumulative Percentage</td></tr></thead><tbody><tr><td>pointer object</td><td>99.11%</td><td>99.11%</td></tr><tr><td>word object</td><td>0.49%</td><td>99.60%</td></tr><tr><td>byte object</td><td>0.40%</td><td>100.00%</td></tr></tbody></table>

Table 12.32 shows the percentage of memory allocated to the three object types. Pointer objects lead this category by an overwhelming margin with an even greater share than in Table 12.31. The next places are reversed, with word objects taking second. Though the system instantiates byte objects more frequently than word objects, the average word object is more than three times larger. A breakdown by classes and sizes will further clarify this situation.
<table><caption>Table 12.33 Object Instantiations by Size in Words</caption><thead><tr><td>Size of Instantiation</td><td>Percentage</td><td>Cumulative Percentage</td></tr></thead><tbody><tr><td>18 words</td><td>83.86%</td><td>83.86%</td></tr><tr><td>2 words</td><td>11.47%</td><td>95.33%</td></tr><tr><td>38 words</td><td>1.90%</td><td>97.23%</td></tr><tr><td>1 word</td><td>0.88%</td><td>98.11%</td></tr><tr><td>all others (98)</td><td>1.89%</td><td>100.00%</td></tr></tbody></table>

Instantiations are listed by object field size in Table 12.33. The three most popular sizes exceed 97% of all instantiations, suggesting a correlation with the preceding type figures. These sizes are those chiefly used for small contexts, points, and large contexts, respectively.

<table><caption>Table 12.34 Average Instantiation Size by Type</caption><thead><tr><td>Type of Instantiation</td><td>Average Size in Words</td></tr></thead><tbody><tr><td>pointer object</td><td>16.50 words</td></tr><tr><td>word object</td><td>14.53 words</td></tr><tr><td>byte object</td><td>6.67 words</td></tr><tr><td>all objects</td><td>16.38 words</td></tr></tbody></table>

From Table 12.34, the average allocation size is less than 17 words. The memory system actually stores byte objects in words, sometimes wasting an odd byte, as a relic from Xerox word-addressed memory architectures. However, there are so few byte objects in the system that this waste is not significant. The system averages about one instantiation for every dozen bytecodes executed. This makes for an allocation rate of 1.4 words per bytecode.

<table><caption>Table 12.35 Pointer Object Instantiations by Class</caption><thead><tr><td>Class of Object</td><td>Percentage</td><td>Cumulative Percentage</td></tr></thead><tbody><tr><td>MethodContext</td><td>83.02%</td><td>83.02%</td></tr><tr><td>Point</td><td>8.32%</td><td>91.34%</td></tr><tr><td>BlockContext</td><td>4.18%</td><td>95.52%</td></tr><tr><td>Rectangle</td><td>2.25%</td><td>97.77%</td></tr><tr><td>all others (79)</td><td>2.23%</td><td>100.00%</td></tr></tbody></table>
Method and block contexts comprise over 87% of pointer object instantiations (Table 12.35). In Smalltalk, the system creates and activates a method context for every non-primitive send, thus leading to their prominent position in these statistics. Over 10% of instantiations are for points and rectangles. Applications use points for screen management, since they are the fundamental reference for graphics operations.

<table><caption>Table 12.36 Pointer Object Instantiations by Size</caption><thead><tr><td>Size of Object</td><td>Percentage</td><td>Cumulative Percentage</td></tr></thead><tbody><tr><td>18 words</td><td>85.28%</td><td>85.28%</td></tr><tr><td>2 words</td><td>10.99%</td><td>96.27%</td></tr><tr><td>38 words</td><td>1.93%</td><td>98.20%</td></tr><tr><td>all others (37)</td><td>1.80%</td><td>100.00%</td></tr></tbody></table>

In Table 12.36 note that point size objects (2 words) are more prevalent than the large context size (38 words). The typically short methods of Smalltalk rarely require the deep stack provided by a large context.

The preceding tables actually underestimate the dominance of contexts in memory allocation. Context instantiations consume nearly 97 out of every 100 words allocated by the system. This is because the average context size (18.44 words) exceeds the mean size for all other objects by 14.52 words, thus boosting the context share from 87% to 97%. For pointer objects alone, if we exclude contexts the average object size drops to 3.28 words.

Even though bit maps are the most frequently accessed word objects, the system creates very few of them (only 3.69% of word object instantiations). Floating point objects are the most frequently instantiated word objects and their size (2) is the most popular, both at 96.31%. Most bit maps were at least 100 words, but so few were created that there was little impact on the average size of word objects. As evidence, the average size of word objects instantiated, excluding those of size 2, was 341.72 words.

<table><caption>Table 12.37 Byte Object Instantiations by Class</caption><thead><tr><td>Class of Object</td><td>Percentage</td><td>Cumulative Percentage</td></tr></thead><tbody><tr><td>LargePositiveInteger</td><td>87.12%</td><td>87.12%</td></tr><tr><td>String</td><td>12.59%</td><td>99.71%</td></tr><tr><td>CompiledMethod</td><td>0.17%</td><td>99.88%</td></tr><tr><td>Symbol</td><td>0.12%</td><td>100.00%</td></tr></tbody></table>
Large integers lead byte object instantiations by a substantial margin (Table 12.37), and together with strings, they encompass nearly all of them. Smalltalk does create many large integers because certain system functions use numbers greater than those small integer objects can contain. A number of solutions are possible: redesign those system functions to stay within the small integer range, implement the arbitrary precision arithmetic primitives in firmware or hardware, or increase the range of small integers through an implementation with 32-bit object pointers.

<table><caption>Table 12.38 Byte Object Instantiations by Size in Bytes</caption><thead><tr><td>Size of Object</td><td>Percentage</td><td>Cumulative Percentage</td></tr></thead><tbody><tr><td>2 bytes</td><td>37.91%</td><td>37.91%</td></tr><tr><td>1 byte</td><td>22.94%</td><td>60.85%</td></tr><tr><td>4 bytes</td><td>16.39%</td><td>77.24%</td></tr><tr><td>0 bytes</td><td>8.59%</td><td>85.83%</td></tr><tr><td>3 bytes</td><td>2.46%</td><td>88.29%</td></tr><tr><td>16 bytes</td><td>1.88%</td><td>90.17%</td></tr><tr><td>200 bytes</td><td>1.10%</td><td>91.27%</td></tr><tr><td>9 bytes</td><td>0.91%</td><td>92.18%</td></tr><tr><td>all others (94)</td><td>7.82%</td><td>100.00%</td></tr></tbody></table>

As one might expect, the byte object instantiations exhibited a more uniform distribution of sizes than the other types (Table 12.38). This reflects the fact that text varies greatly even within an application, and could vary with choice of identifiers, different user interfaces, or foreign language systems.

<table><caption>Table 12.39 Reference Count Size by Amount of Memory Reclaimed</caption><thead><tr><td>Size of Count Field</td><td>Percent of Memory Reclaimed</td></tr></thead><tbody><tr><td>2 bits</td><td>65.21%</td></tr><tr><td>3 bits</td><td>83.34%</td></tr><tr><td>4 bits</td><td>92.42%</td></tr><tr><td>5 bits</td><td>95.67%</td></tr><tr><td>6 bits</td><td>97.31%</td></tr><tr><td>7 bits</td><td>99.87%</td></tr></tbody></table>

Memory
Reclamation

The number of bits necessary for reference counts can be important, especially for those considering hardware implementations of count caches and managers (see Chapter 19). Table 12.39 shows that 4 bits
can reclaim over 90% of memory, while 6 bits can manage over 97%. Because of the availability of fast byte access and arithmetic on our host machines, our system uses an 8 bit reference count field in a 16-bit header with additional separate permanent object and count overflow or exemption flag bits. Using our reference-count verifier, we have found only a few non-permanent object counts over 255, while some of the permanent kernel objects have hundreds of references.

<table><caption>Table 12.40 Pointer Chasing for Count Down Operations by Depth</caption><thead><tr><th>Count Down Extent</th><th>Percentage of<br>Count Downs</th><th>Cumulative<br>Percentage</th></tr></thead><tbody><tr><td>exempt</td><td>75.42%</td><td>75.42%</td></tr><tr><td>decremented, > zero</td><td>20.55%</td><td>95.97%</td></tr><tr><td>sons exempt</td><td>0.06%</td><td>96.03%</td></tr><tr><td>son decremented, > zero</td><td>3.52%</td><td>99.55%</td></tr><tr><td>grandsons exempt</td><td>0.20%</td><td>99.75%</td></tr><tr><td>grandson decremented, > zero</td><td>0.18%</td><td>99.93%</td></tr><tr><td>deeper levels (12)</td><td>0.07%</td><td>100.00%</td></tr></tbody></table>

The most expensive side of the dynamic memory management scheme involves reference count decrement and the possible pointer chasing and object deallocation. There are nearly two reference count decrements for every bytecode executed. Table 12.40 shows to what depth the associated pointer chasing went during experiments with the system. Objects with active reference counts accounted for 24.58% of count down invocations and the other 75.42% were on small integers or objects exempt from count management (either permanent or count overflow). Only 4.03% of count down invocations resulted in a decrement to zero and a subsequent deallocation for a rate of one every 13.61 bytecodes. Nearly all of these deallocations caused some pointer chasing to decrement the counts of objects referenced from the fields of the now dead object; the average depth of such pointer chases was 1.13 levels.

<table><caption>Table 12.41 Objects Disposed through Garbage Collection by Class</caption><thead><tr><th>Class of Object</th><th>Percentage of<br>Disposed</th><th>Cumulative<br>Percentage</th></tr></thead><tbody><tr><td>MethodContext</td><td>49.61%</td><td>49.61%</td></tr><tr><td>Process</td><td>18.74%</td><td>68.35%</td></tr><tr><td>BlockContext</td><td>13.49%</td><td>81.84%</td></tr></tbody></table>
<table><caption>Table 12.41 (Cont.)</caption><thead><tr><th>Class of Object</th><th>Percentage of Disposed</th><th>Cumulative Percentage</th></tr></thead><tbody><tr><td>String</td><td>3.83%</td><td>85.67%</td></tr><tr><td>Array</td><td>2.41%</td><td>88.08%</td></tr><tr><td>Association</td><td>2.06%</td><td>90.14%</td></tr><tr><td>all others (28)</td><td>9.86%</td><td>100.00%</td></tr></tbody></table>

Table 12.41 lists the trouble makers: the objects which compose inaccessible cycles. The high ranking of contexts has to do with the problem of passing a block context as an argument to a message and then having it passed down the line a few levels of sends. When it is all over, there is usually a three or four context cycle (almost invariably with at least one block context).

## System Specifications

The size of our implementation varies with the modules included in the compilation. Table 12.42 lists the major system modules and their specifications. The primitive methods use over four times as much code as the bytecode interpreter itself. Although the memory and interpreter modules contain only about one-quarter of the code, they contain almost all of the macros and over half of the procedures in the system. We designed many of these procedures and macros as part of an implementation palette which we drew upon to build the system. As a result of this approach, some of them actually are never used. The extent of our development environment is apparent from its sheer size. The local routine module contains implementation-dependent code for the graphics device among other things.

<table><caption>Table 12.42 Module Specifications in the Hewlett-Packard Smalltalk-84 System</caption><thead><tr><th>Module</th><th># of Macros</th><th># of Procedures</th><th># of Statements</th></tr></thead><tbody><tr><td>primitive methods</td><td>5</td><td>109</td><td>4600</td></tr><tr><td>development environment</td><td>18</td><td>34</td><td>2300</td></tr><tr><td>object memory</td><td>103</td><td>54</td><td>2000</td></tr><tr><td>local routines</td><td>0</td><td>50</td><td>1300</td></tr><tr><td>bytecode interpreter</td><td>88</td><td>22</td><td>1000</td></tr><tr><td>Totals</td><td>214</td><td>269</td><td>11,200</td></tr></tbody></table>
The code size of our system ranges from 50 kilobytes in an optimized version using procedures to 100 kilobytes for the multi-level debug version using in-line macros. The static data area ranges from 300 to 500 kilobytes, and the dynamic allocation from 400 to 500 kilobytes. Total memory usage falls between 750 kilobytes and 1 megabyte. The system installed at HP Labs has 80 kilobytes of code, 350 kilobytes of static data, and 400 kilobytes of dynamic data.

Throughout the implementation process, the execution profile of the system changed continually. At the beginning of July, the system was spending most of its time in the management of object memory. The top 14 procedures consumed 90% of execution time, and object memory management accounted for over half of that. As the implementation progressed, we steadily improved the performance of the most expensive routines. For example, we were able to reduce the overhead of object memory allocation and freeing to less than 6%. In our latest version, the top 14 procedures consume less than two-thirds of the time and one must add up the first 31 routines to reach 90%. One-quarter of the time is spent in bytecode fetch, event recognition, and the execution of all bytecodes except sends. The major object memory operations of allocation, garbage collection, and reference count management consume another 25%. The message send process takes 25% of the time, including message binding and context initialization. Finally, primitive functions use the final quarter of execution time.

<table><caption>Table 12.43 VAX Instructions Executed for Each Bytecode Category</caption><thead><tr><td>Bytecode Category</td><td>Minimum</td><td>Maximum</td><td>Average</td></tr></thead><tbody><tr><td>stack push</td><td>11</td><td>33</td><td>16</td></tr><tr><td>stack pop and store</td><td>2</td><td>47</td><td>28</td></tr><tr><td>return</td><td>43</td><td>81</td><td>46</td></tr><tr><td>branch and jump</td><td>3</td><td>13</td><td>11</td></tr><tr><td>message send</td><td>33</td><td>&gt; 1000</td><td>120</td></tr></tbody></table>

Recently we investigated the VAX assembly code generated from our C modules. The main interpreter loop is 12 instructions long. Table 12.43 lists the additional instructions executed for each instruction category. The cost of maintaining contexts as separate objects plus the message lookup process contributed heavily to the relatively high figures for sends and returns. The 15-bit signed arithmetic required for small integer objects was also very expensive to implement on the VAX.

The performance of the system also changed substantially over the course of several months. By the first week in July 1981, our system
was executing around 500 bytecodes per CPU second with slow object memory, and over 1000 bytecodes per CPU second with fast memory. A week later we were at 750/1500 bytecodes per CPU second (fast/slow memory versions). By early September, the interpreter was executing better than 2000 bytecodes per CPU second (fast memory version). Two weeks later it had increased to 2800 bytecodes per CPU second. The fifth version of HP Smalltalk boosted this to 4000 bytecodes per second. The final version of HP Smalltalk-84 performs at 5000 bytecodes per second on the average, with a peak rate around 25,000.

<table><caption>Table 12.44 Hewlett-Packard Smalltalk-84 testStandardTests Benchmark Results</caption><thead><tr><th>Test</th><th>Description</th><th>Iterations</th><th>Seconds</th><th>Speed</th></tr></thead><tbody><tr><td>LoadInstVar</td><td>load instance variable</td><td>20,000</td><td>3.183</td><td>12,570</td></tr><tr><td>LoadLiteralIndirect</td><td>load literal indirect</td><td>20,000</td><td>3.500</td><td>11,430</td></tr><tr><td>LoadLiteralNRef</td><td>load literal constant</td><td>20,000</td><td>3.350</td><td>11,940</td></tr><tr><td>LoadQuickConstant</td><td>load</td><td>100,000</td><td>15.950</td><td>12,540</td></tr><tr><td>LoadTempNRef</td><td>load 1 as a temp</td><td>20,000</td><td>3.384</td><td>11,820</td></tr><tr><td>LoadTempRef</td><td>load 0@0</td><td>20,000</td><td>3.851</td><td>10,390</td></tr><tr><td>PopStoreInstVar</td><td>store 1 in an inst. var.</td><td>200,000</td><td>24.083</td><td>16,610</td></tr><tr><td>PopStoreTemp</td><td>store 1 in a temp</td><td>200,000</td><td>23.600</td><td>16,950</td></tr><tr><td>16bitArith</td><td>add 20000 plus 20000</td><td>10,000</td><td>442.783</td><td>3730</td></tr><tr><td>3div4</td><td>divide 3 by 4</td><td>100,000</td><td>36.320</td><td>11,010</td></tr><tr><td>3plus4</td><td>add 3 plus 4</td><td>100,000</td><td>27.752</td><td>14,410</td></tr><tr><td>3times4</td><td>multiply 3 times 4</td><td>100,000</td><td>30.884</td><td>12,950</td></tr><tr><td>LargeIntArith</td><td>add 80000 plus 80000</td><td>1000</td><td>47.034</td><td>4000</td></tr><tr><td>ActivationReturn</td><td>activations and returns</td><td>16,383</td><td>42.084</td><td>4090</td></tr><tr><td>ShortBranch</td><td>short branch on false</td><td>100,000</td><td>14.850</td><td>26,940</td></tr><tr><td>WhileLoop</td><td>simple while loop</td><td>10,000</td><td>7.800</td><td>11,540</td></tr><tr><td>ArrayAt</td><td>send at: to an array</td><td>20,000</td><td>15.000</td><td>5330</td></tr><tr><td>ArrayAtPut</td><td>send at:put: to an array</td><td>20,000</td><td>17.884</td><td>5590</td></tr><tr><td>Size</td><td>send size to a string</td><td>20,000</td><td>11.367</td><td>5280</td></tr><tr><td>StringAt</td><td>send at: to a string</td><td>20,000</td><td>17.284</td><td>4630</td></tr><tr><td>StringAtPut</td><td>send at:put: to a string</td><td>20,000</td><td>18.983</td><td>5270</td></tr><tr><td>StringReplace</td><td>replace part of a string</td><td>5000</td><td>67.385</td><td>4630</td></tr><tr><td>BlockCopy</td><td>send blockCopy: 0</td><td>20,000</td><td>22.000</td><td>3640</td></tr><tr><td>Class</td><td>send class to a point</td><td>20,000</td><td>4.334</td><td>13,840</td></tr><tr><td>Creation</td><td>send new to Point</td><td>20,000</td><td>16.608</td><td>3610</td></tr><tr><td>LoadThisContext</td><td>load a context</td><td>20,000</td><td>4.620</td><td>8660</td></tr><tr><td>PointX</td><td>send x to a point</td><td>20,000</td><td>7.867</td><td>7630</td></tr><tr><td>StreamNext</td><td>send next to a stream</td><td>20,000</td><td>23.934</td><td>2510</td></tr></tbody></table>
<table><caption>Table 12.44 (Cont.)</caption><thead><tr><td>Test</td><td>Description</td><td>Iterations</td><td>Seconds</td><td>Speed</td></tr></thead><tbody><tr><td>StreamNextPut</td><td>send nextPut: to a stream</td><td>20,000</td><td>28.534</td><td>2800</td></tr><tr><td>Value</td><td>send value to a block</td><td>20,000</td><td>31.433</td><td>1910</td></tr><tr><td>Compiler</td><td>compile dummy method</td><td>5</td><td>140.932</td><td>3890</td></tr><tr><td>Deccompiler</td><td>decompile Form and Class</td><td>1</td><td>645.200</td><td>3710</td></tr><tr><td>Inspect</td><td>create an inspector</td><td>1</td><td>10.500</td><td>3540</td></tr><tr><td>TextFormatting</td><td>format a bunch of text</td><td>5</td><td>63.633</td><td>4030</td></tr><tr><td>TextEditing</td><td>text replacement</td><td>20</td><td>215.667</td><td>3120</td></tr></tbody></table>

Table 12.44 gives the results of running the testStandardTests set of benchmarks on the HP Smalltalk-84 system. Note that this is an earlier version of the benchmarks than the one in the current Smalltalk-80 image. The table includes the time in seconds reported by Smalltalk for running each entire test, and the speed of execution in bytecodes per second. We ran the tests on a single-user VAX-11/780 with 4 megabytes main memory under 4.1BSD UNIX. The system was in a normal configuration with display, keyboard, and mouse active. Clearly, the primitive method situation is the most serious. The benchmarks for primitive methods averaged about 5000 bytecodes per second, seriously limiting opportunities for greater speed.

## Conclusion

Our curiosity about the Smalltalk-80 system had lead us down a primrose path. When the termination of the project washed away the path, we traded in our programming language robes for the lab coats of the pathologist. The result of our post mortem was simple: there was little hope for performance high enough to lure users away from traditional programming systems. Although we did not have the luxury of iterating and refining our implementation, the experience of those who did is very discouraging. No one in the test program was able to achieve performance considerably above 25 KIPS. Even with microcode assist, it is difficult to imagine an implementation performing at better than 50% of native mode operation. In our experience, though users like the functionality of a Smalltalk system, they are unwilling to accept a significant loss in performance.
**Acknowledgments**

The analysis of the Smalltalk-80 system at Hewlett-Packard Laboratories was basically a post-mortem. Nearly all of the work described in this report happened after the project terminated. I appreciate the patience and understanding of my management during the period when I spent my spare time generating and analyzing the body of statistics.

**References**

1. Clark, D. W., and Levy, H. M., "Measurement and Analysis of Instruction Use in the VAX-11/780", Proceedings of the Ninth Annual Symposium on Computer Architecture, pp. 9-17, Austin, TX, 1982.

2. *Ibid.*
An Assessment of
Method-Lookup Caches
for Smalltalk-80
Implementations

Thomas J. Conroy

Eduardo Pelegri-Llopart

Computer Science Division

Department of Electrical Engineering and

Computer Sciences

University of California, Berkeley

A unique feature of the Smalltalk-80 language is the dynamic binding of methods to a message based on the class of its receiver. This binding requires a lookup of the selector in the message dictionaries of the superclass chain for the receiver. A way to avoid this time-consuming process is to cache the most frequently used information. In this paper, we present an assessment of the cost effectiveness of this mechanism. A theoretical analysis characterizes the behavior of the cache in terms of variables dependent on both the particular implementation and on the Smalltalk code being executed. One result is that the benefits of the cache heavily depend on the relation of the speed of the implementation to the speed of the cache accesses, and also on the instruction mix being executed. For software implementations of virtual machines, a method-cache can greatly enhance performance. We then present the implementation of the software method-cache in BS, the Smalltalk-80 implementation at UC Berkeley (see Chapter 11). Measurements from this implementation show that the cache increased execution speed by 37%.
## Introduction

A unique feature of the Smalltalk-80 language is the dynamic binding of methods based on the class of the receiver. Conceptually, given a receiver and a message selector, the actions to perform are¹,²:

1. Determine the class of the receiver,

2. Search for the message selector in the message dictionaries of the receiver's superclass chain, and

3. Retrieve the method associated with the message selector in the dictionary where the search succeeded.

A direct implementation of this lookup process is time-consuming since a large number of bytecodes involve method-lookup. A solution to this problem is to cache³ the result of the whole lookup process. A cache can provide a fast by-pass of the lengthy search.

A method cache stores combinations of receivers and message selectors, allowing look-ups to be retrieved quickly when the combinations needed for the look-up are in the cache. For those combinations not found in the cache, a full look-up has to be done. An additional overhead present in caching is the cost of trying to keep the more frequently required combinations on the cache. Clearly, the feasibility of this technique depends on how often the bypass succeeds and the relative cost of each alternative.

The effect of the technique on the performance of an implementation is related to the cost of look-ups, the cost of the remaining components and the relative occurrence of each part. In this short paper we present an assessment of this cache mechanism using a simple theoretical analysis and measurements from a software implementation of the Smalltalk-80 virtual machine, (see Chapter 11).

## Analysis

This analysis compares the behavior of a straightforward implementation of a Smalltalk-80 virtual machine to an implementation with a method-cache. Subscripted capital letters represent virtual machine implementation-dependent quantities, while greek letters represent Smalltalk-80 code-dependent quantities. Specifically,

* A with a subscript represents the time for completing a method look-up,

* S represents the number of bytecodes/second (speed), and
* *F* represents the fraction of total time spent in doing method-lookups.

We stress the distinction between Smalltalk-80 code-dependent and implementation-dependent quantities because the former are constants independent of the implementation. For example, implementations may differ drastically in the number of bytecodes executed per second, but for the same Smalltalk-80 code, the number of method-lookups per bytecode would be identical. The following table lists the variables used and their definitions.

<table><caption>Table 13.1 Parameters and Definitions</caption><thead><tr><th colspan="2">Implementation Dependent Values</th></tr></thead><tbody><tr><td>A<sub>miss</sub></td><td>method lookup time for a cache miss*</td></tr><tr><td>A<sub>nc</sub></td><td>method lookup time without a cache</td></tr><tr><td>A<sub>hit</sub></td><td>method lookup time for a cache hit</td></tr></tbody><thead><tr><th colspan="2">Implementation and Smalltalk Code Dependent Values</th></tr></thead><tbody><tr><td>A<sub>xK</sub></td><td>average method lookup time for an xK entry method cache</td></tr><tr><td>S<sub>nc</sub></td><td>number of bytecodes/sec without a cache</td></tr><tr><td>S<sub>xK</sub></td><td>number of bytecodes/sec with an xK entry method cache</td></tr><tr><td>S<sub>optimal</sub></td><td>the number of bytecodes/sec possible<br>assuming zero access time for method lookup</td></tr><tr><td>F<sub>nc</sub></td><td>fraction of total time spent in lookup without a cache</td></tr><tr><td>F<sub>xK</sub></td><td>fraction of total time spent in lookup with an entry xK cache</td></tr><tr><td>φ</td><td>hit ratio (also depends on cache characteristics)</td></tr></tbody><thead><tr><th colspan="2">Smalltalk Code Dependent Values</th></tr></thead><tbody><tr><td>β</td><td>number of lookups/bytecode</td></tr></tbody></table>

An implementation will be characterized by: A<sub>miss</sub> and A<sub>hit</sub>, S<sub>nc</sub> and A<sub>nc</sub>, and φ and β. These values, together with the equations shown below, are used to obtain the remaining values of interest.

The fraction of time spent doing method lookups is related to the number of lookups per bytecode, the lookup access time, and the number of bytecodes per second by the relationship $F = S\beta A$. Applying this relationship to a cache and a non-cache implementation gives

$$F_{nc} = \beta A_{nc} S_{nc} \quad \text{and} \quad F_{xK} = \beta A_{xK} S_{xK}$$

The average cache access is given by the usual relation

$$A_{xK} = \varphi A_{hit} + (1 - \varphi) A_{miss}$$

<footnote>*Strictly speaking, A<sub>miss</sub> and A<sub>nc</sub> also depend on the length of the superclass chain, and hence on the Smalltalk code being executed.</footnote>
The speed (bytecodes per second) depends partly on how much time is spent in method lookup. $S_{optimal}$ assumes the time to be zero.

If $T_{optimal}$ and $T_{nc}$ are the times required to execute N bytecodes at speeds $S_{optimal}$ and $S_{nc}$, then we have

$$S_{optimal} = \frac{N}{T_{optimal}} = \frac{S_{nc} T_{nc}}{T_{nc}-\text{total lookup time}}$$

where total lookup time = $N\beta A_{nc}$.

Replacing total lookup time by its value, and simplifying, we obtain

$$S_{optimal} = \frac{S_{nc}}{1 - S_{nc} \beta A_{nc}} = \frac{S_{nc}}{1 - F_{nc}}$$

Similarly, the speed of the cache implementation, $S_{xK}$ is derived. The difference is that the cache's average method lookup access time is used instead of the non-cache access time.

If $T_{nc}$ and $T_{xK}$ are the times required to execute N bytecodes at speeds $S_{nc}$ and $S_{xK}$ we have

$$S_{xK} = \frac{N}{T_{xK}} = \frac{S_{nc} T_{nc}}{T_{nc}-\text{total time gained by caching}}$$

where total time gained by caching = $N\beta(A_{xK}-A_{nc})$.

obtaining,

$$S_{xK} = \frac{S_{nc}}{1 - S_{nc} \beta(A_{nc} - A_{xK})} = \frac{S_{nc}}{1 - F_{nc} + S_{nc} \beta A_{xK}}$$

Using the equations above, the ratio $S_{xK}/S_{optimal}$ is computed. This ratio expresses how close the implementation comes to the theoretical lower limit of zero access time for method lookups, and may be expressed as

$$\frac{S_{xK}}{S_{optimal}} = \frac{1 - S_{nc} \beta A_{nc}}{1 - S_{nc} \beta (A_{nc} - A_{xK})} = \frac{1}{1 + S_{optimal} \beta A_{xK}}$$

Furthermore, the ratio $S_{xK}/S_{nc}$ gives the factor increase in execution speed of a cache implementation compared to a non-cache implementation. This ratio can be written as

$$\frac{S_{xK}}{S_{nc}} = \frac{1}{1 - S_{nc} \beta (A_{nc} - A_{xK})}$$

If we consider a given cache organization, and a fixed program behavior, the speed increase has the form $1/(1-KS_{nc})$, where $K = \beta(A_{nc}-A_{xK})$.

One use of this formula is to determine the speed increase that a non-cache-implementation will get by using a caching scheme. In the
next section we present a particular Smalltalk-80 implementation, and on p. 245 we present some measurements on its behavior. Implementors can use these measurements as guidelines to obtain for their particular case, approximations to the expected gains.

## The Implementation in Berkeley Smalltalk

Currently, Smalltalk-80 virtual machines are being implemented on general purpose computers. Smalltalk-80 implementors should consider adding a software cache for method-lookup. As an example of the considerations involved, we now present, in some detail, the implementation used in BS. BS executes on the VAX-11 family of computers, under the UNIX operating system. The programming language used is C. The algorithms were coded with extreme care (sometimes checking the code produced by the C compiler), and macros were used whenever possible.

## Cache Structure

The implemented cache is of the direct-mapped variety. The underlying data structure consists of four arrays, each with 1K entries. The first three arrays have entries 2 bytes long (one VAX-11 word); the last one 1 byte long. The first two arrays (CacheSel and CacheClass) contain the Oops of the combinations for selector and class that are cached. The remaining two (CacheMethod and CachePrimitive) contain the actual information: the method Oop, and an indication of whether it is a primitive or not.

The organization as separate arrays allows the use of the VAX-11 in-dex mode to access all desired information. Thanks to a careful management of the available registers on the hardware, most of the time the fastest modes can be employed. Thus, to access CacheSel[i], if i is in register r0, we can simply use

movw CacheSel[r0],

Note that an implementation as a field in an array of records would produce much longer code, including shifts (or divides) to access the appropriate entry in the array, plus additional code to access the field.

Recently BS has been extended to include a playback facility. With this facility, a script of all the bytecodes executed in a session can be obtained, and later replayed to reproduce the session. In this way we have been able to study the effect of different cache sizes on the hit ratio. For a particular interactive session of about 2M bytecodes, using as a hash function a simple EX-OR the hit ratios found were:
<table><caption>Table 13.2 Hit Ratio and Cache Size</caption><tr><td>entries</td><td>64</td><td>128</td><td>256</td><td>512</td><td>1024</td><td>2048</td><td>4096</td></tr><tr><td>hit ratio</td><td>65.3%</td><td>77.0%</td><td>86.1%</td><td>90.4%</td><td>93.1%</td><td>95.0%</td><td>95.4%</td></tr></table>

This makes a cache of size 1K or 2K the more adequate for most situations.

□ *The lookup algorithm* The lookup algorithm is simple. An entry on the cache is selected using some function of the class and selector *Oops*. Then a comparison is done to check the validity of the information associated to the entry. On a hit, the required information is already obtained. On a miss we have to go through the complete lookup search; when the correct binding is found, the entries in the cache are updated with the appropriate information.

Clearly, the selection of the hashing function is important. Three simple functions are:

1. `hash(class, selector)` — (class EXOR selector) AND `cacheSize`

2. `hash(class, selector)` — (class AND selector) AND `cacheSize`

3. `hash(class, selector)` — (class ADD selector) AND `cacheSize`

As the difference in speed between an EXOR and an ADD is small, on the order of .07 us (approximate value for the 2 register versions of these instructions on a VAX-11/780), 1 and 3 have similar qualities. Although AND requires two instructions on the VAX-11, it also has a similar speed. The total access time in the case of a hit, $A_{hit}$ is reasonably small because of the explicit handling of registers done in C.

The playback facility of BS has allowed us to compare the different functions. The results for the same sample as mentioned above are as follows:

<table><caption>Table 13.3 Hit Ratio and Hash Function</caption><thead><tr><td>Function</td><td>Hit Ratio</td><td>A<sub>hit</sub></td><td>A1K</td></tr></thead><tbody><tr><td>1.</td><td>93.1%</td><td>4.4</td><td>23.6</td></tr><tr><td>2.</td><td>61.6%</td><td>4.5</td><td>111.82</td></tr><tr><td>3.</td><td>94.8%</td><td>4.5</td><td>19.08</td></tr></tbody></table>

It is clear that 2 is a loser and its use is discouraged. The function originally used in BS was 1; its performance is acceptable. The best choice is
3, the hashing function currently being used in BS (and also in the Dolphin and Dorado implementations⁴).

## Measurements in BS

We now present some measurements of the BS implementation. They show a 32-37% increase in the execution speed of the implementation.

When these measurements were made, the hashing function used was the one referred to as 1 above; otherwise the implementation is the one presented there. Two different Smalltalk-80 programs were executed to obtain representative samples. One program was an interactive session of editing, browsing, and short arithmetic computations comprising 6.8 million bytecodes. The other was the Tower of Hanoi problem, a computation intensive problem, comprising 1.5 million bytecodes.

On a VAX-11/780, the constants for cache accesses for BS are

$A_{hit}$ 4.4 µsec

$A_{nc}$ 187 µsec

$A_{miss}$ 284 µsec

The data from the two programs and the computed results are summarized in the table below.

<table><caption>Table 13.4 Berkeley Smalltalk Results</caption><thead><tr><th>Parameter</th><th>Interactive</th><th>Tower of Hanoi</th></tr></thead><tbody><tr><td>φ (hit ratio)</td><td>0.943</td><td>0.996</td></tr><tr><td>β lookup/bytecode</td><td>0.186</td><td>0.078</td></tr><tr><td>A<sub>1K</sub> µsec</td><td>20.4</td><td>5.52</td></tr><tr><td>S<sub>nc</sub> bytecodes/sec</td><td>8,750</td><td>17,350</td></tr><tr><td>S<sub>optimal</sub> bytecodes/sec</td><td>12,570</td><td>23,230</td></tr><tr><td>S<sub>1K</sub> bytecodes/sec</td><td>12,000</td><td>23,000</td></tr><tr><td>F<sub>nc</sub></td><td>0.304</td><td>0.253</td></tr><tr><td>F<sub>1K</sub></td><td>0.046</td><td>0.010</td></tr><tr><td>S<sub>1K</sub>/S<sub>optimal</sub></td><td>0.955</td><td>0.990</td></tr><tr><td>S<sub>1K</sub>/S<sub>nc</sub></td><td>1.372</td><td>1.326</td></tr></tbody></table>

The numeric values for the parameters and values were obtained using various mechanisms. $A_{hit}$ was obtained from the VAX-11 code that accesses the cache. The exact time used by the sequence of instructions is difficult to measure because of the effect of the VAX-11/780 cache; timing the instruction loop gives an overly optimistic value since all the
code ends up in the cache. $A_{nc}$ and $A_{miss}$ were obtained by profiling the execution of the updating routines⁵. The difference between the $A_{nc}$ value and the $A_{miss}$ is the time required to update the cache. The cache is updated every time there is a cache miss. The profile tool also gave the number of lookups and the number of bytecodes executed, used to determine $\beta$, and the number of misses, used to determine $\varphi$. Finally, $S_{1K}$ was obtained from the user time it took to execute the programs. The remaining values were obtained from the equations.

There are several important points to make. The software cache achieves an average method access time of 20.4 microseconds for the interactive session. The Tower of Hanoi problem is atypical and tends to give a best case result since the small amount of code generates few cache misses. Nevertheless note that both hit ratios are high, 94% and 99%. The cache of 1K entries increases execution speed by 37.2 percent (interactive), and 32.6 percent (Hanoi). Execution speed is slower than $S_{optimal}$ by only 4.5 percent (interactive) and 1.0 percent (Hanoi). (Note that, since the two execution profiles are different, we cannot compare the two executions directly.)

## Conclusions

Fast method access is important in achieving better Smalltalk-80 performance. We have presented the main parameters and relations involved in the method lookup process. From these it has been shown that the benefits of adding a method cache depend on the relation of the overall speed of the implementation to the speed of the cache accesses, as well as on the more traditional considerations of hit ratio and miss/hit access speeds.

On an optimized VAX-11/780 implementation, the addition of a software-supported method cache produced a nine-fold reduction of the time required by the lookup process. This by itself, increased the overall speed of the Berkeley Smalltalk-80 implementation by 37%.

## Acknowledgments

We heartily thank all the people on the Smalltalk island, both at Berkeley and at Xerox Palo Alto Research Center. We especially thank the two Daves, Dave Ungar for making BS a reality, and Dave Patterson for encouraging us to write this paper. Without them this work would have never existed. We also want to thank all the reviewers, their comments largely increased the readability of this paper.
References

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

2. Krasner, Glenn, "The Smalltalk-80 Virtual Machine", *Byte* vol. 6, no. 8, pp. 300-320, Aug. 1981.

3. Lipway, J. S. "The Structural Aspects of the System/360 Model 85 II: The Cache", *IBM Systems Journal* vol. 7, no. 1, pp. 15-21, 1968.

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

5. Graham, Susan L., Kessler, Peter B., and McKursick, Marshall K., "Gprof: A Profiler Using Call Graphs", in Proceedings of the Sigplan Conference on Compiler Construction, June 1982.
PART FOUR

<figure><img src="image_30.png" /></figure>
# LOOM—Large Object-Oriented Memory for Smalltalk-80 Systems

Ted Kaehler

Glenn Krasner

Software Concepts Group

Xerox Palo Alto Research Center

Palo Alto, California

## Introduction

The Smalltalk-80 virtual machine is specified as a memory-resident system containing up to 2¹⁵ objects. When full, it typically occupies about 2M bytes of memory. Unfortunately, many machines do not have this capacity in main memory, and many applications require, or will require, more than this capacity. To solve this space problem, one typically uses a virtual memory system in which the resident, "real" memory is used as a cache for the larger mass storage, "virtual" memory. LOOM, Large Object-Oriented Memory, is a virtual memory system designed and implemented for the Smalltalk-80 system. The most important feature of the LOOM design is that it provides virtual addresses that are much wider than either the word size or the memory address size of the computer on which it runs.

LOOM is a single-user virtual memory system that swaps objects and operates without assistance from the programmer. Virtual memory systems may be characterized by the amount of attention that the programmer must pay to the transfers between virtual and real memories, by the extent to which the memory is shared among users, and by the granularity of transfer between memory levels. Overlay mechanisms are an example of systems that require much programmer attention, while all common paging systems require none¹. Databases may be
viewed as the extreme in allowing sharing; the virtual memory for Interlisp-D² is one example of a single-user virtual memory. Most overlay systems transfer program segments, while paging systems transfer disk pages, and a few systems such as the OOZE virtual memory for Smalltalk-76³ transfer objects.

## The LOOM Design

We view virtual memory design as a process of trying to determine what happens most often, making it go fast, and hoping that it will continue to be what happens most often. Our experience with previous Smalltalk systems gave us three major assumptions on which we based the LOOM design: programmers and users have a large appetite for memory, object-swapping is an efficient and effective scheme, and the Smalltalk-80 design for handling resident objects is worth keeping. From these assumptions and the desire to provide a large number of objects on a machine with a narrow word width, we created the major design decisions.

* LOOM assumes that the object is the unit of locality of reference. It swaps individual objects between primary and secondary memory, and allows into main memory only those objects actually needed by the interpreter. Unlike paging systems, LOOM packs objects in main memory at maximum density.

* LOOM is designed for machines with 16-bit words. Fields of objects in main memory are 16 bits wide.

* The address space of the secondary memory is large. LOOM allows as many as 2³¹ objects.

* The interpreter accesses objects in main memory exactly as it does in a resident Smalltalk-80 interpreter. When the necessary objects are already in main memory, the interpreter runs as fast as it did in the resident system.

In order to allow the large number of possible objects, and yet treat the resident objects in the same way they are treated in a non-LOOM Smalltalk-80 implementation, we decided to create two different name spaces. The same object is identified by names from different spaces when it resides in different parts of the system, as shown in Fig. 14.1. The identifier of an object is called an *Oop*, which stands for "object pointer." An object in secondary storage has a 32-bit Oop (a long Oop), and each of its fields containing a pointer to another object holds that
<figure><img src="image_31.png" /><figcaption>**Figure 14.1** To the large secondary memory, main memory looks like a cache.</figcaption></figure>

pointer as a 32-bit Oop. An object cached in main memory has a 16-bit Oop (a short Oop) and 16-bit fields. As in the resident Smalltalk-80 implementation, main memory has a resident object table (*ROT* or sometimes called an *OT*), which contains the actual main memory address of each resident object. An object's short Oop is an index into the *ROT*, so that the object's address can be determined from its Oop with a single addition and memory reference. When an object is brought into main memory from disk, it is assigned a short Oop, and those of its fields that refer to other objects in main memory are assigned the appropriate short Oop. Fields pointing to objects that are not resident are handled specially, the details of which make up the crux of LOOM.

Thus, when all objects in the working set are in main memory, LOOM behaves just like a resident Smalltalk-80 implementation—all objects have short Oops that index the *ROT*, providing their actual core address. When an object in core must access one of its fields that refers to an object that is not in core, something special must happen. LOOM brings that object into core, assigns it a short Oop, and resumes normal Smalltalk execution. The main memory resident space of $2^{15}$ objects acts as a cache for up to $2^{31}$ objects on the disk.
## The LOOM Details

The important issues in the LOOM design implementation are:

* The representation of resident objects,

* The representation of objects in secondary memory,

* The translation between representations, and

* The identification of times when the translations must occur.

### *The Representation of Resident Objects*

Resident objects are represented in a manner similar to their representation in a resident Smalltalk-80 system. Each object has as its name in main memory, a short (16-bit) Oop. The Oop indexes the ROT in order to provide the starting address of the object's body, as shown in Fig. 14.2. The ROT entry also has reference-count bits, and a few other bits, described later. The body of each object contains a word for the length of the body, a pointer to the object's class, and the object's fields. Each field is either a pointer to another object or a collection of "bits", in the same manner as resident Smalltalk-80 fields. We will only deal with pointer fields here. Each field (as well as the class pointer) that refers

### Format of Objects in Main Memory

<figure><img src="image_32.png" /><figcaption>Figure 14.2</figcaption></figure>
to another resident object contains the short `Oop` of that object. Fields that refer to non-resident objects (objects on secondary storage) contain a short `Oop` of one of two types, a *leaf* or a *lambda*.

In addition to these fields, resident objects in a LOOM system have three extra words. Two of these words contain the long (32-bit) `Oop` of that object. The third word, known as the *delta word*, contains a delta reference count and some other bits. The short `Oop` of an object is not only an index into the `ROT` for that object's address, but is also the result of a hash function applied to that object's long `Oop`. See Fig. 14.3, p. 256. The algorithm for translating an object's short `Oop` to its long `Oop` is:

1. Index the `ROT` with the short `Oop` to get the body address

2. Load the long `Oop` from the first two words of the body

The algorithm for translating an object's long `Oop` to its short `Oop` is:

1. Convert the long `Oop` into a short `Oop` by applying the hash function

2. Index the `ROT` with this short `Oop` to get a body address

3. Look at the first two words of the body

4. If they match the long `Oop`, then the short `Oop` is correct

5. If not, create a new short `Oop` from the current one with a reprobe function (e.g., add 1), and go to step 2

Secondary memory is addressed as a linear space of 32-bit words. Objects start with a header word that contains 16 bits of length and some status bits. Each pointer field in the object is 32 bits wide. Non-pointer fields (such as the bytes in *Strings*) are packed, with 4 bytes in each 32-bit word. Resident *Smalltalk-80 SmallIntegers* are rather short to be occupying a full word on the disk. However, since they represent legitimate object pointers, their 15 significant bits are stored along with a flag value in a 32-bit pointer field on the disk. The long `Oops` in pointer fields are 31-bit disk pointers, addressing as many objects as will fit into $2^{31}$ disk words (32-bit words). Fields of objects on secondary storage always refer to objects in secondary storage and do not change when the object to which they point is currently cached in main memory. As shown in Fig. 14.4, no information about primary memory is ever stored in secondary memory. Information such as an object's short `Oop`, its location in primary memory, or whether it is currently cached in primary memory are never recorded in secondary memory.
<figure><img src="image_33.png" /><figcaption>Finding an Object's Short Oop from Its Long Oop</figcaption></figure>

<figure><img src="image_34.png" /><figcaption>Figure 14.3</figcaption></figure>
How Objects in Primary and Secondary Memory Refer to Other Objects.

<figure><img src="image_35.png" /><figcaption>Figure 14.4</figcaption></figure>

When an object on secondary storage is brought into main memory, its fields must be translated from the long form to short form. The object is assigned an appropriate short Oop (one to which its long Oop hashes), a block of memory is reserved for it, and all of its fields are translated from long Oops to short Oops. Those fields that point to objects already in main memory are given the short Oops of those objects; those that point to objects not in main memory are handled in one of two ways, with leaves or with lambdas.

☐ *Leaves* are pseudo-objects that represent an object on secondary storage. They have a short Oop hashed by that object's long Oop and a ROT entry, but their image in memory only contains a length word, disk address words, and the delta word. Their image contains no class word or fields, as shown in Fig. 14.5. Leaves therefore, only take up 4 words of memory, whereas the average object takes up 13. Leaves are created without looking at that object's image on secondary storage.
This is very important, since a major cost in virtual memories is the number of disk accesses. The short Oop of the leaf may be treated as if it were the short Oop of the object; it may be pushed and popped on the stack, stored into fields of other objects, without ever needing the actual contents of that object. Its reference count can be incremented and decremented (see p. 262).

A Leaf

<figure><img src="image_36.png" /><figcaption>Figure 14.5</figcaption></figure>

An object is always in one of three states. Either the entire object is in main memory, a leaf for the object is in main memory, or the object exists only on the disk. See Fig. 14.6. When the interpreter needs a field from an object which is represented by a leaf, the entire object with its fields must be brought into main memory from disk. Since the leaf contains the disk Oop, the body is easy to find. After the body is translated into main memory form, its core address is stored into the leaf's OT entry, and the leaf body is discarded. Short Oop references to the object remain the same, but now the full object is actually there. Since a leaf can be substituted for an object body and vice versa with no effect on pointers to the object, LOOM is always free to make more room in main memory by turning resident objects into leaves.

☐ Lambdas Lambdas are the second way to represent fields of resident objects that refer to objects on secondary storage. Lambda is a place holder for a pointer to an object which has not been assigned a short Oop. Its purpose is to reduce the number of leaves in the system. Lambda is a pseudo-Oop, a reserved short Oop (the Oop 0) which is not the name of any resident object. Consider an object which has a lambda in one of its fields. To discover the actual value of that field, LOOM must go back to the object's image on secondary storage, look in that
<figure><img src="image_37.png" /><figcaption>Figure 14.6</figcaption></figure>

field for a long pointer, and create a leaf or resident object. This means that the cost of fetching a lambda field is an extra disk reference. However, unlike leaves, lambdas do not take up ROT entries (they all use the single pseudo-ROT entry at 0) and they do not take up any main memory storage. Since the number of ROT entries is limited to $2^{15}$, and main memory is a somewhat scarce resource, this saving can be important. During an object's typical stay in main memory, some of its fields will not be referenced. If leaves are created for the values in those fields when the object is swapped in, and then destroyed again when the object is thrown out, much work is wasted. Putting lambdas into fields which will not be referenced during the object's current stay in primary memory saves both the space and the time needed to create and destroy many leaves.

Determining whether to make the fields of an object be leaves or lambdas when the object is brought into main memory is a tricky business. The choice of strategy strongly affects the performance of a LOOM system. Creating a leaf takes more time and uses up more memory and a ROT entry, but does not cause any extra disk accesses. A lambda will cause an extra disk access if the field it occupies happens to be referenced, but a lambda is faster to create. One way to make the decision between leaf and lambda is to rely on history; if a field was a lambda when this object was written to the disk one time, it is likely to remain a lambda during its next trip into main memory. Each pointer field of the disk contains a hint, the *noLambda* bit, and the object faulting code follows the advice of the hint.
*The Translation Between Object Representations*

Translating between the memory-resident and secondary-storage representations of an object is straightforward. For those fields that contain short Oop, the Oop refers to an object or a leaf. The corresponding long Oop can be found in the header of the object or leaf. If the field refers to an object which has not yet been assigned a long pointer, a long pointer is assigned to the object and a copy is installed in the field. For those fields that contain lambdas, the field is guaranteed not to be changed from the object's previous disk image. (The object's disk image is read before it is written). If the object being translated still has some short pointers to it (has a positive in-core reference count), then it must be converted to a leaf instead of being deleted completely from core.

*When to Translate*

We have already mentioned when the translation between representations must occur. When a field of an object being brought into main memory has the noLambda bit set, and that field refers to a non-resident object, then a leaf is created. A leaf is also created when a field of a resident object containing a lambda is accessed. When the interpreter needs to access a field in a leaf, the flow of control in LOOM begins (see Fig. 14.7). The leaf is expanded into a resident object; its fields are translated from long form to short form. This is called an *object fault* (because the similar situation in paging virtual memory systems, trying to access a page that is not resident, is called a *page fault*). The inverse operation, *contracting* an object into a leaf, may be done at any time. The final part of an object's journey into primary memory consists of destroying the leaf and reusing its short Oop and memory space. This can only be done when there are no longer any fields in any resident objects pointing to the leaf.

Lambda's may be resolved into leaves and leaves may be expanded into full objects before they are needed, and this is called a *prefetch*. The complementary operations of contraction and prefetch of objects can both be done in the background. The exact order and mix of objects to prefetch or contract can be adjusted at run-time to optimize the performance of secondary storage (disk head movement or network traffic).

## LOOM Implementation Details

In this section, we provide some details of how LOOM may be implemented. In particular we discuss the discovery of object faults, reference-counting, and the assignment of the extra bits in the ROT entry and the delta word.

*Object Faults*

Object faults occur when the interpreter tries to access a field in a leaf or a field in an object whose value is lambda. By the time the interpreter scrutinizes them, all objects must be full resident objects. How can leaves and lambdas be discovered without greatly slowing the speed of the interpreter?
<figure><img src="image_38.png" /><figcaption>Figure 14.7</figcaption></figure>
It has been our experience that implementations tend to have a single subroutine (or expanded macro) that takes an Oop and sets up some base register to point to the actual address of that object. We call this subroutine "Otmapping." It corresponds roughly to the `ot:bits:` method of the memory manager in the formal specification of the Smalltalk-80 virtual machine, in *Smalltalk-80: The Language and its Implementation*⁴. Otmapping is called if and only if you want to fetch or store a field of an object. Note that this is exactly the condition where you must test for the object being a leaf. (Otmapping may sometimes be used for other purposes— for example a compaction routine may call Otmapping to get the main memory address of the object in order to move it, but it wants to treat leaves and objects the same. These cases tend to be rare, so it is worth having a second subroutine for them.) We reserve one bit of the ROT entry to say whether the entry is for an object or a leaf. The Otmapping subroutine tests this bit and calls the LOOM routines when the entry is a leaf. Since both words of the ROT entry are fetched anyway, this extra test usually only costs one or two extra instruction executions.

Testing for lambda however, must be done on every field reference. In the worst case, this would mean testing occurs every time a field is fetched from an object and every time an object is pushed onto the stack. To decrease the number of tests, we include one bit in each resident object called "holds lambda." It is set by the LOOM routines whenever that object has a field that is a lambda. The interpreter guarantees that the current context, the home context, the current method, and the receiver all have no lambdas in them. If any of them does contain a lambda, then the LOOM routines are called to make those fields into leaves. In this way, the most common fields fetched and all stack operations can work without testing for lambda. Note that these objects must be cleared of lambdas only when the active context changes. This occurs during message sends, returns, process switches, and during the execution of `BlockContext` value and value:

It is useful to note that the LOOM design actually will work with leaves alone, and without lambdas. When the expand routine brings an object into main memory, it turns all the fields into leaves and never creates a lambda. This approach tends to use more short `Oops` and main memory than the full LOOM design, but could be an intermediate stage in the implementation; providing a working virtual memory system with only the modification to the Otmapping subroutine.

Although some Smalltalk-80 implementations use `mark/sweeping garbage collection`, most implementations so far, including ours, use reference counting to identify garbage. Therefore we will describe the reference-counting scheme as it applies to LOOM. Reference counting serves two different purposes. One purpose is to detect when the total count of any object goes to zero. The other is to detect when the last short pointer to any object disappears so that the short pointer may be