Re: Re: Pragmatic Requirements Summary : update

On Tue, 5 Aug 2003, Eric Merritt wrote:

>  There have and are lisps that perform quite well. As a general rule
> they do not outperform C, however in may contexts they can beat C. In
> most contexts they are only a factor of 2 or 3 slower then C. A good
> example of this is CMUCL and its python compiler (no not python the
> langauge, python the compiler). It is very good at generating
> efficient code. From my understanding the commercial implementations
> of lisp generate even better code.

Notice that CMUCL is a native-code compiler.  I wasn't comparing the speed
of LISP to C, I was comparing the speed of interpreted implementations to
statically compiled implementations.

It's not the language which is fast or slow, so much as as the code 
written in the language, and the implementation of that language which is 
used.  The problem with code-as-data is that it encourages the interpreted 
implementations.

Here's an intriguing "what if"- on how a functional language like LISP or 
ML could be signifigantly faster than C.  No one has done this yet (any 
gradual students out there looking for a PhD thesis topic?), but it should 
be done.

The main limitation in computer architecture right now is the limitations 
on instruction level parallelism- how many instructions can be issued at 
once.  For imperitive (C and Fortran) programs, the practical limit seems 
to be 5-7 instructions issued at once:
http://citeseer.nj.nec.com/wall90limits.html

The functional units on a CPU- the circuits that actually do the "real 
work" of adding and subtracting and what have you- are becomming a 
vanishingly small portion of the transitors used.  Most of the rest of the 
chip is various amounts of support to attempt to take better advantage of 
the small number functional units- especially cache (which reduces the 
average amount of time the functional units need to stall waiting for 
memory) and instruction scheduling (which looks for that small handfull of 
instructions which can be executed).  It'd be trivial to add more 
functional units to a CPU- but pointless, as they'd almost never be used.  
You can't use more than 5-7 functional units.

Except what if you could?  Consider the following fragment of Ocaml:
	let x = foo a b
	and y = bar a b
	in
	...

Now, assuming foo and bar are purely functional, there is no dependency 
between them.  You can execute the call to foo first, or the call to bar 
first, and neither will notice.  Or- and here's the trick- you can inline 
them both, and intermingle their execution.  If foo has an average ILP of 
(say) 4 instructions, and so does bar, then their intermingled ILP would 
be 8 instructions.  Every clock you could execute 4 instructions from foo, 
and 4 more isntructions from bar.

I'm simplifying a lot here, but this gets across the core of my idea.  
That purely functional programming may expose parallelism that imperitive 
programming doesn't.  And give optimization opportunities commensurate 
with that.  This is especially important on CPUs like the Itanium, where 
the compiler can express this parallelism directly.

>  Most of this performance penalty can be made up in large programs
> with using the right alsgorithm. You made this point yourself.

Yep.  Interpretation is just a constant factor slowdown- easily overcome
by better algorithms.  Also, large hunks of the programming world simply
aren't that performance bound.  Generally anytime you're talking to a
database, the database is your main slowdown.  User I/O is also very slow.  
I had a friend who got bitched at once for writting a DB query in Perl,
when C was so much faster.  His response was that the query was hitting 
the optical jukebox, and would take 15 minutes to complete.  Wether the 
program spawning the query took 10 milliseconds or 100 milliseconds to run 
probably wasn't going to be an issue.

Most programmers, in my experience, have no clue where performance comes 
from or goes to.

>  
> >  
> > 2) Correctness.  How can you be sure for all inputs that the code  
> > generated is correct? 
>  
>  A program can only modify itself according to its input. If you know
> the input then the output is a foregone conclusion. Not that it cant
> be complex.

The fact that any given input will create a reproducable, and in some 
sense even predictable, result is not in question.  The question is wether 
the output it produces is the one *intended*.  Otherwise I can simply 
replace any program with the following C code:
#include <stdio.h>
int main (int argc, char ** argv) {
    fprintf(stderr, "Fatal error- segment fault.  Program exiting.\n");
    return -1;
}

Hey, it produces an output!  Probably not the one you were intending, 
but...

>  CMUCL's python compiler uses type inference to achieve its goals.
> Type inference and dynamic typing are not mutually exclusive. In fact,
> I would say they complement each other.

Yep.  There's been more than one point where I've wished that ocaml had 
"instanceof" or something similiar.  I'm just arguing against "instead 
of".

Brian



------------------------ Yahoo! Groups Sponsor ---------------------~-->
Buy Ink Cartridges or Refill Kits for Your HP, Epson, Canon or Lexmark
Printer at Myinks.com. Free s/h on orders $50 or more to the US & Canada. http://www.c1tracking.com/l.asp?cid=5511
http://us.click.yahoo.com/sO0ANB/LIdGAA/ySSFAA/W4wwlB/TM
---------------------------------------------------------------------~->

To unsubscribe from this group, send an email to:
pragmatic_lang-unsubscribe-hHKSG33TihhbjbujkaE4pw@public.gmane.org

 

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/