Path: utzoo!utgpu!water!watmath!clyde!att!osu-cis!tut.cis.ohio-state.edu!cwjcc!mailrus!uflorida!novavax!proxftl!twwells!bill From: bill@twwells.uucp (T. William Wells) Newsgroups: comp.lang.c Subject: Efficient coding considered harmful? Message-ID: <119@twwells.uucp> Date: 27 Oct 88 07:33:10 GMT References: <3105@hubcap.UUCP> <34112@XAIT.XEROX.COM> <1700@dataio.Data-IO.COM> <8630@smoke.ARPA> <1704@dataio.Data-IO.COM> Reply-To: bill@twwells.UUCP (T. William Wells) Organization: None, Ft. Lauderdale Lines: 423 Expires: Sender: Followup-To: Keywords: Sorry I wasn't able to participate much in the discussion on efficient coding, but between setting up my new computer, a wedding anniversary, computer problems at work, thinking about comp.archives, and lots of other things, I have had little or no time to write, and certainly not about anything complex. Anyway, here goes... It's the damnedest thing, but people whose opinions I otherwise respect seem to have this thing about coding efficiently. They don't like it. Worse, they discourage it. Well, phooey. --- I advocate training oneself to be one who codes efficient programs. I do not mean writing code and then making it more efficient, I mean writing it that way in the first place. One should make it a practice to consider which coding methods are best on each architecture, so that it is second nature to code efficiently. Efficient coding should take its place right along with easily understood coding as something every coder should do, as a routine part of the job. I have heard three main counterarguments to this: 1) "The compiler ought to handle that, so you shouldn't bother with it." What nonsense! We have to code in the real world, not the world of make-believe and ought-to. 2) "What is more efficient on one machine may well be less efficient on another." Well, this is a good argument for knowing a lot of different machines and adapting one's coding style to the relevant machines, but this is certainly not a good argument for avoiding efficient coding. What it boils down to is an argument that a program which is coded in ignorance of efficiency may well be better (efficiency-wise) than one which is coded to be efficient, albeit only for some set of architectures. Well, could be, but I wouldn't bet on it. 3) "Efficient coding makes obscurer programs." Well, since most efficient coding involves minor changes from the inefficient way of doing things, changes which are mostly a matter of style rather than of organization, this argument should really be read: "*I* don't like to or find it hard to read that kind of program, so it is unclear." Well, speak for yourself! --- [I wrote about improving other people's code. I mentioned that following certain coding practices, eliminating "fat", and doing so throughout a program, I was often able to improve the execution time by 25% or more.] From: rwberry@hubcap.UUCP (Robert W Berry) Message-ID: <3105@hubcap.UUCP> : I've been programming for YEARS, and if it's not a professional trade : secret, I'd love it if you would summarize your "coding practices" and : email them or post them. They are no real secret but I haven't really thought hard about organizing them for presentation, so I can't just tell you about them. However, some of the suggestions that I have seen posted have been similar to what I do. The next time I go over someone else's code, I'll see if I can remember to make notes. Following are some suggestions right off the top of my head, take them with the requisite dollop of thinking for oneself. The first thing: understand the kinds of architectures where efficiency matters. If you are coding a game, you can be reasonably sure that efficiency is only of concern on relatively conventional architectures, so make yous assumptions accordingly. If you are coding some kinds of numerical stuff, where the greatest efficiency ought to be obtained on an array processor, keep in mind the characteristics of array processors when optimizing code. The more you know about the processors that your code could have to run on, and the better your analysis of which ones efficiency matters on, the better will be the decisions you make on which coding practices to adopt. Read compiler design books. Whatever they tell you is good for the compiler is also good for you the coder. They talk about common subexpression elimination: when you write code, look for common subexpressions and eliminate them. (But watch out: not all common subexpressions should be eliminated, this too is a matter of judgegment and experience.) They talk about strength reduction, you look for places where strength reduction is possible. Note that *you* can do a better job of this than the compiler can. *You* are capable of inductions that the compiler is not. *You* can find optimizations that are not possible to discover mechanically. This is one reason why the argument "leave it to the compiler" is often wrong. Along this line, look for redundant calculations: sometimes it is cost effective to store the result of a previous calculation instead of recomputing it. In particular avoid recalculation in the control part of iterative statements. Many's the time that I have got significant improvements just by turning: for (i = 0; i < a[j]; ++i) ... into for (i = 0, ilast = a[j]; i < ilast; ++i) ... or some equivalent. Use register variables. And take a litle pain to get them right. A technique that works enough of the time is this: break up a routine into groups that are executed with about the same frequency. Guessing is OK. Starting with the most frequent, count the number of references to each automatic. If the numbers are sufficiently different, order them by those numbers. Where they are not, use the next most frequent group to decide the order. Repeat till you run out of groups or variables. This is only a heuristic, but it can be done on the fly, or with simple programming tools, and is certainly better than not specifying register variables at all. Avoid excess function calls. A lot of people have been brainwashed by some modularity gurus into believing that every identifiable "whole" should have its own function. What I have found is that this makes the program LESS maintainable than otherwise. And, of course, programs written this way do a lot of function calls. My own recipe divides functions into two classes: those that control the operation of other functions and those that do the dirty work. The control functions should generally restrict themselves to if's and function calls and maybe some initialization; the other functions can do whatever is needed. If the grunge functions start to get too complicated, start from the outside when splitting up the function: this keeps down the number of function calls while getting the most decomposition for your effort. Don't use goto. Yes, oddly enough, this can make programs slower. Many optimizers that I know of give up on any function that contains a goto. So adding a goto may very well slow down your code. --- From: g-rh@XAIT.XEROX.COM (Richard Harter) Message-ID: <34112@XAIT.XEROX.COM> : I would say that we all know what Bill is talking about : here, except that "we" all obviously don't. Basically this is : using hand optimization as a default in coding style. One can take : the view that a good optimizer will do many of these things, e.g. : use of temporaries, moving static expressions outside loops, placing : the appropriate variables in registers, etc. One can also take the : view that the capabilities and realities of optimizing compilers are : less than claimed. Hand optimizing is safer across a variety of : environments. : : In my experience hand optimizing in original code is less : efficient, in the sense of code written per unit time, then writing : code initially in a "clear" style first, and then hand optimizing : afterwards. In short, write it in the simplest way first, get it : working, and then improve performance. This is not quite what I am advocating. Rather than hand-optimizing as you code (though one should certainly do a certain amount of this as a matter of course), I am advocating developing a mindset where this kind of "optimizing" becomes your natural coding style. This does mean developing more than one "natural" coding style, but that is no more a problem than our habit of using different speech patterns in different social situations. As an example of what I mean, when I am coding a program that I expect to be run on one of the "normal" machines, I don't write my code as for (i = 0; i < ALAST; ++i) { ... A[i]; } and then change it to: for (ap = A; ap < &A[ALAST]; ++ap) { ... *ap; } I write it this second way, as a matter of course, because I thought about it for a while and decided that this was the appropriate way to do it. I then trained myself into the habit of doing it this way. Now, I don't spend *any* extra time getting the advantages of the latter formulation. As a necessary and important side effect I also became comfortable with such things and now treat them as no more abnormal or incomprehensible than *ptr++. --- From: bright@Data-IO.COM (Walter Bright) Message-ID: <1700@dataio.Data-IO.COM> : Here's some of the things I do: : o Organize complicated if statements so the result of the calculation : is known by evaluating it as little as possible. For instance, : if (a && b && c) : ... : organize such that if a is easy to evaluate and usually FALSE, put : it first. This also generalizes to sequences of if-else statements. : o Replace stuff like, : if (a) : x = b; : else : x = c; : with, : x = a ? b : c; : Many compilers generate better code for the latter. I have to disagree with this. About the only time that this helps is when combining the statements gives greater scope to the optimizer. This happens because many optimizers won't optimize across statements. Unfortunately, this particular change, when done with complicated expressions, can make the code much harder to read, so it must be done with care. : o Use the ^ operator because many times, : a = !a; : should really be, : a ^= 1; However, some machines can't do ^ very well, so take care. : o Avoid things like, : a %= 4; : Replace with, : a &= 3; Generally true, but watch out for negative numbers. Also, dividing positive numbers by powers of two should be done with a shift. : o Organize control flow such that the most common cases go straight : through, this is most important for pipelined machines. While this is true, this tends to make the code *much* less readable, even when you can get the optimizer to cooperate. So I don't do this one. : o I gag when I see things like, : a = strlen("asdf") + 1; : instead of, : a = sizeof("asdf"); : The strlen case above was even printed in a magazine recently to : 'prove' that assembler was better than C! Gag. This is a specific example of a general case: never do at run time that which you can get the compiler to do at compile time. However, beware of getting the compiler to do floating point for you: some won't, and others will do it differently in the compiler than they would have at run time. : o Try to improve the 'locality' of operations, i.e. move calculations : as close as possible to the point where they are used. This helps : most compilers to utilize registers better. Good point. I hadn't thought of doing this. And it should often make the reader's job easier, bringing related things closer. : o Replace int variables with unsigned where possible. This tells the : optimizer that the variable can never be negative, making certain : optimizations possible. Unfortunately, this one is likely to make the optimizer not do certain optimizations that the compiler writer didn't think were useful for unsigned. Sigh. Not only that, but I have discovered more bugs dealing with unsigned things... : o Put the most frequently accessed member of a struct first, so the : offset is 0. Yes. And put scalar arguments before aggregate arguments in your functions. : o Use char arrays instead of int arrays where possible. Accessing characters on some systems causes a fair amount of code to be generated. For example, on a 68000, accessing an unsigned character to be used as an integer adds an instruction to each read. Accessing a signed character might involve two extra instructions. : o Adjust other : arrays so that the size of the array elements are a power of 2. : (Making the address calculation a simple shift.) Be careful if you are making the arrays larger, you may make the program slower. Demand paging systems and swapping systems both can do you dirty when the program data is bigger. : o Avoid bit fields, most especially signed ones. Try: don't use them at all, they tend to be nonportable. Of course, if you have a good compiler on a VAX... : o Use realloc instead of malloc/free pairs. Use calloc instead of : malloc followed by zeroing each member. Efficient memory allocation is *much* more difficult than this, what you really need to do is to cut down on the number of calls to malloc and free. Of course, that usually means writing some kind of allocation stuff yourself, never an easy task. Realloc has to copy data, so this should be less efficient than just doing another malloc & free. Also, calloc is nearly useless for clearing structures that contain pointers. It is just not portable to assume that a bit pattern of all zeros is equivalent to a null pointer. --- From: gwyn@smoke.ARPA (Doug Gwyn ) Message-ID: <8630@smoke.ARPA> : > o Avoid things like, : > a %= 4; : > Replace with, : > a &= 3; : : You're assuming a is nonnegative. Any decent compiler will : perform such instruction replacements for you. Write whatever : is clearest in context. To get a remainder, % is clearer. You are assuming that the compiler can figure out that a is nonnegative. Unless declared so, it is unlikely that a compiler will figure this out. However, the human can. And, again, clarity is often merely in the eye of the beholder. *I* don't have any problem interpreting the & as a remainder operation. : In the case that the "4" might change, parameterizing the : first case will give correct code after it changes, while : the second will break unless another power of two is used : for the replacement for "4". Thus the first is SAFER. Unless, of course, the programmer remembered to COMMENT. : > o Combine printfs, : > printf("aksdf aksjdhf kahdf jhdsfhj\n"); : > printf(" asdkljfhkajshdf djfh kjahsdfkja h\n"); : > Convert to, : > printf("aksdf aksjdhf kahdf jhdsfhj\n\ : > asdkljfhkajshdf djfh kjahsdfkja h\n"); : : Thereby introducing a bug (exercise for the student). The spaces. Two black spots for K&R string continuation. : The difference in time between these is negligible, : but if you're really tweaking for efficiency puts() : might have been better, depending on the implementation. But I'd think of this as a *space* optimization, not a speed optimization. And I know of several programs where just this one optimization could save 5-10% in the program size. : ... : A related point is to declare local variable in blocks : rather than all at the beginning of the function body. I've found that this can actually make the code harder to read, by making it difficult to find the declaration of a variable. My own practice is to declare things in just four places: in an include file, at the top of a source file, at the top of a function, and within a block, but only if the whole of the block will fit in a 20 line window. : > o Put the most frequently accessed member of a struct first, so the : > offset is 0. : : Not all architectures can access the 0 offset faster than : the others. I knew of one that was actually slower. But, unless one really cares about this oddball situation, one should do it anyway. : > o Avoid struct function parameters and return values. : : This is a matter of interface design. Small structs such : as one might use to represent a complex number are not a : problem; large structs are more quickly (though less conveniently) : passed by reference, so long as not too many references to : the members are made inside the function. Forcing the : caller to allocate the structure may not be convenient. I avoid structure passing and returning. There are still enough compilers out there that don't handle them, or that handle them wrong that portability considerations keep me from using them. --- From: bright@Data-IO.COM (Walter Bright) Message-ID: <1704@dataio.Data-IO.COM> : Micro-efficiency gets regularly denounced. Here are some counterarguments: : o If your commercial product is slower than the competition, you : won't get a chance to take advantage of the maintainability/ : portability advantages because you'll be out of business. Or if it is larger. This discussion has focused on making programs faster, but making them smaller is also relevant. I do know that we have lost customers because someone else offered a smaller program to do the same job. : o The sum of all the tweaks can make the difference (on the PC) : between using a small memory model and the large. This gives : a lot of leverage to seemingly minor changes. The sum of all tweaks can make a difference on lots of machines. Consider the Mac 32K segments, the PDP-11 64K+64K address space, the user forced to wait for 10 seconds instead of 4 because of the 5% slower routine which caused the scheduler to lower his priority.... : o I derive a lot of personal satisfaction from creating 'lean : and mean' code. This is often disregarded: good programmers get that way because they *care*, and if they care, they will insist on doing the best they can. And that should include these "tweaks". --- Phew... I finally got it all answered. On to the next subject... --- Bill {uunet|novavax}!proxftl!twwells!bill