Description

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.
Analyzing and Optimizing the Program
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.
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:
• 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.).
• 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
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.