Move statistical functions in bisect script to their own module.

tools/bisect-perf-regression.py

 #!/usr/bin/env python
 # Copyright (c) 2013 The Chromium Authors. All rights reserved.
 # Use of this source code is governed by a BSD-style license that can be
 # found in the LICENSE file.
 
 """Performance Test Bisect Tool
 
 This script bisects a series of changelists using binary search. It starts at
 a bad revision where a performance metric has regressed, and asks for a last
 known-good revision. It will then binary search across this revision range by
@@ skipping 14 matching lines @@
 revision were merged in.
 
 
 An example usage (using git hashes):
 
 ./tools/bisect-perf-regression.py -c\
 "out/Release/performance_ui_tests --gtest_filter=ShutdownTest.SimpleUserQuit"\
 -g 1f6e67861535121c5c819c16a666f2436c207e7b\
 -b b732f23b4f81c382db0b23b9035f3dadc7d925bb\
 -m shutdown/simple-user-quit
-
 """
 
 import copy
 import datetime
 import errno
 import hashlib
 import math
 import optparse
 import os
 import re
 import shlex
 import shutil
 import StringIO
 import sys
 import time
 import zipfile
 
 sys.path.append(os.path.join(os.path.dirname(__file__), 'telemetry'))
 
 from auto_bisect import bisect_utils
+from auto_bisect import math_utils
 from auto_bisect import post_perf_builder_job as bisect_builder
 from auto_bisect import source_control as source_control_module
 from telemetry.util import cloud_storage
 
 # The additional repositories that might need to be bisected.
 # If the repository has any dependant repositories (such as skia/src needs
 # skia/include and skia/gyp to be updated), specify them in the 'depends'
 # so that they're synced appropriately.
 # Format is:
 # src: path to the working directory.
@@ skipping 186 matching lines @@
 
 def _AddAdditionalDepotInfo(depot_info):
   """Adds additional depot info to the global depot variables."""
   global DEPOT_DEPS_NAME
   global DEPOT_NAMES
   DEPOT_DEPS_NAME = dict(DEPOT_DEPS_NAME.items() +
       depot_info.items())
   DEPOT_NAMES = DEPOT_DEPS_NAME.keys()
 
 
-def CalculateTruncatedMean(data_set, truncate_percent):
-  """Calculates the truncated mean of a set of values.
-
-  Note that this isn't just the mean of the set of values with the highest
-  and lowest values discarded; the non-discarded values are also weighted
-  differently depending how many values are discarded.
-
-  Args:
-    data_set: Non-empty list of values.
-    truncate_percent: The % from the upper and lower portions of the data set
-        to discard, expressed as a value in [0, 1].
-
-  Returns:
-    The truncated mean as a float.
-
-  Raises:
-    TypeError: The data set was empty after discarding values.
-  """
-  if len(data_set) > 2:
-    data_set = sorted(data_set)
-
-    discard_num_float = len(data_set) * truncate_percent
-    discard_num_int = int(math.floor(discard_num_float))
-    kept_weight = len(data_set) - discard_num_float * 2
-
-    data_set = data_set[discard_num_int:len(data_set)-discard_num_int]
-
-    weight_left = 1.0 - (discard_num_float - discard_num_int)
-
-    if weight_left < 1:
-      # If the % to discard leaves a fractional portion, need to weight those
-      # values.
-      unweighted_vals = data_set[1:len(data_set)-1]
-      weighted_vals = [data_set[0], data_set[len(data_set)-1]]
-      weighted_vals = [w * weight_left for w in weighted_vals]
-      data_set = weighted_vals + unweighted_vals
-  else:
-    kept_weight = len(data_set)
-
-  truncated_mean = reduce(lambda x, y: float(x) + float(y),
-                          data_set) / kept_weight
-
-  return truncated_mean
-
-
-def CalculateMean(values):
-  """Calculates the arithmetic mean of a list of values."""
-  return CalculateTruncatedMean(values, 0.0)
-
-
-def CalculateConfidence(good_results_lists, bad_results_lists):
+def ConfidenceScore(good_results_lists, bad_results_lists):
   """Calculates a confidence percentage.
 
   This is calculated based on how distinct the "good" and "bad" values are,
   and how noisy the results are. More precisely, the confidence is the quotient
   of the difference between the closest values across the good and bad groups
   and the sum of the standard deviations of the good and bad groups.
 
   TODO(qyearsley): Replace this confidence function with a function that
       uses a Student's t-test. The confidence would be (1 - p-value), where
       p-value is the probability of obtaining the given a set of good and bad
       values just by chance.
 
   Args:
     good_results_lists: A list of lists of "good" result numbers.
     bad_results_lists: A list of lists of "bad" result numbers.
 
   Returns:
     A number between in the range [0, 100].
   """
   # Get the distance between the two groups.
