Optimization

Optimization - Introduction

General Rules …

  • Focus on clean design ⟶ efficiency follows

  • Optimization near the end of the project

  • Proven hotspots need optimization

  • Proof through profiling

Note

“Premature optimization is the root of all evil”

Donald E. Knuth

Compute Bound or IO Bound? (1)

Decide whether, what and how to optimize!

  • Collect representative input data

  • Why does the program take long?

  • Where does it spend most of its time?

    • Userspace: this is where computation is generally done

    • Kernel: ideally very little computation

Compute Bound or IO Bound? (2)

Checksumming From An Externel USB Disk

$ time sha1sum 8G-dev.img.xz > /dev/null
real 0m38.879s
user 0m3.349s
sys  0m0.375s

  • real: total perceived run time (“wall clock time”)

  • user: total CPU time spent in userspace

  • sys: total CPU time spent in kernel

Here: user + sys is far less than real ⟶ mostly IO

Compute Bound or IO Bound? (3)

Checksumming From Internal SSD

$ time sha1sum 01\ -\ Dazed\ and\ Confused.mp3 1>/dev/null

real 0m0.128s
user 0m0.107s
sys  0m0.018s

Here: user + sys is roughly equal to real

  • Almost no IO

  • ⟶ Compute bound

What to do Next?

Now that we know that our application is compute bound …

  • See where it spends most of its time ⟶ profiling

  • Decide whether optimization would pay off

  • Understand what can be done

  • Understand optimizations that compilers generally perform