---
title: "Optimisation"
author: "Richèl Bilderbeek"
format: revealjs
editor: visual
from: markdown+emoji
bibliography: optimisation_lecture.bib
csl: vancouver.csl
css: styles.css
slide-number: true
number-sections: true
---

# The Big Picture ![](CC-BY-NC-SA.png)

<https://github.com/UPPMAX/programming_formalisms/blob/main/tdd/tdd_lecture/tdd_lecture.qmd>

![](programming_formalism_logo_25_cropped.png)

## Breaks

Please take breaks: these are important for learning.

It can sometimes be painful/annoying when there is a break in the middle of the exercise.

Ideally, do something boring @newport2016deep!

## Schedule

| From  | To    | What                                                    |
|-------|-------|---------------------------------------------------------|
| 12:00 | 13:00 | Lunch                                                   |
| 13:00 | 13:45 | Discuss Retrospect, misconceptions, get a speed profile |
| 13:45 | 14:00 | Break                                                   |
| 14:00 | 14:45 | Get a speed profile, ?case study                        |
| 14:45 | 15:00 | Break                                                   |
| 15:00 | 15:30 | Course recap, Open discussion                           |
| 15:30 | 16:00 | Reflection                                              |

# Retrospect

-   [ ] Discuss

# Optimisation

<https://github.com/UPPMAX/programming_formalisms/blob/main/optimisation/optimisation_lecture/optimisation_lecture.qmd>

![](programming_formalism_course.png)

# Why optimization?

To improve the runtime speed (or memory use) of a program

![](captain_obvious.png)

