-Michael Abrash

So without further ado, I present to you Programming Optimization ...

where

What is typically seen is that Total time is usually dominated by one or very few of the time of task_i terms because either those tasks are where there is the most work to do or where their algorithms are complicated enough for them to have a low rate of execution. This effect tends to be recursive in the sense of breaking tasks down into sub-tasks, which has lead to the creation and adoption of line-by-line based execution profilers.

What one should also notice is that if the strategy for improving the performance of code is to improve the efficiency of the code for one particular task_i we can see that it's possible to reach a point of diminishing returns, because each term cannot go below 0 in its overall contribution to the time consumption. So an optimization exercise of this sort for any particular task need not proceed past the point where the total time taken for any task_i is significantly below the average. This usually means that effort is better spent in switching to another task_i to optimize.

This, of course, is fine and a credible way of proceeding, however, by itself leaves out algorithm analysis, as well as the possibility of trying different task breakdowns. The classic example here is that tweaking bubble sort is not going to be as useful as switching to a better algorithm, such as quicksort or heapsort if you are sorting a lot of data.

One also has to be careful about what actually is being measured. This is epitomized by the story that if the Unix kernel typically spends most of its time in the idle loop, that doesn't mean there will be any useful advantage in optimizing it.

• Simple mathematical analysis. Calculate the approximate running time of your algorithm (i.e., calculate its "O") taking all bottlenecks into account. Is it optimal? Can you prove it? Can you justify up your algorithmic design with theoretically known results?

• Understanding technological performance considerations. Even at high levels, you need to have a rough understanding of what goes fast, what doesn't and why. Examples follow:

  (1) Data bandwidth performance for PC devices are roughly ordered (slowest to fastest): user input device, tape drives, network, CDROM, hard drive, memory mapped local BUS device (graphics memory), uncached main memory, external cached main memory, local/CPU cached memory, local variables (registers.)

  The usual approaches to improve the performance of data bandwidth is to use a faster device to cache the data for slower devices to allow pre-emption of slower device access if the access is redundant. For example, to know where you are pointing your mouse, your mouse interface is likely to just look up a pair of coordinates saved to memory, rather than poll the mouse directly every time. This general idea is probably what inspired Terje Mathisen (a well-known programming optimization guru) to say: "All programming is an exercise in caching."

  (2) Arithmetic operation performance is ordered roughly: transcendental  functions, square root, modulo, divide, multiply, add/subtract/mutiply by  power of 2/divide by power of 2/modulo by a power of 2.

  Nearly all programs have to do some rudimentary calculations of some kind. Simplifying your formulae to use faster functions is a very typical optimization opportunity. The integer versus floating point differences are usually very platform dependent, but in modern microprocessors, the performance of each is usually quite similar. Knowing how data bandwidth and calculations perform relative to each other is also very important. For example, using tables to avoid certain recalculations is often a good idea, but you have to look carefully at the data speed versus recalculation; large tables will typically be uncached and may perform even slower than a CPU divide.

  (3) Control flow is ordered roughly by: indirect function calls, switch() statements, fixed function calls, if() statements, while() statements.

  But a larger additional concern with modern pipelined processors is the "predictability" of a control transfer. Modern processors essentially guess the direction of a control transfer, and back out if and when they realize that they are wrong (throwing away what incorrect work they have done.) Incorrect predictions are very costly. As such one must be aware of arithmetically equivalent ways of performing conditional computation.

• Localized tricks/massaging.  Are your results computed by complex calculations at each stage, when an incremental approach can produce results faster, or vice versa? Example: What is the fastest way to compute the nth Fibonacci numbers? What is the fastest way to compute the first n Fibonacci numbers? In the former case, there is a simple formula involving an exponent calculation.  In the latter case, the recursive definition allows for an iterative approach which only requires an addition and variable shuffling at each stage.

• Parallelism.  Although the typical programming model is a single threaded one, sometimes the width of the data stream is a lot smaller than the naturally supported data types. More concretely, if your algorithm operates on bytes you may be able to operate on 2, 4 or 8 of them simultaneously by using word based instructions that are  supported by your CPU. Alternatively, does your target system have  multiple execution units?  For example, do you have a graphics coprocessor which can draw in parallel to ordinary CPU computation and do you have an API for it?

