Lab 4 — Profiling

ECE 459: Programming for Performance
Lab 4 — Profiling

One of the keys to improving performance is identifying bottlenecks that are slowing a program
down. The key to doing that is the use of profiling tools.
In this assignment, you are provided a simulation of a Hackathon. The program is slow, and
you will use some profiling tools to analyze the code to find out where it’s spending its time.
Based on what you find, you can make changes to the program to speed it up.
Background
The Hackathon has three different kinds of threads: Students, Idea Generators, and Package
Downloaders. The Idea Generator generates an idea the way many startup companies are
pitched, as an equivalent of a known service for a new audience, such as “LinkedIn for Service
Animals”. Students work on ideas, and working on an idea requires downloading some number
of software Packages. The Hackathon simulation runs until all ideas have been built.
Since we have multiple threads, the order of outputs may differ. However, we can still check for
correctness by taking the xor (exclusive or) of the SHA256 hashes of every idea generated and
every package downloaded.
Analyzing and Optimizing the Program
Your goal is to speed up the program. You should therefore do some analysis using profiling
tools. You may have some ideas about where to start immediately, but tools help you check your
assumptions and find places for improvement. The basic workflow is to use profiling tools to
identify what’s slow, make changes, and re-evaluate to see how much (or how little) it improved
the runtime of your program. If the program is sped up enough, you’re all done (and can go on
to writing your commit message).
You can use any analysis tools you like, whether or not they were presented in the lectures.
However, for the purposes of your commit log message you should use a flamegraph. A flamegraph is a visualization of profiling data, meant to show you where a program is spending most
of its time. And they look cool, so there’s that.
You probably need to know about how flamegraphs work. To read up on them, see http://www.
brendangregg.com/flamegraphs.html. There are some useful YouTube videos linked there to
give you guidance. In particular, the video at https://youtu.be/D53T1Ejig1Q is useful. If you’re
in a rush, just watch from the 10 minute mark to about the 16 minute mark.
1
Here’s a flamegraph of the starter code:
For your convenience, we’ve created a Makefile target that runs your program and generates
the flamegraph. You can run it by typing “make”. This will generate an SVG (Scalable Vector Graphics) file called “flamegraph.svg” containing the graph, which can be viewed in any
graphical viewing program or in your preferred web browser.
In your commit log message, explain how you used your profiling data to decide what to change.
Be sure to include the flamegraph for the final version of the program and provide some explanation to the reader as to how your updated flamegraph demonstrates improvement over the
starter code.
Rules/Restrictions. To prevent trivializing the problem, and to make it possible for us to
compare your code against the starter code, here is a list of rules:
• You may change how threads communicate.
• You may change intermediate checksums, but the checksums printed out at the end of
execution must be identical to the ones generated by the starter code.
• You may not change the numbers of threads, students, ideas, packages.
• The arguments of the program must still be respected (so you can’t change the the number
of students/ideas/packages managed by each thread).
• Must not introduce bugs (memory leaks, deadlocks, etc.).
• Must not trivialize the threads e.g. moving everything to 1 thread to eliminate synchronization. You may rewrite how the threads communicate (different mutex/constructs
usage, for example).
2
• All publicly observable final behaviour/output for each thread must be preserved. You
may change intermediate prints (I/O) but not final ones. For example, IdeaGenerator
must add NewIdea Events to the queue. It must also be responsible for inserting the poison
pills (OutOfIdeas) for the Student threads.
• Any threads you create may only be terminated with the OutOfIdeas event (no passing
"expected number of ideas").
• You must not hardcode any values that are read from files. We will be testing with different
files of various sizes.
• No other changes that trivialize the simulation or execution (e.g. deleting functionality
or things that consume CPU time).
Rubric
We’re switching things up here and requiring a commit log message instead of a report. Probably you didn’t like writing reports that much and the TAs didn’t really enjoy reading them
either. Commit messages should still argue for why your change should be merged (including
the flamegraph) but imply less boilerplate.
Implementation (35 marks) Your code must preserve the original behaviour and cannot
violate any of the rules specified above. The changes you make should be supported by a
profiling tool of some sort and not just be random changes.
Commit Log (15 marks) 12 marks for explaining the changes that you’ve made, including
your final flamegraph and some explanation for the reader. 3 marks for clarity of exposition.
Performance (50 marks) For this lab, we are finally measuring performance. Your code must
run faster than the starter code. The faster, the better. Updated marking guidelines:
Speedup (×) (% of marks for performance)
≥ 13.5 100
[12, 13.5) 90
[11, 12) 80
[10, 11) 70
[9, 10) 60
[8, 9) 50
[7, 8) 40
[6, 7) 30
[5, 6) 20
[4, 5) 10
< 4 0
3
What goes in a commit log
Here’s a suggested structure for your commit log message justifying the pull request.
• Pull Request title explaining the change (less than 80 characters)
• Summary (about 1 paragraph): brief, high-level description of the work done.
• Tech details (3–5 paragraphs): anything interesting or noteworthy for the reviewer about
how the work is done.
• Something about how you tested this code for correctness and know it works (about 1
paragraph)
• Something about how you tested this code for performance and know it is faster (about
3 paragraphs, referring to the flamegraph as appropriate).
Write your message in the file commit-log/message.md and put the final generated flamegraph
into commit-log/flamegraph.svg. Don’t forget to git add commit-log/flamegraph.svg.
4