macrakis@harvard.ARPA (Stavros Macrakis) (03/13/85)
> [perhaps] the original test [was] against the old DEC Fortran > compiler, F40. .... This particular piece of folklore (that Maclisp > generates as good code as Fortran) is more widely quoted than you > might think. If it isn't true, or if the Fortran compiler is one that > would now be viewed as substandard, I would very much like to know. It's not true. What is true is that in some cases (heavy use of procedures, light use of arrays), Maclisp can hold its own. The Fortran compiler being used was not great, but then the Maclisp compiler is old-fashioned as far as compiler technology goes, too. Now for the details: you asked for them.... Inner loop times only. All execute the same floating-point instructions, so the number of memory references plus the number of multiplications (for 2D indexing) is a good measure of time. Version Date Inner prod Sum up 2d array F10/Opt V.1A 76 6 6 F10 " 76 7 9 + Mul F40 F40I V27(360) 76 8 10 + Mul Maclisp 1135 83 23 16 + Mul Note that the problems are chosen to emphasize Fortran's strength with arrays. In straight-line numerical code, Maclisp will do relatively better, but still not as well as the Fortrans. Maclisp has faster procedure call/return as well: the DEC Fortrans take about 11 + 7 * arg + 3 * out-arg mem refs, while Maclisp can take as little as 4 + 1 * arg , (if args stay in registers) although more common is 6 + 3 * arg . (if args are stashed on stack) It is this advantage in procedure calling that was largely responsible, if I remember correctly, for the good Lisp results in the Sigsam article (sorry, I don't have the reference: something like 1977). Of course, the Fortran arguments are by-reference, and the Lisp by-value; and the register conventions differ. There are other, hidden, overheads in the Lisp use of arrays, namely that in Maclisp (at least), they can neither be stack-allocated nor statically-allocated, but rather come out of a heap, increasing allocate/deallocate overhead. As always, remember that all languages have their strengths and weaknesses, that a language may have good implementations and bad, and that speed is only one consideration. -s Appendix For your delectation, the Lisp and Fortran code, and F10/opt's output. Note that the Fortran source is much clearer in this case, too. Sum up 2d array (do ((i 0 (1+ i))) ((>= i 1000)) (do ((j 0 (1+ j))) ((>= j 1000)) (setq sum (+$ sum (a j i))))) DO 10 I=1,1000 DO 10 J=1,1000 10 SUM=SUM+A(J,I) 8M: MOVEI 14,0(15) ADD 14,.O0000 ; should have put .O0000 in register FADR 2,A-13(14) AOBJN 15,8M Inner product (do ((i 0 (1+ i))) ((>= i 1000)) (setq sum (+$ sum (*$ (b i) (c i))))) DO 20 I=1,1000 20 SUM=SUM+B(I)*C(I) END 10M: MOVE 14,B-1(15) FMPR 14,C-1(15) FADR 2,14 AOBJN 15,10M
tim@cmu-cs-k.ARPA (Tim Maroney) (03/14/85)
That seems like some pretty dumb code to put in Lisp. Iteration, setq -- yech! I don't think any person in their right mind would disagree that Fortran-like or Algol-like languages are far better suited to this style of programming than Lisp. Now, let's see you write a recursive linked-list program in Fortran, which doesn't have stack-based calling, pointers, or anything remotely like structured data types.... -=- Tim Maroney, Carnegie-Mellon University, Networking ARPA: Tim.Maroney@CMU-CS-K uucp: seismo!cmu-cs-k!tim CompuServe: 74176,1360 audio: shout "Hey, Tim!"
macrakis@harvard.ARPA (Stavros Macrakis) (03/14/85)
I don't mean this to go on forever, but Maroney's gross distortion of my point forces me to: > That seems like some pretty dumb code to put in Lisp. Iteration, setq -- > yech! I don't think any person in their right mind would disagree that > Fortran-like or Algol-like languages are far better suited to this style of > programming than Lisp. > Now, let's see you write a recursive linked-list program in Fortran, which > doesn't have stack-based calling, pointers, or anything remotely like > structured data types.... -- Tim.Maroney@CMU-CS-K The point was simply that in fact MacLisp numeric code is not all that it's cracked up to be, and indeed if you want efficient number-crunching you use some other language. Fortran happens to be the language in terms of which the original argument was couched. Given what I know of the internals and the I/O behavior of both the Maclisp compiler and the Intermetrics AIE Ada compiler (I work part-time there), I suspect that it too will produce better numeric code but also non-numeric code (including handling recursion, linked lists, etc.) than Maclisp. Regrettably, garbage collection was not funded in the AIE. Having worked with Lisp for 14 years now, I think I have some idea of its strengths, which in my opinion are being diluted by pretending it is just a general-purpose language with a funny syntax and poor type-checking. > The most sophisticated Lisps (such as Common Lisp) include a wealth of > other datatypes intended for high efficiency in applications. -- shebs Here's an example of the `wealth' of datatypes from a member of the Common Lisp committee: "Common Lisp arrays are incredibly complex.... The resulting tangle of types...is clearly a political compromise and not something that would exist after careful design". [RA Brooks and RP Gabriel (an very experiencied Lisp implementer), "A Critique of Common Lisp", 1984 ACM Symposium on Lisp and Func. Prog.; an excellent paper, by the way] > For many years, the Maclisp compiler on the DEC-20 has produced > numerical code superior to Fortran. -- stan shebs This is not and never was true. See my previous posting. As for poor Common Lisp, "it requires either specially micro-coded machines, a fantastically complex compiler (which relies on copious declarations from the poor incompetant user), or very slow running time." [ibid] > There was an informal experiment done in the early-mid seventies at > MIT [: a] translator was written to translate (say) FORTRAN into > MACLISP.... In every case the lisp versions ran faster and took up > less memory.... The programs being used were purely [numerical]. -- > sasaki@harvard This is the same error being repeated. Fateman's 1974 SIGSAM Notes article seems to be the source. There was exactly one example given, and my previous posting discusses why it did well. Indeed, Macsyma has both a Fortran-to-Lisp translator (written by Kent Pitman) and a numerical-Fortran-code-generator. They are both useful: F-L to import numerical libraries into Lisp (unfortunately the runtime conventions apparently clashed too much to allow Fortran code simply to be linked in); Macsyma-F to use symbolic results to generate Fortran programs which were then run on other machines. Lisp is a wonderful language, but it has never run numbers fast. It is even less likely to run numbers, or anything else, fast, in its current PL/I-like phase of development. -s
hen@bu-cs.UUCP (Bill Henneman) (03/15/85)
Well, yes, FORTRAN is a more logical choice than LISP for crunching numbers if thats *all* you're doing. But suppose your application involves 80% stuff where LISP routines are your best choice, but 20% number crunching (an intelligent robot, for example, where the scene analysis part would be a nightmare in FORTRAN, but the joint control and the bit maps corresponding to the visual scene have heavy numerical calculation). I am not too proud to write an occasional SETQ, and I might even stoop to writing a nested DO, if in return a get pattern matching, and all those other goodies.
shebs@utah-cs.UUCP (Stanley Shebs) (03/15/85)
In article <473@harvard.ARPA> Stavros Macrakis writes: >The point was simply that in fact MacLisp numeric code is not all that >it's cracked up to be, and indeed if you want efficient number-crunching >you use some other language. Fortran happens to be the language in >terms of which the original argument was couched. Given what I know of >the internals and the I/O behavior of both the Maclisp compiler and the >Intermetrics AIE Ada compiler (I work part-time there), I suspect that >it too will produce better numeric code but also non-numeric code >(including handling recursion, linked lists, etc.) than Maclisp. >Regrettably, garbage collection was not funded in the AIE. > >Having worked with Lisp for 14 years now, I think I have some idea of >its strengths, which in my opinion are being diluted by pretending it is >just a general-purpose language with a funny syntax and poor >type-checking. There were a lot of people at AAAI that had worked with Lisp for a long time and whose Lisps were beaten by PSL in the Gabriel timing tests. Lisp is a sufficiently high-level language that implementation tricks buy you a lot. The problem seems to be that really efficient Lisp requires so MANY tricks that it strains normal hacking practice to include them all (thus my own research on accountable knowledge-based implementations). >Here's an example of the `wealth' of datatypes from a member of the >Common Lisp committee: "Common Lisp arrays are incredibly complex.... >The resulting tangle of types...is clearly a political compromise and >not something that would exist after careful design". [RA Brooks and RP >Gabriel (an very experiencied Lisp implementer), "A Critique of Common >Lisp", 1984 ACM Symposium on Lisp and Func. Prog.; an excellent paper, >by the way] Actually, I was just pointing out that real Lisps have more than just integers, symbols, and pairs. In any case, I think it's interesting that languages intended for many different uses get so large - PL/I, Common Lisp, Ada... Everybody complains about it, but I don't know that it's such a bad thing. At least in CL, 90% of the hair can be coded using a simpler Lisp - the purpose of the standard is just to ensure that everybody's utilities look alike, and that portable programs don't need to carry 10,000 lines of libraries around (including a 69th implementation of defstruct, looping macros, formatting functions, ad nauseam). CL is about the same size and complexity as a PSL (which is generally considered to be a "small" Lisp) with all the loadable stuff brought in. >> For many years, the Maclisp compiler on the DEC-20 has produced >> numerical code superior to Fortran. -- stan shebs > >This is not and never was true. See my previous posting. As for poor >Common Lisp, "it requires either specially micro-coded machines, a >fantastically complex compiler (which relies on copious declarations >from the poor incompetant user), or very slow running time." [ibid] I was wrong and I apologize if I misled anyone. However, I personally don't believe the statement about CL (except maybe the part about the compiler being complex!). After all, didn't people used to believe that Lisp is inherently a very slow language? >Lisp is a wonderful language, but it has never run numbers fast. It is >even less likely to run numbers, or anything else, fast, in its current >PL/I-like phase of development. The PSL group here has a pretty good compiler under development. The old PSL compiler (which did so well on the Gabriel timing tests) is pretty crude by comparison... We're also looking at ways to make CL run as fast as PSL. One final note: an Ada person accusing Common Lisp of being too big and complex is definitely a pot calling the kettle black. stan shebs
tim@cmu-cs-k.ARPA (Tim Maroney) (03/16/85)
Ideally, if you are writing a program which has 80% "Lisp-like" code and 20% "Fortran-like" code, the programming environment should make it possible to link Fortran functions into the Lisp interpreter. Unfortunately, many (most?) Lisps do not support this.... -=- Tim Maroney, Carnegie-Mellon University, Networking ARPA: Tim.Maroney@CMU-CS-K uucp: seismo!cmu-cs-k!tim CompuServe: 74176,1360 audio: shout "Hey, Tim!"
hen@bu-cs.UUCP (Bill Henneman) (03/17/85)
I don't share the same set of ideals. I can link FORTRAN (or PASCAL, or PL/I, or whatever) routines in our LISP. I can even fire up supprocesses written in strange languages, and pipe the answers back. Should I? I think not, possibly because I have a stronger belief in the Whorfian hypothesis for programming languages than for natural languages. If I want to build a system, I don't want to have to switch languages in mid-development. Niggling little details about representation switching start using up all my hacking time, which I would rather devote to the application level. Do you link SNOBOL routines when you want pattern matching? I bet not. Should you, ideally? By your argument, yes. I have had the distinctly unpleasant experience of trying to fix a DEC internal system which was written in OPS5, but fired up tasks written in o BASIC o BLISS o COBOL(!) Anyone acting in the role of program doctor would have done what I did. I prescribed euthinasia.
tim@cmu-cs-k.ARPA (Tim Maroney) (03/19/85)
Don't start acting as if I had said "Whenever it is possible to link code from another language into a Lisp system, you should do so." I said that if you were doing something numerically in Lisp which could be better done by Fortran, then your Lisp system ought to make it possible to link in the Fortran routines. Representational problems are unlikely to be serious when you are dealing with integers and reals on the same machine! The worst problem would be arrays, but a pair of conversion functions between the representations should be near-trivial to write and debug, and once that is done there is no problem. No, I wouldn't advocate linking a SNOBOL program into one written in another language, nor did I ever imply that I would. -=- Tim Maroney, Carnegie-Mellon University, Networking ARPA: Tim.Maroney@CMU-CS-K uucp: seismo!cmu-cs-k!tim CompuServe: 74176,1360 audio: shout "Hey, Tim!"
ndiamond@watdaisy.UUCP (Norman Diamond) (03/19/85)
> If I want to build a system, I don't want to have to switch > languages in mid-development. Niggling little details about > representation switching start using up all my hacking time, which I > would rather devote to the application level. That's exactly why you do some planning in very early development (I will need this routine in that language, so I will code it last and add an assembly-language interface, or I will code it first and maybe / maybe not need an assembly-language interface); and why you switch languages only at the very end of development (when you are actually coding). When I code a call to a subroutine, I do not suspend this routine and immediately code the subroutine. The subroutine is already written or will be written later. Language switching is even less frequent than routine switching. -- Norman Diamond UUCP: {decvax|utzoo|ihnp4|allegra}!watmath!watdaisy!ndiamond CSNET: ndiamond%watdaisy@waterloo.csnet ARPA: ndiamond%watdaisy%waterloo.csnet@csnet-relay.arpa "Opinions are those of the keyboard, and do not reflect on me or higher-ups."
hen@bu-cs.UUCP (Bill Henneman) (03/19/85)
Um, I think I made a careless error. I have been responding to messages in net.ai without checking the cross-listings of the postings. I phrased my reply under the misapprehension that I was conversing with an experienced LISP user. My curt reply was based on a wrong model of how elliptic I could be. The only thing I accused you of was basing an argument on experience you didn't have. I'll start over. If you say that PASCAL or ADA ought to be able to link FORTRAN library routines, I'll interpret the statement as a comment about the benefits gained from using carefully crafted library packages like the IMSL routines vs. the cost of accommodating the linkage. Any compiler builder will agree - something like the support required has to be there, the cost of accommodation is small, the benefit is great. It ought to be done. But LISP is not some sort of Cambridge Polish form of FORTRAN. It makes different assumptions about the computing environment. LISP is interpreted, and has a rather devil-may-care attitude about errors, since it can inspect the entire run time environment to take corrective action. The FORTRAN compiler inserts certain implicit assumptions about the run-time environment into compiled code, and refuses to compile "dangerous-looking" code, because it can't see the run-time environment. While most LISPs I am familiar with can load FORTRAN library routines, none fully support them. As a simple example of the difference between allowing alien routines to be called and supporting their use, consider the trivial problem of linking to SQRT from LISP. This does involve a trivial reformatting of numbers to support the call. No problem - float the number if necessary, build the calling sequence and call SQRT. But what happens if SQRT detects what it thinks is an error condition (such as a negative number being passed)? Who gets to handle the problem? SQRT assumes the presence of a fairly elaborate run-time support module to handle error messages, and in this case to provide standard fix-ups. Does the LISP user get a FORTRAN error message with the answer canonically set to 0, or a LISP error break? The only answer acceptable to the LISP user is to be thrown into the LISP error break, so the FORTRAN error handler has to be trapped by a special LISP module to support the FORTRAN run-time routine. Building such a beast is a non-trivial job, since you have to take into account all the different ways FORTRAN routines might react to error conditions. Some FORTRAN library routines depend on interrupt handlers being present, or specific interrupts being masked off. Some FORTRAN graphics library routines feel free to use the complete I/O capabilities of the machine. In fact, in order to provide LISP functions with the ability to use the FORTRAN routines called, LISP ends up having to simulate (and override) the full run-time environment of FORTRAN. This simulation is a complete add-on, since LISP treats all such environmental issues in a completely different fashion. And so, we come to my assertion that you might as well try to link SNOBOL routines. Well, if you have provided the full run-time support for FORTRAN library routines, you get SNOBOL support essentially for free! Read "The Macro Implementation of SNOBOL 4" by Ralph E. Griswold to see how much SNOBOL relies on the FORTRAN environment. In order to get the benefit, you have to pay the cost. The cost in the case of PASCAL supporting FORTRAN library routines is paid in how you code a module which in some form or another had to be there anyway, and the user sees nothing but benefits. The cost in the case of LISP supporting FORTRAN library routines is paid in designing a module which allows things to be done in a way inconsistent with the way everything else is done in LISP, leading to code which is difficult to maintain, an interface which is impossible to document, and a very angry user community. It just isn't worth it.
tim@cmu-cs-k.ARPA (Tim Maroney) (03/24/85)
Since you have chosen to cast false aspersions on my Lisp experience and to ignore all my main points, I see no reason to continue this discussion. -=- Tim Maroney, Carnegie-Mellon University, Networking ARPA: Tim.Maroney@CMU-CS-K uucp: seismo!cmu-cs-k!tim CompuServe: 74176,1360 audio: shout "Hey, Tim!"