Optimizing Code for Speed

From Wikibooks, the open-content textbooks collection

Contents 1 Other Resources 2 Introduction 2.1 In which programs is optimization required? 2.2 When to optimize? 2.3 When not to optimize? 2.3.1 Optimization vs. Modularity and Readability 3 Order of Complexity Optimizations 3.1 What is order of complexity?

[edit] Other Resources

• Optimizing Code for Speed/Outline

[edit] Introduction

Optimization of code is the term that was applied to a process in which a code is tuned to be better in some respects: either speed, memory consumption, Input/Output (disk read and writes or network reads and writes), etc. In Mathematics, Optimization means a process in which one finds the values with the best performance. In Computers where programs are very complex, usually optimizing for speed in the mathematical sense is impossible. Instead the term has come to mean just advancing in the direction of better performance in one or more respects.

This document will focus on optimizing code to run faster. However, as you will see later, doing this may involve having to optimize the in a different aspect. Furthermore, often when programmers are trying to optimize one aspect of a program, they are doing so in order to increase speed.

[edit] In which programs is optimization required?

There are several classes of programs in which optimization is required. One such class are real time programs. Despite common mis-conception, these are not necessarily programs that need to be very fast. Instead real time programs are programs that must respond to certain events within a certain time limit that was dedicated to the event. So for example, if the user presses a keyboard key while inside a word processor window, it should displays the character relatively promptly. A 5 seconds delay will be unacceptable and as such a word processor is a kind of application that has some real-time constraints.

Some parts of real-time systems may need optimization. However, once the time falls below the required delay, no other optimization is necessary. (At least not until testing proves it is again exceeding the limit.)

Other programs that require optimization are programs that cannot be fast enough. Examples for such programs are Artificial Intelligence programs, games, multimedia programs, virtual machines and interpreters for programming languages, or any type of publicly available library or module whose use "in the wild" may necessitate it to be very fast.

And naturally another type of programs are programs that are too slow or perceived to be too slow. While some problem domains cause the program that solves them to be very slow, but that is usually not the case. Such programs should be optimized so they will run faster.

[edit] When to optimize?

The rule of the thumb is that one should optimize if the program is not fast enough compared to the desired speed. A common misconception is that if a program is not fast enough now, it will run faster as hardware gets faster. However that is not always the case.

If your program is slow, it is usually because the code is not optimized (such as due to the fact it uses sub-optimal algorithms). While better hardware will usually improve performance, it does not guarantee a noticeable speed increase. Furthermore the progress in hardware speed has allowed programmers to write less wasteful code (see Paul Graham's "The Hundred Years Language" essay), but some programs are still excessively slow.

When writing a program on a modern hardware, one should make it fast enough already. Some people have claimed that we have already reached the end of Moore's First Law in regards to uni-core processors, and we cannot expect single-processed single-threaded program to run faster. In any case, even if the program runs well on a high-end platform, it may be needed to run on older hardware.

We've all seen the fact that while computers got faster, software has often become slower to run unless the hardware is upgraded. The so-called "Gates' Law" claims that commercial programs decrease in speed by half every 18 months, due to various reasons. It is well known that the various versions of the DOS operating system ran adequately on a PC XT's and 286's and that a Intel 386 was a "lean and mean DOS machine" as a certain journalist claimed back then. On the other hand, Microsoft Windows 3.0 and Microsoft Windows 3.1 already required a fast 486 computer to be ran comfortably, while Windows 95 was barely usable there and needed a Pentium computer. Windows XP already ran slowly on a Pentium machine and required a high end Pentium III or Pentium 4 computer. Windows Vista will require even more hardware resources than Windows XP.

Now, while software simulations that run directly against the CPU and memory (and possibly hard-disk) are still running much faster than before, the responsiveness of the system itself does not seem to improve much.

[edit] When not to optimize?

One should not optimize when the program in question runs fast enough. However, if it also has to run adequately on slower hardware, it might need to be optimized further based on such requirements.

[edit] Optimization vs. Modularity and Readability

[edit] Order of Complexity Optimizations

[edit] What is order of complexity?

Generally, an algorithm has an asymptotic complexity. Assuming the input is of size N, we can say that the algorithm will finish at O(N), O(N^2), O(N^3), O(N*log(N)) etc. This means that it is a certain mathematical expression of the size of the input, and the algorithm finishes between two factors of it.