shivers@centro.soar.cs.cmu.edu (Olin Shivers) (02/22/89)
Mr. Van Roy writes asking about comparisons of "symbolic" programming
languages versus imperative ones, and the impact of compilers and
non-standard architectures.
Performance implementations of languages like Scheme and ML is one of my
research areas. I think you would be surprised how well you can do with
the latest technology in Scheme compilers. The T group's Scheme compiler,
Orbit, produces code which is competitive with cc. Orbit is described in
detail in David Kranz' PhD dissertation,
Orbit: An Optimizing Compiler for Scheme
David Kranz
YALEU/DCS/RR-632 February 1988
and also in the paper
Orbit: An Optimizing Compiler for Scheme
Kranz, David and Kelsey, R. and Rees, Jonathan
and Hudak, Paul and Philbin, J. and Adams, N.
Proceedings of the {SIGPLAN} 86 Symposium on Compiler Construction,
219-233
In his dissertation, David wrote the Stanford benchmark suite in T and
compared it against its equivalent in Pascal. The T code was compiled by
Orbit; the Pascal by the Apollo Pascal compiler. Both were run on an Apollo
DN3000. The numbers from his dissertation:
Program Pascal T
perm .95 .69
towers 1.24 1.03
quick .35 .26
fib .17 .12
tak .57 .30
bubble .73 .67
puzzle 3.17 3.33
intmm 2.41 2.45
Now, benchmarks are unreliable, blah, blah, blah, but I think you can
get a notion that good Lisp compilers can deliver performance competitive
with vanilla imperative language compilers -- on stock hardware, to boot.
Of course, highly optimising compilers, like Bliss-11, PL.8 or the new
round of risc C compilers just starting to surface are going to kick
Scheme compilers like Orbit. My thesis research addresses this next
increment in performance.
In general, I don't think special hardware is a worthwhile avenue for getting
performance for powerful languages, unless you're getting some *extreme*
architectural leverage. It is common knowledge that general-purpose processor
architectures move so fast that special hardware approaches are a very bad
bet. Symbolics' difficulties will testify to this eloquently, and Mr.
Mashey's excellent post is a nice summary of the situation. Furthermore,
if you're clever enough, you can implement languages like Lisp, Scheme and
ML on stock hardware quite nicely -- and then you can track the latest,
leanest & meanest technology courtesy of MIPS and Motorola and all those other
guys.
I used to think garbage collection was one area where you really had to
have special hardware support. But the new garbage collection algorithms
-- e.g., the Appel/Ellis/Li collector reported on in a DEC SRC tech report
and in the PLDI 88 conference proceedings -- implement very cheap, concurrent
garbage collection on stock hardware. GC is now at the point where it
is competitive with and sometimes superior to explicit storage management
in efficiency. So the general lesson is that compiler and runtime cleverness
can do amazingly well without requiring oddball hardware.
Of course, prolog, the particular subject of Mr. Van Roy's research, could
be another story altogether. I don't know much about performance
implementations of prolog. But holy cow, I'd hate to think my academic
hardware was going to have to compete with the tense stuff the maniacs at MIPS
crank out.
-Olin
--