From: quasi
Subject: compiled code
Date: 
Message-ID: <3d7edbb2.2307456@News.CIS.DFN.DE>
Friends,
	Excue me.  But this quiestion seems confusing to me but may
turn out to to extremely silly.  Because of the confusion I may be a
little long-winded. 

	In my understanding, when a compiler compiles to native binary
then that binary contains instructions for the CPU, right?
	Say, I have a program in C which at some point has a function
foo which does complex numerical calculates.  Now a C compiler
compiles this function and writes some binary instructions for it,
right?
	Now suppose this same program I am doing in Lisp (CMUCL, say)
then for foo (the algorithm is the same)  the compiler generates
binary instructions, right?
	But then, why is it so that the instructions created by the C
compiler are supposed to work faster than those instructions created
by the Lisp compiler (regarding foo)?  Is there some inherent reason
for this?

thanks,
quasi

From: Stefan Schmiedl
Subject: Re: compiled code
Date: 
Message-ID: <almpj3$1rekgj$1@ID-57631.news.dfncis.de>
On Wed, 11 Sep 2002 06:18:13 GMT,
quasi <······@vsnl.net> wrote:
> Friends,
> 	Excue me.  But this quiestion seems confusing to me but may
> turn out to to extremely silly.

Questions are what the respondents make them.

> 
> 	In my understanding, when a compiler compiles to native binary
> then that binary contains instructions for the CPU, right?

yes, "machine code".

> 	Say, I have a program in C which at some point has a function
> foo which does complex numerical calculates.  Now a C compiler
> compiles this function and writes some binary instructions for it,
> right?

yes.

> 	Now suppose this same program I am doing in Lisp (CMUCL, say)
> then for foo (the algorithm is the same)  the compiler generates
> binary instructions, right?

yes, but those can be different from the one the C compiler generates.


> 	But then, why is it so that the instructions created by the C
> compiler are supposed to work faster than those instructions created
> by the Lisp compiler (regarding foo)?  Is there some inherent reason
> for this?

Because in "classical C", which is a kind of high level assembler,
you put in a lot of work yourself so that the compiler can generate
very good code. Not optimal, but very good.

Many of the "higher level languages" take some of the programmers'
burden off their shoulders (e.g. by offering dynamic typing) and
take some runtime penalty for this. Imagine having to access every
"real" chunk of data through a pointer. Then your compiler would
still be able to generate machine code for this, but the instructions
would have to use indirection, which involves more memory access,
which takes longer.

IIRC, some Lisp implementation use "boxed floating point numbers",
on which you might do a google search. One of the results is:
http://makeashorterlink.com/?I54A210C1

For another example check out the story of Mel, which is in
one of the appendices of "The New Hacker's Dictionary", I think.
Do a google for "most pessimum" including the quotes, and you're set.

s.
From: quasi
Subject: Re: compiled code
Date: 
Message-ID: <3d7f2ee3.182663@News.CIS.DFN.DE>
On 11 Sep 2002 06:58:43 GMT, Stefan Schmiedl <·@xss.de> wrote:

>For another example check out the story of Mel, which is in
>one of the appendices of "The New Hacker's Dictionary", I think.
>Do a google for "most pessimum" including the quotes, and you're set.
>
>s.
>

good story.  I get the point.
From: Friedrich Dominicus
Subject: Re: compiled code
Date: 
Message-ID: <87y9a9aum0.fsf@fbigm.here>
······@vsnl.net (quasi) writes:

> 	But then, why is it so that the instructions created by the C
> compiler are supposed to work faster than those instructions created
> by the Lisp compiler (regarding foo)?  Is there some inherent reason
> for this?
Less checks. C does not look after array bounds violations and in fact
if the question in C is speed of safety with 99% likeliness C
programmers will go for speed. Those who do not are those one should
hire, they know what they do.

Another example
C does just work with integers of a known length. That mean if you use
there type int you usually get results modulo wordsiz.e. In Lisp you
got the correct result.

And so it goes on and on. You can check out the different code
yourself in both languages. Just compile down to Assembler and inspect
the code. You'll see that, depending on the settings, C will never
insert extra check which do not have explicitly stated. Common Lisp
will do that just if you drop all safety, you'll see that both will
generate very simular code. 

Well my preference should be clear. Speed is nothing worth without
correctness. 

Friedrich
From: Joe Marshall
Subject: Re: compiled code
Date: 
Message-ID: <y9a8twm5.fsf@ccs.neu.edu>
······@vsnl.net (quasi) writes:

> 	In my understanding, when a compiler compiles to native binary
> then that binary contains instructions for the CPU, right?

Essentially yes.

> 	Say, I have a program in C which at some point has a function
> foo which does complex numerical calculates.  Now a C compiler
> compiles this function and writes some binary instructions for it,
> right?

Ok.

