Performance

Table of Contents

Motivation

Algorithms

Big O notation

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(N2) Quadrupled runtime for doubled input
Exponential complexity O(2N) 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.

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.

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

Algorithm engineering

Books on this subject

Miscellaneous

GitHubImpressum