From: pardo@cs.washington.edu (David Keppel)
Newsgroups: comp.compilers
Subject: Re: Why is compiled basic slower than C? (Basic is the future)
Keywords: interpreter, performance, Basic, smalltalk
Date: 15 Aug 92 22:40:03 GMT
Reply-To: pardo@cs.washington.edu (David Keppel)
Organization: Computer Science & Engineering, U. of Washington, Seattle

>>[Why isn't compile BASIC as fast as C?]
>[It's too dynamic.]

I'm surprised nobody has mentioned the Deutsch-Shiffman Smalltalk-80
virtual machine implementation or the SELF system.  Neither system is a
`traditional' compiler, but both run fast and are examples of `dynamic'
languages (little information for static optimization) with efficient
implementations.  Their results shold apply to BASIC and to some other
languages.

Smalltalk programs lack type declarations.  Programmers are encouraged to
modularize extensively, resulting in very small procedures (methods).
Some common control structures are implemented using method invocation.
Smalltalk is more dynamic than basic, yet a ``fairly straightforward''
dynamic compilation implemenation of the Smalltalk-80 Virtual machine runs
benchmarks within an order of magnitude of compiled C, while an optimized
interpreter is 2X slower.

SELF is more dynamic than even Smalltalk-80.  Even primitive control
structures (if/then/else, loops) are built using method invocation [*].
Yet on a set of benchmarks, SELF programs run with an optimizing dynamic
compiler run at about half the speed of modestly-optimized C programs (on
a SPARC, using the default pcc-based compiler with optimization turned
on).  With an interpretive implementation, SELF programs might be two
orders of magnitude slower than it is; indeed, programs compiled without
inlining (procedure integration) are about that much slower.

The disadvantages of dynamic compilation generally include (a) the need to
pay for compilation at runtime and (b) a lack of ways to share code (e.g.,
each instance of program `foo' has a private copy of the compiled machine
code).  The first sometimes results in long startup times or variability
in execution time.  The latter results in large(r) memory demands.

[*] Note that in Smalltalk, some control structures appear to be message
sends but are inlined; changing the implementation code for the control
structures does not change the system's behavior.  In SELF, the control
structures are treated uniformly as message sends.

5 References Follow:

%A Craig Chambers
%T The Design and Implementation of the S\s-2ELF\s+2 Compiler,
an Optimizing Compiler for Object-Oriented Programming Languages
%R Ph.D. dissertation, Department of Computer Science, Stanford
University

%A Craig Chambers
%A David Ungar
%T Making Pure Object-Oriented Languages Practical
%J OOPSLA '91 Proceedings; SIGPLAN Notices
%V 26
%N 11
%P 1-15
%C Phoenix, AZ
%D November 1991

%A Craig Chambers
%A David Ungar
%A Elgin Lee
%T An Efficient Implementation of SELF, a Dynamically-Typed
Object-Oriented Language Based on Prototypes
%J OOPSLA '89 Proceedings
%D October 1-6 1989
%P 49-70

%A Craig Chambers
%A David Ungar
%T Customization: Obptimizing Compiler Technology for SELF, a
Dynamically-Typed Object-Oriented Programming Language
%J 0-89791-306-X/89/006/0146
%D 1989
%P 146-160

%A Peter Deutsch
%A Alan M. Schiffman
%T Efficient Implementation of the Smalltalk-80 System
%J 11th Annual Symposium on Principles of Programming Languages
(POPL 11)
%D January 1984
%P 297-302

	;-D on  ( Just call me Mr. Runtime! )  Pardo
[Many APL systems (other than IBM's) also compile on the fly since it can't
usually tell what the types and array rank of variables will be until a
procedure is actually called. -John]
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.