> [Captain Obvious](https://allthetropes.org/wiki/File:Captainobvious02_778_7124.png)

# Misconceptions

Q: What would be **bad advice** to improve the run-time speed of an algorithm?

Fill in in the shared document!

(if you dare and have time: add good advice too)

## Bad advice 1

'Use C or C++ or Rust'

. . .

Variance within programming languages is bigger than variance between languages (adapted fig 2, from @prechelt2000empirical)

![](prechelt_fig_2_sub.png)

## Bad advice 2

'No for loops', 'unroll for-loops', any other micro-optimization.

. . .

Premature optimization is the root of all evil. It likely has no measurable effect.

## Bad advice 2

> We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%.
>
> Donald Knuth

![Donald Knuth](donald_knuth.jpg)

> Source: [Wikipedia](https://upload.wikimedia.org/wikipedia/commons/4/4f/KnuthAtOpenContentAlliance.jpg)

## Bad advice 3

'Always parallelize'

. . .

-   Maximum gain depends on proportion spent in the parallelized part @rodgers1985improvements
-   Overhead is underestimated
-   Hard to debug

## Bad advice 3

![https://en.wikipedia.org/wiki/File:AmdahlsLaw.svg#file](amdahls_law.png)

## Bad advice 4

'Optimize the function where you feel the performance problem is'

Developers -also very experienced developers- are known to have a bad intuition @sutter2004cpp

Instead, from @chellappa2008write:

1.  finding code program spends most time in
2.  measure timing of that code
3.  analyze the measured runtimes

## Bad advice 5

'Optimize each function'

-   The 90-10 rule: 90% of all time, the program spends in 10% of the code.
-   Your working hours can be spent once

# Proper method

## Problem

Q: When to optimize for speed?

. . .

A:

-   [C++ Core Guidelines: Per.1: Don't optimize without reason](https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines#Rper-reason)
-   [C++ Core Guidelines: Per.2: Don't optimize prematurely](https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines#per2-dont-optimize-prematurely)
-   [C++ Core Guidelines: Per.3: Don't optimize something that's not performance critical](https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines#per3-dont-optimize-something-thats-not-performance-critical)

## Problem

Q: How to improve the run-time speed of an algorithm?

. . .

> Make it work, make it right, make it fast.
>
> Kent Beck

A (simplified):

1.  Measure (hard to do @bartz2020benchmarking)
2.  Think
3.  Change code
4.  Measure again

## Problem

Q: How to improve the run-time speed of an algorithm?

A (simplified):

1.  Measure big-O
2.  Measure speed profile
3.  Think
4.  Change code
5.  Measure again

## Measurement 1: big-O

How your (combination of) algorithms scales with more complex input.

-   Counting the words in a book: O(n)
-   Looking up a word in a dictionary: O(log2(n))

:warning: Do measure big-O in release mode!

## Your algorithm

![](many_scatter_plots.png)

## Example

```{r}
create_big_o_example <- function(n = seq(0, 100)) {
  t_wide <- tibble::tibble(n = n)
  t_wide$a <- 10 + log10(t_wide$n + 0.1)
  t_wide$b <- t_wide$n
  t_wide$c <- 0.001 * (t_wide$n ^ 2)
  t_wide$total <- t_wide$a + t_wide$b + t_wide$c
  t <- tidyr::pivot_longer(t_wide, cols = c("a", "b", "c", "total"))
  colnames(t) <- c("n", "sub", "t")
  t
}
t <- create_big_o_example(n = seq(0, 100))
ggplot2::ggplot(t, ggplot2::aes(x = n, y = t, color = sub)) + 
  ggplot2::geom_line(size = 4) + 
  ggplot2::theme(text = ggplot2::element_text(size = 20))
```

:monocle_face: Work on B?

## Example

```{r}
t <- create_big_o_example(n = seq(0, 500))
ggplot2::ggplot(t, ggplot2::aes(x = n, y = t, color = sub)) + 
  ggplot2::geom_line(size = 4) + 
  ggplot2::theme(text = ggplot2::element_text(size = 20))
```

## Example

```{r}
t <- create_big_o_example(n = seq(0, 2000))
ggplot2::ggplot(t, ggplot2::aes(x = n, y = t, color = sub)) + 
  ggplot2::geom_line(size = 4) + 
  ggplot2::theme(text = ggplot2::element_text(size = 20))
```

:sunglasses: No, work on C instead

## Discussion

Big-O helps to:

-   find algorithm to profile
-   make predictions

Agree yes/no

## Exercise 1 \[SKIP\]

-   Measure big-O complexity of https://www.pythonpool.com/check-if-number-is-prime-in-python/

::: columns
::: {.column width="50%"}
🪱

```{python}
#| echo: true
#| eval: false
def isprime(num):
  for n in range(
    2, int(num**0.5)+1
  ):
    if num%n==0:
      return False
  return True
```
:::

::: {.column width="50%"}
🪱

```{python}
#| echo: true
#| eval: false
def isprime(num):
    if num> 1:  
        for n in range(2,num):  
            if (num % n) == 0:  
                return False
        return True
    else:
        return False
```
:::
:::

## Exercise 1 \[SKIP\]

-   Measure big-O complexity of https://www.pythonpool.com/check-if-number-is-prime-in-python/

::: columns
::: {.column width="50%"}
🪱

```{python}
#| echo: true
#| eval: false
def isprime(num):
  for n in range(
    2, int(num**0.5)+1
  ):
    if num%n==0:
      return False
  return True
```
:::

::: {.column width="50%"}
🪱

```{python}
#| echo: true
#| eval: false
def Prime(no, i = 2):
    if no == i:
        return True
    elif no % i == 0:
        return False
    return Prime(no, i + 1)
```
:::
:::

## Exercise 2 \[SKIP\]

-   Measure big-O complexity of DNA alignment at https://johnlekberg.com/blog/2020-10-25-seq-align.html

```         
ACGTACGTACGTACGTACGTACGT
ACGTACGTACGTCGTACGTACGT
```

```         
ACGTACGTACGTACGTACGTACGT
ACGTACGTACGT-CGTACGTACGT
```

# Measurement 2: Run-time speed profile

-   See which code is spent most time in
-   :monocle_face: Use an input of suitable complexity
    -   Note to self: next example should take at least 10 seconds!
-   :sunglasses: Consider using CI to obtain a speed profile every push!

## Run-time speed profile: code

-   [ ] Show R code in repo
-   [ ] Run R code from RStudio
-   [ ] Show Python code in repo
-   [ ] Run Python code from command line

## Myth 1

```{python}
#| echo: true
#| eval: true
def slow_tmp_swap(x, y):
    tmp = x
    x = y
    y = tmp
    return x, y

def superfast_xor_swap(x, y):
    x ^= y
    y ^= x
    x ^= y
    return x, y
```

. . .

-   [C++ Core Guidelines: Per.4: Don't assume that complicated code is necessarily faster than simple code](https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines#per4-dont-assume-that-complicated-code-is-necessarily-faster-than-simple-code)
-   [C++ Core Guidelines: Per.5: Don't assume that low-level code is necessarily faster than high-level code](https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines#per5-dont-assume-that-low-level-code-is-necessarily-faster-than-high-level-code)

## Exercise 1 \[30 mins\]

Create speed profile of any function you like.

-   [ ] Remind Python and R code on learner's repo

## Exercise 2 \[SKIP\]

Create speed profile of https://www.pythonpool.com/check-if-number-is-prime-in-python/

## Exercise 3 \[SKIP\]

Create speed profile of DNA alignment

# Step 3: Think

-   How to achieve the same with less calculations?
    -   Aim to change big-O, not some micro-optimization
    -   For example, store earlier results in a sorted look-up table

> Feynman Problem Solving Algorithm:
>
> 1.  Write down the problem.
> 2.  Think very hard.
> 3.  Write down the answer

# Step 4: Measure again

In TDD, this test would have been present already:

```{python}
#| echo: true
#| eval: false
assert 10.0 * get_t_runtime_b() < get_t_runtime_a()
```

Adapt the constant to reality.

-   [C++ Core Guidelines: Per.6: Don't make claims about performance without measurements](https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines#per6-dont-make-claims-about-performance-without-measurements)

## Recap quote

> It is far, far easier to make a correct program fast, than it is to make a fast program correct.
>
> Herb Sutter

![Herb Sutter](herb_sutter.jpg)

> Source [Wikimedia](https://commons.wikimedia.org/wiki/Category:Herb_Sutter#/media/File:Professional_Developers_Conference_2009_Technical_Leaders_Panel_7.jpg)

## Case study

-   [ ] Show ProjectRampal

## Discussion

-   Be critical on speed optimization solutions
-   Tested and clean code always comes first
-   Measure correctly, at the right complexity, before and after
-   Prefer changing big-O over micro-optimizations (but see first point!)

Agree yes/no?

## The End

## Links

-   Lecture of 2022: [here](https://uppsala.instructure.com/courses/69215/pages/optimisation-when-and-how?module_item_id=503139):
