Notes on Performance Measurement

Design and implementation research in programming languages calls for performance evaluations. The following notes are supposed to help you with this topic. They do not represent a self-study course but they get you off the ground.

Must Read Papers

• Jan Vitek and Tomas Kalibera. R3---Repeatability, Reproducibility and Rigor

  This paper describes the (sorry) state of the art in 2011, especially the standard mistakes that sneak into performance evaluations and the general unawareness of computer scientists (PL and systems researchers): lack of benchmarks, lack of experimental methodology and lack of understanding of statistical methods.

  Jan started this effort when he investigated the widely praised trace compiler from Michael Franz's group at UCI and found that the published results weren't repeatable in real world settings.

• Mytkowicz et al. Producing wrong data without doing anything obviously wrong!

  @inproceedings{mdhs:asplos2009,
   author = {Mytkowicz, Todd and Diwan, Amer and Hauswirth, Matthias and Sweeney, Peter F.},
   title = {Producing wrong data without doing anything obviously wrong!},
   booktitle = {Proceedings of the 14th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS)},
   year = {2009},
   pages = {265--276},
   doi = {10.1145/1508244.1508275},
  } 
  

  This is partly about "measurement bias" that scientists inadvertently inject into the process w/o realizing it. Good ideas on the process and statistics on how to avoid it.

  The key problem is that all statistical analysis make assumptions about the normality of the distribution of measurements that cannot be taken for granted in a computational setting.

  NOTE: see geo-vs-arith-means.pdf

  The geo v arith mean question is still subject to debate, but in my view it's not that hard. Geo is just the exp of the log of the arith mean (so it amounts to taking the mean in the log space). If the quantities you are aggregating are absolute then use an arithmetic mean. If they are normalized to some common base then use the geo. To understand the latter, consider a comparison of optimizations A & B. If you want to aggregate against N benchmarks and each result is normalized to performance of A, then you want a result of 2.0 to count the same (although with an opposite sign) as 0.5. The geomean does this exactly; the arithmetic mean does not.

• Mytkowicz, Diwan, Hauswirth, Sweeney. The Effect of Omitted-Variable Bias on the Evaluation of Compiler Optimizations

  @article{mdhs:ieee2010, 
    author = {Todd Mytkowicz and Amer Diwan and Matthias Hauswirth and Peter Sweeney},
    title = {The Effect of Omitted-Variable Bias on the Evaluation of Compiler Optimizations},
    journal ={Computer},
    volume = {43},
    number = {9},
    year = {2010},
    pages = {62-67},
    doi = {http://doi.ieeecomputersociety.org/10.1109/MC.2010.214},
  }
  

• Georges et al. Statistically rigorous Java performance evaluation

  @inproceedings{gbe:oopsla2007,
   author = {Georges, Andy and Buytaert, Dries and Eeckhout, Lieven},
   title = {Statistically rigorous Java performance evaluation},
   booktitle = oopsla,
   year = {2007},
   pages = {57--76},
   doi = {10.1145/1297027.1297033},
  } 
  

• L. Kirkup. Experimental Methods: An Introduction to the Analysis and Presentation of Data. 1994.

  Vitek/Kaliberg recommend this book as a general introduction to experimentation.

Benchmarks

• Dacapo @ OOPSLA

  @inproceedings{dacapo:2006,
   author = {Blackburn, Stephen M. and Garner, Robin and Hoffmann, Chris and Khang, Asjad M. and McKinley, Kathryn S. and Bentzur, Rotem and Diwan, Amer and Feinberg, Daniel and Frampton, Daniel and Guyer, Samuel Z. and Hirzel, Martin and Hosking, Antony and Jump, Maria and Lee, Han and Moss, J. Eliot B. and Phansalkar, Aashish and Stefanovi\'{c}, Darko and VanDrunen, Thomas and von Dincklage, Daniel and Wiedermann, Ben},
   title = {The DaCapo benchmarks: Java benchmarking development and analysis},
   booktitle = oopsla,
   year = {2006},
   pages = {169--190},
   numpages = {22},
   doi = {10.1145/1167473.1167488},
  } 
  

• Dacapo @ OOPSLA
• Automated Construction of JavaScript Benchmarks

Dissertations (background)

• Mytkowicz: dissertation
• Georges: dissertation

Artifact Submissions

• Christos Dimoulas, Artifact Submission for OOPSLA 2013

  Here is my self-criticism after we got detailed and solid feedback on this submission.