bench/bench_util.py

'''
Created on May 19, 2011

@author: bungeman
'''

import re
import math

# bench representation algorithm constant names
ALGORITHM_AVERAGE = 'avg'
ALGORITHM_MEDIAN = 'med'
ALGORITHM_MINIMUM = 'min'
ALGORITHM_25TH_PERCENTILE = '25th'

# Regular expressions used throughout.
PER_SETTING_RE = '([^\s=]+)(?:=(\S+))?'
SETTINGS_RE = 'skia bench:((?:\s+' + PER_SETTING_RE + ')*)'
BENCH_RE = 'running bench (?:\[\d+ \d+\] )?\s*(\S+)'
TIME_RE = '(?:(\w*)msecs = )?\s*((?:\d+\.\d+)(?:,\s*\d+\.\d+)*)'
# non-per-tile benches have configs that don't end with ']' or '>'
CONFIG_RE = '(\S+[^\]>]):\s+((?:' + TIME_RE + '\s+)+)'
# per-tile bench lines are in the following format. Note that there are
# non-averaged bench numbers in separate lines, which we ignore now due to
# their inaccuracy.
TILE_RE = ('  tile_(\S+): tile \[\d+,\d+\] out of \[\d+,\d+\] <averaged>:'
           ' ((?:' + TIME_RE + '\s+)+)')
# for extracting tile layout
TILE_LAYOUT_RE = ' out of \[(\d+),(\d+)\] <averaged>: '

PER_SETTING_RE_COMPILED = re.compile(PER_SETTING_RE)
SETTINGS_RE_COMPILED = re.compile(SETTINGS_RE)
BENCH_RE_COMPILED = re.compile(BENCH_RE)
TIME_RE_COMPILED = re.compile(TIME_RE)
CONFIG_RE_COMPILED = re.compile(CONFIG_RE)
TILE_RE_COMPILED = re.compile(TILE_RE)
TILE_LAYOUT_RE_COMPILED = re.compile(TILE_LAYOUT_RE)

class BenchDataPoint:
    """A single data point produced by bench.
    """
    def __init__(self, bench, config, time_type, time, settings,
                 tile_layout='', per_tile_values=[], per_iter_time=[]):
        # string name of the benchmark to measure
        self.bench = bench
        # string name of the configurations to run
        self.config = config
        # type of the timer in string: '' (walltime), 'c' (cpu) or 'g' (gpu)
        self.time_type = time_type
        # float number of the bench time value
        self.time = time
        # dictionary of the run settings
        self.settings = settings
        # how tiles cover the whole picture: '5x3' means 5 columns and 3 rows
        self.tile_layout = tile_layout
        # list of float for per_tile bench values, if applicable
        self.per_tile_values = per_tile_values
        # list of float for per-iteration bench time, if applicable
        self.per_iter_time = per_iter_time

    def __repr__(self):
        return "BenchDataPoint(%s, %s, %s, %s, %s)" % (
                   str(self.bench),
                   str(self.config),
                   str(self.time_type),
                   str(self.time),
                   str(self.settings),
               )

class _ExtremeType(object):
    """Instances of this class compare greater or less than other objects."""
    def __init__(self, cmpr, rep):
        object.__init__(self)
        self._cmpr = cmpr
        self._rep = rep

    def __cmp__(self, other):
        if isinstance(other, self.__class__) and other._cmpr == self._cmpr:
            return 0
        return self._cmpr

    def __repr__(self):
        return self._rep

Max = _ExtremeType(1, "Max")
Min = _ExtremeType(-1, "Min")

