The Tor Browser / file comparison

comparison: js/src/devtools/jint/treesearch.py

js/src/devtools/jint/treesearch.py

branch
TOR_BUG_3246
changeset 7
129ffea94266
equal deleted inserted replaced
-1:000000000000 0:e814c6e08711
1 # vim: set ts=8 sts=4 et sw=4 tw=99:
2 # This Source Code Form is subject to the terms of the Mozilla Public
3 # License, v. 2.0. If a copy of the MPL was not distributed with this
4 # file, You can obtain one at http://mozilla.org/MPL/2.0/.
5
6 import os, re
7 import tempfile
8 import subprocess
9 import sys, math
10 import datetime
11 import random
12
13 def realpath(k):
14 return os.path.realpath(os.path.normpath(k))
15
16 class UCTNode:
17 def __init__(self, loop):
18 self.children = None
19 self.loop = loop
20 self.visits = 1
21 self.score = 0
22
23 def addChild(self, child):
24 if self.children == None:
25 self.children = []
26 self.children.append(child)
27
28 def computeUCB(self, coeff):
29 return (self.score / self.visits) + math.sqrt(coeff / self.visits)
30
31 class UCT:
32 def __init__(self, benchmark, bestTime, enableLoops, loops, fd, playouts):
33 self.bm = benchmark
34 self.fd = fd
35 self.numPlayouts = playouts
36 self.maxNodes = self.numPlayouts * 20
37 self.loops = loops
38 self.enableLoops = enableLoops
39 self.maturityThreshold = 20
40 self.originalBest = bestTime
41 self.bestTime = bestTime
42 self.bias = 20
43 self.combos = []
44 self.zobrist = { }
45 random.seed()
46
47 def expandNode(self, node, pending):
48 for loop in pending:
49 node.addChild(UCTNode(loop))
50 self.numNodes += 1
51 if self.numNodes >= self.maxNodes:
52 return False
53 return True
54
55 def findBestChild(self, node):
56 coeff = self.bias * math.log(node.visits)
57 bestChild = None
58 bestUCB = -float('Infinity')
59
60 for child in node.children:
61 ucb = child.computeUCB(coeff)
62 if ucb >= bestUCB:
63 bestUCB = ucb
64 bestChild = child
65
66 return child
67
68 def playout(self, history):
69 queue = []
70 for i in range(0, len(self.loops)):
71 queue.append(random.randint(0, 1))
72 for node in history:
73 queue[node.loop] = not self.enableLoops
74 zash = 0
75 for i in range(0, len(queue)):
76 if queue[i]:
77 zash |= (1 << i)
78 if zash in self.zobrist:
79 return self.zobrist[zash]
80
81 self.bm.generateBanList(self.loops, queue)
82 result = self.bm.treeSearchRun(self.fd, ['-m', '-j'], 3)
83 self.zobrist[zash] = result
84 return result
85
86 def step(self, loopList):
87 node = self.root
88 pending = loopList[:]
89 history = [node]
90
91 while True:
92 # If this is a leaf node...
93 if node.children == None:
94 # And the leaf node is mature...
95 if node.visits >= self.maturityThreshold:
96 # If the node can be expanded, keep spinning.
97 if self.expandNode(node, pending) and node.children != None:
98 continue
99
100 # Otherwise, this is a leaf node. Run a playout.
101 score = self.playout(history)
102 break
103
104 # Find the best child.
105 node = self.findBestChild(node)
106 history.append(node)
107 pending.remove(node.loop)
108
109 # Normalize the score.
110 origScore = score
111 score = (self.originalBest - score) / self.originalBest
112
113 for node in history:
114 node.visits += 1
115 node.score += score
116
117 if int(origScore) < int(self.bestTime):
118 print('New best score: {0:f}ms'.format(origScore))
119 self.combos = [history]
120 self.bestTime = origScore
121 elif int(origScore) == int(self.bestTime):
122 self.combos.append(history)
123
124 def run(self):
125 loopList = [i for i in range(0, len(self.loops))]
126 self.numNodes = 1
127 self.root = UCTNode(-1)
128 self.expandNode(self.root, loopList)
129
130 for i in range(0, self.numPlayouts):
131 self.step(loopList)
132
133 # Build the expected combination vector.
134 combos = [ ]
135 for combo in self.combos:
136 vec = [ ]
137 for i in range(0, len(self.loops)):
138 vec.append(int(self.enableLoops))
139 for node in combo:
140 vec[node.loop] = int(not self.enableLoops)
141 combos.append(vec)
142
143 return [self.bestTime, combos]
144
145 class Benchmark:
146 def __init__(self, JS, fname):
147 self.fname = fname
148 self.JS = JS
149 self.stats = { }
150 self.runList = [ ]
151
152 def run(self, fd, eargs):
153 args = [self.JS]
154 args.extend(eargs)
155 args.append(fd.name)
156 return subprocess.check_output(args).decode()
157
158 # self.stats[name] = { }
159 # self.runList.append(name)
160 # for line in output.split('\n'):
161 # m = re.search('line (\d+): (\d+)', line)
162 # if m:
163 # self.stats[name][int(m.group(1))] = int(m.group(2))
164 # else:
165 # m = re.search('total: (\d+)', line)
166 # if m:
167 # self.stats[name]['total'] = m.group(1)
168
169 def winnerForLine(self, line):
170 best = self.runList[0]
171 bestTime = self.stats[best][line]
172 for run in self.runList[1:]:
173 x = self.stats[run][line]
174 if x < bestTime:
175 best = run
176 bestTime = x
177 return best
178
179 def chart(self):
180 sys.stdout.write('{0:7s}'.format(''))
181 sys.stdout.write('{0:15s}'.format('line'))
182 for run in self.runList:
183 sys.stdout.write('{0:15s}'.format(run))
184 sys.stdout.write('{0:15s}\n'.format('best'))
185 for c in self.counters:
186 sys.stdout.write('{0:10d}'.format(c))
187 for run in self.runList:
188 sys.stdout.write('{0:15d}'.format(self.stats[run][c]))
189 sys.stdout.write('{0:12s}'.format(''))
190 sys.stdout.write('{0:15s}'.format(self.winnerForLine(c)))
191 sys.stdout.write('\n')
192
193 def preprocess(self, lines, onBegin, onEnd):
194 stack = []
195 counters = []
196 rd = open(self.fname, 'rt')
197 for line in rd:
198 if re.search('\/\* BEGIN LOOP \*\/', line):
199 stack.append([len(lines), len(counters)])
200 counters.append([len(lines), 0])
201 onBegin(lines, len(lines))
202 elif re.search('\/\* END LOOP \*\/', line):
203 old = stack.pop()
204 onEnd(lines, old[0], len(lines))
205 counters[old[1]][1] = len(lines)
206 else:
207 lines.append(line)
208 return [lines, counters]
209
210 def treeSearchRun(self, fd, args, count = 5):
211 total = 0
212 for i in range(0, count):
213 output = self.run(fd, args)
214 total += int(output)
215 return total / count
216
217 def generateBanList(self, counters, queue):
218 if os.path.exists('/tmp/permabans'):
219 os.unlink('/tmp/permabans')
220 fd = open('/tmp/permabans', 'wt')
221 for i in range(0, len(counters)):
222 for j in range(counters[i][0], counters[i][1] + 1):
223 fd.write('{0:d} {1:d}\n'.format(j, int(queue[i])))
224 fd.close()
225
226 def internalExhaustiveSearch(self, params):
227 counters = params['counters']
228
229 # iterative algorithm to explore every combination
230 ncombos = 2 ** len(counters)
231 queue = []
232 for c in counters:
233 queue.append(0)
234
235 fd = params['fd']
236 bestTime = float('Infinity')
237 bestCombos = []
238
239 i = 0
240 while i < ncombos:
241 temp = i
242 for j in range(0, len(counters)):
243 queue[j] = temp & 1
244 temp = temp >> 1
245 self.generateBanList(counters, queue)
246
247 t = self.treeSearchRun(fd, ['-m', '-j'])
248 if (t < bestTime):
249 bestTime = t
250 bestCombos = [queue[:]]
251 print('New best time: {0:f}ms'.format(t))
252 elif int(t) == int(bestTime):
253 bestCombos.append(queue[:])
254
255 i = i + 1
256
257 return [bestTime, bestCombos]
258
259 def internalTreeSearch(self, params):
260 fd = params['fd']
261 methodTime = params['methodTime']
262 tracerTime = params['tracerTime']
263 combinedTime = params['combinedTime']
264 counters = params['counters']
265
266 # Build the initial loop data.
267 # If the method JIT already wins, disable tracing by default.
268 # Otherwise, enable tracing by default.
269 if methodTime < combinedTime:
270 enableLoops = True
271 else:
272 enableLoops = False
273
274 enableLoops = False
275
276 uct = UCT(self, combinedTime, enableLoops, counters[:], fd, 50000)
277 return uct.run()
278
279 def treeSearch(self):
280 fd, counters = self.ppForTreeSearch()
281
282 os.system("cat " + fd.name + " > /tmp/k.js")
283
284 if os.path.exists('/tmp/permabans'):
285 os.unlink('/tmp/permabans')
286 methodTime = self.treeSearchRun(fd, ['-m'])
287 tracerTime = self.treeSearchRun(fd, ['-j'])
288 combinedTime = self.treeSearchRun(fd, ['-m', '-j'])
289
290 #Get a rough estimate of how long this benchmark will take to fully compute.
291 upperBound = max(methodTime, tracerTime, combinedTime)
292 upperBound *= 2 ** len(counters)
293 upperBound *= 5 # Number of runs
294 treeSearch = False
295 if (upperBound < 1000):
296 print('Estimating {0:d}ms to test, so picking exhaustive '.format(int(upperBound)) +
297 'search.')
298 else:
299 upperBound = int(upperBound / 1000)
300 delta = datetime.timedelta(seconds = upperBound)
301 if upperBound < 180:
302 print('Estimating {0:d}s to test, so picking exhaustive '.format(int(upperBound)))
303 else:
304 print('Estimating {0:s} to test, so picking tree search '.format(str(delta)))
305 treeSearch = True
306
307 best = min(methodTime, tracerTime, combinedTime)
308
309 params = {
310 'fd': fd,
311 'counters': counters,
312 'methodTime': methodTime,
313 'tracerTime': tracerTime,
314 'combinedTime': combinedTime
315 }
316
317 print('Method JIT: {0:d}ms'.format(int(methodTime)))
318 print('Tracing JIT: {0:d}ms'.format(int(tracerTime)))
319 print('Combined: {0:d}ms'.format(int(combinedTime)))
320
321 if 1 and treeSearch:
322 results = self.internalTreeSearch(params)
323 else:
324 results = self.internalExhaustiveSearch(params)
325
326 bestTime = results[0]
327 bestCombos = results[1]
328 print('Search found winning time {0:d}ms!'.format(int(bestTime)))
329 print('Combos at this time: {0:d}'.format(len(bestCombos)))
330
331 #Find loops that traced every single time
332 for i in range(0, len(counters)):
333 start = counters[i][0]
334 end = counters[i][1]
335 n = len(bestCombos)
336 for j in bestCombos:
337 n -= j[i]
338 print('\tloop @ {0:d}-{1:d} traced {2:d}% of the time'.format(
339 start, end, int(n / len(bestCombos) * 100)))
340
341 def ppForTreeSearch(self):
342 def onBegin(lines, lineno):
343 lines.append('GLOBAL_THINGY = 1;\n')
344 def onEnd(lines, old, lineno):
345 lines.append('GLOBAL_THINGY = 1;\n')
346
347 lines = ['var JINT_START_TIME = Date.now();\n',
348 'var GLOBAL_THINGY = 0;\n']
349
350 lines, counters = self.preprocess(lines, onBegin, onEnd)
351 fd = tempfile.NamedTemporaryFile('wt')
352 for line in lines:
353 fd.write(line)
354 fd.write('print(Date.now() - JINT_START_TIME);\n')
355 fd.flush()
356 return [fd, counters]
357
358 def preprocessForLoopCounting(self):
359 def onBegin(lines, lineno):
360 lines.append('JINT_TRACKER.line_' + str(lineno) + '_start = Date.now();\n')
361
362 def onEnd(lines, old, lineno):
363 lines.append('JINT_TRACKER.line_' + str(old) + '_end = Date.now();\n')
364 lines.append('JINT_TRACKER.line_' + str(old) + '_total += ' + \
365 'JINT_TRACKER.line_' + str(old) + '_end - ' + \
366 'JINT_TRACKER.line_' + str(old) + '_start;\n')
367
368 lines, counters = self.preprocess(onBegin, onEnd)
369 fd = tempfile.NamedTemporaryFile('wt')
370 fd.write('var JINT_TRACKER = { };\n')
371 for c in counters:
372 fd.write('JINT_TRACKER.line_' + str(c) + '_start = 0;\n')
373 fd.write('JINT_TRACKER.line_' + str(c) + '_end = 0;\n')
374 fd.write('JINT_TRACKER.line_' + str(c) + '_total = 0;\n')
375 fd.write('JINT_TRACKER.begin = Date.now();\n')
376 for line in lines:
377 fd.write(line)
378 fd.write('JINT_TRACKER.total = Date.now() - JINT_TRACKER.begin;\n')
379 for c in self.counters:
380 fd.write('print("line ' + str(c) + ': " + JINT_TRACKER.line_' + str(c) +
381 '_total);')
382 fd.write('print("total: " + JINT_TRACKER.total);')
383 fd.flush()
384 return fd
385
386 if __name__ == '__main__':
387 script_path = os.path.abspath(__file__)
388 script_dir = os.path.dirname(script_path)
389 test_dir = os.path.join(script_dir, 'tests')
390 lib_dir = os.path.join(script_dir, 'lib')
391
392 # The [TESTS] optional arguments are paths of test files relative
393 # to the jit-test/tests directory.
394
395 from optparse import OptionParser
396 op = OptionParser(usage='%prog [options] JS_SHELL test')
397 (OPTIONS, args) = op.parse_args()
398 if len(args) < 2:
399 op.error('missing JS_SHELL and test argument')
400 # We need to make sure we are using backslashes on Windows.
401 JS = realpath(args[0])
402 test = realpath(args[1])
403
404 bm = Benchmark(JS, test)
405 bm.treeSearch()
406 # bm.preprocess()
407 # bm.run('mjit', ['-m'])
408 # bm.run('tjit', ['-j'])
409 # bm.run('m+tjit', ['-m', '-j'])
410 # bm.chart()
411

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial