From 85669f9d77117329f4dbe9d219cc97f4f72b9137 Mon Sep 17 00:00:00 2001
From: "bungeman@google.com"
 <bungeman@google.com@2bbb7eff-a529-9590-31e7-b0007b416f81>
Date: Fri, 17 Jun 2011 13:58:14 +0000
Subject: [PATCH] Add graphing for multiple runs of bench.
 http://codereview.appspot.com/4539087/

git-svn-id: http://skia.googlecode.com/svn/trunk@1628 2bbb7eff-a529-9590-31e7-b0007b416f81
---
 bench/bench_compare.py   | 109 ++++----
 bench/bench_graph_svg.py | 671 +++++++++++++++++++++++++++++++++++++++++++++++
 bench/bench_util.py      | 170 ++++++++++++
 3 files changed, 900 insertions(+), 50 deletions(-)
 create mode 100644 bench/bench_graph_svg.py
 create mode 100644 bench/bench_util.py

diff --git a/bench/bench_compare.py b/bench/bench_compare.py
index f6909b1..c1a1ff9 100644
--- a/bench/bench_compare.py
+++ b/bench/bench_compare.py
@@ -5,31 +5,7 @@ Created on May 16, 2011
 '''
 import sys
 import getopt
-import re
-
-def parse(lines):
-    """Takes iterable lines of bench output, returns {bench:{config:time}}."""
-    
-    benches = {}
-    current_bench = None
-    
-    for line in lines:
-        #see if this line starts a new bench
-        new_bench = re.search('running bench \[\d+ \d+\] (.{28})', line)
-        if new_bench:
-            current_bench = new_bench.group(1)
-        
-        #add configs on this line to the current bench
-        if current_bench:
-            for new_config in re.finditer('  (.{4}): msecs = (\d+\.\d+)', line):
-                current_config = new_config.group(1)
-                current_time = float(new_config.group(2))
-                if current_bench in benches:
-                    benches[current_bench][current_config] = current_time
-                else:
-                    benches[current_bench] = {current_config : current_time}
-    
-    return benches
+import bench_util
 
 def usage():
     """Prints simple usage information."""
@@ -38,20 +14,39 @@ def usage():
     print '-n <file> the new bench output file.'
     print '-h causes headers to be output.'
     print '-f <fieldSpec> which fields to output and in what order.'
-    print '   Not specifying is the same as -f "bcondp".'
+    print '   Not specifying is the same as -f "bctondp".'
     print '  b: bench'
     print '  c: config'
+    print '  t: time type'
     print '  o: old time'
     print '  n: new time'
     print '  d: diff'
     print '  p: percent diff'
     
-    
+class BenchDiff:
+    """A compare between data points produced by bench.
+    
+    (BenchDataPoint, BenchDataPoint)"""
+    def __init__(self, old, new):
+        self.old = old
+        self.new = new
+        self.diff = old.time - new.time
+        diffp = 0
+        if old.time != 0:
+            diffp = self.diff / old.time
+        self.diffp = diffp
+    
+    def __repr__(self):
+        return "BenchDiff(%s, %s)" % (
+                   str(self.new),
+                   str(self.old),
+               )
+        
 def main():
     """Parses command line and writes output."""
     
     try:
-        opts, args = getopt.getopt(sys.argv[1:], "f:o:n:h")
+        opts, _ = getopt.getopt(sys.argv[1:], "f:o:n:h")
     except getopt.GetoptError, err:
         print str(err) 
         usage()
@@ -60,25 +55,27 @@ def main():
     column_formats = {
         'b' : '{bench: >28} ',
         'c' : '{config: <4} ',
+        't' : '{time_type: <4} ',
         'o' : '{old_time: >10.2f} ',
         'n' : '{new_time: >10.2f} ',
         'd' : '{diff: >+10.2f} ',
-        'p' : '{diffp: >+7.1%} ',
+        'p' : '{diffp: >+8.1%} ',
     }
     header_formats = {
         'b' : '{bench: >28} ',
         'c' : '{config: <4} ',
+        't' : '{time_type: <4} ',
         'o' : '{old_time: >10} ',
         'n' : '{new_time: >10} ',
         'd' : '{diff: >10} ',
-        'p' : '{diffp: >7} ',
+        'p' : '{diffp: >8} ',
     }
     
     old = None
     new = None
     column_format = ""
     header_format = ""
-    columns = 'bcondp'
+    columns = 'bctondp'
     header = False
     
     for option, value in opts:
@@ -110,31 +107,43 @@ def main():
         print header_format.format(
             bench='bench'
             , config='conf'
+            , time_type='time'
             , old_time='old'
             , new_time='new'
             , diff='diff'
             , diffp='diffP'
         )
     
-    old_benches = parse(open(old, 'r'))
-    new_benches = parse(open(new, 'r'))
-    
-    for old_bench, old_configs in old_benches.items():
-        if old_bench in new_benches:
-            new_configs = new_benches[old_bench]
-            for old_config, old_time in old_configs.items():
-                if old_config in new_configs:
-                    new_time = new_configs[old_config]
-                    old_time = old_configs[old_config]
-                    print column_format.format(
-                        bench=old_bench.strip()
-                        , config=old_config.strip()
-                        , old_time=old_time
-                        , new_time=new_time
-                        , diff=(old_time - new_time)
-                        , diffp=((old_time-new_time)/old_time)
-                    )
-    
+    old_benches = bench_util.parse({}, open(old, 'r'))
+    new_benches = bench_util.parse({}, open(new, 'r'))
+    
+    bench_diffs = []
+    for old_bench in old_benches:
+        #filter new_benches for benches that match old_bench
+        new_bench_match = [bench for bench in new_benches
+            if old_bench.bench == bench.bench and
+               old_bench.config == bench.config and
+               old_bench.time_type == bench.time_type
+        ]
+        if (len(new_bench_match) < 1):
+            continue
+        bench_diffs.append(BenchDiff(old_bench, new_bench_match[0]))
+    
+    bench_diffs.sort(key=lambda d : [d.diffp,
+                                     d.old.bench,
+                                     d.old.config,
+                                     d.old.time_type,
+                                    ])
+    for bench_diff in bench_diffs:
+        print column_format.format(
+            bench=bench_diff.old.bench.strip()
+            , config=bench_diff.old.config.strip()
+            , time_type=bench_diff.old.time_type
+            , old_time=bench_diff.old.time
+            , new_time=bench_diff.new.time
+            , diff=bench_diff.diff
+            , diffp=bench_diff.diffp
+        )
     
 if __name__ == "__main__":
     main()
diff --git a/bench/bench_graph_svg.py b/bench/bench_graph_svg.py
new file mode 100644
index 0000000..649a3a1
--- /dev/null
+++ b/bench/bench_graph_svg.py
@@ -0,0 +1,671 @@
+'''
+Created on May 16, 2011
+
+@author: bungeman
+'''
+import sys
+import getopt
+import re
+import os
+import bench_util
+import json
+import xml.sax.saxutils
+
+def usage():
+    """Prints simple usage information."""
+    
+    print '-d <dir> a directory containing bench_r<revision>_<scalar> files.'
+    print '-b <bench> the bench to show.'
+    print '-c <config> the config to show (GPU, 8888, 565, etc).'
+    print '-t <time> the time to show (w, c, g, etc).'
+    print '-s <setting>[=<value>] a setting to show (alpha, scalar, etc).'
+    print '-r <revision>[:<revision>] the revisions to show.'
+    print '-f <revision>[:<revision>] the revisions to use for fitting.'
+    print '-x <int> the desired width of the svg.'
+    print '-y <int> the desired height of the svg.'
+    print '--default-setting <setting>[=<value>] setting for those without.'
+    
+
+class Label:
+    """The information in a label.
+    
+    (str, str, str, str, {str:str})"""
+    def __init__(self, bench, config, time_type, settings):
+        self.bench = bench
+        self.config = config
+        self.time_type = time_type
+        self.settings = settings
+    
+    def __repr__(self):
+        return "Label(%s, %s, %s, %s)" % (
+                   str(self.bench),
+                   str(self.config),
+                   str(self.time_type),
+                   str(self.settings),
+               )
+    
+    def __str__(self):
+        return "%s_%s_%s_%s" % (
+                   str(self.bench),
+                   str(self.config),
+                   str(self.time_type),
+                   str(self.settings),
+               )
+    
+    def __eq__(self, other):
+        return (self.bench == other.bench and
+                self.config == other.config and
+                self.time_type == other.time_type and
+                self.settings == other.settings)
+    
+    def __hash__(self):
+        return (hash(self.bench) ^
+                hash(self.config) ^
+                hash(self.time_type) ^
+                hash(frozenset(self.settings.iteritems())))
+
+def parse_dir(directory, default_settings, oldest_revision, newest_revision):
+    """Parses bench data from files like bench_r<revision>_<scalar>.
+    
+    (str, {str, str}, Number, Number) -> {int:[BenchDataPoints]}"""
+    revision_data_points = {} # {revision : [BenchDataPoints]}
+    for bench_file in os.listdir(directory):
+        file_name_match = re.match('bench_r(\d+)_(\S+)', bench_file)
+        if (file_name_match is None):
+            continue
+        
+        revision = int(file_name_match.group(1))
+        scalar_type = file_name_match.group(2)
+        
+        if (revision < oldest_revision or revision > newest_revision):
+            continue
+        
+        file_handle = open(directory + '/' + bench_file, 'r')
+        
+        if (revision not in revision_data_points):
+            revision_data_points[revision] = []
+        default_settings['scalar'] = scalar_type
+        revision_data_points[revision].extend(
+                        bench_util.parse(default_settings, file_handle))
+        file_handle.close()
+    return revision_data_points
+
+def create_lines(revision_data_points, settings
+               , bench_of_interest, config_of_interest, time_of_interest):
+    """Convert revision data into sorted line data.
+    
+    ({int:[BenchDataPoints]}, {str:str}, str?, str?, str?)
+        -> {Label:[(x,y)] | [n].x <= [n+1].x}"""
+    revisions = revision_data_points.keys()
+    revisions.sort()
+    lines = {} # {Label:[(x,y)] | x[n] <= x[n+1]}
+    for revision in revisions:
+        for point in revision_data_points[revision]:
+            if (bench_of_interest is not None and
+                not bench_of_interest == point.bench):
+                continue
+            
+            if (config_of_interest is not None and
+                not config_of_interest == point.config):
+                continue
+            
+            if (time_of_interest is not None and
+                not time_of_interest == point.time_type):
+                continue
+            
+            skip = False
+            for key, value in settings.items():
+                if key in point.settings and point.settings[key] != value:
+                    skip = True
+                    break
+            if skip:
+                continue
+            
+            line_name = Label(point.bench
+                            , point.config
+                            , point.time_type
+                            , point.settings)
+            
+            if line_name not in lines:
+                lines[line_name] = []
+            
+            lines[line_name].append((revision, point.time))
+            
+    return lines
+
+def bounds(lines):
+    """Finds the bounding rectangle for the lines.
+    
+    {Label:[(x,y)]} -> ((min_x, min_y),(max_x,max_y))"""
+    min_x = bench_util.Max
+    min_y = bench_util.Max
+    max_x = bench_util.Min
+    max_y = bench_util.Min
+    
+    for line in lines.itervalues():
+        for x, y in line:
+            min_x = min(min_x, x)
+            min_y = min(min_y, y)
+            max_x = max(max_x, x)
+            max_y = max(max_y, y)
+            
+    return ((min_x, min_y), (max_x, max_y))
+
+def create_regressions(lines, start_x, end_x):
+    """Creates regression data from line segments.
+    
+    ({Label:[(x,y)] | [n].x <= [n+1].x}, Number, Number)
+        -> {Label:LinearRegression}"""
+    regressions = {} # {Label : LinearRegression}
+    
+    for label, line in lines.iteritems():
+        regression_line = [p for p in line if start_x <= p[0] <= end_x]
+        
+        if (len(regression_line) < 2):
+            continue
+        regression = bench_util.LinearRegression(regression_line)
+        regressions[label] = regression
+    
+    return regressions
+
+def bounds_slope(regressions):
+    """Finds the extreme up and down slopes of a set of linear regressions.
+    
+    ({Label:LinearRegression}) -> (max_up_slope, min_down_slope)"""
+    max_up_slope = 0
+    min_down_slope = 0
+    for regression in regressions.itervalues():
+        min_slope = regression.find_min_slope()
+        max_up_slope = max(max_up_slope, min_slope)
+        min_down_slope = min(min_down_slope, min_slope)
+    
+    return (max_up_slope, min_down_slope)
+
+def main():
+    """Parses command line and writes output."""
+    
+    try:
+        opts, _ = getopt.getopt(sys.argv[1:]
+                                 , "d:b:c:t:s:r:f:x:y:"
+                                 , "default-setting=")
+    except getopt.GetoptError, err:
+        print str(err) 
+        usage()
+        sys.exit(2)
+    
+    directory = None
+    config_of_interest = None
+    bench_of_interest = None
+    time_of_interest = None
+    oldest_revision = 0
+    newest_revision = bench_util.Max
+    oldest_regression = 0
+    newest_regression = bench_util.Max
+    requested_height = None
+    requested_width = None
+    settings = {}
+    default_settings = {}
+    
+    def parse_range(revision_range):
+        """Takes <old>[:<new>] returns (old, new) or (old, Max)."""
+        old, _, new = revision_range.partition(":")
+        if not new:
+            return (int(old), bench_util.Max)
+        return (int(old), int(new))
+    
+    def add_setting(settings, setting):
+        """Takes <key>[=<value>] adds {key:value} or {key:True} to settings."""
+        name, _, value = setting.partition('=')
+        if not value:
+            settings[name] = True
+        else:
+            settings[name] = value
+        
+    try:
+        for option, value in opts:
+            if option == "-d":
+                directory = value
+            elif option == "-b":
+                bench_of_interest = value
+            elif option == "-c":
+                config_of_interest = value
+            elif option == "-t":
+                time_of_interest = value
+            elif option == "-s":
+                add_setting(settings, value)
+            elif option == "-r":
+                oldest_revision, newest_revision = parse_range(value)
+            elif option == "-f":
+                oldest_regression, newest_regression = parse_range(value)
+            elif option == "-x":
+                requested_width = int(value)
+            elif option == "-y":
+                requested_height = int(value)
+            elif option == "--default-setting":
+                add_setting(default_settings, value)
+            else:
+                usage()
+                assert False, "unhandled option"
+    except ValueError:
+        usage()
+        sys.exit(2)
+                
+    if directory is None:
+        usage()
+        sys.exit(2)
+    
+    revision_data_points = parse_dir(directory
+                                   , default_settings
+                                   , oldest_revision
+                                   , newest_revision)
+    
+    lines = create_lines(revision_data_points
+                   , settings
+                   , bench_of_interest
+                   , config_of_interest
+                   , time_of_interest)
+    
+    regressions = create_regressions(lines
+                                   , oldest_regression
+                                   , newest_regression)
+    
+    output_xhtml(lines, regressions, requested_width, requested_height)
+
+def qa(out):
+    """Stringify input and quote as an xml attribute."""
+    return xml.sax.saxutils.quoteattr(str(out))
+def qe(out):
+    """Stringify input and escape as xml data."""
+    return xml.sax.saxutils.escape(str(out))
+
+def create_select(qualifier, lines, select_id=None):
+    """Output select with options showing lines which qualifier maps to it.
+    
+    ((Label) -> str, {Label:_}, str?) -> _"""
+    options = {} #{ option : [Label]}
+    for label in lines.keys():
+        option = qualifier(label)
+        if (option not in options):
+            options[option] = []
+        options[option].append(label)
+    option_list = list(options.keys())
+    option_list.sort()
+    print '<select class="lines"',
+    if select_id is not None:
+        print 'id=%s' % qa(select_id)
+    print 'multiple="true" size="10" onchange="updateSvg();">'
+    for option in option_list:
+        print '<option value=' + qa('[' + 
+        reduce(lambda x,y:x+json.dumps(str(y))+',',options[option],"")[0:-1]
+        + ']') + '>'+qe(option)+'</option>'
+    print '</select>'
+
+def output_xhtml(lines, regressions, requested_width, requested_height):
+    """Outputs an svg/xhtml view of the data."""
+    print '<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"',
+    print '"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">'
+    print '<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">'
+    print '<head>'
+    print '<title>Bench graph</title>'
+    print '</head>'
+    print '<body>'
+    
+    output_svg(lines, regressions, requested_width, requested_height)
+    
+    #output the manipulation controls
+    print """
+<script type="text/javascript">//<![CDATA[
+    function getElementsByClass(node, searchClass, tag) {
+        var classElements = new Array();
+        var elements = node.getElementsByTagName(tag);
+        var pattern = new RegExp("^|\\s"+searchClass+"\\s|$");
+        for (var i = 0, elementsFound = 0; i < elements.length; ++i) {
+            if (pattern.test(elements[i].className)) {
+                classElements[elementsFound] = elements[i];
+                ++elementsFound;
+            }
+        }
+        return classElements;
+    }
+    function getAllLines() {
+        var selectElem = document.getElementById('benchSelect');
+        var linesObj = {};
+        for (var i = 0; i < selectElem.options.length; ++i) {
+            var lines = JSON.parse(selectElem.options[i].value);
+            for (var j = 0; j < lines.length; ++j) {
+                linesObj[lines[j]] = true;
+            }
+        }
+        return linesObj;
+    }
+    function getOptions(selectElem) {
+        var linesSelectedObj = {};
+        for (var i = 0; i < selectElem.options.length; ++i) {
+            if (!selectElem.options[i].selected) continue;
+            
+            var linesSelected = JSON.parse(selectElem.options[i].value);
+            for (var j = 0; j < linesSelected.length; ++j) {
+                linesSelectedObj[linesSelected[j]] = true;
+            }
+        }
+        return linesSelectedObj;
+    }
+    function objectEmpty(obj) {
+        for (var p in obj) {
+            return false;
+        }
+        return true;
+    }
+    function markSelectedLines(selectElem, allLines) {
+        var linesSelected = getOptions(selectElem);
+        if (!objectEmpty(linesSelected)) {
+            for (var line in allLines) {
+                allLines[line] &= (linesSelected[line] == true);
+            }
+        }
+    }
+    function updateSvg() {
+        var allLines = getAllLines();
+        
+        var selects = getElementsByClass(document, 'lines', 'select');
+        for (var i = 0; i < selects.length; ++i) {
+            markSelectedLines(selects[i], allLines);
+        }
+        
+        for (var line in allLines) {
+            var svgLine = document.getElementById(line);
+            var display = (allLines[line] ? 'inline' : 'none');
+            svgLine.setAttributeNS(null,'display', display);
+        }
+    }
+    
+    function mark(markerId) {
+        for (var line in getAllLines()) {
+            var svgLineGroup = document.getElementById(line);
+            var display = svgLineGroup.getAttributeNS(null,'display');
+            if (display == null || display == "" || display != "none") {
+                var svgLine = document.getElementById(line+'_line');
+                if (markerId == null) {
+                    svgLine.removeAttributeNS(null,'marker-mid');
+                } else {
+                    svgLine.setAttributeNS(null,'marker-mid', markerId);
+                }
+            }
+        }
+    }
+//]]></script>"""
+    
+    print '<form>'
+    
+    create_select(lambda l: l.bench, lines, 'benchSelect')
+    create_select(lambda l: l.config, lines)
+    create_select(lambda l: l.time_type, lines)
+    
+    all_settings = {}
+    variant_settings = set()
+    for label in lines.keys():
+        for key, value  in label.settings.items():
+            if key not in all_settings:
+                all_settings[key] = value
+            elif all_settings[key] != value:
+                variant_settings.add(key)
+    
+    for k in variant_settings:
+        create_select(lambda l: l.settings[k], lines)
+    
+    print '<button type="button"',
+    print 'onclick=%s' % qa("mark('url(#circleMark)'); return false;"),
+    print '>Mark</button>'
+    print '<button type="button" onclick="mark(null);">Clear</button>'
+    
+    print '</form>'
+    print '</body>'
+    print '</html>'
+    
+def compute_size(requested_width, requested_height, rev_width, time_height):
+    """Converts potentially empty requested size into a concrete size.
+    
+    (Number?,  Number?) -> (Number, Number)"""
+    pic_width = 0
+    pic_height = 0
+    if (requested_width is not None and requested_height is not None):
+        pic_height = requested_height
+        pic_width = requested_width
+    
+    elif (requested_width is not None):
+        pic_width = requested_width
+        pic_height = pic_width * (float(time_height) / rev_width)
+        
+    elif (requested_height is not None):
+        pic_height = requested_height
+        pic_width = pic_height * (float(rev_width) / time_height)
+        
+    else:
+        pic_height = 800
+        pic_width = max(rev_width*3
+                      , pic_height * (float(rev_width) / time_height))
+    
+    return (pic_width, pic_height)
+
+def output_svg(lines, regressions, requested_width, requested_height):
+    """Outputs an svg view of the data."""
+    
+    (global_min_x, _), (global_max_x, global_max_y) = bounds(lines)
+    max_up_slope, min_down_slope = bounds_slope(regressions)
+    
+    #output
+    global_min_y = 0
+    x = global_min_x
+    y = global_min_y
+    w = global_max_x - global_min_x
+    h = global_max_y - global_min_y
+    font_size = 16
+    line_width = 2
+    
+    pic_width, pic_height = compute_size(requested_width, requested_height
+                                       , w, h)
+    
+    def cw(w1):
+        """Converts a revision difference to display width."""
+        return (pic_width / float(w)) * w1
+    def cx(x):
+        """Converts a revision to a horizontal display position."""
+        return cw(x - global_min_x)
+
+    def ch(h1):
+        """Converts a time difference to a display height."""
+        return -(pic_height / float(h)) * h1
+    def cy(y):
+        """Converts a time to a vertical display position."""
+        return pic_height + ch(y - global_min_y)
+    
+    print '<svg',
+    print 'width=%s' % qa(str(pic_width)+'px')
+    print 'height=%s' % qa(str(pic_height)+'px')
+    print 'viewBox="0 0 %s %s"' % (str(pic_width), str(pic_height))
+    print 'onclick=%s' % qa(
+            "var event = arguments[0] || window.event;"
+            " if (event.shiftKey) { highlightRevision(null); }"
+            " if (event.ctrlKey) { highlight(null); }"
+            " return false;")
+    print 'xmlns="http://www.w3.org/2000/svg"'
+    print 'xmlns:xlink="http://www.w3.org/1999/xlink">'
+    
+    print """
+<defs>
+    <marker id="circleMark"
+      viewBox="0 0 2 2" refX="1" refY="1"
+      markerUnits="strokeWidth"
+      markerWidth="2" markerHeight="2"
+      orient="0">
+      <circle cx="1" cy="1" r="1"/>
+    </marker>
+</defs>"""
+    
+    #output the revisions
+    print """
+<script type="text/javascript">//<![CDATA[
+    var previousRevision;
+    var previousRevisionFill;
+    var previousRevisionStroke
+    function highlightRevision(id) {
+        if (previousRevision == id) return;
+        
+        document.getElementById('revision').firstChild.nodeValue = id;
+        
+        var preRevision = document.getElementById(previousRevision);
+        if (preRevision) {
+            preRevision.setAttributeNS(null,'fill', previousRevisionFill);
+            preRevision.setAttributeNS(null,'stroke', previousRevisionStroke);
+        }
+        
+        var revision = document.getElementById(id);
+        previousRevision = id;
+        if (revision) {
+            previousRevisionFill = revision.getAttributeNS(null,'fill');
+            revision.setAttributeNS(null,'fill','rgb(100%, 95%, 95%)');
+            
+            previousRevisionStroke = revision.getAttributeNS(null,'stroke');
+            revision.setAttributeNS(null,'stroke','rgb(100%, 90%, 90%)');
+        }
+    }
+//]]></script>"""
+    
+    def print_rect(x, y, w, h, revision):
+        """Outputs a revision rectangle in display space,
+           taking arguments in revision space."""
+        disp_y = cy(y)
+        disp_h = ch(h)
+        if disp_h < 0:
+            disp_y += disp_h
+            disp_h = -disp_h
+        
+        print '<rect id=%s x=%s y=%s' % (qa(revision), qa(cx(x)), qa(disp_y),),
+        print 'width=%s height=%s' % (qa(cw(w)), qa(disp_h),),
+        print 'fill="white"',
+        print 'stroke="rgb(99%%,99%%,99%%)" stroke-width=%s' % qa(line_width),
+        print 'onmouseover=%s' % qa(
+                "var event = arguments[0] || window.event;"
+                " if (event.shiftKey) {"
+                    " highlightRevision('"+str(revision)+"');"
+                    " return false;"
+                " }"),
+        print ' />'
+    
+    xes = set()
+    for line in lines.itervalues():
+        for point in line:
+            xes.add(point[0])
+    revisions = list(xes)
+    revisions.sort()
+    
+    left = x
+    current_revision = revisions[0]
+    for next_revision in revisions[1:]:
+        width = (((next_revision - current_revision) / 2.0)
+                 + (current_revision - left))
+        print_rect(left, y, width, h, current_revision)
+        left += width
+        current_revision = next_revision
+    print_rect(left, y, x+w - left, h, current_revision)
+    
+    #output the lines
+    print """
+<script type="text/javascript">//<![CDATA[
+    var previous;
+    var previousColor;
+    var previousOpacity;
+    function highlight(id) {
+        if (previous == id) return;
+        
+        document.getElementById('label').firstChild.nodeValue = id;
+        
+        var preGroup = document.getElementById(previous);
+        if (preGroup) {
+            var preLine = document.getElementById(previous+'_line');
+            preLine.setAttributeNS(null,'stroke', previousColor);
+            preLine.setAttributeNS(null,'opacity', previousOpacity);
+            
+            var preSlope = document.getElementById(previous+'_linear');
+            if (preSlope) {
+                preSlope.setAttributeNS(null,'visibility', 'hidden');
+            }
+        }
+        
+        var group = document.getElementById(id);
+        previous = id;
+        if (group) {
+            group.parentNode.appendChild(group);
+            
+            var line = document.getElementById(id+'_line');
+            previousColor = line.getAttributeNS(null,'stroke');
+            previousOpacity = line.getAttributeNS(null,'opacity');
+            line.setAttributeNS(null,'stroke', 'blue');
+            line.setAttributeNS(null,'opacity', '1');
+            
+            var slope = document.getElementById(id+'_linear');
+            if (slope) {
+                slope.setAttributeNS(null,'visibility', 'visible');
+            }
+        }
+    }
+//]]></script>"""
+    for label, line in lines.items():
+        print '<g id=%s>' % qa(label)
+        r = 128
+        g = 128
+        b = 128
+        a = .10
+        if label in regressions:
+            regression = regressions[label]
+            min_slope = regression.find_min_slope()
+            if min_slope < 0:
+                d = max(0, (min_slope / min_down_slope))
+                g += int(d*128)
+                a += d*0.9
+            elif min_slope > 0:
+                d = max(0, (min_slope / max_up_slope))
+                r += int(d*128)
+                a += d*0.9
+            
+            slope = regression.slope
+            intercept = regression.intercept
+            min_x = regression.min_x
+            max_x = regression.max_x
+            print '<polyline id=%s' % qa(str(label)+'_linear'),
+            print 'fill="none" stroke="yellow"',
+            print 'stroke-width=%s' % qa(abs(ch(regression.serror*2))),
+            print 'opacity="0.5" pointer-events="none" visibility="hidden"',
+            print 'points="',
+            print '%s,%s' % (str(cx(min_x)), str(cy(slope*min_x + intercept))),
+            print '%s,%s' % (str(cx(max_x)), str(cy(slope*max_x + intercept))),
+            print '"/>'
+        
+        print '<polyline id=%s' % qa(str(label)+'_line'),
+        print 'onmouseover=%s' % qa(
+                "var event = arguments[0] || window.event;"
+                " if (event.ctrlKey) {"
+                    " highlight('"+str(label).replace("'", "\\'")+"');"
+                    " return false;"
+                " }"),
+        print 'fill="none" stroke="rgb(%s,%s,%s)"' % (str(r), str(g), str(b)),
+        print 'stroke-width=%s' % qa(line_width),
+        print 'opacity=%s' % qa(a),
+        print 'points="',
+        for point in line:
+            print '%s,%s' % (str(cx(point[0])), str(cy(point[1]))),
+        print '"/>'
+        
+        print '</g>'
+    
+    #output the labels
+    print '<text id="label" x="0" y=%s' % qa(font_size),
+    print 'font-size=%s> </text>' % qa(font_size)
+    
+    print '<text id="revision" x="0" y=%s' % qa(font_size*2),
+    print 'font-size=%s> </text>' % qa(font_size)
+    
+    print '</svg>'
+    
+if __name__ == "__main__":
+    main()
diff --git a/bench/bench_util.py b/bench/bench_util.py
new file mode 100644
index 0000000..3bfe218
--- /dev/null
+++ b/bench/bench_util.py
@@ -0,0 +1,170 @@
+'''
+Created on May 19, 2011
+
+@author: bungeman
+'''
+
+import re
+import math
+
+class BenchDataPoint:
+    """A single data point produced by bench.
+    
+    (str, str, str, float, {str:str})"""
+    def __init__(self, bench, config, time_type, time, settings):
+        self.bench = bench
+        self.config = config
+        self.time_type = time_type
+        self.time = time
+        self.settings = settings
+    
+    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")
+
+def parse(settings, lines):
+    """Parses bench output into a useful data structure.
+    
+    ({str:str}, __iter__ -> str) -> [BenchDataPoint]"""
+    
+    benches = []
+    current_bench = None
+    setting_re = '([^\s=]+)(?:=(\S+))?'
+    settings_re = 'skia bench:((?:\s+' + setting_re + ')*)'
+    bench_re = 'running bench (?:\[\d+ \d+\] )?\s*(\S+)'
+    time_re = '(?:(\w*)msecs = )?\s*(\d+\.\d+)'
+    config_re = '(\S+): ((?:' + time_re + '\s+)+)'
+    
+    for line in lines:
+        
+        #see if this line is a settings line
+        settingsMatch = re.search(settings_re, line)
+        if (settingsMatch):
+            settings = dict(settings)
+            for settingMatch in re.finditer(setting_re, 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 = re.search(bench_re, line)
+        if new_bench:
+            current_bench = new_bench.group(1)
+        
+        #add configs on this line to the current bench
+        if current_bench:
+            for new_config in re.finditer(config_re, line):
+                current_config = new_config.group(1)
+                times = new_config.group(2)
+                for new_time in re.finditer(time_re, times):
+                    current_time_type = new_time.group(1)
+                    current_time = float(new_time.group(2))
+                    benches.append(BenchDataPoint(
+                            current_bench
+                            , current_config
+                            , current_time_type
+                            , current_time
+                            , settings))
+    
+    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
+        
+        B = (n*Sxy - Sx*Sy) / (n*Sxx - Sx*Sx)
+        a = (1.0/n)*(Sy - B*Sx)
+        
+        se2 = 0
+        sB2 = 0
+        sa2 = 0
+        if (n >= 3):
+            se2 = (1.0/(n*(n-2)) * (n*Syy - Sy*Sy - B*B*(n*Sxx - Sx*Sx)))
+            sB2 = (n*se2) / (n*Sxx - Sx*Sx)
+            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
-- 
2.7.4