Smalltalk.org™ | articles | article_20050929_a1

Bytecode-to-bytecode adaptive optimization for Smalltalk
Submitted by Scott Bleackley
Edited by Peter William Lount
version 1, 20050929 2:00pm EST
version 2, 20050929 3:20pm EST

"Smalltalk is a vision of the computer as a medium of self expression. ... A humanistic vision of the computer as something everyone could use and benefit from. If you are going to have a medium for self expression, programability is key because unless you can actually make the system behave as you want you are a slave to what's on the machine. So it's really vital, and so language comes to the for because it's through language that you express yourself to the machine.

The thing that is most radical, I think, about the Smalltalk Vision, and the thing which much of the instustry misses and has left behind, except maybe at the GUI level, is that the [Smalltalk] language design follows from a human centric design; a vision of, a humanist vision of what we might do to make peoples lives better, more enjoyable, more productive; and from that starting point a very very radical and original language, and a very very radical and original set of implementation technologies came along."
- Elliot Miranda, Cincom

This talk summarises two decades of work on Smalltalk and Self compilation and virtual machine technology and describes a novel attempt at an adaptive optimizer for Smalltalk that is written in Smalltalk and to a meaningful extent, portable across implementations. Smalltalk-80 and Self are fully object-oriented implicitly typed dynamic programming languages and interactive programming environments hosted above virtual machines that appear to execute stack-oriented bytecode for a pure stack machine. These systems' code and execution state are all represented by objects programmed in Smalltalk, such that the compiler, debugger, exception system and more are all implemented entirely in Smalltalk and available to the programmer for immediate incremental and interactive modification.

Google Video (1 hr 27 min 37 sec).
Video Abstract + Speaker Bio

Paper referenced in the video: Optimizing Dynamically-Typed Object-Oriented Languages With Polymorphic Inline Caches (PDF)by Urs Hölzle, Craig Chambers and David Ungar.

All of the techniques referenced in the paper also apply to Smalltalk virtual machines. The fact that Elliot Miranda presented this talk is a good indication that Cincom is working on adding such optimizations to VisualWorks Smalltalk.

Quoting from the paper:

Polymorphic inline caches (PICs) provide a new way to reduce the overhead of polymorphic message sends by extending inline caches to include more than one cached lookup result per call site. For a set of typical object-oriented SELF programs, PICs achieve a median speedup of 11%.

As an important side effect, PICs collect type information by recording all of the receiver types actually used at a given call site. The compiler can exploit this type information to generate better code when recompiling a method. An experimental version of such a system achieves a median speedup of 27% for our set of SELF programs, reducing the number of non-inlined message sends by a factor of two.

Implementations of dynamically-typed object-oriented languages have been limited by the paucity of type information available to the compiler. The abundance of the type information provided by PICs suggests a new compilation approach for these languages, adaptive compilation. Such compilers may succeed in generating very efficient code for the time-critical parts of a program without incurring distracting compilation pauses.

Polymorphic inline caches (PICs) significantly speed up polymorphic sends: some programs making frequent use of polymorphism run up to 37% faster with PICs. More importantly, polymorphic inline caches are an important source of type information since they record the set of likely receiver types for every send; such type information is essential for optimizing compilers to generate efficient code. By taking advantage of this information, our experimental implementation of the SELF language executes some fairly typical object-oriented programs up to 52% faster than the base system and reduces the number of dynamically executed message sends by a factor of two to four.

The presence of PIC-based type information may fundamentally alter the problem of optimizing dynamically- typed object-oriented languages. In current systems, type information is scarce, and consequently the compiler needs to work hard in order to preserve and exploit the scarce information it has. Unfortunately, such techniques are expensive both in terms of compile time and compiled code space. In contrast, type information is abundant in a system using adaptive compilation.Such a system may reduce compilation times significantly by eliminating most of the computationally expensive type analysis phase and by only optimizing the most-used parts of programs. In addition, adaptive compilation could overcome some drawbacks of existing optimization techniques such as static type prediction. We are currently implementing such a system for the SELF language in order to validate our ideas.

Thursday
July 24 2008

Interoperate.org, the place to find out how to interoperate.

Meet other Smalltalk people, contribute, learn, earn.

lingoize.me™

On speaking languages
naturally with ease
aiming for fluid fluency.