# Performance

## Table of Contents

## Motivation

## Algorithms

- Is studying algorithms important for game development? | softwareengineering.stackexchange.com
- Top 7 algorithms and data structures every programmer should know about

### Big O notation

- What is a plain English explanation of “Big O” notation? | stackoverflow
- "N" is the data input to be processed
- Considered are the average, best and worst case

### Classification

Class | Notation | Description |
---|---|---|

Constant complexity | O(1) | Most instructions are executed once |

Logarithmic complexity | O(log N) | Program becomes gradually slower with more input data |

Linear complexity | O(N) | Runtime increases linearly with input data |

Linear-logarithmic complexity | O(N log N) | Runtime is a bit more than doubled for doubled input (in devide and conquer algorithms) |

Quadratic complexity | O(N^{2}) |
Quadrupled runtime for doubled input |

Exponential complexity | O(2^{N}) |
Runtime grows expontentially for increased input. |

## Profiling

The performance of a system is not only dependent upon the theoretical complexity of the algorithms. It also depends upon its environment, e.g. the operating system, the compiler, runtime environment and the hardware. As all this factors cannot be reliably derived from theory an emperical analysis is necessary as well.

### Mechanical sympathy

### Scientific method

Document:

- How much faster?
- What tried out with which effects?
- Make experiments reproducible

## Optimization

The purpose of optimization is to find a better approximation to the ideal runtime and resource consumption. The optimization process is a variant of the scientific method. It should be applied incrementally.

- Start with the simplest possible solution for the required functionality
- Analyze the performance and resource usage of the system
- Identify the bottleneck
- Define a testing scenario for the bottleneck (with best, average and worst case input data)
- Apply the SCAMPER checklist to every instruction to find out a possibly better solution
- Implement the improved solution
- Rerun the testing scenario and compare the mutation with previous versions of the algorithm
- Go back to step (5) until solution is good enough
- Go back to step (2) until termination

### Algorithm engineering

- https://en.wikipedia.org/wiki/Algorithm_engineering
- Algorithm Engineering | Peter Sanders, Dorothea Wagner, Karlsruhe Institute of Technology
- Algorithm Engineering: Concepts and Practice | Markus Chimani and Karsten Klein

### Books on this subject

- Experimental Methods for the Analysis of Optimization Algorithms | Thomas Bartz-Beielstein, Marco Chiarandini, Luís Paquete, Mike Preuss
- Evolutionary Optimization Algorithms | Dan Simon