> 	Now suppose this same program I am doing in Lisp (CMUCL, say)
> then for foo (the algorithm is the same)  the compiler generates
> binary instructions, right?

Ok.

> 	But then, why is it so that the instructions created by the C
> compiler are supposed to work faster than those instructions created
> by the Lisp compiler (regarding foo)?  

They won't.  The instructions work at the same speed regardless of
what the source code language was.

HOWEVER, it is can be quite difficult to write `the same' code in Lisp
and in C.  To give a very small example, suppose you wrote function
foo that `simply' added two numbers:

int foo (int left, int right)
{
  return left + right;
}

(defun foo (left right)
  (+ left right))

The C code compiles to this:

  push        ebp  
  mov         ebp,esp 
  mov         eax,dword ptr [right] 
  mov         ecx,dword ptr [left] 
  add         eax,ecx 
  pop         ebp  
  ret

And the Lisp code compiles to this:

  push    ebp
  mov     ebp,esp
  push    edi
  cmp     ecx,00002h
  je      000F
  call    near dword ptr [esi+0000010BCh]
  push    dword ptr [ebp+0000Ch]
  mov     eax,[ebp+00008h]
  pop     edx
  test    al,007h
  jne     0025
  test    dl,007h
  jne     0025
  add     eax,edx
  jno     002B
  sub     eax,edx
  call    near dword ptr [esi+0000017FCh]
  mov     ecx,0001
  mov     esp,ebp
  pop     ebp
  ret

These are clearly different.  The reason is that although the C and
the Lisp code superficially resemble one another, the Lisp code is
doing far more work.  These instructions:

  cmp     ecx,00002h
  je      000F
  call    near dword ptr [esi+0000010BCh]

ensure that FOO is invoked with exactly two
arguments.  The C code doesn't bother to check.

These instructions:

  test    al,007h
  jne     0025
  test    dl,007h
  jne     0025

check whether both the arguments are fixnums.  If they are not, the
out-of-line addition operation is called.

This instruction:

  jno     002B

checks that the result did not overflow.

Finally this instruction:

  mov     ecx,0001

notifies the caller that a single value is being returned.

The lisp code

(defun foo (left right)
  (+ left right))

is closer to this C code:

Object * foo (int argcount, Object * left, Object * right)
{
    register int result;

    if (argcount != 2)
        wrong_number_of_arguments ();

    return (((char) left) == FIXNUM_CODE 
             && ((char) right) == FIXNUM_CODE
             && (result = left + right, 
                  __no_overflow()))   // assume some sort of intrinsic
           ? result
           : generic_add (left, right);
}

It is pretty hard to write safe, generic code in C.
 
From: Duane Rettig
Subject: Re: compiled code
Date: 
Message-ID: <41y80cz9s.fsf@beta.franz.com>
Joe Marshall <···@ccs.neu.edu> writes:

> int foo (int left, int right)
> {
>   return left + right;
> }
> 
> (defun foo (left right)
>   (+ left right))
> 
> The C code compiles to this:
> 
>   push        ebp  
>   mov         ebp,esp 
>   mov         eax,dword ptr [right] 
>   mov         ecx,dword ptr [left] 
>   add         eax,ecx 
>   pop         ebp  
>   ret

This is actually pretty bad compilation - it is not tail-merging and
is using stack for no good reason.  I suspect that
if you use a -O option on whatever C compiler you are using,
you will get better code.

Also, I understand that the point of your post was to show how
difficult it was to do generic coding in C, but also it is
important to know how easy it is to do fast programming in lisp -
the same example with a few declarations can be as fast or faster
than the C version.  In Allegro CL:

CL-USER(9): (compile (defun foo (left right)
                       (declare (optimize speed (safety 0) (debug 0))
                                (fixnum left right))
                       (+ left right)))
