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.

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.

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).
• 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).