-  means_good = map(CalculateMean, good_results_lists)
-  means_bad = map(CalculateMean, bad_results_lists)
+  means_good = map(math_utils.Mean, good_results_lists)
+  means_bad = map(math_utils.Mean, bad_results_lists)
   bounds_good = (min(means_good), max(means_good))
   bounds_bad = (min(means_bad), max(means_bad))
   dist_between_groups = min(
       math.fabs(bounds_bad[1] - bounds_good[0]),
       math.fabs(bounds_bad[0] - bounds_good[1]))
 
   # Get the sum of the standard deviations of the two groups.
   good_results_flattened = sum(good_results_lists, [])
   bad_results_flattened = sum(bad_results_lists, [])
-  stddev_good = CalculateStandardDeviation(good_results_flattened)
-  stddev_bad = CalculateStandardDeviation(bad_results_flattened)
+  stddev_good = math_utils.StandardDeviation(good_results_flattened)
+  stddev_bad = math_utils.StandardDeviation(bad_results_flattened)
   stddev_sum = stddev_good + stddev_bad
 
   confidence = dist_between_groups / (max(0.0001, stddev_sum))
   confidence = int(min(1.0, max(confidence, 0.0)) * 100.0)
   return confidence
 
 
-def CalculateStandardDeviation(values):
-  """Calculates the sample standard deviation of the given list of values."""
-  if len(values) == 1:
-    return 0.0
-
-  mean = CalculateMean(values)
-  differences_from_mean = [float(x) - mean for x in values]
-  squared_differences = [float(x * x) for x in differences_from_mean]
-  variance = sum(squared_differences) / (len(values) - 1)
-  std_dev = math.sqrt(variance)
-
-  return std_dev
-
-
-def CalculateRelativeChange(before, after):
-  """Returns the relative change of before and after, relative to before.
-
-  There are several different ways to define relative difference between
-  two numbers; sometimes it is defined as relative to the smaller number,
-  or to the mean of the two numbers. This version returns the difference
-  relative to the first of the two numbers.
-
-  Args:
-    before: A number representing an earlier value.
-    after: Another number, representing a later value.
-
-  Returns:
-    A non-negative floating point number; 0.1 represents a 10% change.
-  """
-  if before == after:
-    return 0.0
-  if before == 0:
-    return float('nan')
-  difference = after - before
-  return math.fabs(difference / before)
-
-
-def CalculatePooledStandardError(work_sets):
-  numerator = 0.0
-  denominator1 = 0.0
-  denominator2 = 0.0
-
-  for current_set in work_sets:
-    std_dev = CalculateStandardDeviation(current_set)
-    numerator += (len(current_set) - 1) * std_dev ** 2
-    denominator1 += len(current_set) - 1
-    denominator2 += 1.0 / len(current_set)
-
-  if denominator1:
-    return math.sqrt(numerator / denominator1) * math.sqrt(denominator2)
-  return 0.0
-
-
-def CalculateStandardError(values):
-  """Calculates the standard error of a list of values."""
-  if len(values) <= 1:
-    return 0.0
-
-  std_dev = CalculateStandardDeviation(values)
-
-  return std_dev / math.sqrt(len(values))
-
-
-
-
 def GetSHA1HexDigest(contents):
   """Returns secured hash containing hexadecimal for the given contents."""
   return hashlib.sha1(contents).hexdigest()
 
 
 def GetZipFileName(build_revision=None, target_arch='ia32', patch_sha=None):
   """Gets the archive file name for the given revision."""
   def PlatformName():
     """Return a string to be used in paths for the platform."""
     if bisect_utils.IsWindowsHost():
@@ skipping 1546 matching lines @@
         'std_err': 0.0,
         'std_dev': 0.0,
         'values': metric_values,
       }
 
       print 'Results of performance test: Command returned with %d' % (
           overall_return_code)
       print
     else:
       # Need to get the average value if there were multiple values.