• Taking a global view. At some stage, you should take a step back and look at the entire flow of your algorithms. Are you using a general architecture to solve a problem that could be more efficiently dealt with a specific architecture? For that matter, does your procedural breakdown allow for easy analysis of performance in the first place (see profiling below)?

        /* Set our cap according to some variable condition */

        lpDRV->dpCAPS |= x;

        ...

        /* This is an important inner loop */

        for(i=0; i<n; i++)
        {
            if( (lpDRV->dpCAPS) & CLIPPING )
            {
                DoOneThing(i);
            }
            else if( (lpDRV->dpCAPS) & ALREADYCULLED )
            {
                DoSomethingElse(i);
            }
            else
            {
                DoYetAnotherThing(i);
            }
        }

        /* Set our cap according to some variable condition */

        lpDRV->dpCAPS |= x;

        ...

        /* This is an important inner loop */

        if( (lpDRV->dpCAPS) & CLIPPING )
        {
            for(i=0; i<n; i++)
            {
                DoOneThing(i);
            }
        }
        else if( (lpDRV->dpCAPS) & ALREADYCULLED )
        {
            for(i=0; i<n; i++)
            {
                DoSomethingElse(i);
            }
        }
        else
        {
            for(i=0; i<n; i++)
            {
                DoYetAnotherThing(i);
            }
        }

When all algorithmic optimization approaches have been tried and you are still an order of magnitude away from your target performance you may find that you have no choice but to analyze the situation at the lowest possible level. 3 useful resources at this point are (1) Paul Hsieh's x86 Assembly language Page (2) The Zen of Code Optimization (by Michael Abrash) and (3) an HTML page entitled Pentium Optimizations by Agner Fog

• Profiling. One way or another, you have to *know* where your performance bottlenecks are. Good compilers will have comprehensive tools for measuring performance analysis which makes this job easier. But even with the best tools, care is often required in analyzing profiling information when algorithms become complex. For example, most UNIX kernels will spend the vast majority of their processor cycles in the "idle-loop". Clearly, no amount of optimization of the "idle-loop" will have any impact on performance.

• Disassembling. When writing in high-level languages there can be huge complexity differences coming from subtle source code changes. While experience can help you out a lot in this area, generally the only way to be sure is to actually produce an assembly listings of your object code. Typically one will see things like: multiplications for address generations when a shift could do just as well if only the array limits were a power of 2; complex "for" loops may generate an extra jump to the condition evaluator to conserve on code size, when a do .. while loop is just as effective but wouldn't generate the extra jump. One can also see the impact of declaring variables or functions as "static". (With the WATCOM C/C++ compiler I've noticed that functions declarations will only "inline" if they are static, but that local variables use shorter instructions if they are not static.)

• Using CPU/platform specific features(even in cross-platform situations.) How you deal with this is obviously CPU dependent, however here are some things to watch out for: Burst write's, memory access constraints (cache coherency), branch prediction, pipelining, counting down rather than up, side-effects, multiple execution units. With flexible optimizing compilers, many of these effects can be achieved by merely "massaging" your high level source code. The theory that you can inline assembly to make any routine faster is not always true of the better, modern optimizing compilers (C compilers anyway.)

    float x[MAX_ENTRIES];

        ...

        if( x[i] ) {

            ....

        }

    float x[MAX_ENTRIES];
    long temp;

        ...

        temp = *((long *)&(x[i]));
        if( temp + temp ) {

            ....

        }

• Ever improving hardware, makes software optimization unimportant

  (1) If you don't optimize your code, but your competition does, then they end up with a faster solution, independent of hardware improvements. (2) Hardware performance improvements expectations almost always exceeds reality. PC disk performance has remained relatively stable for  the past 5 years, and memory technology has been driven more by quantity  than performance. (3) Hardware improvements often only target optimal  software solutions.

• Using tables always beats recalculating

  This is not always true. Remember that in recalculating, you have the potential of using parallelism, and incremental calculation with the right formulations. Tables that are too large will not fit in your cache and hence may be very slow to access. If your table is multi-indexed, then there is a hidden multiply which can be costly if it is not a power of 2. On a fast Pentium, an uncached memory access can take more time than a divide.

• My C compiler can't be much worse than 10% off of optimal assembly on my code

  This is something some people can only be convinced of by experience. The cogitations and bizarre operator fumbling that you can do in the C language convinces many that they are there for the purposes of optimization.  Modern C compilers usually unify C's complex operators,  semantics and syntax into much a simpler format before proceeding to the optimization and code generation phase.  ANSI C only addresses a  subset of your computers' capabilities and is in of itself too  generic in specification to take advantage of all of your processor  nuances.  Remember ANSI C does not know the difference between cached and uncached memory.  Also many arithmetic redundancies allow for usage of processor features that C compilers to date have not yet mastered (for e.g.., there are clever tricks for host based texture mapping if the stride of the source texture is a power of two, or  in particular 256 on an x86.)  

  Unfortunately, many research based, and work station programmers as well as professors of higher education, who might even know better, have taken it upon themselves to impress upon newbie programmers to avoid assembly language programming at all costs; all in the name of maintainability and portability. A blatant example of this can be seen in the POV-ray FAQ, which outright recommends that there is no benefit to be had in attempting assembly language optimizations. (I wouldn't be surprised, if you couldn't simply low level optimize POV-Ray, change the interface and turn around and sell the darn thing!) The fact is, low-level optimization has its place and only should be passed by if there is a conflicting requirement (like portability), there is no need, or there are no resources to do it. For more, see High level vs. Low level below.

