rob@vger.UUCP (Rob Field) (05/08/86)
I am interested in writing a highly optimized native code compiler for Smalltalk. Does anyone know about work that has been done in this area, compilers that have been written, articles published relevant to this,...
jsgray@watdragon.UUCP (Jan Gray) (05/13/86)
In article <418@vger.UUCP> rob@vger.UUCP (Rob Field) writes: >I am interested in writing a highly optimized native code compiler >for Smalltalk. Does anyone know about work that has been done >in this area, compilers that have been written, articles published >relevant to this,... The Berkeley SOAR (Smalltalk On A RISC) runs specially compiled code (as opposed to virtual machine bytecodes). [Aside: Would someone from the SOAR project care to comment on project status?] Peter Deutsch's "PS" implementation translates and caches virtual machine bytecodes into native 68000 code. As far as I know it is the fastest ST-80 implementation (110% of a Dorado on a SUN-3). Bob Atkinson (BAtkinson.pa@XEROX.ARPA) has written a native compiler, but you should get in contact with him for details. There will probably be a few papers on this subject at the upcoming OOPSLA conference. References: L.P. Deutsch and A.M.Schiffman, Efficient Implementation of the Smalltalk-80 System, Procedings of the 11th Annual ACM SIGACT News-SIGPLAN Notices Symposium on the Principles of Programming Languages, Salt Lake City, Utah, January, 1984. D. Ungar, et al, Architecture of SOAR: Smalltalk on a RISC, Eleventh Annual International Symposium on Computer Architecture, Ann Arbor, MI, June 1984. "Making slow progress at bringing up BSII on the Atari ST", Jan Gray
johnson@uiucdcsp.CS.UIUC.EDU (05/13/86)
The best paper on Smalltalk implementations is the one by Peter Deutsch and Allan Schiffman in the 10'th POPL conference. There is also a paper by Suzuki and Terada in that same proceedings that talks about implementation issues. One of the things that is apparent from the Deutsch and Schiffman paper is that interpretation alone is not the reason why Smalltalk is slow, so just compiling Smalltalk to machine language will not improve the speed much. However, certain optimizations can make a big difference. In order to optimize Smalltalk programs the compiler must know the particular methods that are being invoked by a given message. A type system is necessary to do this. Suzuki describes one type system in the 8'th POPL conference proceedings, while Borning and Ingalls described a more complete type system in the 9'th POPL conference proceedings. I am having a paper in the Object-oriented Programming Languages, Applications, and Systems conference next October that explains why these type systems are not suficient for code-optimization and that presents a type system for Smalltalk that (I claim) is. There will probably be a lot of papers on compilation and other implementation techniques at this conference, so anyone who is interested in implementing object-oriented languages should certainly attend. I have been looking at optimizing Smalltalk programs for a couple of years and am in the early stages of an implementation of an optimizing compiler. Smalltalk was not really designed to be optimized because it is typeless. Retrofitting a type system to Smalltalk is tricky and inevitably requires some modification to some of the primitives. It might be better to just start over and design a language that is well integrated with a type system. Building an optimizing compiler for Smalltalk is interesting research but it is by no means obvious that such a project will be a success. Ralph Johnson
mdr@reed.UUCP (Mike Rutenberg) (05/17/86)
In article <9000005@uiucdcsp> johnson@uiucdcsp.CS.UIUC.EDU writes: > >The best paper on Smalltalk implementations is the one by Peter Deutsch >and Allan Schiffman in the 10'th POPL conference. There is also a paper >by Suzuki and Terada in that same proceedings that talks about >implementation issues. One of the things that is apparent from the >Deutsch and Schiffman paper is that interpretation alone is not the >reason why Smalltalk is slow, so just compiling Smalltalk to machine >language will not improve the speed much. However, certain optimizations >can make a big difference. In order to optimize Smalltalk programs the >compiler must know the particular methods that are being invoked by a given >message. A type system is necessary to do this. Suzuki describes one type >system in the 8'th POPL conference proceedings, while Borning and Ingalls >described a more complete type system in the 9'th POPL conference proceedings. What Ralph says above hits the nail right on the head. By far, the largest overhead in Smalltalk 80 is the extremely late binding of procedures or methods. Do optimization without a type system can not be absolutely ruled out, but it is by far a much more difficult task. A fellow by the name of Pavel Curtis at Cornell is doing his PhD on a formal type system that attempts to handle polymorphism, so you might want to get in touch with him if you want to know more. (Pavel.pa@Xerox.com on the arpanet will work, I think) The two type systems mentioned above are really quite different. However, they both are not well founded in that they produce incorrect results. Borning and Ingalls approach can be modified to some degree to produce a workable and correct system that will support an optimizing compiler capable of statically determining the identity of called methods. I spent eight months last year creating such a compiler, which I named Hurricane. I am presenting a paper on it at OOPSLA in October. If anyone is interested, and the response is not TOO great, I could send you an advance copy of the paper. >I am having a paper in the Object-oriented Programming Languages, >Applications, and Systems conference next October that explains why these >type systems are not suficient for code-optimization and that presents a >type system for Smalltalk that (I claim) is. There will probably be a lot of I am very interested to see how close Ralph's type system is to mine. Should be a fun conference! >papers on compilation and other implementation techniques at this conference, >so anyone who is interested in implementing object-oriented languages should >certainly attend. > >I have been looking at optimizing Smalltalk programs for a couple of years >and am in the early stages of an implementation of an optimizing compiler. >Smalltalk was not really designed to be optimized because it is typeless. >Retrofitting a type system to Smalltalk is tricky and inevitably requires Tricky is quite an understatement! Especially if you take the point of view as I did that you want to do any optimiziations completely transparently. That is, to not change the semantics of the language at all. >some modification to some of the primitives. It might be better to just >start over and design a language that is well integrated with a type system. >Building an optimizing compiler for Smalltalk is interesting research but >it is by no means obvious that such a project will be a success. Depending on your point of view, Hurricane was quite successful. My feeling at this point is that if you really use the paradigm provided by Smalltalk effectively, then there is virtually no leverage to be gained by optimization that can do static method bindings. However, if you pretend you are writing Pascal say, but instead use Smalltalk, we can probably do a lot for you, and there is no fundamental reason why the code should not run as fast as if you had actually used Pascal. > >Ralph Johnson bob atkinson BAtkinson.pa@Xerox.com arpanet BAtkinson.pa%Xerox.com@csnet-relay.csnet or something like that on csnet 503-293-4318