Skip to the content. Disable Animations :x: :movie_camera:

Week 8, 2020: Gotta Go Fast

đź”— Pre-Discussion Learning Material

đź”— Agenda

  • group discussion of Alaxandrescu’s talk
  • using a profiler
    • Emily Dolson
    • gprof: useful for figuring out distribution of run time spent in different parts a program
    • gprof2dot: useful for visualizing gprof’s output
    • example.cc
      #include <iostream>
      int long_function() {
          int j = 0;
          for (int i = 0; i < 100000000; i++) {
              j++;
          }
          return j;
      }
      int short_function() {
          int j = 0;
          for (int i = 0; i < 10; i++) {
              j++;
          }
          return j;
      }
      int calling_function() {
          int a = long_function();
          int b = 0;
          for (int i = 0; i < 10; i++) {
              b = short_function();
          }
          if (a > b) {
              return a;
          }
          return b;
      }
      int main() {
          int res = calling_function();
          std::cout << res << std::endl;
      }
      
    • compile command: g++ -pg example.cc
    • run command: gprof a.out
    • visualize command: gprof a.out | gprof2dot.py | dot -Tpng -o output.png
  • taking and interpreting timings
    • Matthew Andres Moreno
    • using std::chrono to measure elapsed time
    • olsen.cpp
      #include <chrono>
      #include <thread>
      #include <iostream>
      #include <ratio>
      #include <algorithm>
      #include <vector>
      #include <random>
      
      int schedule_olsen_sleepover_party() {
        // choose two MK & A themed magic numbers...
        // reference: http://sweetie_olsen.tripod.com/sweetieolsen/id21.html
        const std::string mary_kate_color{ "yellow" };
        const std::string ashley_color{ "maroon" };
      
        const int mary_kate_number{ std::accumulate(
          std::begin(mary_kate_color),
          std::end(mary_kate_color),
          0
        ) };
        const int ashley_number{ std::accumulate(
          std::begin(ashley_color),
          std::end(ashley_color),
          0
        ) };
      
        // ... define a random distribution using those numbers...
        // adapated from https://stackoverflow.com/a/13445752
        std::mt19937 rng{std::random_device{}()};
        std::uniform_int_distribution<int> sleep_distribution{
          std::min(mary_kate_number, ashley_number),
          std::max(mary_kate_number, ashley_number)
        };
      
        return sleep_distribution(rng);
      }
      
      int main() {
      
        // stopwatch begin
        const auto before{
          std::chrono::steady_clock::now()
        };
      
        // do work
        // ... sleep for a MK&A-themed duration
        std::this_thread::sleep_for( std::chrono::milliseconds{
          schedule_olsen_sleepover_party()
        } );
      
        // stopwatch end
        const auto after{
          std::chrono::steady_clock::now()
        };
      
        // print time elapsed in milliseconds
        std::cout << std::chrono::duration<
            double,
            std::milli
          >{
            after - before
          }.count() << " milliseconds" << std::endl;
      }
      
    • (… compiling Mary-Kate & Ashley …)
      g++ Olsen.cpp -o Mary-Kate -std=c++17
      g++ Olsen.cpp -o Ashley -std=c++17
      
    • using time to measure elapsed time
      echo "Algorithm,Replicate,Seconds" > "olsen-timings.csv"
      for Replicate in {0..9}; do
        echo "Replicate ${Replicate}"
        for Algorithm in Mary-Kate Ashley; do
          echo "Algorithm ${Algorithm}"
          /usr/bin/time -f "%e" -o tmp \
            "./${Algorithm}" \
               > /dev/null 2>&1
          Seconds=$(cat tmp)
          echo "Seconds ${Seconds}"
          echo "${Algorithm},${Replicate},${Seconds}" >> "olsen-timings.csv"
        done
       echo
       echo "!!! <%) Gimme Pizza <%) !!!"
       echo
      done
      
    • (… example data …)
    • olsen-timings.csv
      Algorithm,Replicate,Seconds
      Mary-Kate,0,0.65
      Ashley,0,0.66
      Mary-Kate,1,0.66
      Ashley,1,0.67
      Mary-Kate,2,0.65
      Ashley,2,0.66
      Mary-Kate,3,0.65
      Ashley,3,0.66
      Mary-Kate,4,0.66
      Ashley,4,0.66
      Mary-Kate,5,0.66
      Ashley,5,0.66
      Mary-Kate,6,0.66
      Ashley,6,0.66
      Mary-Kate,7,0.66
      Ashley,7,0.66
      Mary-Kate,8,0.66
      Ashley,8,0.67
      Mary-Kate,9,0.66
      Ashley,9,0.65
      
    • using seaborn to draw plots with bootstrapped confidence intervals
      import pandas as pd
      import seaborn as sns
      from matplotlib import pyplot as plt
      
      df = pd.read_csv('olsen-timings.csv')
      
      sns.barplot(
        data=df,
        x='Algorithm',
        y='Seconds',
      )
      
      plt.savefig(
        'timings-by-algorithm.png',
        transparent=True,
        dpi=300,
      )
      
    • using scipy.stats to perform a Kruskal-Wallis test
      import scipy.stats as stats
      import pandas as pd
      
      df = pd.read_csv('olsen-timings.csv')
      
      print(
        stats.kruskal(*(
            chunk
            for idx, chunk
            in df.groupby('Algorithm')['Seconds']
        ))
      )
      
  • profiling memory usage
    • Santiago Rodriguez
    • leak.cpp
      #include <iostream>
      #include <cstdlib>
      #include <time.h>
      int add_up(int arr[], size_t size) {
         int count = 0;
         for (int i = 0; i < size; ++i) {
             count += arr[i];
         }
         return count;
      }
      int main() {
          // set our random seed to current time
          std::srand(time(NULL));
          // make array a random size
          int size = rand() % 10 + 1;
          int* arr = new int[size];
          // fill up array with random ints
          for (int i = 0; i < size; ++i) {
              arr[i] = rand() % 100000;
          }
          // print array contents
          for (int i = 0; i < size; ++i) {
              std::cout << arr[i] << " ";
          }
          std::cout << std::endl;
          add_up(arr, size);
          delete arr;
          return 0;
      }
      
    • compile: g++ -std=c++17 -O0 leak.cpp -o leak -g
    • run: valgrind -s --leak-check=full ./leak
    • limitation.cpp
      #include <iostream>
      int main() {
          static int arr[2];
          arr[3] = 0;
          return 0;
      }
      
    • compile: g++ -std=c++17 -O0 limitation.cpp -o limitation -g
    • run: valgrind -s --leak-check=full ./limitation
    • misses.cpp
      #include <list>
      #include <vector>
      #include <cstdlib>
      #include <numeric>
      #include <iostream>
      int main() {
          std::vector<int> vec(1000000000);
          std::iota(
              vec.begin(),
              vec.end(),
              0
          );
          std::srand(0);
          int total = 0;
          for (int i = 0; i < 1000000; ++i) {
              total = total + vec[rand() % vec.size()];
              //total = total + vec[i];
          }
          return total;
      }
      
    • compile: g++ -std=c++17 -O0 misses.cpp -o misses -g
    • run: valgrind -s --tool=cachegrind ./misses
    • run: valgrind -s --tool=massif ./misses

đź”— Conversation Starters/Discussion Questions

  1. What did you think was effective about Alaxandrescu’s presentation? In what ways could it have been more effective?
  2. Does goto merit continued existence as a keyword?
  3. What do you use as a heuristic for balancing optimization and maintainability?
  4. To what extent is predicting or understanding why an optimization works important? Why?
  5. With modern compilers, do less readable/more directive coding approaches still make sense (e.g., size & 1 to avoid a conditional)?
  6. In a detail-rich talk like Alaxandrescu’s, how do you decide what to pay attention to?