-      truncated_mean = CalculateTruncatedMean(metric_values,
-          self.opts.truncate_percent)
-      standard_err = CalculateStandardError(metric_values)
-      standard_dev = CalculateStandardDeviation(metric_values)
+      truncated_mean = math_utils.TruncatedMean(
+          metric_values, self.opts.truncate_percent)
+      standard_err = math_utils.StandardError(metric_values)
+      standard_dev = math_utils.StandardDeviation(metric_values)
 
       if self._IsBisectModeStandardDeviation():
         metric_values = [standard_dev]
 
       values = {
         'mean': truncated_mean,
         'std_err': standard_err,
         'std_dev': standard_dev,
         'values': metric_values,
       }
@@ skipping 1169 matching lines @@
 
   def _FindOtherRegressions(self, revision_data_sorted, bad_greater_than_good):
     other_regressions = []
     previous_values = []
     previous_id = None
     for current_id, current_data in revision_data_sorted:
       current_values = current_data['value']
       if current_values:
         current_values = current_values['values']
         if previous_values:
-          confidence = CalculateConfidence(previous_values, [current_values])
-          mean_of_prev_runs = CalculateMean(sum(previous_values, []))
-          mean_of_current_runs = CalculateMean(current_values)
+          confidence = ConfidenceScore(previous_values, [current_values])
+          mean_of_prev_runs = math_utils.Mean(sum(previous_values, []))
+          mean_of_current_runs = math_utils.Mean(current_values)
 
           # Check that the potential regression is in the same direction as
           # the overall regression. If the mean of the previous runs < the
           # mean of the current runs, this local regression is in same
           # direction.
           prev_less_than_current = mean_of_prev_runs < mean_of_current_runs
           is_same_direction = (prev_less_than_current if
               bad_greater_than_good else not prev_less_than_current)
 
           # Only report potential regressions with high confidence.
@@ skipping 31 matching lines @@
       working_means = []
       for i in xrange(first_working_revision_index, len(revision_data_sorted)):
         if revision_data_sorted[i][1]['value']:
           working_means.append(revision_data_sorted[i][1]['value']['values'])
 
       # Flatten the lists to calculate mean of all values.
       working_mean = sum(working_means, [])
       broken_mean = sum(broken_means, [])
 
       # Calculate the approximate size of the regression
-      mean_of_bad_runs = CalculateMean(broken_mean)
-      mean_of_good_runs = CalculateMean(working_mean)
+      mean_of_bad_runs = math_utils.Mean(broken_mean)
+      mean_of_good_runs = math_utils.Mean(working_mean)
 
-      regression_size = 100 * CalculateRelativeChange(mean_of_good_runs,
+      regression_size = 100 * math_utils.RelativeChange(mean_of_good_runs,
                                                       mean_of_bad_runs)
       if math.isnan(regression_size):
         regression_size = 'zero-to-nonzero'
 
-      regression_std_err = math.fabs(CalculatePooledStandardError(
+      regression_std_err = math.fabs(math_utils.PooledStandardError(
           [working_mean, broken_mean]) /
           max(0.0001, min(mean_of_good_runs, mean_of_bad_runs))) * 100.0
 
       # Give a "confidence" in the bisect. At the moment we use how distinct the
       # values are before and after the last broken revision, and how noisy the
       # overall graph is.
-      confidence = CalculateConfidence(working_means, broken_means)
+      confidence = ConfidenceScore(working_means, broken_means)
 
       culprit_revisions = []
 
       cwd = os.getcwd()
       self.ChangeToDepotWorkingDirectory(
           revision_data[last_broken_revision]['depot'])
 
       if revision_data[last_broken_revision]['depot'] == 'cros':
         # Want to get a list of all the commits and what depots they belong
         # to so that we can grab info about each.
@@ skipping 507 matching lines @@
   except RuntimeError, e:
     if opts.output_buildbot_annotations:
       # The perf dashboard scrapes the "results" step in order to comment on
       # bugs. If you change this, please update the perf dashboard as well.
       bisect_utils.OutputAnnotationStepStart('Results')
     print 'Error: %s' % e.message
     if opts.output_buildbot_annotations:
       bisect_utils.OutputAnnotationStepClosed()
   return 1
 
+
 if __name__ == '__main__':
   sys.exit(main())