Summary
By using the O(n) notation to describe the behavior of an algorithm in relation to the number of elements of data it needs to handle, a lot can be said about algorithm efficiency even before it has been implemented. Algorithms that have already been implemented can easily be pitted against each other using a timing function as is described in this chapter. When performing this second kind of speed tests, however, you should realize that you are effectively timing system behavior while your test is running. There are several things you can do to minimize the influence of system overhead during testing. To minimize the side effects caused by other processes and OS administrative tasks you can
Run as few other processes on the system as possible
Increase the priority of the testing process
Run on a clean (rebooted) system
Perform several test runs and average only least contaminated results
To minimize cache misses and page faults while your software is running, you can use several optimization strategies:
Group data and functions according to frequency of use
Group data and functions which are related to each other
Access and store data sequentially
Perform intelligent prefetching
Lock frequently used data and functions
Adjust the working set of a process
Take specific system information into account
How fast data and instruction access can be, is dependant on where it must come from. Figure 5.3 provides an overview.
Figure 5.3. Overview of locality.
This diagram shows the different places from which the CPU can get data and instructions. This diagram orders the places by proximity to the CPU, where the registers are closest to the CPU and the external storage is furthest away. In general it can be said that the closer a storage is to the CPU, the smaller and faster it is.