mercurial/lsprofcalltree.py
author Durham Goode <durham@fb.com>
Sat, 07 Nov 2015 16:11:49 -0800
changeset 26909 e36118815a39
parent 8390 beae42f3d93b
child 27505 071af8d385a9
permissions -rw-r--r--
phase: improve retractboundary perf The existing retractboundary implementation computed the new boundary by walking all descendants of all existing roots and computing the new roots. This is O(commits since first root), which on long repos can be hundreds of thousands of commits. The new algorithm only updates roots that are greater than the new root locations. For common operations like commit on a repo with the earliest root several hundred thousand commits ago, this makes retractboundary go from 1 second to 0.008 seconds. I tested it by running the test suite with both implementations and checking that the root results were always the identical. There was some discussion on IRC about the safety of this (i.e. what if the new nodes are already part of the phase, etc). I've looked into it and believe this patch is safe: 1) The old existing code already filters the input nodes to only contain nodes that require retracting (i.e. we only make node X a new root if the old phase is less than the target phase), so there's no chance of us adding a unnecessary root to the phase (unless the input root is made unnecessary by another root in the same input, but see point #3). 2) Another way of thinking about this is: the only way the new algorithm would be different from the old algorithm is if it added a root that is a descendant of an old root (since the old algorithm would've caught this in the big "roots(%ln::)". At the beginning of the function, when we filter out roots that already meet the phase criteria, the *definition* of meeting the phase criteria is "not being a descendant of an existing root". Therefore, by definition none of the new roots we are processing are descendants of an existing root. 3) If two nodes are passed in as input, and one node is an ancestor of the other (and therefore the later node should not be a root), this is still caught by the 'roots(%ln::)' revset. So there's no chance of an extra root being introduced that way either.
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
8024
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
     1
"""
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
     2
lsprofcalltree.py - lsprof output which is readable by kcachegrind
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
     3
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
     4
Authors:
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
     5
    * David Allouche <david <at> allouche.net>
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
     6
    * Jp Calderone & Itamar Shtull-Trauring
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
     7
    * Johan Dahlin
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
     8
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
     9
This software may be used and distributed according to the terms
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    10
of the GNU General Public License, incorporated herein by reference.
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    11
"""
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    12
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    13
def label(code):
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    14
    if isinstance(code, str):
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    15
        return '~' + code    # built-in functions ('~' sorts at the end)
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    16
    else:
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    17
        return '%s %s:%d' % (code.co_name,
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    18
                             code.co_filename,
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    19
                             code.co_firstlineno)
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    20
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    21
class KCacheGrind(object):
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    22
    def __init__(self, profiler):
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    23
        self.data = profiler.getstats()
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    24
        self.out_file = None
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    25
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    26
    def output(self, out_file):
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    27
        self.out_file = out_file
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    28
        print >> out_file, 'events: Ticks'
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    29
        self._print_summary()
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    30
        for entry in self.data:
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    31
            self._entry(entry)
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    32
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    33
    def _print_summary(self):
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    34
        max_cost = 0
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    35
        for entry in self.data:
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    36
            totaltime = int(entry.totaltime * 1000)
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    37
            max_cost = max(max_cost, totaltime)
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    38
        print >> self.out_file, 'summary: %d' % (max_cost,)
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    39
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    40
    def _entry(self, entry):
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    41
        out_file = self.out_file
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    42
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    43
        code = entry.code
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    44
        #print >> out_file, 'ob=%s' % (code.co_filename,)
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    45
        if isinstance(code, str):
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    46
            print >> out_file, 'fi=~'
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    47
        else:
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    48
            print >> out_file, 'fi=%s' % (code.co_filename,)
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    49
        print >> out_file, 'fn=%s' % (label(code),)
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    50
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    51
        inlinetime = int(entry.inlinetime * 1000)
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    52
        if isinstance(code, str):
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    53
            print >> out_file, '0 ', inlinetime
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    54
        else:
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    55
            print >> out_file, '%d %d' % (code.co_firstlineno, inlinetime)
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    56
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    57
        # recursive calls are counted in entry.calls
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    58
        if entry.calls:
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    59
            calls = entry.calls
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    60
        else:
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    61
            calls = []
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    62
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    63
        if isinstance(code, str):
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    64
            lineno = 0
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    65
        else:
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    66
            lineno = code.co_firstlineno
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    67
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    68
        for subentry in calls:
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    69
            self._subentry(lineno, subentry)
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    70
        print >> out_file
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    71
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    72
    def _subentry(self, lineno, subentry):
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    73
        out_file = self.out_file
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    74
        code = subentry.code
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    75
        #print >> out_file, 'cob=%s' % (code.co_filename,)
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    76
        print >> out_file, 'cfn=%s' % (label(code),)
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    77
        if isinstance(code, str):
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    78
            print >> out_file, 'cfi=~'
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    79
            print >> out_file, 'calls=%d 0' % (subentry.callcount,)
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    80
        else:
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    81
            print >> out_file, 'cfi=%s' % (code.co_filename,)
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    82
            print >> out_file, 'calls=%d %d' % (
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    83
                subentry.callcount, code.co_firstlineno)
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    84
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    85
        totaltime = int(subentry.totaltime * 1000)
9a1b86cfd29e profiling: Adding support for kcachegrind output format, using lsprofcalltree
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
diff changeset
    86
        print >> out_file, '%d %d' % (lineno, totaltime)