blob: 7e8a13ed1050bc72c57b7bf36f27e99a9004ef1a [file] [log] [blame]
bungeman@google.com85669f92011-06-17 13:58:14 +00001'''
2Created on May 19, 2011
3
4@author: bungeman
5'''
6
7import re
8import math
9
bensong@google.comd3fd98f2012-12-18 20:06:10 +000010# bench representation algorithm constant names
11ALGORITHM_AVERAGE = 'avg'
12ALGORITHM_MEDIAN = 'med'
13ALGORITHM_MINIMUM = 'min'
14ALGORITHM_25TH_PERCENTILE = '25th'
15
epoger@google.comad91d922013-02-14 18:35:17 +000016# Regular expressions used throughout
17PER_SETTING_RE = '([^\s=]+)(?:=(\S+))?'
18SETTINGS_RE = 'skia bench:((?:\s+' + PER_SETTING_RE + ')*)'
19BENCH_RE = 'running bench (?:\[\d+ \d+\] )?\s*(\S+)'
20TIME_RE = '(?:(\w*)msecs = )?\s*((?:\d+\.\d+)(?:,\d+\.\d+)*)'
21# non-per-tile benches have configs that don't end with ']' or '>'
22CONFIG_RE = '(\S+[^\]>]): ((?:' + TIME_RE + '\s+)+)'
23# per-tile bench lines are in the following format. Note that there are
24# non-averaged bench numbers in separate lines, which we ignore now due to
25# their inaccuracy.
26TILE_RE = (' tile_(\S+): tile \[\d+,\d+\] out of \[\d+,\d+\] <averaged>:'
27 ' ((?:' + TIME_RE + '\s+)+)')
28# for extracting tile layout
29TILE_LAYOUT_RE = ' out of \[(\d+),(\d+)\] <averaged>: '
30
31PER_SETTING_RE_COMPILED = re.compile(PER_SETTING_RE)
32SETTINGS_RE_COMPILED = re.compile(SETTINGS_RE)
33BENCH_RE_COMPILED = re.compile(BENCH_RE)
34TIME_RE_COMPILED = re.compile(TIME_RE)
35CONFIG_RE_COMPILED = re.compile(CONFIG_RE)
36TILE_RE_COMPILED = re.compile(TILE_RE)
37TILE_LAYOUT_RE_COMPILED = re.compile(TILE_LAYOUT_RE)
38
bungeman@google.com85669f92011-06-17 13:58:14 +000039class BenchDataPoint:
40 """A single data point produced by bench.
bensong@google.comd3fd98f2012-12-18 20:06:10 +000041
bensong@google.comba98f952013-02-13 23:22:29 +000042 (str, str, str, float, {str:str}, str, [floats])"""
43 def __init__(self, bench, config, time_type, time, settings,
44 tile_layout='', per_tile_values=[]):
bungeman@google.com85669f92011-06-17 13:58:14 +000045 self.bench = bench
46 self.config = config
47 self.time_type = time_type
48 self.time = time
49 self.settings = settings
bensong@google.comba98f952013-02-13 23:22:29 +000050 # how tiles cover the whole picture. '5x3' means 5 columns and 3 rows.
51 self.tile_layout = tile_layout
52 # list of per_tile bench values, if applicable
53 self.per_tile_values = per_tile_values
bensong@google.comd3fd98f2012-12-18 20:06:10 +000054
bungeman@google.com85669f92011-06-17 13:58:14 +000055 def __repr__(self):
56 return "BenchDataPoint(%s, %s, %s, %s, %s)" % (
57 str(self.bench),
58 str(self.config),
59 str(self.time_type),
60 str(self.time),
61 str(self.settings),
62 )
bensong@google.comd3fd98f2012-12-18 20:06:10 +000063
bungeman@google.com85669f92011-06-17 13:58:14 +000064class _ExtremeType(object):
65 """Instances of this class compare greater or less than other objects."""
66 def __init__(self, cmpr, rep):
67 object.__init__(self)
68 self._cmpr = cmpr
69 self._rep = rep
bensong@google.comd3fd98f2012-12-18 20:06:10 +000070
bungeman@google.com85669f92011-06-17 13:58:14 +000071 def __cmp__(self, other):
72 if isinstance(other, self.__class__) and other._cmpr == self._cmpr:
73 return 0
74 return self._cmpr
bensong@google.comd3fd98f2012-12-18 20:06:10 +000075
bungeman@google.com85669f92011-06-17 13:58:14 +000076 def __repr__(self):
77 return self._rep
78
79Max = _ExtremeType(1, "Max")
80Min = _ExtremeType(-1, "Min")
81
bensong@google.comb6204b12012-08-16 20:49:28 +000082class _ListAlgorithm(object):
83 """Algorithm for selecting the representation value from a given list.
bensong@google.comd3fd98f2012-12-18 20:06:10 +000084 representation is one of the ALGORITHM_XXX representation types."""
bensong@google.comb6204b12012-08-16 20:49:28 +000085 def __init__(self, data, representation=None):
86 if not representation:
bensong@google.comd3fd98f2012-12-18 20:06:10 +000087 representation = ALGORITHM_AVERAGE # default algorithm
bensong@google.comb6204b12012-08-16 20:49:28 +000088 self._data = data
89 self._len = len(data)
bensong@google.comd3fd98f2012-12-18 20:06:10 +000090 if representation == ALGORITHM_AVERAGE:
bensong@google.comb6204b12012-08-16 20:49:28 +000091 self._rep = sum(self._data) / self._len
92 else:
93 self._data.sort()
bensong@google.comd3fd98f2012-12-18 20:06:10 +000094 if representation == ALGORITHM_MINIMUM:
bensong@google.comb6204b12012-08-16 20:49:28 +000095 self._rep = self._data[0]
96 else:
97 # for percentiles, we use the value below which x% of values are
98 # found, which allows for better detection of quantum behaviors.
bensong@google.comd3fd98f2012-12-18 20:06:10 +000099 if representation == ALGORITHM_MEDIAN:
bensong@google.comb6204b12012-08-16 20:49:28 +0000100 x = int(round(0.5 * self._len + 0.5))
bensong@google.comd3fd98f2012-12-18 20:06:10 +0000101 elif representation == ALGORITHM_25TH_PERCENTILE:
bensong@google.comb6204b12012-08-16 20:49:28 +0000102 x = int(round(0.25 * self._len + 0.5))
103 else:
104 raise Exception("invalid representation algorithm %s!" %
105 representation)
106 self._rep = self._data[x - 1]
107
108 def compute(self):
109 return self._rep
110
epoger@google.comad91d922013-02-14 18:35:17 +0000111def _ParseAndStoreTimes(config_re_compiled, is_per_tile, line, bench,
112 value_dic, layout_dic, representation=None):
bensong@google.comba98f952013-02-13 23:22:29 +0000113 """Parses given bench time line with regex and adds data to value_dic.
epoger@google.comad91d922013-02-14 18:35:17 +0000114
115 config_re_compiled: precompiled regular expression for parsing the config
116 line.
117 is_per_tile: boolean indicating whether this is a per-tile bench.
118 If so, we add tile layout into layout_dic as well.
bensong@google.comd3fd98f2012-12-18 20:06:10 +0000119 line: input string line to parse.
120 bench: name of bench for the time values.
bensong@google.comba98f952013-02-13 23:22:29 +0000121 value_dic: dictionary to store bench values. See bench_dic in parse() below.
122 layout_dic: dictionary to store tile layouts. See parse() for descriptions.
bensong@google.comd3fd98f2012-12-18 20:06:10 +0000123 representation: should match one of the ALGORITHM_XXX types."""
124
epoger@google.comad91d922013-02-14 18:35:17 +0000125 for config in config_re_compiled.finditer(line):
bensong@google.comd3fd98f2012-12-18 20:06:10 +0000126 current_config = config.group(1)
bensong@google.comba98f952013-02-13 23:22:29 +0000127 tile_layout = ''
epoger@google.comad91d922013-02-14 18:35:17 +0000128 if is_per_tile: # per-tile bench, add name prefix
bensong@google.comd3fd98f2012-12-18 20:06:10 +0000129 current_config = 'tile_' + current_config
epoger@google.comad91d922013-02-14 18:35:17 +0000130 layouts = TILE_LAYOUT_RE_COMPILED.search(line)
bensong@google.comba98f952013-02-13 23:22:29 +0000131 if layouts and len(layouts.groups()) == 2:
132 tile_layout = '%sx%s' % layouts.groups()
bensong@google.comd3fd98f2012-12-18 20:06:10 +0000133 times = config.group(2)
epoger@google.comad91d922013-02-14 18:35:17 +0000134 for new_time in TIME_RE_COMPILED.finditer(times):
bensong@google.comd3fd98f2012-12-18 20:06:10 +0000135 current_time_type = new_time.group(1)
136 iters = [float(i) for i in
137 new_time.group(2).strip().split(',')]
bensong@google.comba98f952013-02-13 23:22:29 +0000138 value_dic.setdefault(bench, {}).setdefault(
139 current_config, {}).setdefault(current_time_type, []).append(
140 _ListAlgorithm(iters, representation).compute())
141 layout_dic.setdefault(bench, {}).setdefault(
142 current_config, {}).setdefault(current_time_type, tile_layout)
bensong@google.comd3fd98f2012-12-18 20:06:10 +0000143
144def parse(settings, lines, representation=None):
bungeman@google.com85669f92011-06-17 13:58:14 +0000145 """Parses bench output into a useful data structure.
bensong@google.comd3fd98f2012-12-18 20:06:10 +0000146
bensong@google.com87348162012-08-15 17:31:46 +0000147 ({str:str}, __iter__ -> str) -> [BenchDataPoint]
bensong@google.comd3fd98f2012-12-18 20:06:10 +0000148 representation is one of the ALGORITHM_XXX types."""
149
bungeman@google.com85669f92011-06-17 13:58:14 +0000150 benches = []
151 current_bench = None
bensong@google.comd3fd98f2012-12-18 20:06:10 +0000152 bench_dic = {} # [bench][config][time_type] -> [list of bench values]
bensong@google.comba98f952013-02-13 23:22:29 +0000153 # [bench][config][time_type] -> tile_layout
154 layout_dic = {}
bensong@google.comd3fd98f2012-12-18 20:06:10 +0000155
bungeman@google.com85669f92011-06-17 13:58:14 +0000156 for line in lines:
bensong@google.comd3fd98f2012-12-18 20:06:10 +0000157
158 # see if this line is a settings line
epoger@google.comad91d922013-02-14 18:35:17 +0000159 settingsMatch = SETTINGS_RE_COMPILED.search(line)
bungeman@google.com85669f92011-06-17 13:58:14 +0000160 if (settingsMatch):
161 settings = dict(settings)
epoger@google.comad91d922013-02-14 18:35:17 +0000162 for settingMatch in PER_SETTING_RE_COMPILED.finditer(settingsMatch.group(1)):
bungeman@google.com85669f92011-06-17 13:58:14 +0000163 if (settingMatch.group(2)):
164 settings[settingMatch.group(1)] = settingMatch.group(2)
165 else:
166 settings[settingMatch.group(1)] = True
bensong@google.comd3fd98f2012-12-18 20:06:10 +0000167
168 # see if this line starts a new bench
epoger@google.comad91d922013-02-14 18:35:17 +0000169 new_bench = BENCH_RE_COMPILED.search(line)
bungeman@google.com85669f92011-06-17 13:58:14 +0000170 if new_bench:
171 current_bench = new_bench.group(1)
bensong@google.comd3fd98f2012-12-18 20:06:10 +0000172
173 # add configs on this line to the bench_dic
bungeman@google.com85669f92011-06-17 13:58:14 +0000174 if current_bench:
epoger@google.comad91d922013-02-14 18:35:17 +0000175 _ParseAndStoreTimes(CONFIG_RE_COMPILED, False, line, current_bench,
176 bench_dic, layout_dic, representation)
177 _ParseAndStoreTimes(TILE_RE_COMPILED, True, line, current_bench,
178 bench_dic, layout_dic, representation)
bensong@google.comd3fd98f2012-12-18 20:06:10 +0000179
180 # append benches to list, use the total time as final bench value.
181 for bench in bench_dic:
182 for config in bench_dic[bench]:
183 for time_type in bench_dic[bench][config]:
bensong@google.comba98f952013-02-13 23:22:29 +0000184 tile_layout = ''
185 per_tile_values = []
186 if len(bench_dic[bench][config][time_type]) > 1:
187 # per-tile values, extract tile_layout
188 per_tile_values = bench_dic[bench][config][time_type]
189 tile_layout = layout_dic[bench][config][time_type]
bensong@google.comd3fd98f2012-12-18 20:06:10 +0000190 benches.append(BenchDataPoint(
191 bench,
192 config,
193 time_type,
194 sum(bench_dic[bench][config][time_type]),
bensong@google.comba98f952013-02-13 23:22:29 +0000195 settings,
196 tile_layout,
197 per_tile_values))
bensong@google.comd3fd98f2012-12-18 20:06:10 +0000198
bungeman@google.com85669f92011-06-17 13:58:14 +0000199 return benches
bensong@google.comd3fd98f2012-12-18 20:06:10 +0000200
bungeman@google.com85669f92011-06-17 13:58:14 +0000201class LinearRegression:
202 """Linear regression data based on a set of data points.
bensong@google.comd3fd98f2012-12-18 20:06:10 +0000203
bungeman@google.com85669f92011-06-17 13:58:14 +0000204 ([(Number,Number)])
205 There must be at least two points for this to make sense."""
206 def __init__(self, points):
207 n = len(points)
208 max_x = Min
209 min_x = Max
bensong@google.comd3fd98f2012-12-18 20:06:10 +0000210
bungeman@google.com85669f92011-06-17 13:58:14 +0000211 Sx = 0.0
212 Sy = 0.0
213 Sxx = 0.0
214 Sxy = 0.0
215 Syy = 0.0
216 for point in points:
217 x = point[0]
218 y = point[1]
219 max_x = max(max_x, x)
220 min_x = min(min_x, x)
bensong@google.comd3fd98f2012-12-18 20:06:10 +0000221
bungeman@google.com85669f92011-06-17 13:58:14 +0000222 Sx += x
223 Sy += y
224 Sxx += x*x
225 Sxy += x*y
226 Syy += y*y
bensong@google.comd3fd98f2012-12-18 20:06:10 +0000227
senorblanco@chromium.orgc5e1ed82012-09-20 19:05:33 +0000228 denom = n*Sxx - Sx*Sx
229 if (denom != 0.0):
230 B = (n*Sxy - Sx*Sy) / denom
231 else:
232 B = 0.0
bungeman@google.com85669f92011-06-17 13:58:14 +0000233 a = (1.0/n)*(Sy - B*Sx)
bensong@google.comd3fd98f2012-12-18 20:06:10 +0000234
bungeman@google.com85669f92011-06-17 13:58:14 +0000235 se2 = 0
236 sB2 = 0
237 sa2 = 0
senorblanco@chromium.orgc5e1ed82012-09-20 19:05:33 +0000238 if (n >= 3 and denom != 0.0):
239 se2 = (1.0/(n*(n-2)) * (n*Syy - Sy*Sy - B*B*denom))
240 sB2 = (n*se2) / denom
bungeman@google.com85669f92011-06-17 13:58:14 +0000241 sa2 = sB2 * (1.0/n) * Sxx
bensong@google.comd3fd98f2012-12-18 20:06:10 +0000242
243
bungeman@google.com85669f92011-06-17 13:58:14 +0000244 self.slope = B
245 self.intercept = a
246 self.serror = math.sqrt(max(0, se2))
247 self.serror_slope = math.sqrt(max(0, sB2))
248 self.serror_intercept = math.sqrt(max(0, sa2))
249 self.max_x = max_x
250 self.min_x = min_x
bensong@google.comd3fd98f2012-12-18 20:06:10 +0000251
bungeman@google.com85669f92011-06-17 13:58:14 +0000252 def __repr__(self):
253 return "LinearRegression(%s, %s, %s, %s, %s)" % (
254 str(self.slope),
255 str(self.intercept),
256 str(self.serror),
257 str(self.serror_slope),
258 str(self.serror_intercept),
259 )
bensong@google.comd3fd98f2012-12-18 20:06:10 +0000260
bungeman@google.com85669f92011-06-17 13:58:14 +0000261 def find_min_slope(self):
262 """Finds the minimal slope given one standard deviation."""
263 slope = self.slope
264 intercept = self.intercept
265 error = self.serror
266 regr_start = self.min_x
267 regr_end = self.max_x
268 regr_width = regr_end - regr_start
bensong@google.comd3fd98f2012-12-18 20:06:10 +0000269
bungeman@google.com85669f92011-06-17 13:58:14 +0000270 if slope < 0:
271 lower_left_y = slope*regr_start + intercept - error
272 upper_right_y = slope*regr_end + intercept + error
273 return min(0, (upper_right_y - lower_left_y) / regr_width)
bensong@google.comd3fd98f2012-12-18 20:06:10 +0000274
bungeman@google.com85669f92011-06-17 13:58:14 +0000275 elif slope > 0:
276 upper_left_y = slope*regr_start + intercept + error
277 lower_right_y = slope*regr_end + intercept - error
278 return max(0, (lower_right_y - upper_left_y) / regr_width)
bensong@google.comd3fd98f2012-12-18 20:06:10 +0000279
bungeman@google.com85669f92011-06-17 13:58:14 +0000280 return 0
epoger@google.comc71174d2011-08-08 17:19:23 +0000281
282def CreateRevisionLink(revision_number):
283 """Returns HTML displaying the given revision number and linking to
284 that revision's change page at code.google.com, e.g.
285 http://code.google.com/p/skia/source/detail?r=2056
286 """
287 return '<a href="http://code.google.com/p/skia/source/detail?r=%s">%s</a>'%(
288 revision_number, revision_number)
senorblanco@chromium.orgc5e1ed82012-09-20 19:05:33 +0000289
290def main():
291 foo = [[0.0, 0.0], [0.0, 1.0], [0.0, 2.0], [0.0, 3.0]]
292 LinearRegression(foo)
293
294if __name__ == "__main__":
295 main()