FOO
NIL
NIL
CL-USER(10): (disassemble 'foo)
;; disassembly of #<Function FOO>
;; formals: LEFT RIGHT

;; code start: #x714980a4:
   0: 03 c2       addl	eax,edx
   2: f8          clc
   3: 8b 75 fc    movl	esi,[ebp-4]
   6: c3          ret
   7: 90          nop
CL-USER(11): 

The extra nop is included in the code vector for alignment purposes
only and has no bearing on execution.

-- 
Duane Rettig    ·····@franz.com    Franz Inc.  http://www.franz.com/
555 12th St., Suite 1450               http://www.555citycenter.com/
Oakland, Ca. 94607        Phone: (510) 452-2000; Fax: (510) 452-0182   
From: Matthew Danish
Subject: Re: compiled code
Date: 
Message-ID: <20020911132946.J23781@lain.res.cmu.edu>
On Wed, Sep 11, 2002 at 04:00:01PM +0000, Duane Rettig wrote:
> CL-USER(9): (compile (defun foo (left right)
>                        (declare (optimize speed (safety 0) (debug 0))
>                                 (fixnum left right))
>                        (+ left right)))
> FOO
> NIL
> NIL
> CL-USER(10): (disassemble 'foo)
> ;; disassembly of #<Function FOO>
> ;; formals: LEFT RIGHT
> 
> ;; code start: #x714980a4:
>    0: 03 c2       addl	eax,edx
>    2: f8          clc
>    3: 8b 75 fc    movl	esi,[ebp-4]
>    6: c3          ret
>    7: 90          nop
> CL-USER(11): 

Very nice output =)  But how does it know that the result is a fixnum?

-- 
; Matthew Danish <·······@andrew.cmu.edu>
; OpenPGP public key: C24B6010 on keyring.debian.org
; Signed or encrypted mail welcome.
; "There is no dark side of the moon really; matter of fact, it's all dark."
From: Erik Naggum
Subject: Re: compiled code
Date: 
Message-ID: <3240786408336302@naggum.no>
* Matthew Danish
| Very nice output =)  But how does it know that the result is a fixnum?

  Allegro CL has a compiler optimization switch that makes declared fixnums
  remain fixnums.  It defaults to true only when speed is 3 and safety 0.  If
  you turn it off, the same Common Lisp code produces more machine code:

   0: c1 f8 02    sarl	eax,$2
   3: c1 fa 02    sarl	edx,$2
   6: 03 c2       addl	eax,edx
   8: ff a7 87 00 jmp	*[edi+135]      ; sys::fixnum-or-bignum
      00 00 

  The shifts convert from the fixnum representation (two type tag bits) to the
  machine integer and the tail-called function will shift the sum back if there
  is space or cons a bignum if not.

-- 
Erik Naggum, Oslo, Norway

Act from reason, and failure makes you rethink and study harder.
Act from faith, and failure makes you blame someone and push harder.
From: Frode Vatvedt Fjeld
Subject: Re: compiled code
Date: 
Message-ID: <2hlm68jbmm.fsf@vserver.cs.uit.no>
Matthew Danish <·······@andrew.cmu.edu> writes:

> But how does it know that the result is a fixnum?

Agreed. That looks to me to be a false conclusion by the
compiler. Unless the (safety 0) somehow makes it okay.

-- 
Frode Vatvedt Fjeld
From: Nils Goesche
Subject: Re: compiled code
Date: 
Message-ID: <lkd6rkzidn.fsf@pc022.bln.elmeg.de>
Joe Marshall <···@ccs.neu.edu> writes:

> ······@vsnl.net (quasi) writes:
> 
> > 	But then, why is it so that the instructions created by the C
> > compiler are supposed to work faster than those instructions created
> > by the Lisp compiler (regarding foo)?  
> 
> They won't.  The instructions work at the same speed regardless of
> what the source code language was.
> 
> HOWEVER, it is can be quite difficult to write `the same' code in Lisp
> and in C.  To give a very small example, suppose you wrote function
> foo that `simply' added two numbers:
> 
> int foo (int left, int right)
> {
>   return left + right;
> }
> 
> (defun foo (left right)
>   (+ left right))
> 
> The C code compiles to this:
> 
>   push        ebp  
>   mov         ebp,esp 
>   mov         eax,dword ptr [right] 
>   mov         ecx,dword ptr [left] 
>   add         eax,ecx 
>   pop         ebp  
>   ret
> 
> And the Lisp code compiles to this:

[snip longer code]

> These are clearly different.  The reason is that although the C and
> the Lisp code superficially resemble one another, the Lisp code is
> doing far more work.

> It is pretty hard to write safe, generic code in C.

But if you really want to, you often can tell your Lisp compiler to
omit many security checks.  For instance, in Lispworks you get

CL-USER 35 > (defun foo (left right)
               (declare (optimize speed (safety 0) (debug 0)
                                  (space 0) (compilation-speed 0))
                        (fixnum left right))
               (the fixnum (+ left right)))
FOO

