Thanks to advances in computer technology, performance is no longer a concern for the majority of programs. However, many applications exist, particularly in the context of scientific computing, where performance is still important. In such cases, programs can be optimized to run faster by exploiting knowledge about the relative performance of different approaches.
This chapter examines the most important techniques for optimizing F# programs. The overall approach to whole program optimization is to perform each of the following steps in order:
Profile the program compiled with automated optimizations and running on representative input.
Of the sequential computations performed by the program, identify the most time-consuming one from the profile.
Calculate the (possibly asymptotic) algorithmic complexity of this bottleneck in terms of suitable primitive operations.
If possible, manually alter the program such that the algorithm used by the bottleneck has a lower asymptotic complexity and repeat from step 1.
If possible, modify the bottleneck algorithm such that it accesses its data structures less randomly to increase cache coherence.
Perform low-level optimizations on the expressions in the bottleneck.
The mathematical concept of asympotic algorithmic complexity (covered in section 3.1) is an excellent way to choose a data structure when inputs will be large, i.e. when the asymptotic approximation is most accurate. However, many programs perform a large number ...