optimization is a decision making method:

- identify a performance measure and a space of possible strategies to try
- run a bunch of simulations given a particular strategy, and measuring the performance
- try strategies with the goal of maximizing the performance measured

Importantly: model is not used to guide the search, it is only used to run simulations to evaluate performance.

## Disadvantage (or advantage)

does **not** take a advantage of the structure of the problem

## Optimization Steps

- if you are doing something infrequently, make sure the simplest code
- If you are doing something very often, and/or on big inputs, make the primary algorithm big-o cost reasonable
- Make GCC Work!
- Optimize explicitly as last resort.

## Main Optimization Techniques

- constant folding
- sub-expression elimination
- dead code elimination
- “strength reduction”
- code motion
- tail recursion
- loop unrolling

### constant folding

There are many constants which happens during code writing. Therefore, for functions that operate on constant values, they will be folded in and the math done ahead-of-time during compilation.

### common sub-instruction elimination

If you have the same sub-expression over and over again, we compute it ahead of time and use that result in multiple places.

### dead code elimination

Code which doesn’t do anything of interest. This maybe subtle:

```
if (param == 0) {
return 0;
} else {
return param;
}
```

this is (mostly) dead code. It all return `0`

.

### strength reduction

Multiply can be rounded to a bit shift, and mod can be changed to an AND operation.

```
7 * a == 8*a - a
```

vs So you can left shift and then subtract, which is dramatically easier.

We can even do this with:

```
b / 3
```

which can be converted to

```
(b*3) / 10
```

which is much easier because its a multiplication

### code motion

if there is a common sub-exppression, it can be pull out of loops

```
for (size_t i = 0; i < strlen(s); i++) {
arr[i] = s[i];
}
```

the `strlen`

call can be and will be pulled out.

### tail recursion

turn a recursive call into a while loop to save stack frame management time

### loop unrolling

A loop can be “factored out”:

```
for (int i=0; i<=n; i++) {
sum += arr[i];
}
```

can turn into

```
for (int i=0; i<=n-4; i+=4) {
sum += arr[i];
sum += arr[i+1];
sum += arr[i+2];
sum += arr[i+3];
} // handle ending cases
```

Why don’t we unroll all the way? We don’t know what \(n\) is.