CS:APP--Chapter05 : optimizing program performance (part 1)

标签（空格分隔）： CS:APP

prologue

The primative object of a programmer is make it run correctly even fast. Not only do we ensure others can make sense of it, but also others can understand the code during review and when some modifications are needed.

Several types of program optimization are necessary :

1. select an appropriate set of data structure and algorithm
2. write code in a way that we assist compiler to turn source code into an efficient executable code
3. parallelism ( detailen it in chapter 12 )

This chapter focus on one ultimate goal - how to make code run faster via several different types of program optimization. Eliminating the unnecessary work that has nothing to do with processor and executing the divided work in parallel that highlt depend on the architecture of processor make our code run faster. For increasing the degree of parallelism with which we execute our code, more information will be discussed in chapter 12.

A good way of gain an better understanding of optimization is looking into the assembly language with the optimzation level Og and O1 and even higher.

1. capabilities and limtation of optimizing compiler

Here, compiler with a growing ability of optimization would not optimize code in a aggresive and radical way due to its constraints.

1.1 memory aliasing

In many cases, the probability of referring to a identical memory makes compiler runs with a safe optimization.

A example is proposed on page 535 that adding two numbers twice is for a factor of 4 to one variable, which runs same as 4 times it with less operations at assembly-language level. But compile cannot optimize first directly to the second case, because compiler doesn't ensure whether or not they refer to the identical memory leading to the erroneous result.

1.2 function calls

another optimization block here is optimizing multiple calls of one function to less times of call for the function may leading to side effect here. If there is a global variable, it must be modified several times to change program behavior.

In this case, compile assume the worst case and just leaves the function calss intact(unchanged).

Even though many types of optimization exploit program to its full extent, the constraints of compilers limits the set of optimization.

2. expressing program performance

Like the metric throughout and latency in last chapter, a metric "cycles per element" is introduced here, abbreviated by CPM and Especially for loop behavior.

The time required by the precudure is characterized as a constant plus a factor proportional to the number of elements processed.

-> least squares fit to find the expression for example: 60+35n