Hobbit4a (Scheme->C compiler for scm) now available

                                                  ANNOUNCEMENT


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.


Excerpts from the documentation:
--------------------------------


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:


(*) It does not fully conform to the requirement of being properly
tail-recursive: non-mutual tailrecursion is detected, but mutual
tailrecursion is not.
(*) Macros from the Report 4 appendix are not supported (yet):
only the common-lisp-like defmacro is supported.


Hobbit treats scm files as a C library and provides integration of compiled
procedures and variables with the scm interpreter as new primitives.


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).


2. The aims of developing hobbit
--------------------------------


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.




10. Gain in speed: examples and benchmarks
------------------------------------------


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.


Benchmarks
----------


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
----------------------------------------------------------------


--

Return to the comp.compilers page.
Search the comp.compilers archives again.