• Using C compilers make it impossible to optimize code for performance

  Most C compilers come with an "inline assembly" feature that allows you to roll your own opcodes. Most also come with linkers that allow you to link completely external assembly modules. Of course not all C compilers are created equal and the effects of mixing C and assembly will vary depending on the compiler implementation. (Example: WATCOM and DJGPP mix ASM in very smoothly, whereas VC++ and Borland do not.)

  Modern C compilers will do a reasonable job if they are given assistance. I usually try to break my inner loops down into the most basic expressions possible, that are as analogous to low level assembly as possible, without resorting to inline assembly whenever possible. Again your results will vary from compiler to compiler. (The WATCOM C/C++ compiler can be helped significantly with this sort of approach.)

• Compiled bitmaps are the fastest way to plot graphics

  This method replaces each bitmap graphics source data word with a specific CPU instruction to store it straight to graphics memory. The problem with it is, that it chews up large amounts of instruction cache space. This is to be compared against a data copying routine which needs to read the source data from memory (and typically caches it.) Both use lots of cache space, but the compiled bitmap method uses far more, since it must encode a CPU store command for each source data word.

  Furthermore, CPU performance is usually more sensitive to instruction cache performance than it is to data cache performance. The reason is that data manipulations and resource contentions can be managed by write buffers and modern CPU's ability to execute instructions out of order. With instruction data, if they are not in the cache, they must be prefetched, paying non-overlapping sequential penalties whenever the pre-fetch buffer runs out.

  On older x86's this method worked well because the instruction prefetch penalties were paid on a per instruction basis regardless (there was no cache to put them into!) But starting with the 486, this was no longer a sensible solution since short loops paid no instruction prefetch penalties, which rendered the compiled bitmap technique completely useless.

