Index: contrib/ChangeLog

2012-11-05  Lawrence Crowl  <crowl@google.com>

	* compare_two_ftime_report_sets: New.

Index: contrib/compare_two_ftime_report_sets
===================================================================
--- contrib/compare_two_ftime_report_sets	(revision 0)
+++ contrib/compare_two_ftime_report_sets	(revision 0)
@@ -0,0 +1,605 @@
+#!/usr/bin/python
+
+# Script to statistically compare two sets of log files with -ftime-report
+# output embedded within them.
+
+# Contributed by Lawrence Crowl <crowl@google.com>
+#
+# Copyright (C) 2012 Free Software Foundation, Inc.
+#
+# This file is part of GCC.
+#
+# GCC is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 3, or (at your option)
+# any later version.
+#
+# GCC is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with GCC; see the file COPYING.  If not, write to
+# the Free Software Foundation, 51 Franklin Street, Fifth Floor,
+# Boston, MA 02110-1301, USA.
+
+
+""" Compare two sets of compile-time performance numbers.
+
+The intent of this script is to compare compile-time performance of two
+different versions of the compiler.  Each version of the compiler must be
+run at least three times with the -ftime-report option.  Each log file
+represents a data point, or trial.  The set of trials for each compiler
+version constitutes a sample.  The ouput of the script is a description
+of the statistically significant difference between the two version of
+the compiler.
+
+The parameters to the script are:
+
+  Two file patterns that each match a set of log files.  You will probably
+  need to quote the patterns before passing them to the script.
+
+    Each pattern corresponds to a version of the compiler.
+
+  A regular expression that finds interesting lines in the log files.
+  If you want to match the beginning of the line, you will need to add
+  the ^ operator.  The filtering uses Python regular expression syntax.
+
+    The default is "TOTAL".
+
+    All of the interesting lines in a single log file are summed to produce
+    a single trial (data point).
+
+  A desired statistical confidence within the range 60% to 99.9%.  Due to
+  the implementation, this confidence will be rounded down to one of 60%,
+  70%, 80%, 90%, 95%, 98%, 99%, 99.5%, 99.8%, and 99.9%.
+
+    The default is 95.
+
+    If the computed confidence is lower than desired, the script will
+    estimate the number of trials needed to meet the desired confidence.
+    This estimate is not very good, as the variance tends to change as
+    you increase the number of trials.
+
+The most common use of the script is total compile-time comparison between
+logfiles stored in different directories.
+
+compare_two_ftime_report_sets "Log1/*perf" "Log2/*perf"
+
+One can also look at parsing time, but expecting a lower confidence.
+
+compare_two_ftime_report_sets "Log1/*perf" "Log2/*perf" "^phase parsing" 75
+
+"""
+
+
+import os
+import sys
+import fnmatch
+import glob
+import re
+import math
+
+
+####################################################################### Utility
+
+
+def divide(dividend, divisor):
+  """ Return the quotient, avoiding division by zero.
+  """
+  if divisor == 0:
+    return sys.float_info.max
+  else:
+    return dividend / divisor
+
+
+################################################################# File and Line
+
+
+# Should you repurpose this script, this code might help.
+#
+#def find_files(topdir, filepat):
+#  """ Find a set of file names, under a given directory,
+#  matching a Unix shell file pattern.
+#  Returns an iterator over the file names.
+#  """
+#  for path, dirlist, filelist in os.walk(topdir):
+#    for name in fnmatch.filter(filelist, filepat):
+#      yield os.path.join(path, name)
+
+
+def match_files(fileglob):
+  """ Find a set of file names matching a Unix shell glob pattern.
+  Returns an iterator over the file names.
+  """
+  return glob.iglob(os.path.expanduser(fileglob))
+
+
+def lines_in_file(filename):
+  """ Return an iterator over lines in the named file.  """
+  filedesc = open(filename, "r")
+  for line in filedesc:
+    yield line
+  filedesc.close()
+
+
+def lines_containing_pattern(pattern, lines):
+  """ Find lines by a Python regular-expression.
+  Returns an iterator over lines containing the expression.
+  """
+  parser = re.compile(pattern)
+  for line in lines:
+    if parser.search(line):
+      yield line
+
+
+############################################################# Number Formatting
+
+
+def strip_redundant_digits(numrep):
+  if numrep.find(".") == -1:
+    return numrep
+  return numrep.rstrip("0").rstrip(".")
+
+
+def text_number(number):
+  return strip_redundant_digits("%g" % number)
+
+
+def round_significant(digits, number):
+  if number == 0:
+    return 0
+  magnitude = abs(number)
+  significance = math.floor(math.log10(magnitude))
+  least_position = int(significance - digits + 1)
+  return round(number, -least_position)
+
+
+def text_significant(digits, number):
+  return text_number(round_significant(digits, number))
+
+
+def text_percent(number):
+  return text_significant(3, number*100) + "%"
+
+
+################################################################ T-Distribution
+
+
+# This section of code provides functions for using Student's t-distribution.
+
+
+# The functions are implemented using table lookup
+# to facilitate implementation of inverse functions.
+
+
+# The table is comprised of row 0 listing the alpha values,
+# column 0 listing the degree-of-freedom values,
+# and the other entries listing the corresponding t-distribution values.
+
+t_dist_table = [
+[  0, 0.200, 0.150, 0.100, 0.050, 0.025, 0.010, 0.005, .0025, 0.001, .0005],
+[  1, 1.376, 1.963, 3.078, 6.314, 12.71, 31.82, 63.66, 127.3, 318.3, 636.6],
+[  2, 1.061, 1.386, 1.886, 2.920, 4.303, 6.965, 9.925, 14.09, 22.33, 31.60],
+[  3, 0.978, 1.250, 1.638, 2.353, 3.182, 4.541, 5.841, 7.453, 10.21, 12.92],
+[  4, 0.941, 1.190, 1.533, 2.132, 2.776, 3.747, 4.604, 5.598, 7.173, 8.610],
+[  5, 0.920, 1.156, 1.476, 2.015, 2.571, 3.365, 4.032, 4.773, 5.894, 6.869],
+[  6, 0.906, 1.134, 1.440, 1.943, 2.447, 3.143, 3.707, 4.317, 5.208, 5.959],
+[  7, 0.896, 1.119, 1.415, 1.895, 2.365, 2.998, 3.499, 4.029, 4.785, 5.408],
+[  8, 0.889, 1.108, 1.397, 1.860, 2.306, 2.896, 3.355, 3.833, 4.501, 5.041],
+[  9, 0.883, 1.100, 1.383, 1.833, 2.262, 2.821, 3.250, 3.690, 4.297, 4.781],
+[ 10, 0.879, 1.093, 1.372, 1.812, 2.228, 2.764, 3.169, 3.581, 4.144, 4.587],
+[ 11, 0.876, 1.088, 1.363, 1.796, 2.201, 2.718, 3.106, 3.497, 4.025, 4.437],
+[ 12, 0.873, 1.083, 1.356, 1.782, 2.179, 2.681, 3.055, 3.428, 3.930, 4.318],
+[ 13, 0.870, 1.079, 1.350, 1.771, 2.160, 2.650, 3.012, 3.372, 3.852, 4.221],
+[ 14, 0.868, 1.076, 1.345, 1.761, 2.145, 2.624, 2.977, 3.326, 3.787, 4.140],
+[ 15, 0.866, 1.074, 1.341, 1.753, 2.131, 2.602, 2.947, 3.286, 3.733, 4.073],
+[ 16, 0.865, 1.071, 1.337, 1.746, 2.120, 2.583, 2.921, 3.252, 3.686, 4.015],
+[ 17, 0.863, 1.069, 1.333, 1.740, 2.110, 2.567, 2.898, 3.222, 3.646, 3.965],
+[ 18, 0.862, 1.067, 1.330, 1.734, 2.101, 2.552, 2.878, 3.197, 3.610, 3.922],
+[ 19, 0.861, 1.066, 1.328, 1.729, 2.093, 2.539, 2.861, 3.174, 3.579, 3.883],
+[ 20, 0.860, 1.064, 1.325, 1.725, 2.086, 2.528, 2.845, 3.153, 3.552, 3.850],
+[ 21, 0.859, 1.063, 1.323, 1.721, 2.080, 2.518, 2.831, 3.135, 3.527, 3.819],
+[ 22, 0.858, 1.061, 1.321, 1.717, 2.074, 2.508, 2.819, 3.119, 3.505, 3.792],
+[ 23, 0.858, 1.060, 1.319, 1.714, 2.069, 2.500, 2.807, 3.104, 3.485, 3.768],
+[ 24, 0.857, 1.059, 1.318, 1.711, 2.064, 2.492, 2.797, 3.091, 3.467, 3.745],
+[ 25, 0.856, 1.058, 1.316, 1.708, 2.060, 2.485, 2.787, 3.078, 3.450, 3.725],
+[ 26, 0.856, 1.058, 1.315, 1.706, 2.056, 2.479, 2.779, 3.067, 3.435, 3.707],
+[ 27, 0.855, 1.057, 1.314, 1.703, 2.052, 2.473, 2.771, 3.057, 3.421, 3.689],
+[ 28, 0.855, 1.056, 1.313, 1.701, 2.048, 2.467, 2.763, 3.047, 3.408, 3.674],
+[ 29, 0.854, 1.055, 1.311, 1.699, 2.045, 2.462, 2.756, 3.038, 3.396, 3.660],
+[ 30, 0.854, 1.055, 1.310, 1.697, 2.042, 2.457, 2.750, 3.030, 3.385, 3.646],
+[ 31, 0.853, 1.054, 1.309, 1.696, 2.040, 2.453, 2.744, 3.022, 3.375, 3.633],
+[ 32, 0.853, 1.054, 1.309, 1.694, 2.037, 2.449, 2.738, 3.015, 3.365, 3.622],
+[ 33, 0.853, 1.053, 1.308, 1.692, 2.035, 2.445, 2.733, 3.008, 3.356, 3.611],
+[ 34, 0.852, 1.052, 1.307, 1.691, 2.032, 2.441, 2.728, 3.002, 3.348, 3.601],
+[ 35, 0.852, 1.052, 1.306, 1.690, 2.030, 2.438, 2.724, 2.996, 3.340, 3.591],
+[ 36, 0.852, 1.052, 1.306, 1.688, 2.028, 2.434, 2.719, 2.990, 3.333, 3.582],
+[ 37, 0.851, 1.051, 1.305, 1.687, 2.026, 2.431, 2.715, 2.985, 3.326, 3.574],
+[ 38, 0.851, 1.051, 1.304, 1.686, 2.024, 2.429, 2.712, 2.980, 3.319, 3.566],
+[ 39, 0.851, 1.050, 1.304, 1.685, 2.023, 2.426, 2.708, 2.976, 3.313, 3.558],
+[ 40, 0.851, 1.050, 1.303, 1.684, 2.021, 2.423, 2.704, 2.971, 3.307, 3.551],
+[ 50, 0.849, 1.047, 1.299, 1.676, 2.009, 2.403, 2.678, 2.937, 3.261, 3.496],
+[ 60, 0.848, 1.045, 1.296, 1.671, 2.000, 2.390, 2.660, 2.915, 3.232, 3.460],
+[ 80, 0.846, 1.043, 1.292, 1.664, 1.990, 2.374, 2.639, 2.887, 3.195, 3.416],
+[100, 0.845, 1.042, 1.290, 1.660, 1.984, 2.364, 2.626, 2.871, 3.174, 3.390],
+[150, 0.844, 1.040, 1.287, 1.655, 1.976, 2.351, 2.609, 2.849, 3.145, 3.357] ]
+
+
+# The functions use the following parameter name conventions:
+# alpha - the alpha parameter
+# degree - the degree-of-freedom parameter
+# value - the t-distribution value for some alpha and degree
+# deviations - a confidence interval radius,
+#   expressed as a multiple of the standard deviation of the sample
+# ax - the alpha parameter index
+# dx - the degree-of-freedom parameter index
+
+# The interface to this section of code is the last three functions,
+# find_t_dist_value, find_t_dist_alpha, and find_t_dist_degree.
+
+
+def t_dist_alpha_at_index(ax):
+  if ax == 0:
+    return .25 # effectively no confidence
+  else:
+    return t_dist_table[0][ax]
+
+
+def t_dist_degree_at_index(dx):
+  return t_dist_table[dx][0]
+
+
+def t_dist_value_at_index(ax, dx):
+  return t_dist_table[dx][ax]
+
+
+def t_dist_index_of_degree(degree):
+  limit = len(t_dist_table) - 1
+  dx = 0
+  while dx < limit and t_dist_degree_at_index(dx+1) <= degree:
+    dx += 1
+  return dx
+
+
+def t_dist_index_of_alpha(alpha):
+  limit = len(t_dist_table[0]) - 1
+  ax = 0
+  while ax < limit and t_dist_alpha_at_index(ax+1) >= alpha:
+    ax += 1
+  return ax
+
+
+def t_dist_index_of_value(dx, value):
+  limit = len(t_dist_table[dx]) - 1
+  ax = 0
+  while ax < limit and t_dist_value_at_index(ax+1, dx) < value:
+    ax += 1
+  return ax
+
+
+def t_dist_value_within_deviations(dx, ax, deviations):
+  degree = t_dist_degree_at_index(dx)
+  count = degree + 1
+  root = math.sqrt(count)
+  value = t_dist_value_at_index(ax, dx)
+  nominal = value / root
+  comparison = nominal <= deviations
+  return comparison
+
+
+def t_dist_index_of_degree_for_deviations(ax, deviations):
+  limit = len(t_dist_table) - 1
+  dx = 1
+  while dx < limit and not t_dist_value_within_deviations(dx, ax, deviations):
+    dx += 1
+  return dx
+
+
+def find_t_dist_value(alpha, degree):
+  """ Return the t-distribution value.
+  The parameters are alpha and degree of freedom.
+  """
+  dx = t_dist_index_of_degree(degree)
+  ax = t_dist_index_of_alpha(alpha)
+  return t_dist_value_at_index(ax, dx)
+
+
+def find_t_dist_alpha(value, degree):
+  """ Return the alpha.
+  The parameters are the t-distribution value for a given degree of freedom.
+  """
+  dx = t_dist_index_of_degree(degree)
+  ax = t_dist_index_of_value(dx, value)
+  return t_dist_alpha_at_index(ax)
+
+
+def find_t_dist_degree(alpha, deviations):
+  """ Return the degree-of-freedom.
+  The parameters are the desired alpha and the number of standard deviations
+  away from the mean that the degree should handle.
+  """
+  ax = t_dist_index_of_alpha(alpha)
+  dx = t_dist_index_of_degree_for_deviations(ax, deviations)
+  return t_dist_degree_at_index(dx)
+
+
+############################################################## Core Statistical
+
+
+# This section provides the core statistical classes and functions.
+
+
+class Accumulator:
+
+  """ An accumulator for statistical information using arithmetic mean.  """
+
+  def __init__(self):
+    self.count = 0
+    self.mean = 0
+    self.sumsqdiff = 0
+
+  def insert(self, value):
+    self.count += 1
+    diff = value - self.mean
+    self.mean += diff / self.count
+    self.sumsqdiff += (self.count - 1) * diff * diff / self.count
+
+
+def fill_accumulator_from_values(values):
+  accumulator = Accumulator()
+  for value in values:
+    accumulator.insert(value)
+  return accumulator
+
+
+def alpha_from_confidence(confidence):
+  scrubbed = min(99.99, max(confidence, 60))
+  return (100.0 - scrubbed) / 200.0
+
+
+def confidence_from_alpha(alpha):
+  return 100 - 200 * alpha
+
+
+class Sample:
+
+  """ A description of a sample using an arithmetic mean.  """
+
+  def __init__(self, accumulator, alpha):
+    if accumulator.count < 3:
+      sys.exit("Samples must contain three trials.")
+    self.count = accumulator.count
+    self.mean = accumulator.mean
+    variance = accumulator.sumsqdiff / (self.count - 1)
+    self.deviation = math.sqrt(variance)
+    self.error = self.deviation / math.sqrt(self.count)
+    self.alpha = alpha
+    self.radius = find_t_dist_value(alpha, self.count - 1) * self.error
+
+  def alpha_for_radius(self, radius):
+    return find_t_dist_alpha(divide(radius, self.error), self.count)
+
+  def degree_for_radius(self, radius):
+    return find_t_dist_degree(self.alpha, divide(radius, self.deviation))
+
+  def __str__(self):
+    text = "trial count is " + text_number(self.count)
+    text += ", mean is " + text_number(self.mean)
+    text += " (" + text_number(confidence_from_alpha(self.alpha)) +"%"
+    text += " confidence in " + text_number(self.mean - self.radius)
+    text += " to " + text_number(self.mean + self.radius) + ")"
+    text += ",\nstd.deviation is " + text_number(self.deviation)
+    text += ", std.error is " + text_number(self.error)
+    return text
+
+
+def sample_from_values(values, alpha):
+  accumulator = fill_accumulator_from_values(values)
+  return Sample(accumulator, alpha)
+
+
+class Comparison:
+
+  """ A comparison of two samples using arithmetic means.  """
+
+  def __init__(self, first, second, alpha):
+    if first.mean > second.mean:
+      self.upper = first
+      self.lower = second
+      self.larger = "first"
+    else:
+      self.upper = second
+      self.lower = first
+      self.larger = "second"
+    self.a_wanted = alpha
+    radius = self.upper.mean - self.lower.mean
+    rising = self.lower.alpha_for_radius(radius)
+    falling = self.upper.alpha_for_radius(radius)
+    self.a_actual = max(rising, falling)
+    rising = self.lower.degree_for_radius(radius)
+    falling = self.upper.degree_for_radius(radius)
+    self.count = max(rising, falling) + 1
+
+  def __str__(self):
+    message = "The " + self.larger + " sample appears to be "
+    change = divide(self.upper.mean, self.lower.mean) - 1
+    message += text_percent(change) + " larger,\n"
+    confidence = confidence_from_alpha(self.a_actual)
+    if confidence >= 60:
+      message += "with " + text_number(confidence) + "% confidence"
+      message += " of being larger."
+    else:
+      message += "but with no confidence of actually being larger."
+    if self.a_actual > self.a_wanted:
+      confidence = confidence_from_alpha(self.a_wanted)
+      message += "\nTo reach " + text_number(confidence) + "% confidence,"
+      if self.count < 100:
+        message += " you need roughly " + text_number(self.count) + "
trials,\n"
+        message += "assuming the standard deviation is stable, which is iffy."
+      else:
+        message += "\nyou need to reduce the larger deviation"
+        message += " or increase the number of trials."
+    return message
+
+
+############################################################ Single Value Files
+
+
+# This section provides functions to compare two raw data files,
+# each containing a whole sample consisting of single number per line.
+
+
+# Should you repurpose this script, this code might help.
+#
+#def values_from_data_file(filename):
+#  for line in lines_in_file(filename):
+#    yield float(line)
+
+
+# Should you repurpose this script, this code might help.
+#
+#def sample_from_data_file(filename, alpha):
+#  confidence = confidence_from_alpha(alpha)
+#  text = "\nArithmetic sample for data file\n\"" + filename + "\""
+#  text += " with desired confidence " + text_number(confidence) + " is "
+#  print text
+#  values = values_from_data_file(filename)
+#  sample = sample_from_values(values, alpha)
+#  print sample
+#  return sample
+
+
+# Should you repurpose this script, this code might help.
+#
+#def compare_two_data_files(filename1, filename2, confidence):
+#  alpha = alpha_from_confidence(confidence)
+#  sample1 = sample_from_data_file(filename1, alpha)
+#  sample2 = sample_from_data_file(filename2, alpha)
+#  print
+#  print Comparison(sample1, sample2, alpha)
+
+
+# Should you repurpose this script, this code might help.
+#
+#def command_two_data_files():
+#  argc = len(sys.argv)
+#  if argc < 2 or 4 < argc:
+#    message = "usage: " + sys.argv[0]
+#    message += " file-name file-name [confidence]"
+#    print message
+#  else:
+#    filename1 = sys.argv[1]
+#    filename2 = sys.argv[2]
+#    if len(sys.argv) >= 4:
+#      confidence = int(sys.argv[3])
+#    else:
+#      confidence = 95
+#  compare_two_data_files(filename1, filename2, confidence)
+
+
+############################################### -ftime-report TimeVar Log Files
+
+
+# This section provides functions to compare two sets of -ftime-report log
+# files.  Each set is a sample, where each data point is derived from the
+# sum of values in a single log file.
+
+
+label = r"^ *([^:]*[^: ]) *:"
+number = r" *([0-9.]*) *"
+percent = r"\( *[0-9]*\%\)"
+numpct = number + percent
+total_format = label + number + number + number + number + " kB\n"
+total_parser = re.compile(total_format)
+tmvar_format = label + numpct + " usr" + numpct + " sys"
+tmvar_format += numpct + " wall" + number + " kB " + percent + " ggc\n"
+tmvar_parser = re.compile(tmvar_format)
+replace = r"\2\t\3\t\4\t\5\t\1"
+
+
+def split_time_report(lines, pattern):
+  if pattern == "TOTAL":
+    parser = total_parser
+  else:
+    parser = tmvar_parser
+  for line in lines:
+    modified = parser.sub(replace, line)
+    if modified != line:
+      yield re.split("\t", modified)
+
+
+def extract_cpu_time(tvtuples):
+  for tuple in tvtuples:
+    yield float(tuple[0]) + float(tuple[1])
+
+
+def sum_values(values):
+  sum = 0
+  for value in values:
+    sum += value
+  return sum
+
+
+def extract_time_for_timevar_log(filename, pattern):
+  lines = lines_in_file(filename)
+  tmvars = lines_containing_pattern(pattern, lines)
+  tuples = split_time_report(tmvars, pattern)
+  times = extract_cpu_time(tuples)
+  return sum_values(times)
+
+
+def extract_times_for_timevar_logs(filelist, pattern):
+  for filename in filelist:
+    yield extract_time_for_timevar_log(filename, pattern)
+
+
+def sample_from_timevar_logs(fileglob, pattern, alpha):
+  confidence = confidence_from_alpha(alpha)
+  text = "\nArithmetic sample for timevar log files\n\"" + fileglob + "\""
+  text += "\nand selecting lines containing \"" + pattern + "\""
+  text += " with desired confidence " + text_number(confidence) + " is "
+  print text
+  filelist = match_files(fileglob)
+  values = extract_times_for_timevar_logs(filelist, pattern)
+  sample = sample_from_values(values, alpha)
+  print sample
+  return sample
+
+
+def compare_two_timevar_logs(fileglob1, fileglob2, pattern, confidence):
+  alpha = alpha_from_confidence(confidence)
+  sample1 = sample_from_timevar_logs(fileglob1, pattern, alpha)
+  sample2 = sample_from_timevar_logs(fileglob2, pattern, alpha)
+  print
+  print Comparison(sample1, sample2, alpha)
+
+
+def command_two_timevar_logs():
+  argc = len(sys.argv)
+  if argc < 3 or 5 < argc:
+    message = "usage: " + sys.argv[0]
+    message += " file-pattern file-pattern [line-pattern [confidence]]"
+    print message
+  else:
+    filepat1 = sys.argv[1]
+    filepat2 = sys.argv[2]
+    if len(sys.argv) >= 5:
+      confidence = int(sys.argv[4])
+    else:
+      confidence = 95
+    if len(sys.argv) >= 4:
+      linepat = sys.argv[3]
+    else:
+      linepat = "TOTAL"
+    compare_two_timevar_logs(filepat1, filepat2, linepat, confidence)
+
+
+########################################################################## Main
+
+
+# This section is the main code, implementing the command.
+
+
