Subject: compiler

From: [email-masked] (Phil Harrison)
Date: Thu, 22 Oct 1998 10:56:27 -0700

I experimented with CLISP on Solaris to run our grammar checker, 
which is written in Common Lisp.  CLISP was very easy to use, but 
the compiled code ran much too slowly to be deployable as a useful tool.
Our application needs an order of magnitude improvement in speed.  Is
anyone working to improve the CLISP compiler?   What is the state of
the compiler on other platforms besides Solaris?

---

From: Sam Steingold <[email-masked]>
Date: 22 Oct 1998 14:28:45 -0400

>>>> In message <[email-masked]>
>>>> On the subject of "compiler"
>>>> Sent on Thu, 22 Oct 1998 10:49:47 -0700 (PDT)
>>>> Honorable [email-masked] (Phil Harrison) writes:

CLISP compiles to bytecode, which is platform independent.
Depending on the kind of code you have, you can get a order of magnitude
speed-up by switching to CMUCL (http://www.cons.org/cmucl).
Another (more efficient!) way to speed up the code is to improve your
algorithms. :-)

-- 
Sam Steingold (http://www.goems.com/~sds) running RedHat5.1 GNU/Linux
Micros**t is not the answer.  Micros**t is a question, and the answer is Linux,
(http://www.linux.org) the choice of the GNU (http://www.gnu.org) generation.
I want Tamagochi! -- What for?  Your pet hamster is still alive!

---

From: Bruno Haible <[email-masked]>
Date: Thu, 22 Oct 1998 20:33:28 +0200 (MET DST)

Phil Harrison <[email-masked]> writes:
> Our application needs an order of magnitude improvement in speed.

Hmm. I estimate the speed gain of using a native compiler like CMUCL [1]
to be a factor 5 or so. If you want more than this, I suggest you get an
idea of what's eating up all that CPU time, by using the `space' macro of
CLISP, and the `metering' tool of Mark Kantrowitz [2].

> Is anyone working to improve the CLISP compiler?   What is the state of

The CLISP compiler is stable for a long time. Noone plans to let it
generate machine code directly - we don't have the resources to do that.
But if someone wants to let it generate C/C++/Java code and use gcc
as a "back end", he is welcome to do that.

                     Bruno

[1] ftp://ftp2.cons.org/pub/lisp/cmucl/release/
[2] ftp://ftp2.cons.org/pub/lisp/clisp/contrib/metering.lsp.gz

---

From: Raymond Toy <[email-masked]>
Date: Thu, 22 Oct 1998 14:53:03 -0400

>>>>> "Bruno" == Bruno Haible <[email-masked]> writes:

    >> Our application needs an order of magnitude improvement in speed.

    Bruno> Hmm. I estimate the speed gain of using a native compiler like CMUCL [1]
    Bruno> to be a factor 5 or so. If you want more than this, I suggest you get an
    Bruno> idea of what's eating up all that CPU time, by using the `space' macro of
    Bruno> CLISP, and the `metering' tool of Mark Kantrowitz [2].

But this is highly dependent on what you are running and how many
declarations you put in.

On some bignum code I did, I think CLISP was equal or slightly faster
than CMUCL, and used far less memory. (Sparc versions).  I used CLISP
in that particular application.

For heavy number crunching on single- or double-float numbers, with
appropriate declarations, I think 5 or 10 or more would be possible.
In fact, on my 16384-point complex FFT test with full declarations,
CLISP takes 2.42 sec to run.  CMUCL takes 0.06 sec, a factor of 40.
This doesn't mean you'll always get 40!

I still think CLISP is a great Lisp:  small and quite fast for many
things. 

Ray

---

From: Sam Steingold <[email-masked]>
Date: 22 Oct 1998 15:13:20 -0400

>>>> In message <[email-masked]>
>>>> On the subject of "Re: compiler"
>>>> Sent on Thu, 22 Oct 1998 11:19:32 -0700 (PDT)
>>>> Honorable Bruno Haible <[email-masked]> writes:
 >> 
 >> If someone wants to let it generate C/C++/Java code and use gcc as a
 >> "back end", he is welcome to do that.

IIRC, gcc compiles c/c++/obj-c to some internal intermediate
pseuso-assembler.
Would it be a reasonable idea to compile CLISP into that?  

-- 
Sam Steingold (http://www.goems.com/~sds) running RedHat5.1 GNU/Linux
Micros**t is not the answer.  Micros**t is a question, and the answer is Linux,
(http://www.linux.org) the choice of the GNU (http://www.gnu.org) generation.
A computer scientist is someone who fixes things that aren't broken.

---

From: Rodrigo Ventura <[email-masked]>
Date: Fri, 23 Oct 1998 09:10:36 GMT

>>>>> "Sam" == Sam Steingold <[email-masked]> writes:

    >>> "back end", he is welcome to do that.

    Sam> IIRC, gcc compiles c/c++/obj-c to some internal intermediate
    Sam> pseuso-assembler.
    Sam> Would it be a reasonable idea to compile CLISP into that?  

        Yeah, I like that idea too. That intermediate language is
called RTL (register transfer language). I suppose this language is
completely platform independent, but I'm not quite sure. Probably
not. Here is a sample of it (gcc -dr yproxy.c):

(insn 290 289 291 (set (mem:QI (plus:SI (reg:SI 18)
                (const_int -298)))
        (asm_operands/v ("btl %1,%2 ; setb %0") ("=q") 0[ 
                (mem:SI (plus:SI (reg:SI 18)
                        (const_int -8)))
                (mem/s:BLK (plus:SI (reg:SI 18)
                        (const_int -288)))
            ] 
            [ 
                (asm_input:SI ("r"))
                (asm_input:BLK ("m"))
            ]  ("yproxy.c") 211)) -1 (nil)
    (nil))

Sounds familiar? He he.... Maybe a huge macro would do the job....

        BTW, I read somewhere that the interpretative nature of CLISP
(in the sense that it interprets compiled bytecodes) is a plus in
certain aspects. I was wondering in what respects, specifically, would
the whole CLISP philosofy would be affected by the use of an assembly
level compiler. How hard it is to compile to assembly after all?

        Best regards,

-- 
--

*** Rodrigo Martins de Matos Ventura, alias <Yoda>
***  [email-masked], http://www.isr.ist.utl.pt/~yoda
***   Instituto de Sistemas e Robotica, Polo de Lisboa
***    Instituto Superior Tecnico, Lisboa, Portugal
***     PGP Public Key available on my homepage
*** Key fingerprint = 0C 0A 25 58 46 CF 14 99  CF 9C AF 9E 10 02 BB 2A

---

From: Bruno Haible <[email-masked]>
Date: Fri, 23 Oct 1998 15:02:41 +0200 (MET DST)

> Would it be a reasonable idea to compile CLISP into that?  

What would be the benefits and drawbacks vs. compiling to C ?

* Benefits:

  You can do some things which you cannot express in C:
  - Functions with multiple entry points, useful for functions with keyword
    arguments.
  - unwind-protect and handler-case (although you can express them in Java,
    which means that gcc already has support for it).

* Drawbacks:

  - Compiling into gcc's tree and rtl representations is a lot of work.
    When clisp's compiler, written in Lisp, is 500KB, you can imagine its
    size if it were written in C. (Just for comparison, the Java frontend
    of gcc is already 2.5 MB of C code right now.) And if it's not written
    in C, you have a bootstrapping problem (like GNAT, the GNU Ada compiler,
    has).

  - When compiling to C, you have distinct passes, which makes development
    and bug tracking a lot easier: just have a look at the intermediate C file
    and you know whether the bug is in the Lisp to C compiler or in the C to
    machine code compiler.

Rodrigo Ventura <[email-masked]> writes:

> certain aspects.

One plus is that is consumes not much memory. Another one, that it's
easy to develop :-)

> I was wondering in what respects, specifically, would the whole CLISP
> philosophy would be affected by the use of an assembly level compiler.

You would get an implementation like CMUCL.

> How hard it is to compile to assembly after all?

Very hard. The core development deam of GCC comprises 20 persons.
Lots of platforms have to be supported, with lots of calling conventions.
Register allocation and instruction scheduling are hard.

Bruno

---

From: Rodrigo Ventura <[email-masked]>
Date: Fri, 23 Oct 1998 13:36:45 GMT

>> How hard it is to compile to assembly after all?

    Bruno> Very hard. The core development deam of GCC comprises 20 persons.
    Bruno> Lots of platforms have to be supported, with lots of calling conventions.
    Bruno> Register allocation and instruction scheduling are hard.

        Ok, but much of that effort is to produce assembly code as
efficient as possible. I guess that a plain C->assembly compiler is
not all that complex, although awfuly slow.

        But I suppose that translating LISP directly into assembly is
an extremely difficult task. But let me ask, how hard is it to
translate from the CLISP bytecode into assembly? The CLISP VM is a
stack machine, right? Isn't it straightforward to turn that into
assembly, say, using memory stack instead of taking advantage of the
multiple registers? Even this inefficient way would be faster than the
present implementation, which I suppose must use some sort of dispatch
table and manual instruction fetch loop.

        Best Regards,

-- 
--

---

From: Sam Steingold <[email-masked]>
Date: 23 Oct 1998 10:46:49 -0400

>>>> In message <[email-masked]>
>>>> Sent on Fri, 23 Oct 1998 05:49:36 -0700 (PDT)

I did not realize these arguments!
My idea was that *.fas byte-code might be ideologically closer to the
gcc's "pseuso-assembler", so the compilation might be easier.

 >>     in C, you have a bootstrapping problem (like GNAT, the GNU Ada compiler,

Nope.  You are saying that CLISP will deteriorate into the CMUCL's
disaster of "you need cmucl to build cmucl".  Not necessarily.
IIUC from observing the CLISP build process, it goes like this:

1. build lisp.run from *.d
2. load *.lsp and dump interpreted.mem
3. compile compiler.lsp (into compiler.fas)
4. load *.lsp + compiler.fas and dump halfcompiled.mem
5. compile *.lsp (into *.fas)
6. load *.fas and dump lispinit.mem.

Now the native compiler will add the following steps:

7. compile native-comp.fas (into native-comp.bin)
8. load native-comp.bin and dump binhalfcompiled.mem [this step can be omitted]
9. compile *.fas (into *.bin)
10. load *.bin and dump lispinitbin.mem

Yes, this is 50-60% more at build time.  If it will buy orders of magnitude
of speedup, it is worth it.

 >>     and you know whether the bug is in the Lisp to C compiler or in the C to

This is a very strong point.

Another drawback (moderate) is that this would mean sticking with gcc -
no other C compiler would do.

The issue here is: will CLISP remain "a nice small CL for fun" or will
it graduate to an "industry strength implementation".

IMO, "industry strength" means
 - MT
 - ANSI
 - native compilation.

-- 
Sam Steingold (http://www.goems.com/~sds) running RedHat5.1 GNU/Linux
Micros**t is not the answer.  Micros**t is a question, and the answer is Linux,
(http://www.linux.org) the choice of the GNU (http://www.gnu.org) generation.
MS DOS: Keyboard not found. Press F1 to continue.

---

From: Bruno Haible <[email-masked]>
Date: Fri, 23 Oct 1998 17:34:27 +0200 (MET DST)

Rodrigo Ventura <[email-masked]> writes:

> But let me ask, how hard is it to

You're right. Such a direct bytecode to machine code translation would
be about twice as fast as current clisp. (I know that half of the time
of the bytecode interpreter is spent in fetching and decoding the bytecode
instructions.) For a widely used CPU, such as x86, I think it's worth
doing.

Bruno

---

From: Immanuel Litzroth <[email-masked]>
Date: Fri, 23 Oct 1998 19:36:54 +0200

>>>>> "Sam Steingold" == Sam Steingold <[email-masked]> writes:

    Sam Steingold> IIRC, gcc compiles c/c++/obj-c to some internal
    Sam Steingold> intermediate pseuso-assembler.  Would it be a
    Sam Steingold> reasonable idea to compile CLISP into that?

Thought about this too, but the following fragment comes from the gcc
info file.

>   People frequently have the idea of using RTL stored as text in a
>file as an interface between a language front end and the bulk of GNU
>CC.  This idea is not feasible.

>   GNU CC was designed to use RTL internally only.  Correct RTL for a
>given program is very dependent on the particular target machine.  And
>the RTL does not contain all the information about the program.

>   The proper way to interface GNU CC to a new language front end is
>with the "tree" data structure.  There is no manual for this data
>structure, but it is described in the files `tree.h' and `tree.def'.

Maybe someone should check this out, as I have not the time (or the
skills).
Immanuel

---

From: Raymond Toy <[email-masked]>
Date: Sun, 25 Oct 1998 07:54:10 -0500

>>>>> "Sam" == Sam Steingold <[email-masked]> writes:

    Sam> Nope.  You are saying that CLISP will deteriorate into the CMUCL's
    Sam> disaster of "you need cmucl to build cmucl".  Not necessarily.
    Sam> IIUC from observing the CLISP build process, it goes like this:

No seems to consider gcc to be a disaster.  Have you ever tried
building it without a C compiler?  So, you basically need "gcc to
build gcc".  

The only real difference is that no one has made it possible to
compile CMUCL's compiler on a different lisp.

Ray

---

From: Sam Steingold <[email-masked]>
Date: 25 Oct 1998 11:24:14 -0500

>>>> In message <[email-masked]>
>>>> Sent on Sun, 25 Oct 1998 04:41:11 -0800 (PST)
>>>> Honorable Raymond Toy <[email-masked]> writes:

I must admit that I have never compiled gcc myself, but I would expect
that if I have a working Linux with, say, gcc 2.7, I will be able to
do exactly this:

$ tar zxfv gcc-2.8.tgz
$ cd gcc-2.8
$ ./configure
$ make
$ make install

I would be surprised if the procedure were much different.

With cmucl I have to type esoteric commands by hand (there are no
makefiles, no configure script, nothing), and at the end, when
everything fails, I am told that CMUCL 18a+ cannot compile CMUCL 18b. 

 >> compile CMUCL's compiler on a different lisp.

A crucial difference!  Also, even older versions of CMUCL can't compile
a new CMUCL, which is mildly strange (yes, I read the relevant thread in
c.l.l).

Nobody is trying to insult or denigrate CMUCL, mind you.

-- 
Sam Steingold (http://www.goems.com/~sds) running RedHat5.1 GNU/Linux
Micros**t is not the answer.  Micros**t is a question, and the answer is Linux,
(http://www.linux.org) the choice of the GNU (http://www.gnu.org) generation.
Bus error -- please leave by the rear door.

---

From: Raymond Toy <[email-masked]>
Date: Mon, 26 Oct 1998 09:29:35 -0500

>>>>> "Sam" == Sam Steingold <[email-masked]> writes:

    Sam> With cmucl I have to type esoteric commands by hand (there are no
    Sam> makefiles, no configure script, nothing), and at the end, when
    Sam> everything fails, I am told that CMUCL 18a+ cannot compile CMUCL 18b. 

There are scripts in the tools directory.  I've never used them,
except for worldbuild and worldload.  I do it with home-made scripts.

    >>> compile CMUCL's compiler on a different lisp.

    Sam> A crucial difference!  Also, even older versions of CMUCL can't compile
    Sam> a new CMUCL, which is mildly strange (yes, I read the relevant thread in
    Sam> c.l.l).

I guess that's just the nature of lisp:  compiling a lisp can modify the 
running lisp.

    Sam> Nobody is trying to insult or denigrate CMUCL, mind you.

None taken.  I agree that it's bad for CMUCL that building is so
hard.  I think CMUCL would progress much faster than it has if it
weren't so hard.  It took many months to get specialized support for
complex numbers in, and that wasn't particularly hard.

It would be nice if CLISP could be used to compile up a new version of 
CMUCL.  I guess all the principal developers are too busy for such a
mundane task.  Oh, well.

Ray

---

From: Sam Steingold <[email-masked]>
Date: 26 Oct 1998 10:19:14 -0500

>>>> In message <[email-masked]>
>>>> Sent on Mon, 26 Oct 1998 06:15:31 -0800 (PST)
 >> It would be nice if CLISP could be used to compile up a new version
 >> of CMUCL.

I wonder what breaks when CLISP loads Python.

---

From: Raymond Toy <[email-masked]>
Date: Mon, 26 Oct 1998 10:26:20 -0500

>>> It would be nice if CLISP could be used to compile up a new version

    Sam> I wonder what breaks when CLISP loads Python.

It's mostly the fact that the packages and stuff don't exist.  You
have to go track down lots of support packages, then compile, and load
them, before you can actually compile Python.  After an hour of so, I
stopped trying.  I should try again, because I know much more about
CMUCL than I did then....

Ray

---

From: Raymond Toy <[email-masked]>
Date: Wed, 28 Oct 1998 17:09:47 -0500

>> table and manual instruction fetch loop.

    Bruno> You're right. Such a direct bytecode to machine code translation would
    Bruno> be about twice as fast as current clisp. (I know that half of the time
    Bruno> of the bytecode interpreter is spent in fetching and decoding the bytecode
    Bruno> instructions.) For a widely used CPU, such as x86, I think it's worth
    Bruno> doing.

Wouldn't it be possible to cache or compile the bytecode lookup
directly into the corresponding built-in native lisp ops?  I might be
way off base here, since I don't know how the compiler/bytecode
interpreter works.

If this works, then everyone wins, and it might be easier to do than
compile to x86 code.

Ray