michaelm@bcsaic.UUCP (michael b maxwell) (11/27/85)
It is now a couple months since my original posting concerning the benifits of converting Lisp programs to C (in terms of speed, etc.). Since a few people asked me to post the results, I'm doing so. The trouble is, I don't have many results to post which didn't already appear on the net, and very little even there. A few notes: 1: Jay Freeman (spar!freeman) observed that real-time systems need incremental garbage collection, something which many lisps don't provide. 2: Jim Kempf (hplabs!kempf) says: > If you want to recode in C, then profiling > tools are absolutely essential for determining what parts to recode. > One possibility for avoiding recoding is to track down what parts > of the code are heavily consing and preallocate where necessary, > if storage is being allocated and thrown away within a single routine. > We have found that removing this kind of consing from within an > interface to a Pascal database reduced by almost a factor of 2 the > amount of time for the Lisp to Pascal database calls. 3: In a posted message that I won't repeat here, John Nagle (wdl1!jbn) discussed the conversion of an "expert system" (the Ventilator Manager) which was converted from EMYCIN to (gasp!) BASIC, which conversion made it a real-time system. But it appears that it wasn't really an expert system problem in the first place, rather a process control problem, so maybe this isn't typical. 4: There was considerable discussion (mainly in net.lang.c) about garbage collection methods, which I won't attempt to summarize here. Peter Ashwood-Smith (utzoo!hcrvax!petera) suggested that "simple programs (where you know you are not going to run out of memory doing one 'evaluation') are probably more effecient when written in C." I know that several groups have created programs in Lisp, then recoded in C, but either they aren't listening, or they don't have time to post any info on speed-up they may have (or pointers to published references). My original msg asked "Have many people really done the translation? Or is it one of those things that everyone talks about, but no one does anything about? :-)" Perhaps the ":-)" wasn't appropriate; maybe no one *does* do anything about it! -- Mike Maxwell Boeing Artificial Intelligence Center ...uw-beaver!uw-june!bcsaic!michaelm
root@topaz.RUTGERS.EDU (Charles Root) (12/02/85)
I conjecture that you didn't hear much about Lisp to C conversion because it isn't often done. It is fairly common to do research using a Lisp prototype and then build a second-generation system. It would be reasonable for this second-generation system to be in C. However the gains there are not due to conversion from Lisp to some other language, but from using a more highly-tuned implementation. There is no reason to think that a simple translation from Lisp to C would gain anything, if the original Lisp program was a sensible one. Of course if the original program was ill-suited to Lisp (e.g. floating point array computations in a dialect of Lisp that doesn't do a good job with this), then a translation might make sense. The quality of existing Lisp compilers seems about as good as existing C compilers. Indeed the most widespread Lisp system that I know of (Utah's Portable Standard Lisp) does more optimization than the most widespread C system that I know of (various versions of PCC and Berkeley's compilers). The main limitation in the Lisp compilers I know about is in dealing with heavy numerical computing. This is not because the compilers are stupid, but because of Lisp's nature as a typeless language. (Of course there are implementations that allow type declarations.)
mwm@ucbopal.BERKELEY.EDU (Mike (I'll be mellow when I'm dead) Meyer) (12/05/85)
In case it got misssed, the last (?) SIGART Newsletter (No. 94, Oct. 85) had a paper by Bruce Wilcox "Reflections on Building Two Go Programs" wherein he describes the lessons learned from writing a medium-sized LISP program, then re-writing it in C. There's not much in it on the port problems; you can probably summarize what there is as "Not worth the effort in current environments." <mike
richw@ada-uts.UUCP (12/05/85)
"topaz!root" says: >> Indeed the most widespread Lisp system that I know of (Utah's Portable >> Standard Lisp) does more optimization than the most widespread C Can you be more specific about "more optimization"? ---- "Optimize" is a horrible word for "code-size/execution-time reduction". Did you ever consider that ALL programs which don't read any input (e.g. a program to calculate the first 1000 digits of pi) would be, theoretically, totally consumed by true "optimizing" compilers? That is, you tell the compiler to optimize your pi-calculating program and it spews out "3.14159..." -- Rich Wagner
levy@ttrdc.UUCP (Daniel R. Levy) (12/08/85)
In article <10200028@ada-uts.UUCP>, richw@ada-uts.UUCP writes: >"topaz!root" says: >Can you be more specific about "more optimization"? >"Optimize" is a horrible word for "code-size/execution-time reduction". >Did you ever consider that ALL programs which don't read any input >(e.g. a program to calculate the first 1000 digits of pi) would be, >theoretically, totally consumed by true "optimizing" compilers? >That is, you tell the compiler to optimize your pi-calculating program >and it spews out "3.14159..." > >-- Rich Wagner That would be a marvel of "artificial intelligence" -- an optimizer that can recognize algorithms. Imagine--it would replace your bubble sorts with Shell sorts (or better); linear searches would become binary or hashed; all sorts of neat stuff. The optimizer itself would crunch for long, long periods of time; for "inputless" problems it might as well BE the task. And how well would this apply to a gargantuan problem like the current attempt to calculate the mass of the proton from an entirely theoretical basis on a bevy of high-powered IBM CPUs? This is the kind of program where the data needed could well be hardcoded in; I'd hate to wait for your "optimizer" to finish with something of this kind!
johnl@ima.UUCP (12/09/85)
/* Written 1:57 am Dec 8, 1985 by levy@ttrdc in ima:net.lang.c */ > >Did you ever consider that ALL programs which don't read any input > >(e.g. a program to calculate the first 1000 digits of pi) would be, > >theoretically, totally consumed by true "optimizing" compilers? > >That is, you tell the compiler to optimize your pi-calculating program > >and it spews out "3.14159..." > That would be a marvel of "artificial intelligence" -- an optimizer that > can recognize algorithms. Not at all. It's just aggressive constant folding. It's not hard for a compiler to tell that some piece of a program has no inputs, and once it's figured that out, it can compute the result of that piece at compile time and substitute its result. Compilers for traditional sorts of languages like Fortran and C generally don't do very much of that because they don't usually look across routine boundaries, but I've seen great stuff in some Lisp compilers. Since practically everything in Lisp is a function call, the only way a compiler can do any good is to look into functions and tell that, for example, a call to (car foo) can be turned into one or two instructions that fetch the car part of foo. Lisp compilers do more in-line expansion of small functions than they do constant folding, because the gain in most Lisp code is greater, but there's no reason they can't do both. The upshot of this is that I agree that your typical algorithm would run faster compiled by a typical C compiler than by a typical Lisp compiler, but that's because both compilers have serious blind spots in their optimizations, and C wins because it was designed to be easier to compile. John Levine, ima!johnl
bright@dataioDataio.UUCP (Walter Bright) (12/12/85)
In article <124000003@ima.UUCP> johnl@ima.UUCP writes: >It's not hard for a >compiler to tell that some piece of a program has no inputs, and once it's >figured that out, it can compute the result of that piece at compile time >and substitute its result. Programs that have no inputs tend to fall into two groups: o Benchmarks. o Programs that are to be run only once per recompilation. In either case, it doesn't seem worthwhile to compute the program output at compile-time. As for parts of programs that have no inputs, or the inputs are always known, this is a major focus of global flow optimization techniques. Unfortunately, I have yet to see one powerful enough that worked across loops (I'd love to see one that could optimize the notorious sieve benchmark down to printf("1899 primes\n");). I've also seen some work on attempting to determine when run-time array bounds checking could be safely eliminated. Of course, the corollary is that out-of-bounds detection could be accomplished at compile-time... but I'm dreaming on.
zben@umd5.UUCP (12/16/85)
In article <628@ttrdc.UUCP> levy@ttrdc.UUCP (Daniel R. Levy) writes: >In article <10200028@ada-uts.UUCP>, richw@ada-uts.UUCP writes: >>That is, you tell the compiler to optimize your pi-calculating program >>and it spews out "3.14159..." >That would be a marvel of "artificial intelligence" -- an optimizer that >can recognize algorithms. Imagine--it would replace your bubble sorts >with Shell sorts (or better) ... If you were writing in Cobol, you would just say "sort", and the compiler would probably automagically include in a 90K word (thats 360K byte) vendor- supplied polyphase sort merge that automagically goes to N magnetic tape drives when the number of records goes above 10 million.... :-) Don't laugh - my dinosaur actually does this. Now if it only had a C compiler... (sigh) -- "We're taught to cherish what we have | Ben Cranston by what we have no longer..." | zben@umd2.umd.edu ...{seismo!umcp-cs,ihnp4!rlgvax}!cvl!umd5!zben