jbn@glacier.UUCP (03/02/87)
Floating point computations in current LISP implementations tend to
be unnecessarily slow. While PDP-10 MACLISP may have exhibited excellent
floating point performance, several of today's popular LISP implementations
definitely do not. Although Common LISP contains means of providing the
compiler with enough information to permit the generation of in-line code
for floating point operations, many compilers do not use this information
effectively.
So I pose the following question:
Is there a Common LISP for SUN or VAXen which, given enough declarations,
will generate code for, say, a matrix multiply which does not contain any
subroutine calls, boxing, unboxing, storage allocation, type checking, tests,
stack manipulation, or other unwanted fooling around within the inner loop?
I'm not asking for the strength reductions for nested loops one expects from
a good FORTRAN compiler; just good clean code.
John Naglekempf@hplabsc.UUCP (03/02/87)
In article <16921@glacier.STANFORD.EDU>, jbn@glacier.STANFORD.EDU (John B. Nagle) writes: > > Floating point computations in current LISP implementations tend to > be unnecessarily slow. While PDP-10 MACLISP may have exhibited excellent > floating point performance, several of today's popular LISP implementations > definitely do not. Although Common LISP contains means of providing the > compiler with enough information to permit the generation of in-line code > for floating point operations, many compilers do not use this information > effectively. > > So I pose the following question: > Is there a Common LISP for SUN or VAXen which, given enough declarations, > will generate code for, say, a matrix multiply which does not contain any > subroutine calls, boxing, unboxing, storage allocation, type checking, tests, > stack manipulation, or other unwanted fooling around within the inner loop? > I'm not asking for the strength reductions for nested loops one expects from > a good FORTRAN compiler; just good clean code. > > John Nagle I think most people who want to do good floating point would tend to want to code the numerical part in C or FORTRAN, or, better yet, use an existing FORTRAN library, like IMSL, where they don't need to code anything at all, but simply reuse an existing library. The existence of good foreign function calling capabilities in modern Lisps makes this an attractive option to coding the entire application in Lisp. This allows developers to use Lisp for symbolic processing, which most existing implementations do well, and use C, FORTRAN, or a FORTRAN library for numerical code, which these implementations tend to stress. This would argue for improving foreign function calling to make it as fast and as CONSless as possible. Not that good floating point optimization for Lisp isn't an interesting problem, but, as a practical matter, there are other ways to achieve the same result which may be less expensive in the end. Jim Kempf kempf@hplabs.hp.com
malcolm@spar.UUCP (03/03/87)
In article <16921@glacier.STANFORD.EDU> John B. Nagle writes: > Is there a Common LISP for SUN or VAXen which, given enough declarations, >will generate code for, say, a matrix multiply which does not contain any >subroutine calls, boxing, unboxing, storage allocation, type checking, tests, >stack manipulation, or other unwanted fooling around within the inner loop? >I'm not asking for the strength reductions for nested loops one expects from >a good FORTRAN compiler; just good clean code. [I sent this to Sun Spots many weeks ago and I'm still waiting to see it published....oh, well....lets try sending it out here. I don't know what Lucid did to get these numbers....all I'm concerned about is the speed compared to a Symbolics and to native C.] Lucid sent me a new Lisp Compiler that does floating point correctly. Here are the times to execute 10 1024 point fft's. Note that this version of the Lucid compiler will optionally generate code for the 68881. There is no support yet for the FPA. The times below are in seconds. Machine-> 160 260 Symbolics 160/FPA 260/FPA Language \/ ------------------------------------------------ Native 5.4 4.6 4.6 3.1 1.9 Lucid(New) 6.2 5.3 NA NA Lucid(Current) 74.0 43.1 NA NA Franz(Current) 81. 47. NA NA The entries labeled Native mean C on the Suns and Lisp on the Symbolics. There are two amazing pieces of news in these numbers. First, Lucid Lisp on a Sun/3-260 with a 68881 runs within 15% of a Symbolics without an IFU. I expect that when the IFU is factored in then the Symbolics will be about 50% faster. All this changes when (if?) the Sun Lisps' support the FPA. And then there are Sun-4s.... The second amazing news is that Lucid is now within 15% of the raw speed of the machine. I just talked to John Foderaro at Franz, Inc. and they are working on similar enhancements. If your Lisp of choice is Franz then you shouldn't have to wait long. This is a pre-pre-prerelease of the Lucid compiler. Many thanks to David Posner at Lucid and Eric Schoen at Schlumberger and Stanford for helping with these benchmarks. No, I don't know when the new compiler will be released. Cheers. Malcolm P.S. Like all benchmarks, your mileage may vary. These times record just CPU time on machines with enough memory so there was no paging.
billw@navajo.UUCP (03/03/87)
I'd be VERY careful about considering the speed of an FFT coded in C as equivilent to the "native" speed of the machine - after all, C isn't a numeric language either. I'd feel a lot better if the "native" times came from an optimizing fortran compiler like VMS fortran, and better still if they were from carefully hand coded assembler... BillW, dinosaur keeper.
jbn@glacier.UUCP (03/04/87)
The information on LUCID's new compiler is very helpful; I've tried
out their VAX compiler and have been disappointed with the code, but it looks
like they are getting their act together for a future SUN release.
As for the significance of floating point to LISP users, a number of
trends lead toward heavy floating point computation in LISP. The modelling
work at Schlumberger, Pentland's Supersketch at SRI, Barr's work on
superquadrics at Caltech, Thinglab at Xerox, some of the neural net efforts,
simulated-annealing type VLSI design systems, and my own work on common-sense
via solid modelling, are all implemented in LISP and do extensive
floating-point computation. The notion that LISP users don't do floating point
work is decidedly out of date.
John Naglekempf@hplabsc.UUCP (03/04/87)
In article <16930@glacier.STANFORD.EDU>, jbn@glacier.STANFORD.EDU (John B. Nagle) writes: > > floating-point computation. The notion that LISP users don't do floating point > work is decidedly out of date. > > > John Nagle The intention of my posting was not to imply that Lisp users "don't" do floating point, just that, given modern foreign function capabilities and the existence of tried and true reusable software like the IMSL libraries, it may be more cost effective to do the floating point using them rather than trying to recode standard algorithms in Lisp. The inclusion of hooks for good floating point into Common Lisp certainly leaves open the possibility for incorporating floating point optimizations into Common Lisp compilers. I noticed that the listed applications using heavy Lisp floating point all seemed to be prototypes (please correct me if I'm wrong). Are there any Common Lisp applications that are products which use heavy Lisp floating point? If I were in the position of developing a product requiring both symbolic computation and floating point, my tendency would be to go with a tested reusable module like the IMSL library for standard floating point computations, and use Lisp for the symbolic part. Jim Kempf kempf@hplabs.hp.com
aglew@ccvaxa.UUCP (03/12/87)
>I think most people who want to do good floating point would tend to >want to code the numerical part in C or FORTRAN, or, better yet, >use an existing FORTRAN library, like IMSL, where they don't need >to code anything at all, but simply reuse an existing library. >The existence of good foreign function calling capabilities in >modern Lisps makes this an attractive option to coding the entire >application in Lisp. This allows developers to use Lisp for symbolic >processing, which most existing implementations do well, and use >C, FORTRAN, or a FORTRAN library for numerical code, which these >implementations tend to stress. This would argue for improving >foreign function calling to make it as fast and as CONSless as >possible. > >Not that good floating point optimization for Lisp isn't an interesting >problem, but, as a practical matter, there are other ways to achieve >the same result which may be less expensive in the end. > > Jim Kempf kempf@hplabs.hp.com Using foreign functions as an excuse for not providing efficient floating in LISP is a cop-out. Reusing existing code is fine - but if you're writing a new numeric algorithm (and not all numeric analysis was finished by the 60s) it would be nice to use a decent language, with decent macro facilities, and the ability to manipulate the program as data. I mean, have you ever tried to develop a generic interface to integration routines that work over arbitrary regions in N-space? Mathematical notation was invented to simplify thinking - it would be nice if I didn't have to know the 10 billion names of integrate in IMSL, but could have the language choose them for me (perhaps after asking me a few questions about the data). To be fair, Jim Kempf wasn't saying this - but I've sat in on conversations where it has been said. Andy "Krazy" Glew. Gould CSD-Urbana. USEnet: ihnp4!uiucdcs!ccvaxa!aglew 1101 E. University, Urbana, IL 61801 ARPAnet: aglew@gswd-vms.arpa
shebs@utah-orion.UUCP (03/13/87)
In article <31800002@ccvaxa> aglew@ccvaxa.UUCP writes: >Using foreign functions as an excuse for not providing efficient floating >in LISP is a cop-out. There's one place where I'd definitely want to use foreign functions - to call the irrational and transcendental functions in the 4.3 BSD libraries. They are *hot*. Certified performance and everything - wasn't clear to me that a Lisp version could be done as good, given the current state of compiler technology. >Reusing existing code is fine - but if you're writing >a new numeric algorithm (and not all numeric analysis was finished by >the 60s) it would be nice to use a decent language, with decent macro >facilities, and the ability to manipulate the program as data. I mean, >have you ever tried to develop a generic interface to integration routines >that work over arbitrary regions in N-space? I haven't noticed numerical analysts beating down the doors of Lisp implementors begging them to make floating point fast. The only Lisp users around here who care about floating point are graphics hackers. But then Lisp isn't *that* different from Fortran; you've still got to sequentialize your problem and write loops and do all those other nasty programming things. Gries & co at Cornell are working on a system called Gibbs which is supposed to be a sort of numerical analysis tool that doesn't involve programming directly - you give it some equations and it works out a program to calculate on them in some specified way. Macsyma does similar things, and it writes Fortran programs as output instead of Lisp programs, so efficiency of Lisp floating point is not as important. Don't think Lisp; think non-procedural languages! >Andy "Krazy" Glew. Gould CSD-Urbana. USEnet: ihnp4!uiucdcs!ccvaxa!aglew >1101 E. University, Urbana, IL 61801 ARPAnet: aglew@gswd-vms.arpa stan shebs shebs@cs.utah.edu
patrick@mcc-pp.UUCP (03/13/87)
In article <150@utah-orion.UUCP>, shebs@utah-orion.UUCP (Stanley T. Shebs) writes: > In article <31800002@ccvaxa> aglew@ccvaxa.UUCP writes: > >Using foreign functions as an excuse for not providing efficient floating > >in LISP is a cop-out. > > There's one place where I'd definitely want to use foreign functions - > to call the irrational and transcendental functions in the 4.3 BSD libraries. > They are *hot*. Certified performance and everything - ... > so efficiency of Lisp floating point is not as important. > > stan shebs > shebs@cs.utah.edu I agree that good foreign function interfaces is a good thing. However, it is not a substitute for in-line floating point performance. There should be no reason that a good Lisp compiler could not be made to generate identical code to a good Fortran or C compiler for performance critical portions of a program, given enough type declarations, etc. The failure of Lisp compilers to match this performance continues to give numerical hackers excuse to poo-poo Lisp as a language for doing "serious" work in. Thus, the attitude that floating point performance is not important because noone uses Lisp for floating point stuff becomes a self-fulfilling prophecy. While we are on the subject of performance, I have noticed that defstructs are implemented as arrays in a number of Lisp environments. This approach means that several bounds/limit/type checks are necessary for each structure access. A special type for structures would allow all of these checks to be replaced by a single check for structure type. If the structure type matches then by definition the structure field would be a legal access. Even Lisp machines with all their supporting hardware require several memory references to access an array. With hardware type checking, only one reference would be required, while without it, two references might be needed. (While I may be a little off on the exact details, I expect such a change could cut the average time for a structure access in half.) This feature may be overlooked by compiler writers since the Gabriel benchmarks do not include structure accesses. However, current programming style for objects and frames indicates structure accesses could occur even more frequently than list access. - Patrick McGehearty (McGehearty@MCC.COM)
shebs@utah-orion.UUCP (03/13/87)
In article <2774@mcc-pp.UUCP> patrick@mcc-pp.UUCP (Patrick McGehearty) writes: >There should be no reason that a good Lisp compiler could not >be made to generate identical code to a good Fortran or C compiler for >performance critical portions of a program, given enough type declarations, >etc. There is one reason - interactive capability. If you add enough type declarations to make the code pass around raw floating point numbers, then your poor old READ-EVAL-PRINT loop isn't going to be able to deal with the raw number. This means that the compiler must be very careful to add type info when talking to the non-optimized parts of the system. For instance, suppose I have a function (in CL) (defun foo (x y) (declare (float x y)) (let ((z (* x y))) (if (< z 0.0) (error "~S is the wrong number" z)) (* z z))) Yes, I can optimize the multiplications, infer that z is a float, and optimize the comparison - BUT the reference to z in the error message must be to a typed object! Getting this right is hard, and could easily double the size of the compiler. If instead of (error ...) I called, say, (foo z), then I must know ahead of time that foo takes only floats, or I'll have to add the type info in order to ensure correct behavior. This requires more declarations than a C program would have, because C assumes ints, and most everything in C looks like an int :-). >While we are on the subject of performance, I have noticed that >defstructs are implemented as arrays in a number of Lisp environments. >This approach means that several bounds/limit/type checks are necessary >for each structure access. Obviously you should use PSL/PCLS, in which a structure reference turns into one or two machine instructions if all the optimizations are turned on. Forget debugging in that situation though! >This feature may be overlooked by compiler writers since >the Gabriel benchmarks do not include structure accesses. Check out TRAVERSE. Granted, there could be more and better benchmarks, but after all the abuse RPG took for the incredible work he did, I doubt anybody else is going to stick their necks out for quite a while! >However, current programming style for objects and frames indicates >structure accesses could occur even more frequently than list access. Amen! but change "could" to "do". Unfortunately, much of current Lisp Machine designs are based on performance studies by Clark and Green about ten years ago, in which their sample programs were using lists to simulate arrays and structures (such things not being available then). Needless to say, cdr-coding to speed up cadddr etc looked like a good thing to do at the time.... >- Patrick McGehearty (McGehearty@MCC.COM) I wonder if people generally appreciate the amount of work that goes into a Lisp system. It's easy to write a small Lisp compiler in Lisp - we even gave one as a two-week assignment in last fall's intro Lisp class. It's not too much harder to write a fairly good C compiler - compiler classes do it all the time. However, a good Lisp compiler is *much* harder, partly because the language is higher-level, and partly because there are more conflicting requirements. I've alluded to interfacing vs efficiency above, there is also the issue of safety. If in a C system you add two integers that overflow and wrap around and cause a core dump, everybody just sort of shrugs and comments on how the program core dumped so quickly :-). Similar behavior in a Lisp system is met with howls about brain-damaged compilers and incorrect semantics... this is just the compiler, the runtime system is bigger and just as complex! The sensitive implementor gets gray hairs trying to find a compromise, while many others get truculent and suggest that you should be using specialized hardware, or that people doing floating point deserve to use Fortran, or even that you should never care about execution speed. I've heard everything, at one time or another. The moral is that really efficient high-level language implementations (I'm including Prolog, Smalltalk, etc here too) are still research projects, and if you want them, you're going to have to shell out a few extra bucks to researchers (like me :-) ) to come up with the best techniques... stan shebs shebs@cs.utah.edu PS I wasn't kidding about the money - we've got a hot successor to PSL in the works, but are running on an eyedropper-full funding-wise...
patrick@mcc-pp.UUCP (03/14/87)
In article <151@utah-orion.UUCP>, shebs@utah-orion.UUCP (Stanley T. Shebs) writes: > ... some valid comments about why writing a quality Lisp compiler > is harder than writing a quality C compiler. I agree the flexibility of Lisp makes it harder to compile for, but once done, many benefit. > >Refering to defstructs: > >This feature may be overlooked by compiler writers since > >the Gabriel benchmarks do not include structure accesses. > > Check out TRAVERSE. Granted, there could be more and better benchmarks, > but after all the abuse RPG took for the incredible work he did, > I doubt anybody else is going to stick their necks out for quite a while! Oops. My oversight. Also, my apologies to RPG if my comment seems to imply critisicm for his landmark work in getting Lisp implementers to be more aware of many performance related issues, yielding faster Lisps for all of us. > ... Unfortunately, much of current Lisp > Machine designs are based on performance studies by Clark and Green about > ten years ago, ... My comment was actually intended as a hope that the RPG benchmarks would not be taken as the final word since current patterns of Lisp usage are continuing to evolve. We need benchmarks of more, and varied programs to continue to challenge compiler writers to continue to improve. Unfortunately, funding mechanisms are weak as stan points out. Maybe increased usage of Lisp can create positive feedback here. I am being vocal about more performance because my pre-Lisp background is C. Thus, Lisp offers much that I did not have before in many areas such as dynamic storage management, data structures and much more. If it also had the performance of C programs, then its usage would expand even more rapidly. > The sensitive implementor gets gray > hairs trying to find a compromise, while many others get truculent and > suggest that you should be using specialized hardware, or that people > doing floating point deserve to use Fortran, or even that you should never > care about execution speed. I've heard everything, at one time or another. Just adding my voice to the chorus of demands :-) Perhaps the frequent comments of "let the optimizer take care of that" during the Common Lisp standardization efforts were said too frequently. Then again, maybe not... Seriously, Stan Shebs and the PSL bunch are working hard in the right direction as are a number of other Lisp compiler groups. My original comments were triggered by the "let them use Fortran" comments. I've been there and do not want to go back.