About: A sidequest is an optional, not graded, not evaluated in anyway exploration into a topic. Sometimes it is just cool to know what is out there in the world. Sidequests come with a little descritions, presentations, related resources, and a sample code or exercise you can try. Side quests are likely a good area for further independent studies, research project, thesis, etc.

Performance Analysis Study (Part 1)

Problem Statement

When we learn algorithms, we analyze their tradeoffs in terms of the asymptotic growth of a function. As an example, merge sort (n log n) is much better than selection sort(n^2). But is it always better? (And what about something like Flashsort). Hardware complicates the question of "which algorithm is better" when we introduce different types of memory in our memory hierarchy.

Proposed Exercise

For this exercise, you will implement several popular sorting algorithms, sorting different data types. You will then use tools to measure how long the actual algorithm takes. Additionally, you will use tools to measure cache-hits, page-faults, etc. to really understand when an algorithm may perform best.

Proposed Evaluation

Implement and build a test framework for various benchmarks(e.g. sorting algorithms). Measure various metrics like cache-hits, page-faults, time, and allocations. Be very precise about the resolution of timers you are using, taking care that the cache is, or is not warmed up, etc.

Key Resources

(The first resource you should read)

Additional Resources

Performance Debugging (Part 2)

Problem Statement

After understanding which algorithm is empirically faster (by measuring in part 1), we not want to understand 'why' it may be faster or slower than another algorithm. Could there be different parameters passed to the function? Were there many different execution paths within the algorithm? Were there other primitives (e.g. locks) that caused contention over some shared resource?

Proposed Exercise

Generate a call tree of an actual program run. See if you can identify some 'cost' or explanation of why a program was running slow.

Proposed Evaluation

Use the LLVM framework (or something similar, like valgrind) to record a call tree for an algorithms execution. After doing so--see if you can classify various data structures, features (I/O, line count, expensive assembly instructions, number of branches, etc.) of a function to indidicate any performance degradation.

Key Resources

(The first resource you should read)

Additional Resources