Writing Fast Code: Benchmarking and Profiling

Alec Bills

An Impatient Man

1

1

1

1

First 4 Weeks: Tools required for HPC

Next 4 Weeks: How to write efficient HPC code

2

2

2

2

First, a disclaimer: “Premature optimization is the root of all evil”.

• Donald Knuth

https://xkcd.com/1691/

3

3

3

3

First, a disclaimer: “Premature optimization is the root of all evil”.

[1] Kommajosyula, et Al, Practical Computer Science for Computational Scientists. https://drive.google.com/drive/folders/1c-W54GEMRZDZZhNPqGFZREgC7AHWhk12 , [2] Photo: Alex Wadell

4

4

4

4

What are benchmarking and profiling?

Benchmarking (ex situ):

• Statistically rigorous timing (+allocs).
• Benchmarking is used to compare software or hardware to determine which performs better.
• Results in a single metric (e.g. operations/second, seconds, iterations/second)

​

​

Profiling (in situ):

• Looking “inside” the code
• Results are more qualitative – will demo
• Used to find which parts of a single code are taking the most time and operations

Benchmarking and Profiling are Complementary Tools!

5

5

5

5

Benchmarking Tools

https://github.com/JuliaCI/BenchmarkTools.jl

timeit (built-in)

Many others for other languages…

6

6

6

6

How does benchmarking work?

• Runs a given piece of code (e.g. a function call) for N samples
• Each sample has M evaluations
• Timing precision can be lower than time it takes to run 1 eval, so record time to run M evaluations as t, then sample time is t/M
• Times the code for each evaluation
• The user can tune N,M to get best results
• Reports statistics on the time and allocations:
• Mean, Median, Minimum, Maximum.

7

7

7

7

• Fast Functions
• Fast Jacobians
• Fast Solvers

Implicit Euler

Newton-Raphson

We don’t really use these solvers, but the principle is the same

Practical Example: How do we make fast dynamical models?

8

8

8

8

Practical Example: Comparison of different Jacobian Algorithms

Level_sync

8 threads

Baseline

9

9

9

9

Level_sync

Noinline

8 threads h001

Level_sync

Noinline

256 threads h001

Practical Example: Comparison of different jacobian algorithms

10

10

10

10

11

11

11

11

How does profiling work?

• Periodically takes “snapshot” of execution, which captures the current trace of function calls.
• Shows which functions are being called the most often.
• Again, can tune sampling parameters

​

​

12

12

12

12

What comes out of a profile?

13

13

13

13

What comes out of a profile?

╎ 17 @Base/reducedim.jl:999; _maximum

Number of Calls

Code Location (Julia)

Function Name

17 @Base/reducedim.jl:999; #_maximum#783

Second line is called by first line

14

14

14

14

More important: Profile visualization tools

https://github.com/google/pprof

pprof

https://github.com/jiffyclub/snakeviz/

ProfileView.jl, ProfileVega, StatProfileHTML, ProfileSVG, etc., etc.

​

(if someone wants to contribute a profile visualization to MATLABPlots.jl, I will be elated)

15

15

15

15

A Song of Ice and Fire: Flame Graphs and Icicle Plots

(note: I think pprof is using incorrect terminology and that they’re showing icicle plots)¹

pprof

[1] http://linnarssonlab.org/flamemaps/ [2] https://jiffyclub.github.io/snakeviz/ [3] https://github.com/JuliaPerf/PProf.jl

16

16

16

16

Practical Example: Liionpack bottleneck is setting up and solving the circuit

Tranter et al., (2022). liionpack: A Python package for simulating packs of batteries with PyBaMM. Journal of Open Source Software, 7(70), 1 4051. https://doi.org/10.21105/joss.04051

17

17

17

17

Practical Example: Liionpack bottleneck is setting up and solving the circuit

Tranter et al., (2022). liionpack: A Python package for simulating packs of batteries with PyBaMM. Journal of Open Source Software, 7(70), 1 4051. https://doi.org/10.21105/joss.04051

18

18

18

18

What do I do when I find the bottleneck?

• Eliminate anything unnecessary
• Eliminate recomputation
• Write functions in-place
• Find a better algorithm
• SIMD (single instruction multiple data)
• Parallelize
• Google it (stackoverflow)
• Read docs
• Be creative! Write tests and try stuff! Anything!

​

19

19

19

19

https://xkcd.com/1205/

20

20

20

20

Example problem: Monte Carlo Calculation of π

count = 0

for n in 1:N:

x ~ U(0,1)

y ~ U(0,1)

if (x^2+y^2)<1:

count+=1

pi_estimate = 4*count/N

​

21

21

21

21

Questions before live demo

22

22

22

22

Homework (use research code or sample problem). Due Next Fri

1. Benchmark an unoptimized code. Report results for minimum, mean, and median time, number of samples, and number of evaluations. Show a histogram of results.
2. Profile that code. Write down the most expensive part. Show a flamegraph.
3. Optimize the expensive part. (deliverables below)
4. Benchmark the optimized code, reporting the same things as (1)
5. Profile the optimized code and present the flamegraph showing that you’ve reduced the cost of the expensive part.

23

23

23

23