From b6204b1ec4e4940db94bc40d4283ee77729170d6 Mon Sep 17 00:00:00 2001
From: "bensong@google.com"
 <bensong@google.com@2bbb7eff-a529-9590-31e7-b0007b416f81>
Date: Thu, 16 Aug 2012 20:49:28 +0000
Subject: [PATCH] cleaned up algorithm codes and added 25th percentile for
 representation.

git-svn-id: http://skia.googlecode.com/svn/trunk@5139 2bbb7eff-a529-9590-31e7-b0007b416f81
---
 bench/bench_graph_svg.py |  8 +++-----
 bench/bench_util.py      | 51 +++++++++++++++++++++++++++++++-----------------
 2 files changed, 36 insertions(+), 23 deletions(-)

diff --git a/bench/bench_graph_svg.py b/bench/bench_graph_svg.py
index 78a0366..517e691 100644
--- a/bench/bench_graph_svg.py
+++ b/bench/bench_graph_svg.py
@@ -28,8 +28,8 @@ def usage():
     print '-r <revision>[:<revision>] the revisions to show.'
     print '   Negative <revision> is taken as offset from most recent revision.'
     print '-s <setting>[=<value>] a setting to show (alpha, scalar, etc).'
-    print '-m <representative> use "avg", "min", or "med" for bench value.'
-    print '   They correspond to average, minimum and median of bench iters.'
+    print '-m <representation> representation of bench value.'
+    print '   See _ListAlgorithm class in bench_util.py.'
     print '-t <time> the time to show (w, c, g, etc).'
     print '-x <int> the desired width of the svg.'
     print '-y <int> the desired height of the svg.'
@@ -281,7 +281,7 @@ def main():
     config_of_interest = None
     bench_of_interest = None
     time_of_interest = None
-    rep = "avg"  # bench representative calculation algorithm
+    rep = None  # bench representation algorithm
     revision_range = '0:'
     regression_range = '0:'
     latest_revision = None
@@ -329,8 +329,6 @@ def main():
                 title = value
             elif option == "-m":
                 rep = value
-                if rep not in ["avg", "min", "med"]:
-                    raise Exception("Invalid -m representative: %s" % rep)
             elif option == "-o":
                 redirect_stdout(value)
             elif option == "-r":
diff --git a/bench/bench_util.py b/bench/bench_util.py
index 3b150a0..3abdee8 100644
--- a/bench/bench_util.py
+++ b/bench/bench_util.py
@@ -45,11 +45,41 @@ class _ExtremeType(object):
 Max = _ExtremeType(1, "Max")
 Min = _ExtremeType(-1, "Min")
 
-def parse(settings, lines, representative='avg'):
+class _ListAlgorithm(object):
+    """Algorithm for selecting the representation value from a given list.
+    representation is one of 'avg', 'min', 'med', '25th' (average, minimum,
+    median, 25th percentile)"""
+    def __init__(self, data, representation=None):
+        if not representation:
+            representation = 'avg'  # default algorithm is average
+        self._data = data
+        self._len = len(data)
+        if representation == 'avg':
+            self._rep = sum(self._data) / self._len
+        else:
+            self._data.sort()
+            if representation == 'min':
+                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 == 'med':
+                    x = int(round(0.5 * self._len + 0.5))
+                elif representation == '25th':
+                    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 parse(settings, lines, representation='avg'):
     """Parses bench output into a useful data structure.
     
     ({str:str}, __iter__ -> str) -> [BenchDataPoint]
-    representative is one of 'avg', 'min', 'med' (average, mean, median)."""
+    representation should match one of those defined in class _ListAlgorithm."""
     
     benches = []
     current_bench = None
@@ -85,26 +115,11 @@ def parse(settings, lines, representative='avg'):
                     current_time_type = new_time.group(1)
                     iters = [float(i) for i in
                              new_time.group(2).strip().split(',')]
-                    iters.sort()
-                    iter_len = len(iters)
-                    if representative == 'avg':
-                        rep = sum(iters) / iter_len
-                    elif representative == 'min':
-                        rep = iters[0]
-                    elif representative == 'med':
-                        if iter_len % 2:
-                            rep = (iters[iter_len / 2] +
-                                   iters[iter_len / 2 - 1]) / 2
-                        else:
-                            rep = iters[iter_len / 2]
-                    else:
-                        raise Exception("invalid representative algorithm %s!" %
-                                        representative)
                     benches.append(BenchDataPoint(
                             current_bench
                             , current_config
                             , current_time_type
-                            , rep
+                            , _ListAlgorithm(iters, representation).compute()
                             , settings))
     
     return benches
-- 
2.7.4