From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-0.8 required=5.0 tests=BAYES_00,INVALID_DATE, MSGID_SHORT autolearn=no autolearn_force=no version=3.4.4 Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Posting-Version: version B 2.10.2 9/18/84; site harvard.ARPA Path: utzoo!watmath!clyde!burl!ulysses!allegra!mit-eddie!godot!harvard!macrakis From: macrakis@harvard.ARPA (Stavros Macrakis) Newsgroups: net.ai,net.lang.lisp,net.lang.ada Subject: Re: Efficiency of LISP Message-ID: <459@harvard.ARPA> Date: Mon, 11-Mar-85 19:25:44 EST Article-I.D.: harvard.459 Posted: Mon Mar 11 19:25:44 1985 Date-Received: Wed, 13-Mar-85 12:49:28 EST References: <417@ssc-vax.UUCP> <676@topaz.ARPA> <6982@watdaisy.UUCP> Organization: Aiken Comp. Lab., Harvard Xref: watmath net.ai:2606 net.lang.lisp:375 net.lang.ada:221 List-Id: > > > an informal experiment ... at MIT ... compared MACLISP with other > > > programming languages [by] translat[ing] FORTRAN into MACLISP. ... > > > the lisp versions ran faster and took up less memory. > [If] both compilers were doing their best at optimizing the generated > code, it's clear that [that] MACLISP compiler was better than [that] > FORTRAN compiler.... This [doesn't mean] LISP is better than FORTRAN > for numerical work, [just] that LISP may not be as bad as some > might think. -- Guy Harris {seismo,ihnp4,allegra}!rlgvax!guy I didn't make this measurement, but I was there. The reason the DEC Fortran code was worse than the Maclisp code was simply that the DEC standard calling conventions (which Maclisp didn't use) were expensive. Otherwise, the code was very similar. Neither compiler produced impressive code. There is, of course, no inherent reason that the inline code produced for numerical calculations in Lisp (assuming machine arithmetic, not bignums) should be much worse than that produced for Fortran, C, Pascal, or Basic. Some technical reasons that a good Maclisp compiler has to do a bit worse than a good Fortran compiler are in the Appendix (below). The BIG concession you make to get the efficiency, of course, is programming with fixed-type operators (and/or declared variables and, to my taste, stepping out of the elegant beauty of the core of Lisp (not that the semantics of Lisp numbers was ever terribly clean). Note, by the way, that the MacLisp system's consistency checking is rather patchwork: declarations are not processed at all interpretively, and separately compiled modules are not checked for consistent declarations. In other words, like many Lisp extensions, numeric processing is pragmatically useful, but semantically a mess. The other issue is whether we are talking about `Lisp' at all. You could equally well add such features to Snobol and claim Snobol did efficient numerical processing. The problem in saying that `Lisp' does something is that if it doesn't, someone will add it and still call it `Lisp'! You might as well call Ada, `Algol'. I'm all for improvement over time, but it is unfair to pretend that Common Lisp '85 = MacLisp '77 = Lisp 1.5. -s Appendix: Some Technical Details The two restrictions on numerical efficiency in the PDP-10 Maclisp implementation are 1) that only 5 registers are available for numbers, because the rest are stack pointers or garbage-collectable and 2) that arrays can only be referenced indirectly, because they may be relocated between any two instructions (Maclisp allows interrupts at arbitrary points). Consider a loop to take an inner product of two arrays, A and B, declared as fixed length. A good Fortran compiler would produce machine code like the following: float a[len], b[len]; register float *cura = &(a[0]), *curb = &(b[0]); register float sum = 0.0; register int count = len; while (--count) sum = *(cura++) + *(curb++); while Maclisp is obligated to produce (at best) something like: float *(a,len), *(b,len); register int index = 0; register float sum = 0.0; while (index < len) sum = *(a,index) + *(a,index); where *(a,index) has the effect of *(a[index]) but is indivisible--a is an indirect word. In DEC Fortran's case, its main efficiency problem seems to be that it stashes all registers (even ones it doesn't use) over subroutine calls. A better compiler could fix this without doing any damage to the definition of Fortran. I speculate that he callee-saves discipline was chosen so that small machine-language library routines (sqrt etc.) could be hand-tuned to save only the registers they care about while not requiring that a table be kept of which routines clobber what registers.