View this PageEdit this PageAttachments to this PageHistory of this PageHomeRecent ChangesSearch the SwikiHelp Guide
Hotspots: Admin Pages | Turn-in Site |
Current Links: Cases Final Project Summer 2007

Squeak Talk

Squeak is an open, highly-portable Smalltalk implementation whose virtual machine is written entirely in Smalltalk, making it easy to debug, analyze, and change. To achieve practical performance, a translator produces an equivalent C program whose performance is comparable to commercial Smalltalks. Squeak stands alone as a practical Smalltalk in which a researcher, professor, or motivated student can examine source code for every part of the system, including graphics primitives and the virtual machine itself, and make changes immediately and without needing to see or deal with any language other than Smalltalk. It also runs bit-identical images across its wide portability base.

The Interpreter

The interpreter is structured as a single class that gets translated to C along with the Object Memory and BitBlt classes. In addition, a subclass (Interpreter Simulator) runs all the same code from within a Smalltalk environment by supporting basic mouse, file, and display operations. This subclass was the basis for debugging the Squeak system into existence. All of this code is included in the Squeak release and it can run its own image, albeit at a snail's pace (every memory access, even in BitBlt, runs a Smalltalk method). Having an interpreter that runs within Smalltalk is invaluable for studying the virtual machine. Any operation can be stopped and inspected, or it can be instrumented to gather timing profiles, exact method counts, and other statistics.

The Object Memory

Squeakís object memory is general and yet compact. For efficiency and scalability to large projects, the developers used a 32-bit address space with direct pointers (i.e., a system in which an object reference is just the address of that object in memory). The design supports all object formats existing in Smalltalk and is amenable to incremental garbage collection and compaction. Furthermore it supports the ěbecomeî operation (exchange identity of two objects) to the degree required in normal Smalltalk system operation.
In order to achieve the above functionality, Squeak uses a variable-length header format which seldom requires more that a single 32-bit word of header information per object.The format is given in Tables 1 and 2. The design is based on the fact that most objects in a typical Smalltalk image are small instances of a relatively small number of classes. The 5-bit compact class index field, if non-zero, is an index into a table of up to 31 classes that are designated as having compact instances; the programmer can change which classes these are. The 6-bit size field, if non-zero, specifies the size of the object in words, accommodating sizes up to 256 bytes (i.e., 64 words, with the additional 2 bits needed to resolve the length of byte-indexable objects encoded in the format field). With only 12 classes designated as compact in the 1.18 Squeak release, around 81% of the objects have only this single word of overhead. Most of the rest need one additional word to store a full class pointer. Only a few remaining objects (1%) are large enough to require a third header word to encode their size, and this extra word of overhead is a tiny fraction of their size.

Format of a Squeak object header


offset contents occurrence
- storage management (3 bits)
- object hash (12 bits)
- compact class index (5 bits)
- object format field (4 bits, see below)
- size in words (6 bits)
- header type (2 bits) 100%



Encoding of the object format field in a Squeak object header




low 2 bits are low 2 bits of size in bytes
of size in bytes.
The number of literals is specified in method
header, followed by the indexable bytes that store byte codes.

BitBlt


For BitBlt as well, the developers started with the original Smalltalk code, but transformed the later to virtural machine code to run on top of the Object Memory. After making a few optimaizations the first Squeak was ready and running.

Once Squeak became operational, the developers immediately wanted to give it command over color. They chose to support a wide range of color depths, namely: 1-, 2-, 4-, and 8-bit table-based color, as well as 16- and 32-bit direct RGB color (with 5 and 8 bits per color component respectively).
It was relatively simple to extend the internal logic of BitBlt to handle multiple pixel sizes as long as source and destination bit maps were of the same depth. To handle operations between images of different depth, the developers provided a default conversion, and added an optional color map parameter to BitBlt to provide more control when appropriate. The default behavior was simply to extend smaller source pixels to a larger destination size by padding with zeros, and to truncate larger source pixels to a smaller destination pixel size. This approach worked very well among the table-based colors because the color set for each depth included the next smaller depth's color set as a subset. In the case of RGB colors, BitBlt performs the zero-fill or truncation independently on each color component.
The real challenge, however, involved operations between RGB and table-based color depths. In such cases, or when wanting more control over the color conversion, the client can supply BitBlt with a color map. This map is sized so that there is one entry for each of the source colors, and each entry contains a pixel in the format expected by the destination.


Sound


Several of the developers had been involved in early experiments with computer music editing and synthesis, and it was a great disappointment to them that the original Smalltalk-80 release failed to incorporate this vital aspect of any lively computing en
evironment. They were thus determined to right this wrong in the Squeak release.

They initially implemented access to the Macintosh sound driver. But as the performance of the Squeak system improved, they were able to actually synthesize and mix several voices of music in real time using simple wave table and FM algorithms written entirely in Smalltalk.
Nonetheless, these algorithms are compute-intensive, and the developers used this application as an opportunity to experiment with using C translation to improve the performance of isolated, time-critical methods. Sound synthesis was an ideal application for this, since nearly all the work is done by small loops with simple arithmetic and array manipulation. The sound generation methods were written so that they could be run directly in Smalltalk or, without changing a line of code, translated into C and linked into the virtual machine as an optional primitive. Since the sound generation code had already been running for weeks in Smalltalk, the translated primitives worked perfectly the first time they ran. Furthermore, nearly a 40-fold increase in performance was observed: from 3 voices sampled at 8 KHz, it was now possible to mix 20 voices sampled at 44 KHz.


WarpBlt


Dissatisfied with general rotation and scaling of images, the developers added a ěwarp driveî to the BitBlt. WarpBlt takes as input a quadrilateral specifying the traversal of the source image corresponding to BitBlt's normal rectangular destination. If the quadrilateral is larger than the destination rectangle, sampling occurs and the image is reduced. If the quadrilateral is smaller than the destination, then interpolation occurs and the image is expanded. If the quadrilateral is a rotated rectangle, then the image is correspondingly rotated. If the source quadrilateral is not rectangular, then the transformation will be correspondingly distorted.
Later support was added for over sampling and smoothing in the warp drive, which did a reasonable job of anti-aliasing in many cases. The approach was to average a number of pixels around a given source coordinate. Averaging colors is not a simple matter with the table-based colors of 8 bits or less. The approach used was to map from the source color space to RGB colors, average the samples in RGB space, and map the final result back to the nearest indexed color via the normal depth-reducing color map.
As with the sound synthesis work, WarpBlt was completely described in Smalltalk, then translated into C to deliver performance appropriate to interactive graphics.


Conclusion


Squeak is thus the first practical Smalltalk system written in itself that is complete and self-supporting. Squeak runs the Smalltalk code describing its own virtual machine fast enough for debugging purposes: although it requires some patience, one can actually interact with menus and windows in this mode. This is no mean feat, considering that every memory reference in the inner loop of BitBlt is running in Smalltalk.
To achieve useful levels of performance, the Smalltalk code of the virtual machine is translated into C, yielding a speedup of approximately 450. Part of this performance gain, a factor of 3.4, can be attributed to the inlining of function calls in the translation process. The translator can also be used to generate primitive methods for computationally intensive inner loops that manipulate fundamental data types of the machine such as bytes, integers, floats, and arrays of these types.


Team Members




Link to this Page