• Using the register keyword in strategic places C will improve performance substantially

  This keyword is a complete placebo in most modern C compilers. Keep in mind that K&R and the ANSI committee did not design the C language to embody all of the performance characteristics of your CPU. The bulk of the burden of optimizing your C source, is in the hands of your compiler's optimizer which will typically have its own ideas about what variables should go where. If you are interested in the level optimizations available by hand assigning register variable aliasing, you are better off going to hand rolled assembly, rather than relying on these kinds of language features.

  (Addenda: The only real purpose of "register" is to assert to the compiler that an auto variable is never addressed and therefore can never alias with any pointer. While this might be able to assist the compiler's optimizer, a good optimizing compiler is more than capable of deducing this feature of a local by itself.)

• Globals are faster than locals

  Most modern C compilers will alias local variables to your CPUs register's or SRAM. Furthermore, if all variables in a given scope are local, then an optimizing compiler, can forgo maintaining the variable outside the scope, and therefore has more simplification optimization opportunities than with globals. So, in fact, you should find the opposite tends to be true more of the time.

• Using smaller data types is faster than larger ones

  The original reason int was put into the C language was so that the fastest data type on each platform remained abstracted away from the programmer himself. On modern 32 and 64 bit platforms, small data types like chars and shorts actually incur extra overhead when converting to and from the default machine word sized data type.

  On the other hand, one must be wary of cache usage. Using packed data (and in this vein, small structure fields) for large data objects may pay larger dividends in global cache coherence, than local algorithmic optimization issues.

• Fixed point always beats floating point for performance

  Most modern CPUs have a separate floating point unit that will execute in parallel to the main/integer unit. This means that you can simultaneously do floating point and integer calculations. While many processors can perform high throughput multiplies (the Pentium being an exception) general divides and modulos that are not a power of two are slow to execute (from Cray Super Computers right on down to 6502's; nobody has a really good algorithm to perform them in general.) Parallelism (via the usually undertaxed concurrent floating point units in many processors) and redundancy are often better bets than going to fixed point.

  On the redundancy front, if you are dividing or calculating a modulo and if you know the divisor is fixed, or one of only a few possible fixed values there are ways to exploit fast integer (aka fixed point) methods.

  On the Pentium, the biggest concern is moving data around to and from the FPU and the main integer unit. Optimizing FPU usage takes careful programming; no x86 compiler I have see does a particularly good job of this. To exploit maximum optimization potential, you are likely going to have to go to assembly language. As a rule of thumb: if you need many simple results as fast as possible, use fixed point, if you need only a few complicated results use floating point. See Pentium Optimizations by Agner Fog for more information.

  With the introduction of AMD's 3DNOW! SIMD floating point technology, these older rules about floating point performance have been turned upside down. Approximate (14/15 bits) divides, or reciprocal square roots can be computed in a single clock. Two multiplies and two adds can also be computed per clock allowing better than 1 gigaflop of peak performance. We are now at a point in the industry where floating point performance is truly matching the integer performance. With such technologies the right answer is to use the data type format that most closely matches its intended meaning.

• Performance optimization is achieved primarily by counting the cycles of the assembly code

  You usually get a lot more mileage out of optimizing your code at a high level (not meaning to imply that you need a HLL to do this) first. At the very least, changes to the high level source will tend to affect more target code at one time than what you will be able to do in assembly language with the same effort. In more extreme cases, such as exponential (usually highly recursive) algorithms, thorough hand optimization often buys you significantly less than good up front design.

  The cycle counts given in processor instruction lists are usually misleading about the real cycle expenditure of your code.  They  usually ignore the wait states required to access memory, or other devices (that usually have their own independent clocks.)  They are also typically misleading with regards to hidden side effects of  branch targets, pipelining and parallelism.

  The Pentium can take up to 39 clocks to perform a floating point divide. However, the instruction can be issued in one clock, 39 clocks of integer calculations can then be done in parallel and the result of the divide then retrieved in another clock. About 41 clocks in total, but only two of those clocks are actually spent issuing and retrieving the results for the divide itself.
  
  In fact, all modern x86 processors have internal clock timers than can be used to assist in getting real timing results and Intel recommends that programmers use them to get accurate timing results. (See the RDTSC instruction as documented in Intel's processor architectural manuals.)

• Assembly programming is only done in DOS, there's no need under Windows

  The benefits of assembly over C are the same under Windows or Linux as they are under DOS. This delusion doesn't have anything close to logic backing it up, and therefore doesn't deserve much comment.

  See Iczelion's Win32 Assembly Home Page if you don't believe me.

• Complete optimization is impossible; there is always room left to optimize, thus it is pointless to sustain too much effort in pursuit of it

  This is not a technical belief -- its a marketing one. Its one often heard from the folks that live in Redmond, WA. Even to the degree that it is true (in a very large software project, for example) it ignores the fact that optimal performance can be approached asymptotically with a finite, and usually acceptable amount of effort. Using proper profiling and benchmarking one can iteratively grab the "low hanging fruit" which will get most of the available performance.

  Absolutely optimization is also not a completely unattainable goal. Understanding the nature of your task, and bounding it by its input/output performance and the best possible algorithm in the middle in many cases is not an undoable task.

  For example, to read a file from disk, sort its contents and write the result back out, ought to be a very doable performance optimization exercise. (The input/output performance is known, and the algorithm in the middle is approachable by considering the nature of the input and going with a standard algorithm such as heap sort or radix sort.)

  Of course, the degree of analysis that you can apply to your specific problem will vary greatly depending on its nature. My main objection to this misconception is just that it cannot be applied globally.

Chris Lomont wrote:

: Where do you get your ideas about experienced coders? On RISC chips
: and many of the pipelined, superscalar CPU's a good compiler beats out
: most ASM programmers due to the complex issues for instruction
: pariing ...

Most assembly programmers are neither knowledgable or good, but those who
are knowledgable and good have little trouble beating compilers. Even on
true RISC CPUs. A friend had an algorithm reimplemented, I'll redundantly
stress that the algorithm was not changed, in PowerPC assembly by an Apple
engineer. The result was a pixel doubling blitter that ran 3 to 5 times
faster. I've personally seen a graphics intensive game get 5 more frames
per second (25, up from 20, on a P5-100) by replacing low level graphics
code compiled by VC++ 5 with handwritten assembly. Again, same algorithm,
different implementation.

: ... Your hand crafted 486 asm will probably run dog slow on later
: processors with different pairing rules, while a simple recompile on a
: decent PII compiler will make that C code surpass you old asm ...

You overstate the risk. Coincidentally I recently recompiled some code
with VC++ 5 optimizing for both Pentium and PentiumPro. Comparing some 3D
point transformations coded in C and Pentium assembly, the assembly code
ran 30% faster than the Pentium optimized C code on a P5-100 and 12%
faster than the PentiumPro optimized C code on a PII-300. While the older
architecture's assembly code had less of an improvement on the newer
architecture, it was still faster, and using such old code would not be a
liability as you suggest. Perhaps when spanning more than two architecural
generations, as in your 486 to PentiumPro example, there would be such a
problem. But given the lifespan of typical products, especially games,
that is not worth worrying about.

BTW, I'm not advocating that everything should be done in assembly. Just
that claiming C compilers are hard to beat is naive, and that assembly is
often a good solution at times.

For more, see Randall Hyde's Great Debate page.