Are efficient algorithms enough for writing fast code ? And if not, what else ?
The speed of a program is as important as its function. However, unlike function, speed is the result of often surprising interactions across the entire system stack. This course helps understand what influences program speed and the speed should be measured, evaluated and presented. Apart from general guidelines, the course will visit many system details relevant to performance and introduce tools that help in software performance evaluation.
There are no formal prerequisites. However, you should be familiar with very basic concepts from probability and statistics, operating systems, computer architecture and compiler principles. If you have passed the Operating Systems (NSWI004) and Computer Architecture (NSWI143) courses, you are fine. If you have missed these, you should be at least a little interested in the system aspects of computers and programs and be willing to study the statistical methods we use along with the R system.
The course aims at Master program students, but the students of Bachelor program are also welcome. If you like the topic, you will be probably fine.
From the following list, each point will be usually covered in one or two lectures:
- Motivation - why bother when things are easy ?
- How to Measure I - basics, clocks, timers.
- How to Measure II - hardware performance counters.
- How to Measure III - profiling, management interfaces, instrumentation.
- What to Measure - metrics, desired properties, benchmark workloads.
- How to Process Data - aggregate statistics, hypotheses, pitfalls.
- How to Visualize Data - plots, plots, more plots.
- When to Not Measure - modeling, simulation.
- Taking a Step Back - methodology.
For the exam, you should first prepare and execute a performance evaluation experiment of your choice, and describe it in a short write up. It is fine to pick an experiment related to your assignments from other courses or to your thesis, aim for a write up of around 10 pages. During the exam, you will explain your design and results, demonstrating use of the various methods and systems presented in the lectures. The evaluation criteria is roughly as follows:
- Problem definition. Did the experiment clearly state what is the problem or question to be investigated ?
- Experiment design. Does the design of the experiment match the problem definition ? Can the experiment answer the questions posed ?
- Technical execution. Was the experiment carried out in a technically correct way ? Were reasonable precautions taken to obtain correct results ?
- Result analysis. Are the results analyzed in a robust way ? Are the conclusions reasonably backed by the results ? Are threats to validity discussed ?
- Presentation. Is the experiment clearly presented and the conclusions clearly stated ?
- Depth. Is all of this sophisticated enough to match the course level ?
No exam terms are scheduled, submit your write up via mail at any time but two weeks before the end of the exam period at the very latest. Depending on circumstances, expect one to two weeks reaction time.