# WCET Analysis - Fibonacci recursion, structure matters

## The natural way

Here is a recursion function, generating Fibonacci number.

```
int fib (int z) {
int r;
if (z == 0)
r = 0;
else if (z == 1)
r = 1;
else
r = fib(z-1) + fib(z-2);
return r;
}
```

The first two items of the Fib are 0 and 1. So it is very nature to write the code like this. But it is under-optimized, in a "Fibonacci-way".

## WCET Analysis

Now we do the **WCET(worst case execution time)** analysis, assuming:

- Each declaration or assignment statement costs 1 time unit
- Each compare statement costs 1 time unit
- Each return statement costs 1 time unit
- Each addition or subtraction operation costs 4 time units.
- A function call costs 2 time units plus WCET for the function in question.
- All other language constructs can be assumed to take 0 time units to execute.

Let's make $f(z)$ to be the WCET of the `fib(z)`

, so $f(0)$ is the WCET of the `fib(0)`

function execution. For different `z`

value, the code being executed is different, with different length, and different WCET.

Now divide the code snippet to 3 parts, and analyze them seperately:

```
// path a (z=0): 4
int fib (int z) {
int r; // declaration (1)
if (z == 0) // compare (1)
r = 0; // assignment (1)
return r; // return (1)
}
```

For path a, the WCET of `fib(0)`

is 4, that is $f(0)=4$

```
// path b (z=1): 5
int fib (int z) {
int r; // declaration (1)
if (z == 0) // compare (1)
;
else if (z == 1) // compare (1)
;
else
r = 1; // assignment (1)
return r; // return (1)
}
```

For path b, $f(1)=5$ because we have **one more comparison** executed with the if-else statement.

```
// path c (z>=2): 21+f(z-1)+f(z-2)
int fib (int z) {
int r; // declaration (1)
if (z == 0) // compare (1)
;
else if (z == 1) // compare (1)
;
else
r = fib(z-1) + fib(z-2); // 3*4+2*2+f(z-1)+f(z-2)
return r; // return (1)
}
```

For `r = fib(z-1) + fib(z-2);`

it takes 3 ALUs(add/sub), 2 function calls, 1 assignment, and it contains the code of other 2 fib calling. So $f(z)=21+f(z-1)+f(z-2)$ for path c. And you may noticed that, we need to do **one more comparison**, same as path b.

For a if-else code snippet, the structure/placement matters, **especially it will be called recursively**.

```
if (cond1)
func1(); // execute after cond1
else if (cond2)
func1(); // execute after cond1, cond2
else if (cond3)
func1(); // execute after cond1, cond2, cond3
else
func1(); // execute after cond1, cond2, cond3
```

Let me use some real numbers, if we want to compute the WCET for `fib(5)`

, we'll have:

$$

\begin{align*}

f(2)=f(1)+f(0)+c=a+b+c \\

f(3)=f(2)+f(1)+c=a+2b+2c \\

f(4)=f(3)+f(2)+c=2a+3b+4c \\

f(5)=f(4)+f(3)+c=3a+5b+7c \\

\end{align*}

$$

The WCET of `fib(5)`

is composed of some path a, more path b, much more path c. And try to look at it vertically, you may understand why I said, this is **under-optimized in a Fibonacci-way**.

The weight of path A grows in a Fibonacci-way; the weight of path B grows in a same fashion but one step ahead (one step in Fibonacci...). And for path C? Also grows in a Fibonacci fashion, but every time 1 is added to the weight (for the execution of path c itself).

For this natural version code, the WCET of `fib(5)`

is $3\times 4+5\times 5+7\times 21=184$

## Better Structure, nature way for the machine

```
int fib (int z) {
int r;
if (z > 1)
r = fib(z-1) + fib(z-2);
else if (z == 1)
r = 1;
else
r = 0;
return r;
}
```

If we switch the position of path C with path A, it will save one comparison for path C and add one to path A, which makes WCET of the new fib function is $3\times 5 + 5\times 5 + 7\times 20=180$. The difference is 4 time units of comparison.

For a computation of `fib(10)`

, the difference will be 54 time units.

For a computation of `fib(20)`

, the difference will be 6764 time units...