class _ListAlgorithm(object):
    """Algorithm for selecting the representation value from a given list.
    representation is one of the ALGORITHM_XXX representation types."""
    def __init__(self, data, representation=None):
        if not representation:
            representation = ALGORITHM_AVERAGE  # default algorithm
        self._data = data
        self._len = len(data)
        if representation == ALGORITHM_AVERAGE:
            self._rep = sum(self._data) / self._len
        else:
            self._data.sort()
            if representation == ALGORITHM_MINIMUM:
                self._rep = self._data[0]
            else:
                # for percentiles, we use the value below which x% of values are
                # found, which allows for better detection of quantum behaviors.
                if representation == ALGORITHM_MEDIAN:
                    x = int(round(0.5 * self._len + 0.5))
                elif representation == ALGORITHM_25TH_PERCENTILE:
                    x = int(round(0.25 * self._len + 0.5))
                else:
                    raise Exception("invalid representation algorithm %s!" %
                                    representation)
                self._rep = self._data[x - 1]

    def compute(self):
        return self._rep

def _ParseAndStoreTimes(config_re_compiled, is_per_tile, line, bench,
                        value_dic, layout_dic):
    """Parses given bench time line with regex and adds data to value_dic.

    config_re_compiled: precompiled regular expression for parsing the config
        line.
    is_per_tile: boolean indicating whether this is a per-tile bench.
        If so, we add tile layout into layout_dic as well.
    line: input string line to parse.
    bench: name of bench for the time values.
    value_dic: dictionary to store bench values. See bench_dic in parse() below.
    layout_dic: dictionary to store tile layouts. See parse() for descriptions.
    """

    for config in config_re_compiled.finditer(line):
        current_config = config.group(1)
        tile_layout = ''
        if is_per_tile:  # per-tile bench, add name prefix
            current_config = 'tile_' + current_config
            layouts = TILE_LAYOUT_RE_COMPILED.search(line)
            if layouts and len(layouts.groups()) == 2:
              tile_layout = '%sx%s' % layouts.groups()
        times = config.group(2)
        for new_time in TIME_RE_COMPILED.finditer(times):
            current_time_type = new_time.group(1)
            iters = [float(i) for i in
                     new_time.group(2).strip().split(',')]
            value_dic.setdefault(bench, {}).setdefault(
                current_config, {}).setdefault(current_time_type, []).append(
                    iters)
            layout_dic.setdefault(bench, {}).setdefault(
                current_config, {}).setdefault(current_time_type, tile_layout)

# TODO(bensong): switch to reading JSON output when available. This way we don't
# need the RE complexities.
def parse(settings, lines, representation=None):
    """Parses bench output into a useful data structure.

    ({str:str}, __iter__ -> str) -> [BenchDataPoint]
    representation is one of the ALGORITHM_XXX types."""

    benches = []
    current_bench = None
    # [bench][config][time_type] -> [[per-iter values]] where per-tile config
    # has per-iter value list for each tile [[<tile1_iter1>,<tile1_iter2>,...],
    # [<tile2_iter1>,<tile2_iter2>,...],...], while non-per-tile config only
    # contains one list of iterations [[iter1, iter2, ...]].
    bench_dic = {}
    # [bench][config][time_type] -> tile_layout
    layout_dic = {}

    for line in lines:

        # see if this line is a settings line
        settingsMatch = SETTINGS_RE_COMPILED.search(line)
        if (settingsMatch):
            settings = dict(settings)
            for settingMatch in PER_SETTING_RE_COMPILED.finditer(settingsMatch.group(1)):
                if (settingMatch.group(2)):
                    settings[settingMatch.group(1)] = settingMatch.group(2)
                else:
                    settings[settingMatch.group(1)] = True

        # see if this line starts a new bench
        new_bench = BENCH_RE_COMPILED.search(line)
        if new_bench:
            current_bench = new_bench.group(1)

        # add configs on this line to the bench_dic
        if current_bench:
            if line.startswith('  tile_') :
                _ParseAndStoreTimes(TILE_RE_COMPILED, True, line, current_bench,
                                    bench_dic, layout_dic)
            else:
                _ParseAndStoreTimes(CONFIG_RE_COMPILED, False, line,
                                    current_bench, bench_dic, layout_dic)

    # append benches to list
    for bench in bench_dic:
        for config in bench_dic[bench]:
            for time_type in bench_dic[bench][config]:
                tile_layout = ''
                per_tile_values = []  # empty for non-per-tile configs
                per_iter_time = []  # empty for per-tile configs
                bench_summary = None  # a single final bench value
                if len(bench_dic[bench][config][time_type]) > 1:
                    # per-tile config; compute representation for each tile
                    per_tile_values = [
                        _ListAlgorithm(iters, representation).compute()
                            for iters in bench_dic[bench][config][time_type]]
                    # use sum of each tile representation for total bench value
                    bench_summary = sum(per_tile_values)
                    # extract tile layout
                    tile_layout = layout_dic[bench][config][time_type]
                else:
                    # get the list of per-iteration values
                    per_iter_time = bench_dic[bench][config][time_type][0]
                    bench_summary = _ListAlgorithm(
                        per_iter_time, representation).compute()
                benches.append(BenchDataPoint(
                    bench,
                    config,
                    time_type,
                    bench_summary,
                    settings,
                    tile_layout,
                    per_tile_values,
                    per_iter_time))

    return benches

