Article 109810 of comp.sys.amiga.programmer: Path: news.peak.org!news.uoregon.edu!news.mathworks.com!howland.erols.net!surfnet.nl!news.unisource.nl!xs4all!xs4all!usenet From: jtv@xs4all.nl (Jeroen T. Vermeulen) Newsgroups: comp.sys.amiga.programmer Subject: Re: My program is too slow! Date: Tue, 14 Jan 97 18:41:21 Organization: Leiden University, Mathematics & Computer Science, The Netherlands Lines: 318 Message-ID: <19970114.7428748.10AEB@localhost.dial.xs4all.nl> References: <5bb0ka$gff@news.Hawaii.Edu> NNTP-Posting-Host: asd11-05.dial.xs4all.nl Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-XS4ALL-Date: Tue, 14 Jan 1997 18:43:00 MET X-NewsSoftware: GRn 2.1 Feb 19, 1994 In article <5bb0ka$gff@news.Hawaii.Edu> supergrover@Hawaii.Edu (Ryooshi) writes: > Find name in MIME tags or create one if not present > | > V > Read one line of mime code > | > V > Decode 4 characters (one at a time) and store in 3 bytes of array buffer > | > V > If buffer full, write buffer. Else keep decoding. Okay, I'll assume that you've enabled the compiler's optimizer of course. Here are some general hints for optimizing programs. They're standard rules in program optimization, but for some reason many practically-oriented coders (as opposed to academically-oriented) tend to focus on stuff like whether or not "if (x) y else z" is slower than "if (!x) z else y". (*) Profile your code. If you have access to a code profiler, like SAS/C's sprof or guiprof, or StormProfiler for StormC, or gprof for gcc, USE IT. It will be able to tell you where your code really spends the most time. You may find some surprises there; perhaps some small function call is taking up a lot more time than you thought. If you have a profiler at your disposal, go through a couple of large test runs and note the most time-consuming functions. Optimize these first. Remember that if a function eats up only, say, 10% of your running time, it is probably *not* worth optimizing. Even if you could make that function ten times as fast, you would only make the program as a whole 9% faster. (*) Focus on the innermost loops first. These are the instructions that you execute by far most often, so a cycle saved here is worth a great deal more than outside the loop. In your case this would mean that your "character" loop is the most important. Yes, these two suggestions overlap. So they may be contradictory. The profiler will in most cases just tell you that your innermost (non-trivial) loops are the most important, but it can be immensely useful in getting a general overview of how execution time is distributed and in warning you of surprise "hot spots". (*) Try to find "groups" of loop iterations and unroll them. For instance if a line always has a number of characters divisible by 4, you may want to write a loop that does 4 characters per iteration. This may save you 3 out of 4 conditional branches, but it may also make other optimizations more obvious. Example: x = 0; while (x < 4*n) do_something(x++); This could become x = 0; while (x < 4*n) { do_something(x++); do_something(x++); do_something(x++); do_something(x++); } Writing out multiple iterations of a loop is called "unrolling". (*) Minimize memory accesses. Memory is slow, so stay out of it if you can. If you have unrolled the inner loop as suggested above, you may try reading all 4 bytes of an iteration into one 32-bit variable at once and doing the rest of the computation in local variables. If you don't use too many variables, the compiler may be able to squeeze all of it into registers and you've just combined 4 memory accesses into one. Once you've done this, you may discover that there is some clever trick of converting the four bytes in the register at once instead of byte-by-byte. Or maybe it can be done two bytes at a time. This is called "vectorizing" the loop because you treat a vector of values at once instead of a single value at a time. (*) Don't try to be too clever. A good optimizing compiler can be pretty smart too. Look at the following classic loop example: while (*p++ = *q++); This is pretty clever code. It copies a zero-terminated string of bytes from q to p. It looks just about optimal, too. A more naive way to write this would be while (p[x] = q[x]) x++; This is clearly slower and less sophisticated, is it? Actually, no. The compiler's built-in optimizer is there to apply just this kind of cleverness by itself. This not only lets you concentrate on more important matters, it is also able to do things at the machine-language level that would be hard to express just so in the programming languages. It can also be told to optimize for a different processor without forcing you to change your code. Unfortunately there are limits to the cleverness of the optimizer. If we look again at the flashy version, while (*p++ = *q++); How many factors does an optimizer have to take into account here? First off, there are two pointers that change value. Will the original p and q still be used somewhere? Do the new values matter? What if p and q are the same? What if the strings overlap? All these factors can be important in determining how the optimizer can translate this simple line of code. The more factors are unknown to the optimizer, the more it must "play safe" and produce less efficient code. The other variant on the other hand gives the compiler a lot of information: while (p[x] = q[x]) x++; All we have here is a single variable that changes value and whose new value may matter. It is made very clear that the indices always change together. And because p and q don't get altered, it may be easier to determine whether or not the strings overlap. Given this kind of information, the compiler may well decide to generate code that looks like "while (*p++ = *q++);", but it may also produce something better that may not be immediately obvious to a human. (*) Memory is hell. Stay out if you can. There is one thing that the optimizer and your program have in common: They don't like memory. They don't like it because it's so big. Once you start playing with pointers, the optimizer will have a hard time telling what is what and will therefore be very conservative in what it can do to optimize your code. Most optimizations I mention here can easily be performed by your compiler, but that's mostly theory. Once pointers are involved, things quickly get messy and the optimizer can no longer guarantee that it can apply a particular technique. This means that you may have to consider these optimizations while writing your program to get best performance. Note that this is a language-related issue; I'm presently speaking of C. (*) Mind your alignment. Most processors have rules about how variables you access in memory must be aligned for optimal speed. Many processors don't even allow you to access misaligned memory addresses. On the original 68000, the rule was that any word or longword access must be on an even address (ie. divisible by 2). For byte addresses there are no alignment rules. The later processors loosened this rule somewhat: Misaligned memory access is allowed, but it's very slow. Avoid it if you can. The PowerPC has the rule of "natural alignment". It is probably optimal to stick to this rule on the 680x0 processors as well. By this rule, an access is "aligned" if the address is divisible by the size of the access. So reading a byte from memory is always aligned, reading a 16-bit "half-word" is aligned if it's on an even address, a 32-bit "word" is aligned if its address is divisible by 4, and a 64-bit "double-word" is aligned if its address is a multiple of 8. Anything you malloc() or AllocMem() will be properly aligned, so all you need to do is try to stick to reading at aligned accesses. Note that with arrays, X[n] actually means "offset p*n in X", where p is the size of the access. Thus if X is an array of 32-bit longs, any X[1] is still an aligned access because the offset used is 4*1 = 4. Alignment w.r.t. cache lines may also be important in general, but I'll skip it for now. You probably don't need to bother with that. (*) Avoid special cases. Whenever you find yourself writing "if" statements for special values of variables, look for changes that may make this unnecessary. This will often make your algorithm more elegant as well as more efficient. Example: if (x == ERROR_CODE) y = 0; else y = A[x]; This code can be simplified by giving ERROR_CODE its own entry in the array A. Just set this entry of A to zero when you start. Now ERROR_CODE can be treated like any other value of x; this results in one more array access *sometimes* (only when x equals ERROR_CODE) but the net effect is usually beneficial, and may open the door to further optimizations. y = A[x]; /* See? */ A friend and I lost a point once for using this technique in our university Operating Systems course. The virtual memory system we were writing had a "working set" array, and all entries were initially empty. So we defined a special value "WS_EMPTY" which, when used to index yet another array, accessed a harmless unused entry at index -1. This was labelled an "unnecessary hack". Seeing however that we were certainly two of the three highest-rated programmers of the faculty and we both agreed on the technique, they were probably just nitpicking to get around rating our work "perfect". :-) (*) Move code out of loops. Be careful that you don't do anything inside a loop that can be done outside that loop. A simple example would be while (x < y) { n = n * (b - a); x++; } Here the computation "b - a" doesn't ever change value inside the loop. So you would want to transform this to temp = b - a; while (x < y) { n = n * temp; x++; } Note however that in this simple case, most optimizers will be able to do this for you. The optimization is called "code motion". (*) Loop fission If a relatively fat loop does two computations simultaneously, you may be losing performance because its code or its data don't fit well into the processor's cache. Let's look at a loop that adds three vectors A and B to a third, C: for (x=0; x < max; x++) { C[x] += A[x] + B[x]; } Now it might happen that this loop was juuuust a little bigger than your code cache could handle. In that case you would have to read some code from memory to cache on every iteration, slowing down the loop. Or it may happen that two vectors together may just fit into your data cache, but the third one does not. In such cases it may be more efficient to split the work up into two smaller loops: for (x=0; x < max; x++) C[x] += A[x]; for (x=0; x < max; x++) C[x] += B[x]; Although this really gives your processor slightly more work to do overall, it may just be able to run the first loop entirely from cache, then "forget" it and run the second loop entirely from cache. Splitting up a loop like this is called "loop fission"; doing the exact opposite is called "loop fusion". Both may be profitable for different reasons, and are used mostly because they can sometimes give acccess to further optimizations. Advanced compilers should be able to perform these transformations. (*) Loop reversal Your loops will often count from zero to some value n. Sometimes the actual value of the counter isn't important, or the order in which the loop is performed isn't important: x = 0; while (x < max) { C[x] += A[x]; x++; } Since we're just doing this "for every x between 0 and max", the order in which we do it is not important. So what if we changed this to x = max; while (x > 0) { x--; C[x] += A[x]; } Nothing would really change. The effect would still be the same, unless I've made a mistake here. That's a very real risk with this kind of transformation, by the way. So anyway, what would we gain by this change? The answer is that most processors, including the 68000 and the PowerPC, have built-in features to detect if the result of the last operation was zero. When the loop ends at zero, this facility can be used to check whether the loop's termination condition is satisfied without explicitly comparing to max every time. This is really a special case of "code motion" because we've taken the entire "max" thing out of the loop so it's executed only once, while it was executed max times in the original version. A good compiler will be able to perform this optimization for you, but only if it can ensure that it is safe to do so. Phew, quite a list (what, it's morning already!?) but I hope it's informative. Guess I'll stop now, or I could go on forever... Why can't I just recommend a good book like everybody else? -- ========================================================================== # Jeroen T. Vermeulen \\"How are we doing?"// Yes, we use Amigas # #--- jtv@xs4all.nl ---\\"Same as always."//-- ... --# #jvermeul@wi.leidenuniv.nl \\"That bad huh?"// Got a problem with that? # WWW, or "World-Wide Web" in full; pronounce as "sextuple-U"