The Tor Browser: js/src/devtools/jint/treesearch.py@6474c204b198

Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.

     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/.

     6 import os, re

     7 import tempfile

     8 import subprocess

     9 import sys, math

    10 import datetime

    11 import random

    13 def realpath(k):

    14     return os.path.realpath(os.path.normpath(k))

    16 class UCTNode:

    17     def __init__(self, loop):

    18         self.children = None

    19         self.loop = loop

    20         self.visits = 1

    21         self.score = 0

    23     def addChild(self, child):

    24         if self.children == None:

    25             self.children = []

    26         self.children.append(child)

    28     def computeUCB(self, coeff):

    29         return (self.score / self.visits) + math.sqrt(coeff / self.visits)

    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()

    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

    55     def findBestChild(self, node):

    56         coeff = self.bias * math.log(node.visits)

    57         bestChild = None

    58         bestUCB = -float('Infinity')

    60         for child in node.children:

    61             ucb = child.computeUCB(coeff)

    62             if ucb >= bestUCB:

    63                 bestUCB = ucb

    64                 bestChild = child

    66         return child

    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]

    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

    86     def step(self, loopList):

    87         node = self.root

    88         pending = loopList[:]

    89         history = [node]

    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

   100                 # Otherwise, this is a leaf node. Run a playout.

   101                 score = self.playout(history)

   102                 break

   104             # Find the best child.

   105             node = self.findBestChild(node)

   106             history.append(node)

   107             pending.remove(node.loop)

   109         # Normalize the score.

   110         origScore = score

   111         score = (self.originalBest - score) / self.originalBest

   113         for node in history:

   114             node.visits += 1

   115             node.score += score

   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)

   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)

   130         for i in range(0, self.numPlayouts):

   131             self.step(loopList)

   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)

   143         return [self.bestTime, combos]

   145 class Benchmark:

   146     def __init__(self, JS, fname):

   147         self.fname = fname

   148         self.JS = JS

   149         self.stats = { }

   150         self.runList = [ ]

   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()

   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)

   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

   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')

   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]

   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

   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()

   226     def internalExhaustiveSearch(self, params):

   227         counters = params['counters']

   229         # iterative algorithm to explore every combination

   230         ncombos = 2 ** len(counters)

   231         queue = []

   232         for c in counters:

   233             queue.append(0)

   235         fd = params['fd']

   236         bestTime = float('Infinity')

   237         bestCombos = []

   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)

   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[:])

   255             i = i + 1

   257         return [bestTime, bestCombos]

   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']

   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

   274         enableLoops = False

   276         uct = UCT(self, combinedTime, enableLoops, counters[:], fd, 50000)

   277         return uct.run()

   279     def treeSearch(self):

   280         fd, counters = self.ppForTreeSearch()

   282         os.system("cat " + fd.name + " > /tmp/k.js")

   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'])

   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

   307         best = min(methodTime, tracerTime, combinedTime)

   309         params = {

   310                     'fd': fd,

   311                     'counters': counters,

   312                     'methodTime': methodTime,

   313                     'tracerTime': tracerTime,

   314                     'combinedTime': combinedTime

   315                  }

   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)))

   321         if 1 and treeSearch:

   322             results = self.internalTreeSearch(params)

   323         else:

   324             results = self.internalExhaustiveSearch(params)

   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)))

   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)))

   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')

   347         lines = ['var JINT_START_TIME = Date.now();\n',

   348                  'var GLOBAL_THINGY = 0;\n']

   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]

   358     def preprocessForLoopCounting(self):

   359         def onBegin(lines, lineno):

   360             lines.append('JINT_TRACKER.line_' + str(lineno) + '_start = Date.now();\n')

   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')

   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

   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')

   392     # The [TESTS] optional arguments are paths of test files relative

   393     # to the jit-test/tests directory.

   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])

   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()

The Tor Browser / file revision

js/src/devtools/jint/treesearch.py@6474c204b198

js/src/devtools/jint/treesearch.py