Week 8, 2020: Gotta Go Fast

🔗 Pre-Discussion Learning Material

CppCon 2019: Andrei Alexandrescu “Speed Is Found In The Minds of People”
- the first hour of the talk is most important

🔗 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

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

WAVES

Workshop for Avida-ED Software Development

Week 8, 2020: Gotta Go Fast

🔗 Pre-Discussion Learning Material

🔗 Agenda

🔗 Conversation Starters/Discussion Questions