CSCI 3907 Assignment #3: Mechanical Sympathy

AI Policy for this assignment: Again, as nearly all of the work in this assignment will be running timing tests and plotting your results, feel free to use whatever online resources you like to help you complete your code and assemble and plot your results.

Part I: Profiling revisited

To get started, recall how we used gprof (Linux) or sample (OS X) to get profiling results for our code. Using that approach, do a profile of your quicksort program from the previous assignment in class, with N set to the maximum value you used (again, for me, it was 100,000,000). The output from these profiling tools is pretty extensive, but as we did in class, you'll want to focus on the percentage breakdown by function call at the top. For this part of your writeup, include the percentage breakdown For example, here's what I got (which I've cleaned up for presentation, as you should):

  %   cumulative   self                   self     total           
 time   seconds   seconds    calls        s/call   s/call  name    
 79.31     10.26    10.26    66669059     0.00     0.00    partition(int*, int, int)
 16.82     12.43     2.17    1767846632   0.00     0.00    swap(int*, int*)
  2.24     12.72     0.29                                  main

Below this data, answer the following questions:

What general principle (of statistics / data science) dictates that we use the maximum reasonable value of N for this experiment?
Do your profiling results agree with the Pareto Principle? (Google it if you don't know what it is.)

Part II: Inlining

Now that you've collected your profiling data for quicksort, change the compiler options back to the recommended -O2 we used at the end of the previous assignment. Based on the results from Part I, insert the keyword inline in front of the declarations of the most expensive calls (just google it if you're unsure the what I mean). Re-run your timing trials (ten successive values of N) with this trick in your code, and make a plot comparing your old timing values for quicksort with -O2 against quicksort with -O2 plus inlining. Below the plot, comment briefly on your results.

Part III: Array-of-structs vs. struct-of-arrays

Think about a (somewhat silly) kindergarten activity where each student is assigned three wooden building blocks, which the teacher keeps in a storage room. Each student is issued an ID number that the teacher will use to access that student's blocks. At any given time, a student can request a block to be retrieved by the teacher. The student can then play with the block, and perhaps modify it by writing on it or painting it a different color, after which the teacher returns it to the storage room.

Imagining what's in the storage room, the students probably think that they each have a box or cubby containing their three blocks, but in reality the teacher has organized the blocks in a way that turns out to be more efficient for storage and retrieval: there is a rack of three shelves, with one shelf for the big blocks, one shelf for the medium-sized blocks, and one shelf for the small blocks, each shelf labeled with the students' ID numbers in ascending order, spaced according to the size of the block on that row.

This made-up example is similar to what we mean by array-of-structs (the more intuitive, cubbyhole approach, that we learn in our Data Structures course and typically use in our work) versus struct of arrays (rack-of-shelves). In both cases, the less intuitive approach turns out to be more efficient.

Implementing this performance trick in code turns out to be rather simple. We can represent the big blocks as type int (32 bits), the medium-size as type short (16 bits), and the little ones as type char. So your job is to write a program for each approach, and time your two programs on different sizes of N:

array_of_structs.cpp should define two little classes: (1) Cubby with a single instance of each datatype, and the appropriate constructors, and (2) StoreRoom, containing an array of N cubbies. Making everything public will simplify your test code.
struct_of_arrays.cpp should define just a StoreRoom class, containing an array of N values for each of the three numerical types. Again, making everything public will simplify your test code.

The code that accesses your data can likewise be very simple: inspired by an example in Chapter 2 of the Nanosecond C++ book, I simply wrote a loop of N iterations that added a value (I used the constant 1) to every medium value in my data. Because both programs ran so quickly, I started with N=500,000,000 and went to N=1,000,000,000, in increments of 100,000,000; i.e., five large values of N (ten values being overkill because we're not trying to explore the Big-O concept). As before, run your experiments, record your average times for each condition, and in your writeup include a plot showing your results comparing the times you got for the two approaches.

Part IV: `constexpr`

The Nanosecond C++ book, as well as online discussion, devotes quite a bit of praise to the C++ constexpr keyword as a further performance-enhancing trick. After experimenting some examples from the book and from reddit, stackoverflow, etc., I couldn't get any significant speedup by including this keyword before my function declarations (as opposed to inline, which as we've seen can speed things up noticeably). Then it occurred to me that by always using the recommended -O2 optimization level, I might be making the compiler do the equivalent of constexpr automagically. At that point I nearly gave up on constexpr, because why bother to do something by hand that the compiler does for free?

Then it occurred to me: by always using -O2, I wasn't dealing with the fact that a real-world software project is going to involve a lot of debugging and profiling (i.e., -g -pg) before we can switch to optimization with -O2. By using -g -pg instead of -O2, and googling simple c++ constexpr example or the like, I was able to get a tiny program where the use of constexpr made a huge difference in my timing results.

So, to finish up, run this experiment yourself: Find a little constexpr example online, compile it with -g -pg, and compare the timing results when you use constexpr versus when you omit it. As before, pick a sequence of five large values of N that shows a nice difference without taking forever; then make a plot comparing the two conditions (with and without constexpr), and include the plot in your writeup.

What to submit to github

Same as last time: deliverable is a PDF writeup, but please also submit your code, spreadsheets, whatever, for your own future use. Your writeup should include: