beck@qtp.ufl.edu (Sullivan Beck) (10/09/90)
> Second question. I am writing a lisp program which does a lot of > text operations and uses a lot of alists, lists, and vectors. It > does so much in fact that it is a little on the slow side and I will > eventually want to byte-compile it in order to speed it up. What > can I do now to help get the best speed once I byte-compile it? First of all, some clarification. The reason I asked this question in the first place is because of a statement by David Gillespie in his calc program. From the file calc-INSTALL: | Calc is written in a way that maximizes performance when its code has | been byte-compiled; a side effect is that performance is seriously | degraded if it *isn't* compiled. Thus, it is essential to compile the | Calculator before trying to use it. The Emacs command `M-x Some general suggestions were made by Raul about lisp programming. | 1) C-coded Lisp functions will be faster than those written in | Lisp. | 2) Don't use functions that set the mark, or display a message | in the minibuffer, in internal Lisp code. Typically these are | user-oriented, and could be rewritten to be slightly faster | to work in Lisp code. | 3) When calling Lisp functions that are not C-coded (i.e., | (subrp 'function) is `nil'), it is a good idea to ALWAYS | check the Lisp source code to see what they do, and see if | you really need the overhead. For example: the difference | between "next-line" and "forward-line". "next-line" does some | things that you normally don't need to worry about when | using it internally. | 4) `substitute-command-keys' warning: it takes a while, up to | a full second, to execute. Try it! And from David Gillespie: | There are two major reasons for this statement: | | 1. Calc uses lots of Lisp macros nested inside the deepest loops. In | compiled code these macros are expanded once at compile-time, but in | interpreted code each macro is expanded each time it is called. | | 2. Calc's inner loops try to use only Lisp functions which are handled | directly by the byte-compiler. When you write "(stringp x)", the | byte-compiler translates this into one byte-code to fetch "x" and | one byte-code to execute "stringp". But when you write "(integerp x)", | the byte-compiler doesn't have a byte-code for "integerp" so it | produces a general function-call which is only slightly faster than | an interpreted call would be. | | A funny thing about Emacs Lisp is that function calls are about the most | expensive thing in the language. Since Lisp is "supposed" to be written | recursively this seems rather odd; in fact, Calc was originally written | using recursion instead of loops in most places but once I read the | source to the Lisp interpreter I realized "while" loops would be much | faster. In fact, rewriting a few inner loops to use "while" made the | whole calculator twice as fast! | | There are a number of reasons for this; for example, at any time a program | may call "(debug)" to run the Lisp Debugger and display a backtrace, so | all function calls must keep complete backtrace information just in case. | Each function call must also check to see if the garbage collector needs | to be invoked, check for and handle &optional and &rest arguments, and so | on. | | The list of byte-codes can be found at the top of "bytecomp.el" in the | Emacs source directory. Read this list, memorize it, paste it on the wall | or preferably on the inside of your forehead. This list is your friend | if you are trying to get performance out of Emacs Lisp. Also, it can't | hurt to run "disassemble" on your most critical functions to see how | well they compile. | | Another example: The "elt" function can do both "nth" (if its argument | is a list) or "aref" (if its argument is a vector). I used it all over | the place because I figured there wouldn't be much difference and I liked | it a bit more. But it turns out that "elt" is not byte-compiled whereas | "nth" and "aref" are. I went back through my code, and bingo, another | factor of two in performance! | | Other fun tricks: "(+ a b c)" is not byte-compiled, but "(+ a (+ b c))" is. | "*" is not byte-compiled at all, so "(+ a (+ a a))" is faster than "(* 3 a)". | The "setq" function returns the last value that was assigned; if you call it | in a context that does not use the value the compiler must insert a "discard" | instruction to throw away the value, which was left there by a superfluous | "dup" instruction. So "(setq a1 b1 a2 b2)" is faster than "(setq a1 b1) | (setq a2 b2)", and "(if (setq a b) ...)" is faster than "(setq a b) | (if a ...)". All of these are minor gains, but minors gains inside a | tight loop can be important. | | The function-call overhead is enough that it's especially important to use | high-level structural functions whenever you can. For example, if you have | a data structure that you will be searching often, see if you can arrange | so that it can be searched by "memq", "assq", or "assoc". This will be | much faster than an equivalent "while" loop. "memq" is even byte-compiled | (although a single function-call overhead is probably worth having your | whole loop execute in C anyway). Note that "equal" is not byte-compiled, | so using "assoc" to search a list of "equal" things is an especially big | win. For example, I use "(assoc s '(("one") ("two") ("three")))" to check | if "s" is one of these three strings. It seems like overkill, but it's | better because all three tests are done in C. Hope this helps any lisp programmers out there as much as it helped me. Thanks to everyone who responed. S. Beck beck@qtp.ufl.edu
mike@ists.ists.ca (Mike Clarkson) (10/17/90)
In article <1162@red15.qtp.ufl.edu> beck@qtp.ufl.edu (Sullivan Beck) writes: > > < a fascinating and very informative collection of programming > > < tips for speeding up elisp code. > > >Hope this helps any lisp programmers out there as much as it helped me. >Thanks to everyone who responed. This really should read: >Hope this helps any elisp programmers out there as much as it helped me. ***** These pointers are very specific to the GNU elisp byte-compiler. One of the fascinating things about lisp is how these trade-offs differ from dialect to dialect, and implementation to implementation. This is one of the things that makes lisp such a difficult language to program *well* in. Mike. -- Mike Clarkson mike@ists.ists.ca Institute for Space and Terrestrial Science uunet!attcan!ists!mike York University, North York, Ontario, FORTRAN - just say no. CANADA M3J 1P3 +1 (416) 736-5611
kim@Software.Mitel.com (Kim Letkeman) (10/17/90)
In article <13937@ists.ists.ca> mike@ists.ists.ca (Mike Clarkson) writes: | | These pointers are very specific to the GNU elisp byte-compiler. One | of the fascinating things about lisp is how these trade-offs differ | from dialect to dialect, and implementation to implementation. This is | one of the things that makes lisp such a difficult language to program | *well* in. | I'm certain that these tips are appreciated by anyone who feels the "need for speed"@footnote{See TopGun}. But I feel compelled to point out that the main reason why we (in the general computer scientist sense) use high level languages is to take advantage of the built-in abstraction of data and process that comes with such a language. Elisp handles some extremely high level concepts with ease, and there is no shortage of excellent software to go with gnu emacs for that reason. Your earlier posting demonstrated an excellent knowledge of the inner workings of the Elisp byte compiler, which could potentially increase the performance of certain operations within any Elisp-coded functional unit within emacs. But emacs is extremely popular because of its power to tame many of the mundane aspects of programming and of maintaining a liveable environment. I'm one of those that starts up an emacs window covering the vast majority of my Sun workstation's screen area and then live in the editor, using gnus, VM and other ELisp-coded functional units to create an extremely pleasant and efficient environment. I can not remember ever saying to myself "geez, I wish that <operation X> had been code more efficiently .... it's taking too many seconds." The reason for this is, of course, that my overall productivity is much higher inside emacs, so I am forgiving of some of the more time consuming operations (none of which even come close to being annoying anyway ....) Another problem with worrying these micro-details is that I'm sure that the FSF would not hesitate to change the way in which code is byte compiled if it could gain an overall performance advantage. For this reason, it is never a good idea to second guess any compiler. I guess I should make a point. I would like to see the authors of these packages spending their time coming up with more useful and innovative functionality, rather than spending time altering algorithms to attempt to take advantage of a quirk or two in the current byte compiler. There's simply no long-term payoff in it. (Especially when one considers the incredible performance leaps and bounds happening in hardware right now.) -- Kim Letkeman kim@software.mitel.com uunet!mitel!spock!kim
daveg@near.cs.caltech.edu (Dave Gillespie) (10/18/90)
I had a few comments about Kim Letkman's posting concerning whether it is wise to optimize byte-compiled code for speed. First, it's worth recalling that this issue came up because someone had an ELisp program which was uncomfortably slow. It's clear that, even if ELisp is plenty fast for many of the tasks to which people have applied it, there are other tasks which do push it to the limit. My Emacs Calculator is, as far as I know, by far the largest and probably the most computation-intensive Emacs program out there. When I originally wrote it it was uncomfortably slow; a careful reading of the implementations of the Lisp compiler and runtime system allowed me to speed it up by a factor of, roughly, five. This speed-up made the difference between "annoyingly slow" and "pleasantly fast" for simple operations in that program. It made the difference between "impractical" and "practical" for more advanced operations. Many people use Calc for jobs like summing columns of numbers from an Emacs file. That was the original reason for implementing it as part of Emacs, after all. These jobs can use all the performance they can get because the time they take scales with the size of the problem. Many existing ELisp programs share this property, and many others unnaturally constrain themselves to avoid it so that they will still be usable for large inputs. Every extra bit of speed squeezed out of ELisp allows these programs to provide more capabilities to their users. Many of the "useful and innovative functions" Kim asks for would not be practical if the foundations on which they were built were not solid and efficient. Yes, the FSF *could* change the byte-compiler tomorrow and much of the gains I got with Calc would be lost. But in practice, that won't happen tomorrow. Suppose it happens a year or two from now; during those years many people will have been able to do things with Calc that would otherwise have been impractical if I had not put in the extra effort to make it fast. Even if two years from now that effort is made pointless, I still think it was worth it overall. Emacs Lisp will not be around forever, nor will any language in use today. Even aside from optimization issues, any program you write in these languages has a limited lifetime. But that's no excuse to give up and never write anything new. There's no question that it's good to plan for the future, but if you ignore the here-and-now your program won't be around in the future anyway. I don't recommend that people devote huge efforts to squeezing out every last cycle in every part of their programs. I certainly don't. But usually a few parts of a program do deserve that attention, and it's just plain sloppy not to give it to them. And it's no great strain to keep in the back of your mind that "nth" is faster than "elt" and "cons" is faster than "nconc". If there's a fast way of doing something and a slow way, it's only reasonable to expect to know your tools well enough to choose the fast way. Emacs itself is only fast enough to "tame the mundane aspects of programming" and "maintain a liveable environment" because its author paid the same attention to detail. -- Dave -- Dave Gillespie 256-80 Caltech Pasadena CA USA 91125 daveg@csvax.cs.caltech.edu, ...!cit-vax!daveg
kim@Software.Mitel.com (Kim Letkeman) (10/18/90)
In article <DAVEG.90Oct17195731@near.cs.caltech.edu> daveg@near.cs.caltech.edu (Dave Gillespie) writes: | I don't recommend that people devote huge efforts to squeezing out | every last cycle in every part of their programs. I certainly don't. | But usually a few parts of a program do deserve that attention, and | it's just plain sloppy not to give it to them. And it's no great | strain to keep in the back of your mind that "nth" is faster than | "elt" and "cons" is faster than "nconc". If there's a fast way of | doing something and a slow way, it's only reasonable to expect to know | your tools well enough to choose the fast way. Emacs itself is only | fast enough to "tame the mundane aspects of programming" and "maintain | a liveable environment" because its author paid the same attention | to detail. I certainly grant that this attention to detail is what makes gnu emacs such a pleasure to use. And that equivalent attention to detail is what separates the good from the bad in software design in any field. I will also grant that those who take the time to understand a compiler can write more efficient code without penalty. And if one wants to commit to the upkeep necessary if the compiler changes (assuming that the author is not also the author of the compiler), then one can do as one pleases, and the users will benefit. My points actually stem from my experience in real-time systems. Attention to the macro rather than the micro algorithms and details is where the order of magnitude performace increases lie. Many performance problems result from poor design decisions, almost always the result of a lack of abstraction of the problem. Anyway, we're straying off topic in this group and I'll grant that your calculator benefited from the exercise, thereby validating this type of attention to micro-detail under the right circumstances. Kim -- Kim Letkeman kim@software.mitel.com uunet!mitel!spock!kim
worley@compass.com (Dale Worley) (10/18/90)
In article <KIM.90Oct17092802@kim.Software.Mitel.com> kim@Software.Mitel.com (Kim Letkeman) writes:
I can not remember ever saying to myself "geez, I wish that <operation
X> had been code more efficiently .... it's taking too many seconds."
Try byte-compiling the Emacs lisp directory! :-)
Seriously, Kim, if Emacs were always fast enough in practice, there'd
be no need for a byte compiler at all. I've had days when C-n can
take noticable time, and I've used packages that can be agonizingly
slow even when the hardware is otherwise unloaded.
One interesting thing about Sullivan Beck's list of ideas is that many
of them are things the byte-compiler could do for you. Putting the
optimizations in the byte-compiler saves a lot of work -- optimizing
the bytecode is done only once, and the application programmers can
spend their time on new features. Unfortunately, nobody has spent the
time to upgrade the byte-compiler to squeeze out improved performance
from the generated bytecode.
Dale Worley Compass, Inc. worley@compass.com
--
People mistakenly believe that computers have a lot to do with
numbers, which is totally inaccurate. In fact, a large number of
bluffers have gone into computers because there's no area in which
it's easier to hide a complete inability to count, except perhaps
mathematics. -- Bluff Your Way in Computerskim@Software.Mitel.com (Kim Letkeman) (10/19/90)
In article <WORLEY.90Oct18093925@sn1987a.compass.com> worley@compass.com (Dale Worley) writes: | In article <KIM.90Oct17092802@kim.Software.Mitel.com> kim@Software.Mitel.com (Kim Letkeman) writes: | I can not remember ever saying to myself "geez, I wish that <operation | X> had been code more efficiently .... it's taking too many seconds." | | Try byte-compiling the Emacs lisp directory! :-) I do. It doesn't take all that long when one considers the amount of work happening ... but I suppose I should come clean now and mention that I've been using a Sparc 1+ for months now ... maybe that's why I consider emacs to be efficient enough. | Seriously, Kim, if Emacs were always fast enough in practice, there'd | be no need for a byte compiler at all. I've had days when C-n can | take noticable time, and I've used packages that can be agonizingly | slow even when the hardware is otherwise unloaded. I disagree with this. It is always a good idea to use a generic mechanism that is applied in a consistent manner to obtain a known increase in performance. That is one of the many reasons for using compilers in the first place. But when one "hand compiles" (i.e. uses less obvious algorithms) to attain higher efficiency than afforded by the compiler, then I submit that the compiler needs fixing, not the code. | One interesting thing about Sullivan Beck's list of ideas is that many | of them are things the byte-compiler could do for you. Putting the | optimizations in the byte-compiler saves a lot of work -- optimizing | the bytecode is done only once, and the application programmers can | spend their time on new features. Unfortunately, nobody has spent the | time to upgrade the byte-compiler to squeeze out improved performance | from the generated bytecode. Exactly. Although in a previous posting I concurred with the author of the calculator mode that there were certainly circumstances under which one can justify prying the lid off of a compiler, it simply is not the way to go for the general population at all times. Much better that the same people spend their time lobbying the FSF to do these optimizations internally so that common or natural ways of doing things are as fast as specialized methods. Or better yet - someone help them out and do the optimizations to the byte compiler for the good of gnu emacs weenie-kind. I'm sure we'd all appreciate it. By the way, my opinions are not intended to sell short the value of the information on the byte compiler's internals. But rather to express the idea that, in a situation where you have the option of fixing all the code that gets compiled or fixing the compiler, well, there's not much to choose .... Kim -- Kim Letkeman kim@software.mitel.com uunet!mitel!spock!kim