From: tammet@cs.chalmers.se (Tanel Tammet) Newsgroups: comp.lang.scheme Subject: Hobbit4a (Scheme->C compiler for scm) now available Date: 24 Mar 1995 14:37:59 MET Organization: Dept. of CS, Chalmers, Sweden Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit
The new version 4a of the Scheme->C compiler Hobbit is available from ftp.cs.chalmers.se:/pub/users/tammet/hobbit4a.tar.gz.
Differently from the earlier versions of Hobbit, the version 4a compiles full Report 4 Scheme.
Hobbit is written by Tanel Tammet (tammet@cs.chalmers.se) and it requires the scm interpreter of A.Jaffer (jaffer@ai.mit.edu). The development version of scm can be obtained from altdorf.ai.mit.edu:pub/jaffer/scm.zip.
Hobbit is a small optimizing scheme->C compiler written in Report 4 scheme and intended for use together with the scm scheme interpreter of A.Jaffer. Hobbit compiles full Report 4 scheme, except that:
The current version of hobbit works together with the scm versions of scm4e2 born after February 1995. It is crucial that your scm version supports compiled closures:
#define CCLO
must be present in scmfig.h.
Hobbit compiles scheme files to C files and does not provide anything else by itself (eg. calling the C compiler, dynamic loading). Such niceties are provided by the scm library. You can also call the compiler and linker yourself or with the help of a Makefile.hob. See the scm manual and section 5 (Using hobbit) of the current document.
Hobbit distribution consists of six files, approximately 280K altogether.:
hobbit.scm - the hobbit compiler.
scmhob.scm - the file defining some additional procedures recognized
by hobbit as primitives. Use it with the interpreter only.
scmhob.h - the common headerfile for hobbit-compiled C files.
Makefile.hob - a UNIX makefile modified for compiling and linking
hobbit-produced C sources.
hobbit.doc - documentation for hobbit (current file).
hobbit.tms - terms for copying, redistribution and usage.
The development version of scm can be obtained by anonymous ftp from
altdorf.ai.mit.edu:pub/jaffer/scm.zip. Hobbit4a can be obtained (at
least) from ftp.cs.chalmers.se:/pub/users/tammet/hobbit4a.tar.gz.
A.Jaffer (jaffer@ai.mit.edu), the author of scm, has been of major help with a number of suggestions and hacks, especially concerning the interface between compiled code and the scm interpreter.
Several people have helped with suggestions and detailed bug reports, e.g. David J. Fiander (davidf@mks.com), Gordon Oulsnam (STCS8004@IRUCCVAX.UCC.IE), Pertti Kelloma"ki (pk@cs.tut.fi), Dominique de Waleffe (ddw2@sunbim.be) Terry Moore (tmm@databook.com), Marshall Abrams (ab2r@midway.uchicago.edu). Georgy K. Bronnikov (goga@bronnikov.msk.su), Bernard Urban (Bernard.URBAN@meteo.fr), Charlie Xiaoli Huang, Tom Lord (lord@cygnus.com).
Hobbit is developed with two main aims:
1) Producing maximally fast C code from simple scheme code.
By 'simple' we mean code which does not rely on procedures returning procedures (closures) and nontrivial forms of higher-order procedures. All the latter are also compiled, but the optimizations specially target simple code fragments. Hobbit performs global optimization in order to locate such fragments.
2) Producing C code which would preserve as much original scheme code structure as possible, to enable using the output C code by a human programmer (eg. for introducing special optimizations possible in C). Also, this will hopefully help the C compiler to find better optimizations.
The author has so far compiled and tested a number of large programs (theorem provers for various logics and hobbit itself).
The speedup for the provers was between 25 and 40 times for various provable formulas.
The provers were written with care to make the compiled version run fast. They do not perform excessive consing and they perform very little arithmetic.
According to experiments made by A.Jaffer, the compiled form of the example program pi.scm was approximately 11 times faster than the interpreted form.
As a comparison, his hand-coded C program for the same algorithm of computing pi was about 12 times faster than the interpreted form. pi.scm spends most of of its time in immediate arithmetics, vector-ref and vector-set!.
P.Kelloma"ki has reported a 20-fold speedup for his generic scheme debugger. T.Moore has reported a 16-fold speedup for a large gate-level IC optimizer.
Selfcompilation speeds Hobbit up only ca 10 times.
There are also examples where the code compiled by hobbit runs actually slower than the same code running under interpreter: this may happen in case the speed of the code relies on non-liftable closures and proper mutual tailrecursion. See for example the closure-intensive benchmark CPSTAK in the following table.
We will present a table with the performance of three scheme systems on a number of benchmarks: interpreted scm, byte-compiled VSCM and hobbit-compiled code. The upper 13 benchmarks of the table are the famous Gabriel benchmarks (originally written for lisp) modified for scheme by Will Clinger. The lower five benchmarks of the table are proposed by other people.
Hobbit performs well on most of the benchmarks except CPSTAK and CTAK: CPSTAK is a closure-intensive tailrecursive benchmark and CTAK is a continuations-intensive benchmark. Hobbit performs extremely well on these benchmarks which essentially satisfy the criterias for well-optimizable code outlined in the section 6 above.
FFT is real-arithmetic-intensive.
All times are in seconds.
SCM 4c0(U) and 1.1.5*(U) (the latter is the newest version of VSCM) are compiled and run by Matthias Blume on a DecStation 5000 (Ultrix). VSCM is a bytecode-compiler using continuation-passing style, and is well optimized for continuations and closures.
SCM 4e2(S) and Hobbit4x(S) compiled (with cc -xO3) and run by Tanel Tammet on a Sun SS10 (lips.cs.chalmers.se). Hobbit is a Scheme->C compiler for scm, the code it produces does not do any checking. Scm and hobbit are not optimized for continuations. Hobbit is not optimized for closures and proper mutual tailrecursion.
SCM and Hobbit benchmarks were run giving ca 8 MB of free heap space before each test.
Benchmark |SCM 4c0(U) 1.1.5*(U)| SCM 4e2(S) Hobbit4x(S) ----------------|------------------------------------------------ Deriv | 3.40 3.86 | 3.3 0.283 Div-iter | 3.45 2.12 | 3.1 0.13 Div-rec | 3.45 2.55 | 3.8 0.75 TAK | 1.81 1.71 | 1.5 0.027 TAKL |14.50 11.32 | 13.8 0.23 TAKR | 2.20 1.64 | 1.7 0.035 Destruct | ? ? | 8.3(1.3 in gc) 0.33 Boyer | ? ? | 29.(2.3 in gc) 1.9 CPSTAK | 2.72 2.64 | 2.0 3.46(2.83 in gc) CTAK |31.0 4.11 | memory memory CTAK(7 6 1) | ? ? | 0.83 0.74 FFT |12.45 15.7 | 11.3 1.15 Puzzle | 0.28 0.41 | 0.26 0.02 ---------------------------------------------------------------- (recfib 25) | ? ? | 7.5 0.133 (recfib 30) | ? ? | 80. (8.7 in gc) 1.5 (pi 300 3) | ? ? | 9.3 0.7 (hanoi 15) | ? ? | 0.91 0.011 (hanoi 20) | ? ? | 33.9 (6. in gc) 0.31 ----------------------------------------------------------------