class LinearRegression:
    """Linear regression data based on a set of data points.

    ([(Number,Number)])
    There must be at least two points for this to make sense."""
    def __init__(self, points):
        n = len(points)
        max_x = Min
        min_x = Max

        Sx = 0.0
        Sy = 0.0
        Sxx = 0.0
        Sxy = 0.0
        Syy = 0.0
        for point in points:
            x = point[0]
            y = point[1]
            max_x = max(max_x, x)
            min_x = min(min_x, x)

            Sx += x
            Sy += y
            Sxx += x*x
            Sxy += x*y
            Syy += y*y

        denom = n*Sxx - Sx*Sx
        if (denom != 0.0):
            B = (n*Sxy - Sx*Sy) / denom
        else:
            B = 0.0
        a = (1.0/n)*(Sy - B*Sx)

        se2 = 0
        sB2 = 0
        sa2 = 0
        if (n >= 3 and denom != 0.0):
            se2 = (1.0/(n*(n-2)) * (n*Syy - Sy*Sy - B*B*denom))
            sB2 = (n*se2) / denom
            sa2 = sB2 * (1.0/n) * Sxx


        self.slope = B
        self.intercept = a
        self.serror = math.sqrt(max(0, se2))
        self.serror_slope = math.sqrt(max(0, sB2))
        self.serror_intercept = math.sqrt(max(0, sa2))
        self.max_x = max_x
        self.min_x = min_x

    def __repr__(self):
        return "LinearRegression(%s, %s, %s, %s, %s)" % (
                   str(self.slope),
                   str(self.intercept),
                   str(self.serror),
                   str(self.serror_slope),
                   str(self.serror_intercept),
               )

    def find_min_slope(self):
        """Finds the minimal slope given one standard deviation."""
        slope = self.slope
        intercept = self.intercept
        error = self.serror
        regr_start = self.min_x
        regr_end = self.max_x
        regr_width = regr_end - regr_start

        if slope < 0:
            lower_left_y = slope*regr_start + intercept - error
            upper_right_y = slope*regr_end + intercept + error
            return min(0, (upper_right_y - lower_left_y) / regr_width)

        elif slope > 0:
            upper_left_y = slope*regr_start + intercept + error
            lower_right_y = slope*regr_end + intercept - error
            return max(0, (lower_right_y - upper_left_y) / regr_width)

        return 0

def CreateRevisionLink(revision_number):
    """Returns HTML displaying the given revision number and linking to
    that revision's change page at code.google.com, e.g.
    http://code.google.com/p/skia/source/detail?r=2056
    """
    return '<a href="http://code.google.com/p/skia/source/detail?r=%s">%s</a>'%(
        revision_number, revision_number)

def main():
    foo = [[0.0, 0.0], [0.0, 1.0], [0.0, 2.0], [0.0, 3.0]]
    LinearRegression(foo)

if __name__ == "__main__":
    main()