CL-USER 36 > (compile 'foo)
FOO
NIL
NIL

CL-USER 37 > (disassemble 'foo)
2066C85A:
       0:      55               push  ebp
       1:      89E5             move  ebp, esp
       3:      8B7D08           move  edi, [ebp+8]
       6:      03C7             add   eax, edi
       8:      FD               std   
       9:      C9               leave 
      10:      C20400           ret   4
      13:      90               nop   
NIL

Regards,
-- 
Nils Goesche
"Don't ask for whom the <CTRL-G> tolls."

PGP key ID 0x0655CFA0
From: Marco Antoniotti
Subject: Re: compiled code
Date: 
Message-ID: <y6chegwa5u2.fsf@octagon.mrl.nyu.edu>
Nils Goesche <······@cartan.de> writes:

> Joe Marshall <···@ccs.neu.edu> writes:
> 
> > ······@vsnl.net (quasi) writes:
> > 
> > > 	But then, why is it so that the instructions created by the C
> > > compiler are supposed to work faster than those instructions created
> > > by the Lisp compiler (regarding foo)?  
> > 
> > They won't.  The instructions work at the same speed regardless of
> > what the source code language was.
> > 
> > HOWEVER, it is can be quite difficult to write `the same' code in Lisp
> > and in C.  To give a very small example, suppose you wrote function
> > foo that `simply' added two numbers:
> > 
> > int foo (int left, int right)
> > {
> >   return left + right;
> > }
> > 
> > (defun foo (left right)
> >   (+ left right))
> > 
> > The C code compiles to this:
> > 
> >   push        ebp  
> >   mov         ebp,esp 
> >   mov         eax,dword ptr [right] 
> >   mov         ecx,dword ptr [left] 
> >   add         eax,ecx 
> >   pop         ebp  
> >   ret
> > 
> > And the Lisp code compiles to this:
> 
> [snip longer code]
> 
> > These are clearly different.  The reason is that although the C and
> > the Lisp code superficially resemble one another, the Lisp code is
> > doing far more work.
> 
> > It is pretty hard to write safe, generic code in C.
> 
> But if you really want to, you often can tell your Lisp compiler to
> omit many security checks.  For instance, in Lispworks you get
> 
> CL-USER 35 > (defun foo (left right)
>                (declare (optimize speed (safety 0) (debug 0)
>                                   (space 0) (compilation-speed 0))
>                         (fixnum left right))
>                (the fixnum (+ left right)))
> FOO
> 
> CL-USER 36 > (compile 'foo)
> FOO
> NIL
> NIL
> 
> CL-USER 37 > (disassemble 'foo)
> 2066C85A:
>        0:      55               push  ebp
>        1:      89E5             move  ebp, esp
>        3:      8B7D08           move  edi, [ebp+8]
>        6:      03C7             add   eax, edi
>        8:      FD               std   
>        9:      C9               leave 
>       10:      C20400           ret   4
>       13:      90               nop   
> NIL
> 


Thanks for the example.  A very good example of the "First get it
right, then get it fast" doctrine.

Looking at it, I think that one of the things that makes CL kind of
"strange" to the C/C++ programmer is the necessity of adding "strange"
declarations like the

        (the fixnum (+ left right)))

IMHO, CL declarations, altough somtime syntactically encumbrant, are
very well thouth out.  E.g. the above is a promise to the compiler the
the result will fit in a 'fixnum'.  Obviously you should not make such
promise lightheartedly.  But this is exactly what you do (myself
included, of course) whenever I write a piece of C code that does not
check for integer overflows (something that may be ok in most cases,
but maybe not when you declare your variable 'short').

Cheers
        

-- 
Marco Antoniotti ========================================================
NYU Courant Bioinformatics Group        tel. +1 - 212 - 998 3488
715 Broadway 10th Floor                 fax  +1 - 212 - 995 4122
New York, NY 10003, USA                 http://bioinformatics.cat.nyu.edu
                    "Hello New York! We'll do what we can!"
                           Bill Murray in `Ghostbusters'.
From: Adam Warner
Subject: Re: compiled code
Date: 
Message-ID: <almrcs$1qkftr$1@ID-105510.news.dfncis.de>
Hi quasi,

> Friends,
> 	Excue me.  But this quiestion seems confusing to me but may
> turn out to to extremely silly.  Because of the confusion I may be a
> little long-winded.
> 
> 	In my understanding, when a compiler compiles to native binary
> then that binary contains instructions for the CPU, right?

Right

> 	Say, I have a program in C which at some point has a function
> foo which does complex numerical calculates.  Now a C compiler compiles
> this function and writes some binary instructions for it, right?

Right

> 	Now suppose this same program I am doing in Lisp (CMUCL, say)
> then for foo (the algorithm is the same)  the compiler generates binary
> instructions, right?

Right

> 	But then, why is it so that the instructions created by the C
> compiler are supposed to work faster than those instructions created by
> the Lisp compiler (regarding foo)?  Is there some inherent reason for
> this?

Either foo implementation may be faster. One of the factors is the quality
of the compilers. Another is the quality of the libraries. Lisp can be
truly fast and rival C in speed, especially with compile-time type
declarations and all speed (safety) settings set to maximum (minimum).

But compare what can be achieved in the same amount of time. This
factorial function is not optimally fast...

   (defun factorial (n)
     (if (= n 0) 1
       (* n (factorial (1- n))))

...but test how long it takes you to implement this in C for any
non-negative integer. Like 100!:

   (format t "~:D" (factorial 100))
   93,326,215,443,944,152,681,699,238,856,266,700,490,715,968,264,381,621,
   468,592,963,895,217,599,993,229,915,608,941,463,976,156,518,286,253,697,
   920,827,223,758,251,185,210,916,864,000,000,000,000,000,000,000,000

If you gave a Lisp programmer much less time than it would take a C
programmer to implement this they could likely produce as fast an
implementation as someone using C. This simple version only took the
seconds I expended in typing three lines. Think how much longer could be
devoted to get a speed increase before you're even in the ballpark of the
time being devoted by the C programmer.

And at least we can be confident that this initial Lisp implementation
works. The C programmer is going to have to implement a sizable portion of
Common Lisp functionality in order to handle integers of unlimited size.
And spend additional time testing his or her custom implementation (the C
programmer will also need a language with CL-like functionality in order
to test the results of the custom implementation).

So one of the reasons that Lisp may be considered slow is that people
expect everything to be as fast even when they would only expend a
fraction of the resources that any C programmer would devote to accomplish
the same task. Give Lisp programmers the luxury of spending 10 times as
long on any program and it could turn out to be much faster than the
initial implementation and still take much less time to implement than
using C.

Regards,
Adam
From: quasi
Subject: Re: compiled code
Date: 
Message-ID: <3d7efb1f.10353702@News.CIS.DFN.DE>
On Wed, 11 Sep 2002 19:34:26 +1200, "Adam Warner"
<······@consulting.net.nz> wrote:
>So one of the reasons that Lisp may be considered slow is that people
>expect everything to be as fast even when they would only expend a
>fraction of the resources that any C programmer would devote to accomplish
>the same task.

Thank you all.
	The purpose of my query was not to (again) raise the question
if Lisp was good enough.  I have been hanging here for the better part
of a year because it is for me.
	I just wanted to know if it was *possible*, if so required
(may be >1% of the code), to get the compiler to generate fast code.
	Because here people have said often they prefer other
languages (C) for time critical code.  What I wanted to know is
weather you *can* (by optimizing every which way & not considering the
time it takes) generate fast code comparable to what can be achieved
in C.

I gather we can.  That is Great news indeed.

thanks again,
quasi
From: Mark Dalgarno
Subject: Re: compiled code
Date: 
Message-ID: <usn0gnb4t.fsf@scientia.com>
······@vsnl.net (quasi) writes:

> What I wanted to know is weather you *can* (by optimizing every
> which way & not considering the time it takes) generate fast code
> comparable to what can be achieved in C.

I'm no compiler expert but in section 1.2 of
http://www.dreamsongs.com/WIB.html it is noted that Lisp will produce
faster, not just comparable, code than C in some cases.

I think this is an important point because it can be easy for Lisp
programmers to become too defensive about the language's runtime
performance.

Another point to note is that many commercial applications of Lisp are
in domains requiring very high execution speeds e.g. planning and
scheduling, CAD, search. (See
http://www.lisp.org/table/commercial-use.htm or http://www.franz.com/success/)

Mark
From: Petr Swedock
Subject: Re: compiled code
Date: 
Message-ID: <86d6rko9ws.fsf@blade-runner.mit.edu>
Mark Dalgarno <·············@scientia.com> writes:

> ······@vsnl.net (quasi) writes:
> 
> > What I wanted to know is weather you *can* (by optimizing every
> > which way & not considering the time it takes) generate fast code
> > comparable to what can be achieved in C.
> 
> I'm no compiler expert but in section 1.2 of
> http://www.dreamsongs.com/WIB.html it is noted that Lisp will produce
> faster, not just comparable, code than C in some cases.

Well, this was written in 1991 and, most likely, refers to Lisp on
an actual Lisp machine, not Lisp on Unix... Which is a different
story ('cause your most likely compiling in C ultimately when
using Lisp on Unix.)  

> I think this is an important point because it can be easy for Lisp
> programmers to become too defensive about the language's runtime
> performance.

Runtime performance ought not to be judged on the basis of a single 
metric, ie, speed, anyways.

Peace,

Petr
From: Raymond Toy
Subject: Re: compiled code
Date: 
Message-ID: <4nlm68y2wv.fsf@rtp.ericsson.se>
>>>>> "Petr" == Petr Swedock <····@blade-runner.mit.edu> writes:

    Petr> Mark Dalgarno <·············@scientia.com> writes:
    >> ······@vsnl.net (quasi) writes:
    >> 
    >> > What I wanted to know is weather you *can* (by optimizing every
    >> > which way & not considering the time it takes) generate fast code
    >> > comparable to what can be achieved in C.
    >> 
    >> I'm no compiler expert but in section 1.2 of
    >> http://www.dreamsongs.com/WIB.html it is noted that Lisp will produce
    >> faster, not just comparable, code than C in some cases.

    Petr> story ('cause your most likely compiling in C ultimately when
    Petr> using Lisp on Unix.)  

Says who?

Ray
From: Christophe Rhodes
Subject: Re: compiled code
Date: 
Message-ID: <sqelc0k1b3.fsf@lambda.jcn.srcf.net>
Petr Swedock <····@blade-runner.mit.edu> writes:

> ('cause your most likely compiling in C ultimately when
> using Lisp on Unix.)  

Hmm, I dunno.  On my unix boxes I count 6 Lisp implementations, one of
which compiles via C, one of which compiles to byte-code, and four of
which compile directly to native code without touching a C compiler.
That one needs to call routines written in C to interface to the
Operating System is mostly irrelevant.

Cheers,

Christophe
-- 
Jesus College, Cambridge, CB5 8BL                           +44 1223 510 299
http://www-jcsu.jesus.cam.ac.uk/~csr21/                  (defun pling-dollar 
(str schar arg) (first (last +))) (make-dispatch-macro-character #\! t)
(set-dispatch-macro-character #\! #\$ #'pling-dollar)
From: Tim Bradshaw
Subject: Re: compiled code
Date: 
Message-ID: <ey3r8g0ee8g.fsf@cley.com>
* Petr Swedock wrote:
> Well, this was written in 1991 and, most likely, refers to Lisp on
> an actual Lisp machine, not Lisp on Unix... Which is a different
> story ('cause your most likely compiling in C ultimately when
> using Lisp on Unix.)  

While you'd have to ask the author, I don't think it does.  Lucid (his
company at the time) produced stock-hardware lisp systems.

However it definitely is *not* true that Lisp systems need go via C,
even on Unix.  One (gcl) famously does, but I'm not aware of any other
major CL implementations which do - in one case (CLISP) they compile
to byte-code, but most others are native-code compilers.

Even in the case where a compiler does go via C, it can still generate
faster code than a human C programmer generally would, by generating
code that it would be very hard for a human to write. Of course this
typically won't show up for the tiny `loop a billion times doing
nothing' benchmarks that people tend to use to show that C is faster,
but for more complex code, it may.  The `stalin' scheme compiler is a
system for a Lisp-related language which performs very well and which
goes via C I believe.

> Runtime performance ought not to be judged on the basis of a single 
> metric, ie, speed, anyways.

Well said. `Speed' is also not a scalar but a point in a
high-dimensional space, and comparisons of `speed' are thus very
complex.

--tim
From: Richard Fateman
Subject: Re: compiled code
Date: 
Message-ID: <3D7F6D7A.7030605@cs.berkeley.edu>
If speed is more important than convenience, then assembly language
would be the logical choice.  So C is being used for convenience
and the argument is then how much more convenient is some other
language, perhaps Lisp. Arguably one can do profiling more easily
in lisp and concentrate one's hand-optimizations on critical
parts, perhaps even writing them in assembler.  Recent stuff I've
done suggests that cache-based optimizations are far more important
than instruction sequences in Lisp too, so optimizations in the
future may have rather different perspectives.  For example,
an appropriate garbage collector may make list-traversal programs
run faster by improving locality.

As for Gabriel's old paper, he makes some interesting observations,
but his generalizations about people and universities and
companies other than his own, are, in a number of instances,
quite wrong. (I was and still am at Berkeley, helped get the
first VAX for Berkeley UNIX, and led the Franz Lisp project.)

Given the passage of time, one can see where parts of that paper
lead off in the wrong direction; it is not generally
evident where the off-hand historical comments were wrong in 1990
and are still wrong.

But it is plausible that a lisp compiler, generally using declarations,
can produce very good code, without C as an intermediate language,
whether Gabriel says so or not.
RJF



Tim Bradshaw wrote:

> * Petr Swedock wrote:
> 
>>Well, this was written in 1991 and, most likely, refers to Lisp on
>>an actual Lisp machine, not Lisp on Unix... Which is a different
>>story ('cause your most likely compiling in C ultimately when
>>using Lisp on Unix.)  
>>
> 
> While you'd have to ask the author, I don't think it does.  Lucid (his
> company at the time) produced stock-hardware lisp systems.
> 
> However it definitely is *not* true that Lisp systems need go via C,
> even on Unix.  One (gcl) famously does, but I'm not aware of any other
> major CL implementations which do - in one case (CLISP) they compile
> to byte-code, but most others are native-code compilers.
> 
> Even in the case where a compiler does go via C, it can still generate
> faster code than a human C programmer generally would, by generating
> code that it would be very hard for a human to write. Of course this
> typically won't show up for the tiny `loop a billion times doing
> nothing' benchmarks that people tend to use to show that C is faster,
> but for more complex code, it may.  The `stalin' scheme compiler is a
> system for a Lisp-related language which performs very well and which
> goes via C I believe.
> 
> 
>>Runtime performance ought not to be judged on the basis of a single 
>>metric, ie, speed, anyways.
>>
> 
> Well said. `Speed' is also not a scalar but a point in a
> high-dimensional space, and comparisons of `speed' are thus very
> complex.
> 
> --tim
> 
From: Bruce Hoult
Subject: Re: compiled code
Date: 
Message-ID: <bruce-64AF78.11225012092002@copper.ipg.tsnz.net>
In article <···············@cley.com>, Tim Bradshaw <···@cley.com> 
wrote:

> Even in the case where a compiler does go via C, it can still generate
> faster code than a human C programmer generally would, by generating
> code that it would be very hard for a human to write. Of course this
> typically won't show up for the tiny `loop a billion times doing
> nothing' benchmarks that people tend to use to show that C is faster,
> but for more complex code, it may.  The `stalin' scheme compiler is a
> system for a Lisp-related language which performs very well and which
> goes via C I believe.

Correct.

Gwydion Dylan also compiles to C, using a 1-to-1 mapping of the 
functions.  Makes it tough to get tail-call elimination for toplevel 
functions.  So tough that we don't.  But we do tail-call optimize 
Dylan's version of "labels", which is much more important -- especially 
when the built-in for() and while() loop macros expand into 
tail-recursive code :-).

There is also the "Chicken" Scheme compiler, which converts the program 
to continutation-passing style, and then produces a C function for every 
(non-trivial) continuation.  Produces totally unreadable C code, but it 
runs well, and it uses a clever system where all heap allocation is done 
on the C stack, which acts as the nursery for the GC.  GCs are done on 
stack-overflow...

-- Bruce
From: Thomas Stegen
Subject: Re: compiled code
Date: 
Message-ID: <3D7F213E.4080901@cis.strath.ac.uk>
Mark Dalgarno wrote:

> I think this is an important point because it can be easy for Lisp
> programmers to become too defensive about the language's runtime
> performance.

I do not really get why so many people think that speed is so
important. Hardware is becoming so fast that a language like Python
is fast enough for most purposes. And since Common Lisp is much faster
than Python what is the big problem? I would rather my code was bug
free, written in 2 months and run in 100ms than have a few bugs,
written in 4 months and run in 70ms.

-- 
Thomas Stegen
From: Espen Vestre
Subject: Re: compiled code
Date: 
Message-ID: <kwelc0vla3.fsf@merced.netfonds.no>
Thomas Stegen <·······@cis.strath.ac.uk> writes:

> I do not really get why so many people think that speed is so
> important. 

It's unimportant most of the time. But several of us (the c.l.l-ers)
have recently implemented cryptographic software, were e.g. the lack
of "unboxed integers" in some implementations gives performance
penalties that _can_ make the software unusable compared to a C
implementation (for me it's not a real problem, current hardware is
more than fast enough for my limited use of my rather slow rsa and
blowfish implementations, but if I couldn't use it to encrypt really
large amounts of data).

> is fast enough for most purposes. And since Common Lisp is much faster
> than Python what is the big problem? 

It would be great if Python users would think of CL as the language
of choice when Python gets too slow. Currently, it seems like C++
is a common answer to speeding up python-based software :-(
-- 
  (espen)
From: Dr. Des Small
Subject: Re: compiled code
Date: 
Message-ID: <m61y80zo4d.fsf@pc156.maths.bris.ac.uk>
Espen Vestre <·····@*do-not-spam-me*.vestre.net> writes:

> It would be great if Python users would think of CL as the language
> of choice when Python gets too slow. Currently, it seems like C++
> is a common answer to speeding up python-based software :-(

I program in Python rather than Lisp out of expedience: for what I do
the advantages of Lisp, which I do not dispute, are not worth
the overheads of integrating it with other software that I use.

When an inner loop becomes a bottle neck I sometimes wish to implement
a local optimisation.  I use C for that: rewriting the entire
application in another language is not what I call "local", even if
you insist it would be "optimal".

Although I program almost exclusively in Python, this is the only
programming newsgroup I read with any care.  I do not consider that it
would be improved by an influx of speed-obsessed newbies; I want c.l.l
to be a useable resource if I ever find myself needing (rather than
just wanting) the power and flexibility of Common Lisp, and I am
cynical enough to suspect these goals could not easily be reconciled.

Des
is selfish that way.
-- 
Des Small, Scientific Programmer,
School of Mathematics, University of Bristol, UK.
From: Matthias Heiler
Subject: Re: compiled code
Date: 
Message-ID: <alnf2t$34c$1@trumpet.uni-mannheim.de>
Espen Vestre wrote:
> It would be great if Python users would think of CL as the language
> of choice when Python gets too slow. Currently, it seems like C++
> is a common answer to speeding up python-based software :-(

I'm doing image processing and machine learning at times and moved away 
from Python for its lack of speed: It's useless to prototye an algorithm 
which runs so slowly that while waiting for some results I can well 
write the thing in C.

Being impressed by CMUCL's runtime efficiency I considered moving to CL 
as the next step.  For my work the number one problem with CL is lack of 
(free, open-source, high-quality) libraries: I really do not want to 
have to implement every piece of routine-code myself.  To me, a powerful 
programming environment brings together three things: (1) an expressive 
language, (2) reasonably fast execution, and (3) a large base of 
available library code.  Unfortunately, CL fails in standardizing 
bindings to C, so it's unlikely that we will have (3) at some point in 
the future.  People might feel that C++ is actually not such a bad 
language if you want a compromise between (1), (2), and (3).

Matthias
From: Matthew Danish
Subject: Re: compiled code
Date: 
Message-ID: <20020911131828.I23781@lain.res.cmu.edu>
On Wed, Sep 11, 2002 at 03:03:52PM +0200, Matthias Heiler wrote:
> Being impressed by CMUCL's runtime efficiency I considered moving to CL 
> as the next step.  For my work the number one problem with CL is lack of 
> (free, open-source, high-quality) libraries: I really do not want to 
> have to implement every piece of routine-code myself.  To me, a powerful 
> programming environment brings together three things: (1) an expressive 
> language, (2) reasonably fast execution, and (3) a large base of 
> available library code.  Unfortunately, CL fails in standardizing 
> bindings to C, so it's unlikely that we will have (3) at some point in 

While ideally there would be no need for bindings to C, in the meantime
there is the UFFI [1] effort.  Also, cCLan [2].  You may want to note
that it takes more than just bindings to C in order to generate
high-quality interfaces to system libraries.  Usually the C interface is
suboptimal and something needs to be wrapped around it.  Designing a
decent interface is often the hardest part.

[1] http://ww.telent.net/cliki/uffi
[2] http://ww.telent.net/cliki/cclan

-- 
; Matthew Danish <·······@andrew.cmu.edu>
; OpenPGP public key: C24B6010 on keyring.debian.org
; Signed or encrypted mail welcome.
; "There is no dark side of the moon really; matter of fact, it's all dark."
From: Adam Warner
Subject: Re: compiled code
Date: 
Message-ID: <aln42e$1qmtci$1@ID-105510.news.dfncis.de>
Hi Mark Dalgarno,

> I'm no compiler expert but in section 1.2 of
> http://www.dreamsongs.com/WIB.html it is noted that Lisp will produce
> faster, not just comparable, code than C in some cases.
> 
> I think this is an important point because it can be easy for Lisp
> programmers to become too defensive about the language's runtime
> performance.
> 
> Another point to note is that many commercial applications of Lisp are
> in domains requiring very high execution speeds e.g. planning and
> scheduling, CAD, search. (See
> http://www.lisp.org/table/commercial-use.htm or
> http://www.franz.com/success/)

They're good points. Orbitz is another example:
http://www.paulgraham.com/carl.html

However if there are cases where Lisp is able to produce faster code than
C then there should a way to rewrite the C so that it generates assembly
that looks similar to Lisp and runs at a similar speed, even if the
compiler has to be fixed to accomplish this.

(And vice versa! Since you can inline assembly in some Lisp
implementations (like CMUCL) there is effectively no limit to the levels
that the programmer can descend. And the time saved on developing the
structure of the program will allow more time to be spent profiling and
optimising the critical algorithms).

Regards,
Adam
From: Bruce Hoult
Subject: Re: compiled code
Date: 
Message-ID: <bruce-FB7D3F.22252111092002@copper.ipg.tsnz.net>
In article <·················@News.CIS.DFN.DE>, ······@vsnl.net (quasi) 
wrote:

> On Wed, 11 Sep 2002 19:34:26 +1200, "Adam Warner"
> <······@consulting.net.nz> wrote:
> >So one of the reasons that Lisp may be considered slow is that people
> >expect everything to be as fast even when they would only expend a
> >fraction of the resources that any C programmer would devote to accomplish
> >the same task.
> 
> Thank you all.
> 	The purpose of my query was not to (again) raise the question
> if Lisp was good enough.  I have been hanging here for the better part
> of a year because it is for me.
> 	I just wanted to know if it was *possible*, if so required
> (may be >1% of the code), to get the compiler to generate fast code.
> 	Because here people have said often they prefer other
> languages (C) for time critical code.  What I wanted to know is
> weather you *can* (by optimizing every which way & not considering the
> time it takes) generate fast code comparable to what can be achieved
> in C.
> 
> I gather we can.  That is Great news indeed.

The better Lisp compilers can generate very good code.  CMUCL is 
probably one of the better ones.

Dylan is a Lisp dialect where one of the design goals was to provide 
ways to turn the dynamism knob down a little in order to produce more 
efficient code.  I find that with Gwydion Dylan I don't have much 
trouble getting to within experimental error of the same speed as C when 
I need to.  And in the meantime, the 96% of the code that isn't critical 
to the speed of the overall program is much faster and easier to write, 
and much safer.

-- Bruce