Fast Programming Techniques

Notes from Andrei at code::dive 2015. Watch the whole lecture (recommended).

Integrals

Prefer 32-bit ints to other sizes

Prefer unsigned to signed

Most numbers are small

Floating point

Strength reduction

Use minimum strength operations when optimising as the stronger ones are more costly.

Speed hierarchy

operation cycles
Comparisons less than 1
(u)int add, subtract, bitops, shift (2 x 32-bits) 1
Floating point add, subtract TBC
(u)int32 multiply, floating point multiply TBC
Floating point division, remainder TBC
(u)int division, remainder TBC

Why is it cheaper to do floating point division than integer?

Format of floating point: mantissa and exponent, already friendly to division.

Division in integers is unnatural. Division is a search!

Minimise indirect writes

Improvements

Checkpoint

The forgotten parallelism

How do we use ALUs?

ILP: instruction level parallelisation.

better instruction level parallelism = fewer data dependencies

Part 2

https://www.youtube.com/watch?v=9tvbz8CSI8M

Unsigned integer overflow has well-defined behaviour; signed integer overflow is undefined.

Part 3

https://www.youtube.com/watch?v=FJJTYQYB1JQ

1st order conclusions

2nd order conclusions

Timeline

You can't achieve the best sort with generic programming.