使用valgrind进行性能分析，过程如下：
*** @Ubuntu :/Performance$ valgrind --tool=callgrind ./mt/Performance$ ls
==7389== Callgrind, a call-graph generating cache profiler
==7389== Copyright (C) 2002-2012, and GNU GPL'd, by Josef Weidendorfer et al.
==7389== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info
==7389== Command: ./mt
==7389==
==7389== For interactive control, run 'callgrind_control -h'.
==7389==
==7389== Events : Ir
==7389== Collected : 231867136
==7389==
==7389== I refs: 231,867,136
Profiling timer expired
*** @ubuntu :
callgrind.out.7389 gmon.out gprof2dot.py gprof.dot gprof.png map_test.cpp mt prof.log
*** @ubuntu :/Performance$ python gprof2dot.py -f callgrind -n10 -s callgrind.out.7389 > valgrind.dot/Performance$ xdot valgrind.dot 或 dot -Tpng valgrind.dot -o valgrind.png
*** @ubuntu :
首先，使用valgrind运行程序，会生成callgrind.out.7389，其中7389是运行程序的进程号，值得一提的是，valgrind还可以做其他很多事情，比如内存泄漏的检测等。
其次，使用gprof2dot.py生成dot文件。
需下载安装graphviz和valgrind
gprof2dot.py代码：
1#!/usr/bin/env python 2# 3# Copyright 2008-2009 Jose Fonseca 4# 5# This program is free software: you can redistribute it and/or modify it 6# under the terms of the GNU Lesser General Public License as published 7# by the Free Software Foundation, either version 3 of the License, or 8# (at your option) any later version. 9# 10# This program is distributed in the hope that it will be useful, 11# but WITHOUT ANY WARRANTY; without even the implied warranty of 12# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13# GNU Lesser General Public License for more details. 14# 15# You should have received a copy of the GNU Lesser General Public License 16# along with this program. If not, see <http://www.gnu.org/licenses/>. 17# 18 19"""Generate a dot graph from the output of several profilers.""" 20 21__author__ = "Jose Fonseca" 22 23__version__ = "1.0" 24 25 26import sys 27import math 28import os.path 29import re 30import textwrap 31import optparse 32import xml.parsers.expat 33import collections 34 35 36try: 37 # Debugging helper module 38 import debug 39except ImportError: 40 pass 41 42 43def times(x): 44 return u"%u\xd7" % (x,) 45 46def percentage(p): 47 return "%.02f%%" % (p*100.0,) 48 49def add(a, b): 50 return a + b 51 52def equal(a, b): 53 if a == b: 54 return a 55 else: 56 return None 57 58def fail(a, b): 59 assert False 60 61 62tol = 2 ** -23 63 64def ratio(numerator, denominator): 65 try: 66 ratio = float(numerator)/float(denominator) 67 except ZeroDivisionError: 68 # 0/0 is undefined, but 1.0 yields more useful results 69 return 1.0 70 if ratio < 0.0: 71 if ratio < -tol: 72 sys.stderr.write('warning: negative ratio (%s/%s)\n' % (numerator, denominator)) 73 return 0.0 74 if ratio > 1.0: 75 if ratio > 1.0 + tol: 76 sys.stderr.write('warning: ratio greater than one (%s/%s)\n' % (numerator, denominator)) 77 return 1.0 78 return ratio 79 80 81class UndefinedEvent(Exception): 82 """Raised when attempting to get an event which is undefined.""" 83 84 def __init__(self, event): 85 Exception.__init__(self) 86 self.event = event 87 88 def __str__(self): 89 return 'unspecified event %s' % self.event.name 90 91 92class Event(object): 93 """Describe a kind of event, and its basic operations.""" 94 95 def __init__(self, name, null, aggregator, formatter = str): 96 self.name = name 97 self._null = null 98 self._aggregator = aggregator 99 self._formatter = formatter 100 101 def __eq__(self, other): 102 return self is other 103 104 def __hash__(self): 105 return id(self) 106 107 def null(self): 108 return self._null 109 110 def aggregate(self, val1, val2): 111 """Aggregate two event values.""" 112 assert val1 is not None 113 assert val2 is not None 114 return self._aggregator(val1, val2) 115 116 def format(self, val): 117 """Format an event value.""" 118 assert val is not None 119 return self._formatter(val) 120 121 122CALLS = Event("Calls", 0, add, times) 123SAMPLES = Event("Samples", 0, add) 124SAMPLES2 = Event("Samples", 0, add) 125 126TIME = Event("Time", 0.0, add, lambda x: '(' + str(x) + ')') 127TIME_RATIO = Event("Time ratio", 0.0, add, lambda x: '(' + percentage(x) + ')') 128TOTAL_TIME = Event("Total time", 0.0, fail) 129TOTAL_TIME_RATIO = Event("Total time ratio", 0.0, fail, percentage) 130 131 132class Object(object): 133 """Base class for all objects in profile which can store events.""" 134 135 def __init__(self, events=None): 136 if events is None: 137 self.events = {} 138 else: 139 self.events = events 140 141 def __hash__(self): 142 return id(self) 143 144 def __eq__(self, other): 145 return self is other 146 147 def __contains__(self, event): 148 return event in self.events 149 150 def __getitem__(self, event): 151 try: 152 return self.events[event] 153 except KeyError: 154 raise UndefinedEvent(event) 155 156 def __setitem__(self, event, value): 157 if value is None: 158 if event in self.events: 159 del self.events[event] 160 else: 161 self.events[event] = value 162 163 164class Call(Object): 165 """A call between functions. 166 167 There should be at most one call object for every pair of functions. 168 """ 169 170 def __init__(self, callee_id): 171 Object.__init__(self) 172 self.callee_id = callee_id 173 self.ratio = None 174 self.weight = None 175 176 177class Function(Object): 178 """A function.""" 179 180 def __init__(self, id, name): 181 Object.__init__(self) 182 self.id = id 183 self.name = name 184 self.module = None 185 self.process = None 186 self.calls = {} 187 self.called = None 188 self.weight = None 189 self.cycle = None 190 191 def add_call(self, call): 192 if call.callee_id in self.calls: 193 sys.stderr.write('warning: overwriting call from function %s to %s\n' % (str(self.id), str(call.callee_id))) 194 self.calls[call.callee_id] = call 195 196 def get_call(self, callee_id): 197 if not callee_id in self.calls: 198 call = Call(callee_id) 199 call[SAMPLES] = 0 200 call[SAMPLES2] = 0 201 call[CALLS] = 0 202 self.calls[callee_id] = call 203 return self.calls[callee_id] 204 205 _parenthesis_re = re.compile(r'\([^()]*\)') 206 _angles_re = re.compile(r'<[^<>]*>') 207 _const_re = re.compile(r'\s+const$') 208 209 def stripped_name(self): 210 """Remove extraneous information from C++ demangled function names.""" 211 212 name = self.name 213 214 # Strip function parameters from name by recursively removing paired parenthesis 215 while True: 216 name, n = self._parenthesis_re.subn('', name) 217 if not n: 218 break 219 220 # Strip const qualifier 221 name = self._const_re.sub('', name) 222 223 # Strip template parameters from name by recursively removing paired angles 224 while True: 225 name, n = self._angles_re.subn('', name) 226 if not n: 227 break 228 229 return name 230 231 # TODO: write utility functions 232 233 def __repr__(self): 234 return self.name 235 236 237class Cycle(Object): 238 """A cycle made from recursive function calls.""" 239 240 def __init__(self): 241 Object.__init__(self) 242 # XXX: Do cycles need an id? 243 self.functions = set() 244 245 def add_function(self, function): 246 assert function not in self.functions 247 self.functions.add(function) 248 # XXX: Aggregate events? 249 if function.cycle is not None: 250 for other in function.cycle.functions: 251 if function not in self.functions: 252 self.add_function(other) 253 function.cycle = self 254 255 256class Profile(Object): 257 """The whole profile.""" 258 259 def __init__(self): 260 Object.__init__(self) 261 self.functions = {} 262 self.cycles = [] 263 264 def add_function(self, function): 265 if function.id in self.functions: 266 sys.stderr.write('warning: overwriting function %s (id %s)\n' % (function.name, str(function.id))) 267 self.functions[function.id] = function 268 269 def add_cycle(self, cycle): 270 self.cycles.append(cycle) 271 272 def validate(self): 273 """Validate the edges.""" 274 275 for function in self.functions.itervalues(): 276 for callee_id in function.calls.keys(): 277 assert function.calls[callee_id].callee_id == callee_id 278 if callee_id not in self.functions: 279 sys.stderr.write('warning: call to undefined function %s from function %s\n' % (str(callee_id), function.name)) 280 del function.calls[callee_id] 281 282 def find_cycles(self): 283 """Find cycles using Tarjan's strongly connected components algorithm.""" 284 285 # Apply the Tarjan's algorithm successively until all functions are visited 286 visited = set() 287 for function in self.functions.itervalues(): 288 if function not in visited: 289 self._tarjan(function, 0, [], {}, {}, visited) 290 cycles = [] 291 for function in self.functions.itervalues(): 292 if function.cycle is not None and function.cycle not in cycles: 293 cycles.append(function.cycle) 294 self.cycles = cycles 295 if 0: 296 for cycle in cycles: 297 sys.stderr.write("Cycle:\n") 298 for member in cycle.functions: 299 sys.stderr.write("\tFunction %s\n" % member.name) 300 301 def prune_root(self, root): 302 visited = set() 303 frontier = set([root]) 304 while len(frontier) > 0: 305 node = frontier.pop() 306 visited.add(node) 307 f = self.functions[node] 308 newNodes = f.calls.keys() 309 frontier = frontier.union(set(newNodes) - visited) 310 subtreeFunctions = {} 311 for n in visited: 312 subtreeFunctions[n] = self.functions[n] 313 self.functions = subtreeFunctions 314 315 def prune_leaf(self, leaf): 316 edgesUp = collections.defaultdict(set) 317 for f in self.functions.keys(): 318 for n in self.functions[f].calls.keys(): 319 edgesUp[n].add(f) 320 # build the tree up 321 visited = set() 322 frontier = set([leaf]) 323 while len(frontier) > 0: 324 node = frontier.pop() 325 visited.add(node) 326 frontier = frontier.union(edgesUp[node] - visited) 327 downTree = set(self.functions.keys()) 328 upTree = visited 329 path = downTree.intersection(upTree) 330 pathFunctions = {} 331 for n in path: 332 f = self.functions[n] 333 newCalls = {} 334 for c in f.calls.keys(): 335 if c in path: 336 newCalls[c] = f.calls[c] 337 f.calls = newCalls 338 pathFunctions[n] = f 339 self.functions = pathFunctions 340 341 342 def getFunctionId(self, funcName): 343 for f in self.functions: 344 if self.functions[f].name == funcName: 345 return f 346 return False 347 348 def _tarjan(self, function, order, stack, orders, lowlinks, visited): 349 """Tarjan's strongly connected components algorithm. 350 351 See also: 352 - http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm 353 """ 354 355 visited.add(function) 356 orders[function] = order 357 lowlinks[function] = order 358 order += 1 359 pos = len(stack) 360 stack.append(function) 361 for call in function.calls.itervalues(): 362 callee = self.functions[call.callee_id] 363 # TODO: use a set to optimize lookup 364 if callee not in orders: 365 order = self._tarjan(callee, order, stack, orders, lowlinks, visited) 366 lowlinks[function] = min(lowlinks[function], lowlinks[callee]) 367 elif callee in stack: 368 lowlinks[function] = min(lowlinks[function], orders[callee]) 369 if lowlinks[function] == orders[function]: 370 # Strongly connected component found 371 members = stack[pos:] 372 del stack[pos:] 373 if len(members) > 1: 374 cycle = Cycle() 375 for member in members: 376 cycle.add_function(member) 377 return order 378 379 def call_ratios(self, event): 380 # Aggregate for incoming calls 381 cycle_totals = {} 382 for cycle in self.cycles: 383 cycle_totals[cycle] = 0.0 384 function_totals = {} 385 for function in self.functions.itervalues(): 386 function_totals[function] = 0.0 387 for function in self.functions.itervalues(): 388 for call in function.calls.itervalues(): 389 if call.callee_id != function.id: 390 callee = self.functions[call.callee_id] 391 function_totals[callee] += call[event] 392 if callee.cycle is not None and callee.cycle is not function.cycle: 393 cycle_totals[callee.cycle] += call[event] 394 395 # Compute the ratios 396 for function in self.functions.itervalues(): 397 for call in function.calls.itervalues(): 398 assert call.ratio is None 399 if call.callee_id != function.id: 400 callee = self.functions[call.callee_id] 401 if callee.cycle is not None and callee.cycle is not function.cycle: 402 total = cycle_totals[callee.cycle] 403 else: 404 total = function_totals[callee] 405 call.ratio = ratio(call[event], total) 406 407 def integrate(self, outevent, inevent): 408 """Propagate function time ratio allong the function calls. 409 410 Must be called after finding the cycles. 411 412 See also: 413 - http://citeseer.ist.psu.edu/graham82gprof.html 414 """ 415 416 # Sanity checking 417 assert outevent not in self 418 for function in self.functions.itervalues(): 419 assert outevent not in function 420 assert inevent in function 421 for call in function.calls.itervalues(): 422 assert outevent not in call 423 if call.callee_id != function.id: 424 assert call.ratio is not None 425 426 # Aggregate the input for each cycle 427 for cycle in self.cycles: 428 total = inevent.null() 429 for function in self.functions.itervalues(): 430 total = inevent.aggregate(total, function[inevent]) 431 self[inevent] = total 432 433 # Integrate along the edges 434 total = inevent.null() 435 for function in self.functions.itervalues(): 436 total = inevent.aggregate(total, function[inevent]) 437 self._integrate_function(function, outevent, inevent) 438 self[outevent] = total 439 440 def _integrate_function(self, function, outevent, inevent): 441 if function.cycle is not None: 442 return self._integrate_cycle(function.cycle, outevent, inevent) 443 else: 444 if outevent not in function: 445 total = function[inevent] 446 for call in function.calls.itervalues(): 447 if call.callee_id != function.id: 448 total += self._integrate_call(call, outevent, inevent) 449 function[outevent] = total 450 return function[outevent] 451 452 def _integrate_call(self, call, outevent, inevent): 453 assert outevent not in call 454 assert call.ratio is not None 455 callee = self.functions[call.callee_id] 456 subtotal = call.ratio *self._integrate_function(callee, outevent, inevent) 457 call[outevent] = subtotal 458 return subtotal 459 460 def _integrate_cycle(self, cycle, outevent, inevent): 461 if outevent not in cycle: 462 463 # Compute the outevent for the whole cycle 464 total = inevent.null() 465 for member in cycle.functions: 466 subtotal = member[inevent] 467 for call in member.calls.itervalues(): 468 callee = self.functions[call.callee_id] 469 if callee.cycle is not cycle: 470 subtotal += self._integrate_call(call, outevent, inevent) 471 total += subtotal 472 cycle[outevent] = total 473 474 # Compute the time propagated to callers of this cycle 475 callees = {} 476 for function in self.functions.itervalues(): 477 if function.cycle is not cycle: 478 for call in function.calls.itervalues(): 479 callee = self.functions[call.callee_id] 480 if callee.cycle is cycle: 481 try: 482 callees[callee] += call.ratio 483 except KeyError: 484 callees[callee] = call.ratio 485 486 for member in cycle.functions: 487 member[outevent] = outevent.null() 488 489 for callee, call_ratio in callees.iteritems(): 490 ranks = {} 491 call_ratios = {} 492 partials = {} 493 self._rank_cycle_function(cycle, callee, 0, ranks) 494 self._call_ratios_cycle(cycle, callee, ranks, call_ratios, set()) 495 partial = self._integrate_cycle_function(cycle, callee, call_ratio, partials, ranks, call_ratios, outevent, inevent) 496 assert partial == max(partials.values()) 497 assert not total or abs(1.0 - partial/(call_ratio*total)) <= 0.001 498 499 return cycle[outevent] 500 501 def _rank_cycle_function(self, cycle, function, rank, ranks): 502 if function not in ranks or ranks[function] > rank: 503 ranks[function] = rank 504 for call in function.calls.itervalues(): 505 if call.callee_id != function.id: 506 callee = self.functions[call.callee_id] 507 if callee.cycle is cycle: 508 self._rank_cycle_function(cycle, callee, rank + 1, ranks) 509 510 def _call_ratios_cycle(self, cycle, function, ranks, call_ratios, visited): 511 if function not in visited: 512 visited.add(function) 513 for call in function.calls.itervalues(): 514 if call.callee_id != function.id: 515 callee = self.functions[call.callee_id] 516 if callee.cycle is cycle: 517 if ranks[callee] > ranks[function]: 518 call_ratios[callee] = call_ratios.get(callee, 0.0) + call.ratio 519 self._call_ratios_cycle(cycle, callee, ranks, call_ratios, visited) 520 521 def _integrate_cycle_function(self, cycle, function, partial_ratio, partials, ranks, call_ratios, outevent, inevent): 522 if function not in partials: 523 partial = partial_ratio*function[inevent] 524 for call in function.calls.itervalues(): 525 if call.callee_id != function.id: 526 callee = self.functions[call.callee_id] 527 if callee.cycle is not cycle: 528 assert outevent in call 529 partial += partial_ratio*call[outevent] 530 else: 531 if ranks[callee] > ranks[function]: 532 callee_partial = self._integrate_cycle_function(cycle, callee, partial_ratio, partials, ranks, call_ratios, outevent, inevent) 533 call_ratio = ratio(call.ratio, call_ratios[callee]) 534 call_partial = call_ratio*callee_partial 535 try: 536 call[outevent] += call_partial 537 except UndefinedEvent: 538 call[outevent] = call_partial 539 partial += call_partial 540 partials[function] = partial 541 try: 542 function[outevent] += partial 543 except UndefinedEvent: 544 function[outevent] = partial 545 return partials[function] 546 547 def aggregate(self, event): 548 """Aggregate an event for the whole profile.""" 549 550 total = event.null() 551 for function in self.functions.itervalues(): 552 try: 553 total = event.aggregate(total, function[event]) 554 except UndefinedEvent: 555 return 556 self[event] = total 557 558 def ratio(self, outevent, inevent): 559 assert outevent not in self 560 assert inevent in self 561 for function in self.functions.itervalues(): 562 assert outevent not in function 563 assert inevent in function 564 function[outevent] = ratio(function[inevent], self[inevent]) 565 for call in function.calls.itervalues(): 566 assert outevent not in call 567 if inevent in call: 568 call[outevent] = ratio(call[inevent], self[inevent]) 569 self[outevent] = 1.0 570 571 def prune(self, node_thres, edge_thres): 572 """Prune the profile""" 573 574 # compute the prune ratios 575 for function in self.functions.itervalues(): 576 try: 577 function.weight = function[TOTAL_TIME_RATIO] 578 except UndefinedEvent: 579 pass 580 581 for call in function.calls.itervalues(): 582 callee = self.functions[call.callee_id] 583 584 if TOTAL_TIME_RATIO in call: 585 # handle exact cases first 586 call.weight = call[TOTAL_TIME_RATIO] 587 else: 588 try: 589 # make a safe estimate 590 call.weight = min(function[TOTAL_TIME_RATIO], callee[TOTAL_TIME_RATIO]) 591 except UndefinedEvent: 592 pass 593 594 # prune the nodes 595 for function_id in self.functions.keys(): 596 function = self.functions[function_id] 597 if function.weight is not None: 598 if function.weight < node_thres: 599 del self.functions[function_id] 600 601 # prune the egdes 602 for function in self.functions.itervalues(): 603 for callee_id in function.calls.keys(): 604 call = function.calls[callee_id] 605 if callee_id not in self.functions or call.weight is not None and call.weight < edge_thres: 606 del function.calls[callee_id] 607 608 def dump(self): 609 for function in self.functions.itervalues(): 610 sys.stderr.write('Function %s:\n' % (function.name,)) 611 self._dump_events(function.events) 612 for call in function.calls.itervalues(): 613 callee = self.functions[call.callee_id] 614 sys.stderr.write(' Call %s:\n' % (callee.name,)) 615 self._dump_events(call.events) 616 for cycle in self.cycles: 617 sys.stderr.write('Cycle:\n') 618 self._dump_events(cycle.events) 619 for function in cycle.functions: 620 sys.stderr.write(' Function %s\n' % (function.name,)) 621 622 def _dump_events(self, events): 623 for event, value in events.iteritems(): 624 sys.stderr.write(' %s: %s\n' % (event.name, event.format(value))) 625 626 627class Struct: 628 """Masquerade a dictionary with a structure-like behavior.""" 629 630 def __init__(self, attrs = None): 631 if attrs is None: 632 attrs = {} 633 self.__dict__['_attrs'] = attrs 634 635 def __getattr__(self, name): 636 try: 637 return self._attrs[name] 638 except KeyError: 639 raise AttributeError(name) 640 641 def __setattr__(self, name, value): 642 self._attrs[name] = value 643 644 def __str__(self): 645 return str(self._attrs) 646 647 def __repr__(self): 648 return repr(self._attrs) 649 650 651class ParseError(Exception): 652 """Raised when parsing to signal mismatches.""" 653 654 def __init__(self, msg, line): 655 self.msg = msg 656 # TODO: store more source line information 657 self.line = line 658 659 def __str__(self): 660 return '%s: %r' % (self.msg, self.line) 661 662 663class Parser: 664 """Parser interface.""" 665 666 def __init__(self): 667 pass 668 669 def parse(self): 670 raise NotImplementedError 671 672 673class LineParser(Parser): 674 """Base class for parsers that read line-based formats.""" 675 676 def __init__(self, file): 677 Parser.__init__(self) 678 self._file = file 679 self.__line = None 680 self.__eof = False 681 self.line_no = 0 682 683 def readline(self): 684 line = self._file.readline() 685 if not line: 686 self.__line = '' 687 self.__eof = True 688 else: 689 self.line_no += 1 690 self.__line = line.rstrip('\r\n') 691 692 def lookahead(self): 693 assert self.__line is not None 694 return self.__line 695 696 def consume(self): 697 assert self.__line is not None 698 line = self.__line 699 self.readline() 700 return line 701 702 def eof(self): 703 assert self.__line is not None 704 return self.__eof 705 706 707XML_ELEMENT_START, XML_ELEMENT_END, XML_CHARACTER_DATA, XML_EOF = range(4) 708 709 710class XmlToken: 711 712 def __init__(self, type, name_or_data, attrs = None, line = None, column = None): 713 assert type in (XML_ELEMENT_START, XML_ELEMENT_END, XML_CHARACTER_DATA, XML_EOF) 714 self.type = type 715 self.name_or_data = name_or_data 716 self.attrs = attrs 717 self.line = line 718 self.column = column 719 720 def __str__(self): 721 if self.type == XML_ELEMENT_START: 722 return '<' + self.name_or_data + ' ...>' 723 if self.type == XML_ELEMENT_END: 724 return '</' + self.name_or_data + '>' 725 if self.type == XML_CHARACTER_DATA: 726 return self.name_or_data 727 if self.type == XML_EOF: 728 return 'end of file' 729 assert 0 730 731 732class XmlTokenizer: 733 """Expat based XML tokenizer.""" 734 735 def __init__(self, fp, skip_ws = True): 736 self.fp = fp 737 self.tokens = [] 738 self.index = 0 739 self.final = False 740 self.skip_ws = skip_ws 741 742 self.character_pos = 0, 0 743 self.character_data = '' 744 745 self.parser = xml.parsers.expat.ParserCreate() 746 self.parser.StartElementHandler = self.handle_element_start 747 self.parser.EndElementHandler = self.handle_element_end 748 self.parser.CharacterDataHandler = self.handle_character_data 749 750 def handle_element_start(self, name, attributes): 751 self.finish_character_data() 752 line, column = self.pos() 753 token = XmlToken(XML_ELEMENT_START, name, attributes, line, column) 754 self.tokens.append(token) 755 756 def handle_element_end(self, name): 757 self.finish_character_data() 758 line, column = self.pos() 759 token = XmlToken(XML_ELEMENT_END, name, None, line, column) 760 self.tokens.append(token) 761 762 def handle_character_data(self, data): 763 if not self.character_data: 764 self.character_pos = self.pos() 765 self.character_data += data 766 767 def finish_character_data(self): 768 if self.character_data: 769 if not self.skip_ws or not self.character_data.isspace(): 770 line, column = self.character_pos 771 token = XmlToken(XML_CHARACTER_DATA, self.character_data, None, line, column) 772 self.tokens.append(token) 773 self.character_data = '' 774 775 def next(self): 776 size = 16*1024 777 while self.index >= len(self.tokens) and not self.final: 778 self.tokens = [] 779 self.index = 0 780 data = self.fp.read(size) 781 self.final = len(data) < size 782 try: 783 self.parser.Parse(data, self.final) 784 except xml.parsers.expat.ExpatError, e: 785 #if e.code == xml.parsers.expat.errors.XML_ERROR_NO_ELEMENTS: 786 if e.code == 3: 787 pass 788 else: 789 raise e 790 if self.index >= len(self.tokens): 791 line, column = self.pos() 792 token = XmlToken(XML_EOF, None, None, line, column) 793 else: 794 token = self.tokens[self.index] 795 self.index += 1 796 return token 797 798 def pos(self): 799 return self.parser.CurrentLineNumber, self.parser.CurrentColumnNumber 800 801 802class XmlTokenMismatch(Exception): 803 804 def __init__(self, expected, found): 805 self.expected = expected 806 self.found = found 807 808 def __str__(self): 809 return '%u:%u: %s expected, %s found' % (self.found.line, self.found.column, str(self.expected), str(self.found)) 810 811 812class XmlParser(Parser): 813 """Base XML document parser.""" 814 815 def __init__(self, fp): 816 Parser.__init__(self) 817 self.tokenizer = XmlTokenizer(fp) 818 self.consume() 819 820 def consume(self): 821 self.token = self.tokenizer.next() 822 823 def match_element_start(self, name): 824 return self.token.type == XML_ELEMENT_START and self.token.name_or_data == name 825 826 def match_element_end(self, name): 827 return self.token.type == XML_ELEMENT_END and self.token.name_or_data == name 828 829 def element_start(self, name): 830 while self.token.type == XML_CHARACTER_DATA: 831 self.consume() 832 if self.token.type != XML_ELEMENT_START: 833 raise XmlTokenMismatch(XmlToken(XML_ELEMENT_START, name), self.token) 834 if self.token.name_or_data != name: 835 raise XmlTokenMismatch(XmlToken(XML_ELEMENT_START, name), self.token) 836 attrs = self.token.attrs 837 self.consume() 838 return attrs 839 840 def element_end(self, name): 841 while self.token.type == XML_CHARACTER_DATA: 842 self.consume() 843 if self.token.type != XML_ELEMENT_END: 844 raise XmlTokenMismatch(XmlToken(XML_ELEMENT_END, name), self.token) 845 if self.token.name_or_data != name: 846 raise XmlTokenMismatch(XmlToken(XML_ELEMENT_END, name), self.token) 847 self.consume() 848 849 def character_data(self, strip = True): 850 data = '' 851 while self.token.type == XML_CHARACTER_DATA: 852 data += self.token.name_or_data 853 self.consume() 854 if strip: 855 data = data.strip() 856 return data 857 858 859class GprofParser(Parser): 860 """Parser for GNU gprof output. 861 862 See also: 863 - Chapter "Interpreting gprof's Output" from the GNU gprof manual 864 http://sourceware.org/binutils/docs-2.18/gprof/Call-Graph.html#Call-Graph 865 - File "cg_print.c" from the GNU gprof source code 866 http://sourceware.org/cgi-bin/cvsweb.cgi/~checkout~/src/gprof/cg_print.c?rev=1.12&cvsroot=src 867 """ 868 869 def __init__(self, fp): 870 Parser.__init__(self) 871 self.fp = fp 872 self.functions = {} 873 self.cycles = {} 874 875 def readline(self): 876 line = self.fp.readline() 877 if not line: 878 sys.stderr.write('error: unexpected end of file\n') 879 sys.exit(1) 880 line = line.rstrip('\r\n') 881 return line 882 883 _int_re = re.compile(r'^\d+$') 884 _float_re = re.compile(r'^\d+\.\d+$') 885 886 def translate(self, mo): 887 """Extract a structure from a match object, while translating the types in the process.""" 888 attrs = {} 889 groupdict = mo.groupdict() 890 for name, value in groupdict.iteritems(): 891 if value is None: 892 value = None 893 elif self._int_re.match(value): 894 value = int(value) 895 elif self._float_re.match(value): 896 value = float(value) 897 attrs[name] = (value) 898 return Struct(attrs) 899 900 _cg_header_re = re.compile( 901 # original gprof header 902 r'^\s+called/total\s+parents\s*$|' + 903 r'^index\s+%time\s+self\s+descendents\s+called\+self\s+name\s+index\s*$|' + 904 r'^\s+called/total\s+children\s*$|' + 905 # GNU gprof header 906 r'^index\s+%\s+time\s+self\s+children\s+called\s+name\s*$' 907 ) 908 909 _cg_ignore_re = re.compile( 910 # spontaneous 911 r'^\s+<spontaneous>\s*$|' 912 # internal calls (such as "mcount") 913 r'^.*\((\d+)\)$' 914 ) 915 916 _cg_primary_re = re.compile( 917 r'^\[(?P<index>\d+)\]?' + 918 r'\s+(?P<percentage_time>\d+\.\d+)' + 919 r'\s+(?P<self>\d+\.\d+)' + 920 r'\s+(?P<descendants>\d+\.\d+)' + 921 r'\s+(?:(?P<called>\d+)(?:\+(?P<called_self>\d+))?)?' + 922 r'\s+(?P<name>\S.*?)' + 923 r'(?:\s+<cycle\s(?P<cycle>\d+)>)?' + 924 r'\s\[(\d+)\]$' 925 ) 926 927 _cg_parent_re = re.compile( 928 r'^\s+(?P<self>\d+\.\d+)?' + 929 r'\s+(?P<descendants>\d+\.\d+)?' + 930 r'\s+(?P<called>\d+)(?:/(?P<called_total>\d+))?' + 931 r'\s+(?P<name>\S.*?)' + 932 r'(?:\s+<cycle\s(?P<cycle>\d+)>)?' + 933 r'\s\[(?P<index>\d+)\]$' 934 ) 935 936 _cg_child_re = _cg_parent_re 937 938 _cg_cycle_header_re = re.compile( 939 r'^\[(?P<index>\d+)\]?' + 940 r'\s+(?P<percentage_time>\d+\.\d+)' + 941 r'\s+(?P<self>\d+\.\d+)' + 942 r'\s+(?P<descendants>\d+\.\d+)' + 943 r'\s+(?:(?P<called>\d+)(?:\+(?P<called_self>\d+))?)?' + 944 r'\s+<cycle\s(?P<cycle>\d+)\sas\sa\swhole>' + 945 r'\s\[(\d+)\]$' 946 ) 947 948 _cg_cycle_member_re = re.compile( 949 r'^\s+(?P<self>\d+\.\d+)?' + 950 r'\s+(?P<descendants>\d+\.\d+)?' + 951 r'\s+(?P<called>\d+)(?:\+(?P<called_self>\d+))?' + 952 r'\s+(?P<name>\S.*?)' + 953 r'(?:\s+<cycle\s(?P<cycle>\d+)>)?' + 954 r'\s\[(?P<index>\d+)\]$' 955 ) 956 957 _cg_sep_re = re.compile(r'^--+$') 958 959 def parse_function_entry(self, lines): 960 parents = [] 961 children = [] 962 963 while True: 964 if not lines: 965 sys.stderr.write('warning: unexpected end of entry\n') 966 line = lines.pop(0) 967 if line.startswith('['): 968 break 969 970 # read function parent line 971 mo = self._cg_parent_re.match(line) 972 if not mo: 973 if self._cg_ignore_re.match(line): 974 continue 975 sys.stderr.write('warning: unrecognized call graph entry: %r\n' % line) 976 else: 977 parent = self.translate(mo) 978 parents.append(parent) 979 980 # read primary line 981 mo = self._cg_primary_re.match(line) 982 if not mo: 983 sys.stderr.write('warning: unrecognized call graph entry: %r\n' % line) 984 return 985 else: 986 function = self.translate(mo) 987 988 while lines: 989 line = lines.pop(0) 990 991 # read function subroutine line 992 mo = self._cg_child_re.match(line) 993 if not mo: 994 if self._cg_ignore_re.match(line): 995 continue 996 sys.stderr.write('warning: unrecognized call graph entry: %r\n' % line) 997 else: 998 child = self.translate(mo) 999 children.append(child) 1000 1001 function.parents = parents 1002 function.children = children 1003 1004 self.functions[function.index] = function 1005 1006 def parse_cycle_entry(self, lines): 1007 1008 # read cycle header line 1009 line = lines[0] 1010 mo = self._cg_cycle_header_re.match(line) 1011 if not mo: 1012 sys.stderr.write('warning: unrecognized call graph entry: %r\n' % line) 1013 return 1014 cycle = self.translate(mo) 1015 1016 # read cycle member lines 1017 cycle.functions = [] 1018 for line in lines[1:]: 1019 mo = self._cg_cycle_member_re.match(line) 1020 if not mo: 1021 sys.stderr.write('warning: unrecognized call graph entry: %r\n' % line) 1022 continue 1023 call = self.translate(mo) 1024 cycle.functions.append(call) 1025 1026 self.cycles[cycle.cycle] = cycle 1027 1028 def parse_cg_entry(self, lines): 1029 if lines[0].startswith("["): 1030 self.parse_cycle_entry(lines) 1031 else: 1032 self.parse_function_entry(lines) 1033 1034 def parse_cg(self): 1035 """Parse the call graph.""" 1036 1037 # skip call graph header 1038 while not self._cg_header_re.match(self.readline()): 1039 pass 1040 line = self.readline() 1041 while self._cg_header_re.match(line): 1042 line = self.readline() 1043 1044 # process call graph entries 1045 entry_lines = [] 1046 while line != '\014': # form feed 1047 if line and not line.isspace(): 1048 if self._cg_sep_re.match(line): 1049 self.parse_cg_entry(entry_lines) 1050 entry_lines = [] 1051 else: 1052 entry_lines.append(line) 1053 line = self.readline() 1054 1055 def parse(self): 1056 self.parse_cg() 1057 self.fp.close() 1058 1059 profile = Profile() 1060 profile[TIME] = 0.0 1061 1062 cycles = {} 1063 for index in self.cycles.iterkeys(): 1064 cycles[index] = Cycle() 1065 1066 for entry in self.functions.itervalues(): 1067 # populate the function 1068 function = Function(entry.index, entry.name) 1069 function[TIME] = entry.self 1070 if entry.called is not None: 1071 function.called = entry.called 1072 if entry.called_self is not None: 1073 call = Call(entry.index) 1074 call[CALLS] = entry.called_self 1075 function.called += entry.called_self 1076 1077 # populate the function calls 1078 for child in entry.children: 1079 call = Call(child.index) 1080 1081 assert child.called is not None 1082 call[CALLS] = child.called 1083 1084 if child.index not in self.functions: 1085 # NOTE: functions that were never called but were discovered by gprof's 1086 # static call graph analysis dont have a call graph entry so we need 1087 # to add them here 1088 missing = Function(child.index, child.name) 1089 function[TIME] = 0.0 1090 function.called = 0 1091 profile.add_function(missing) 1092 1093 function.add_call(call) 1094 1095 profile.add_function(function) 1096 1097 if entry.cycle is not None: 1098 try: 1099 cycle = cycles[entry.cycle] 1100 except KeyError: 1101 sys.stderr.write('warning: <cycle %u as a whole> entry missing\n' % entry.cycle) 1102 cycle = Cycle() 1103 cycles[entry.cycle] = cycle 1104 cycle.add_function(function) 1105 1106 profile[TIME] = profile[TIME] + function[TIME] 1107 1108 for cycle in cycles.itervalues(): 1109 profile.add_cycle(cycle) 1110 1111 # Compute derived events 1112 profile.validate() 1113 profile.ratio(TIME_RATIO, TIME) 1114 profile.call_ratios(CALLS) 1115 profile.integrate(TOTAL_TIME, TIME) 1116 profile.ratio(TOTAL_TIME_RATIO, TOTAL_TIME) 1117 1118 return profile 1119 1120 1121class CallgrindParser(LineParser): 1122 """Parser for valgrind's callgrind tool. 1123 1124 See also: 1125 - http://valgrind.org/docs/manual/cl-format.html 1126 """ 1127 1128 _call_re = re.compile('^calls=\s*(\d+)\s+((\d+|\+\d+|-\d+|\*)\s+)+$') 1129 1130 def __init__(self, infile): 1131 LineParser.__init__(self, infile) 1132 1133 # Textual positions 1134 self.position_ids = {} 1135 self.positions = {} 1136 1137 # Numeric positions 1138 self.num_positions = 1 1139 self.cost_positions = ['line'] 1140 self.last_positions = [0] 1141 1142 # Events 1143 self.num_events = 0 1144 self.cost_events = [] 1145 1146 self.profile = Profile() 1147 self.profile[SAMPLES] = 0 1148 1149 def parse(self): 1150 # read lookahead 1151 self.readline() 1152 1153 self.parse_key('version') 1154 self.parse_key('creator') 1155 while self.parse_part(): 1156 pass 1157 if not self.eof(): 1158 sys.stderr.write('warning: line %u: unexpected line\n' % self.line_no) 1159 sys.stderr.write('%s\n' % self.lookahead()) 1160 1161 # compute derived data 1162 self.profile.validate() 1163 self.profile.find_cycles() 1164 self.profile.ratio(TIME_RATIO, SAMPLES) 1165 self.profile.call_ratios(CALLS) 1166 self.profile.integrate(TOTAL_TIME_RATIO, TIME_RATIO) 1167 1168 return self.profile 1169 1170 def parse_part(self): 1171 if not self.parse_header_line(): 1172 return False 1173 while self.parse_header_line(): 1174 pass 1175 if not self.parse_body_line(): 1176 return False 1177 while self.parse_body_line(): 1178 pass 1179 return True 1180 1181 def parse_header_line(self): 1182 return \ 1183 self.parse_empty() or \ 1184 self.parse_comment() or \ 1185 self.parse_part_detail() or \ 1186 self.parse_description() or \ 1187 self.parse_event_specification() or \ 1188 self.parse_cost_line_def() or \ 1189 self.parse_cost_summary() 1190 1191 _detail_keys = set(('cmd', 'pid', 'thread', 'part')) 1192 1193 def parse_part_detail(self): 1194 return self.parse_keys(self._detail_keys) 1195 1196 def parse_description(self): 1197 return self.parse_key('desc') is not None 1198 1199 def parse_event_specification(self): 1200 event = self.parse_key('event') 1201 if event is None: 1202 return False 1203 return True 1204 1205 def parse_cost_line_def(self): 1206 pair = self.parse_keys(('events', 'positions')) 1207 if pair is None: 1208 return False 1209 key, value = pair 1210 items = value.split() 1211 if key == 'events': 1212 self.num_events = len(items) 1213 self.cost_events = items 1214 if key == 'positions': 1215 self.num_positions = len(items) 1216 self.cost_positions = items 1217 self.last_positions = [0]*self.num_positions 1218 return True 1219 1220 def parse_cost_summary(self): 1221 pair = self.parse_keys(('summary', 'totals')) 1222 if pair is None: 1223 return False 1224 return True 1225 1226 def parse_body_line(self): 1227 return \ 1228 self.parse_empty() or \ 1229 self.parse_comment() or \ 1230 self.parse_cost_line() or \ 1231 self.parse_position_spec() or \ 1232 self.parse_association_spec() 1233 1234 __subpos_re = r'(0x[0-9a-fA-F]+|\d+|\+\d+|-\d+|\*)' 1235 _cost_re = re.compile(r'^' + 1236 __subpos_re + r'( +' + __subpos_re + r')*' + 1237 r'( +\d+)*' + 1238 '$') 1239 1240 def parse_cost_line(self, calls=None): 1241 line = self.lookahead().rstrip() 1242 mo = self._cost_re.match(line) 1243 if not mo: 1244 return False 1245 1246 function = self.get_function() 1247 1248 if calls is None: 1249 # Unlike other aspects, call object (cob) is relative not to the 1250 # last call object, but to the caller's object (ob), so try to 1251 # update it when processing a functions cost line 1252 try: 1253 self.positions['cob'] = self.positions['ob'] 1254 except KeyError: 1255 pass 1256 1257 values = line.split() 1258 assert len(values) <= self.num_positions + self.num_events 1259 1260 positions = values[0 : self.num_positions] 1261 events = values[self.num_positions : ] 1262 events += ['0']*(self.num_events - len(events)) 1263 1264 for i in range(self.num_positions): 1265 position = positions[i] 1266 if position == '*': 1267 position = self.last_positions[i] 1268 elif position[0] in '-+': 1269 position = self.last_positions[i] + int(position) 1270 elif position.startswith('0x'): 1271 position = int(position, 16) 1272 else: 1273 position = int(position) 1274 self.last_positions[i] = position 1275 1276 events = map(float, events) 1277 1278 if calls is None: 1279 function[SAMPLES] += events[0] 1280 self.profile[SAMPLES] += events[0] 1281 else: 1282 callee = self.get_callee() 1283 callee.called += calls 1284 1285 try: 1286 call = function.calls[callee.id] 1287 except KeyError: 1288 call = Call(callee.id) 1289 call[CALLS] = calls 1290 call[SAMPLES] = events[0] 1291 function.add_call(call) 1292 else: 1293 call[CALLS] += calls 1294 call[SAMPLES] += events[0] 1295 1296 self.consume() 1297 return True 1298 1299 def parse_association_spec(self): 1300 line = self.lookahead() 1301 if not line.startswith('calls='): 1302 return False 1303 1304 _, values = line.split('=', 1) 1305 values = values.strip().split() 1306 calls = int(values[0]) 1307 call_position = values[1:] 1308 self.consume() 1309 1310 self.parse_cost_line(calls) 1311 1312 return True 1313 1314 _position_re = re.compile('^(?P<position>[cj]?(?:ob|fl|fi|fe|fn))=\s*(?:\((?P<id>\d+)\))?(?:\s*(?P<name>.+))?') 1315 1316 _position_table_map = { 1317 'ob': 'ob', 1318 'fl': 'fl', 1319 'fi': 'fl', 1320 'fe': 'fl', 1321 'fn': 'fn', 1322 'cob': 'ob', 1323 'cfl': 'fl', 1324 'cfi': 'fl', 1325 'cfe': 'fl', 1326 'cfn': 'fn', 1327 'jfi': 'fl', 1328 } 1329 1330 _position_map = { 1331 'ob': 'ob', 1332 'fl': 'fl', 1333 'fi': 'fl', 1334 'fe': 'fl', 1335 'fn': 'fn', 1336 'cob': 'cob', 1337 'cfl': 'cfl', 1338 'cfi': 'cfl', 1339 'cfe': 'cfl', 1340 'cfn': 'cfn', 1341 'jfi': 'jfi', 1342 } 1343 1344 def parse_position_spec(self): 1345 line = self.lookahead() 1346 1347 if line.startswith('jump=') or line.startswith('jcnd='): 1348 self.consume() 1349 return True 1350 1351 mo = self._position_re.match(line) 1352 if not mo: 1353 return False 1354 1355 position, id, name = mo.groups() 1356 if id: 1357 table = self._position_table_map[position] 1358 if name: 1359 self.position_ids[(table, id)] = name 1360 else: 1361 name = self.position_ids.get((table, id), '') 1362 self.positions[self._position_map[position]] = name 1363 1364 self.consume() 1365 return True 1366 1367 def parse_empty(self): 1368 if self.eof(): 1369 return False 1370 line = self.lookahead() 1371 if line.strip(): 1372 return False 1373 self.consume() 1374 return True 1375 1376 def parse_comment(self): 1377 line = self.lookahead() 1378 if not line.startswith('#'): 1379 return False 1380 self.consume() 1381 return True 1382 1383 _key_re = re.compile(r'^(\w+):') 1384 1385 def parse_key(self, key): 1386 pair = self.parse_keys((key,)) 1387 if not pair: 1388 return None 1389 key, value = pair 1390 return value 1391 line = self.lookahead() 1392 mo = self._key_re.match(line) 1393 if not mo: 1394 return None 1395 key, value = line.split(':', 1) 1396 if key not in keys: 1397 return None 1398 value = value.strip() 1399 self.consume() 1400 return key, value 1401 1402 def parse_keys(self, keys): 1403 line = self.lookahead() 1404 mo = self._key_re.match(line) 1405 if not mo: 1406 return None 1407 key, value = line.split(':', 1) 1408 if key not in keys: 1409 return None 1410 value = value.strip() 1411 self.consume() 1412 return key, value 1413 1414 def make_function(self, module, filename, name): 1415 # FIXME: module and filename are not being tracked reliably 1416 #id = '|'.join((module, filename, name)) 1417 id = name 1418 try: 1419 function = self.profile.functions[id] 1420 except KeyError: 1421 function = Function(id, name) 1422 if module: 1423 function.module = os.path.basename(module) 1424 function[SAMPLES] = 0 1425 function.called = 0 1426 self.profile.add_function(function) 1427 return function 1428 1429 def get_function(self): 1430 module = self.positions.get('ob', '') 1431 filename = self.positions.get('fl', '') 1432 function = self.positions.get('fn', '') 1433 return self.make_function(module, filename, function) 1434 1435 def get_callee(self): 1436 module = self.positions.get('cob', '') 1437 filename = self.positions.get('cfi', '') 1438 function = self.positions.get('cfn', '') 1439 return self.make_function(module, filename, function) 1440 1441 1442class PerfParser(LineParser): 1443 """Parser for linux perf callgraph output. 1444 1445 It expects output generated with 1446 1447 perf record -g 1448 perf script | gprof2dot.py --format=perf 1449 """ 1450 1451 def __init__(self, infile): 1452 LineParser.__init__(self, infile) 1453 self.profile = Profile() 1454 1455 def readline(self): 1456 # Override LineParser.readline to ignore comment lines 1457 while True: 1458 LineParser.readline(self) 1459 if self.eof() or not self.lookahead().startswith('#'): 1460 break 1461 1462 def parse(self): 1463 # read lookahead 1464 self.readline() 1465 1466 profile = self.profile 1467 profile[SAMPLES] = 0 1468 while not self.eof(): 1469 self.parse_event() 1470 1471 # compute derived data 1472 profile.validate() 1473 profile.find_cycles() 1474 profile.ratio(TIME_RATIO, SAMPLES) 1475 profile.call_ratios(SAMPLES2) 1476 profile.integrate(TOTAL_TIME_RATIO, TIME_RATIO) 1477 1478 return profile 1479 1480 def parse_event(self): 1481 if self.eof(): 1482 return 1483 1484 line = self.consume() 1485 assert line 1486 1487 callchain = self.parse_callchain() 1488 if not callchain: 1489 return 1490 1491 callee = callchain[0] 1492 callee[SAMPLES] += 1 1493 self.profile[SAMPLES] += 1 1494 1495 for caller in callchain[1:]: 1496 try: 1497 call = caller.calls[callee.id] 1498 except KeyError: 1499 call = Call(callee.id) 1500 call[SAMPLES2] = 1 1501 caller.add_call(call) 1502 else: 1503 call[SAMPLES2] += 1 1504 1505 callee = caller 1506 1507 def parse_callchain(self): 1508 callchain = [] 1509 while self.lookahead(): 1510 function = self.parse_call() 1511 if function is None: 1512 break 1513 callchain.append(function) 1514 if self.lookahead() == '': 1515 self.consume() 1516 return callchain 1517 1518 call_re = re.compile(r'^\s+(?P<address>[0-9a-fA-F]+)\s+(?P<symbol>.*)\s+\((?P<module>[^)]*)\)$') 1519 1520 def parse_call(self): 1521 line = self.consume() 1522 mo = self.call_re.match(line) 1523 assert mo 1524 if not mo: 1525 return None 1526 1527 function_name = mo.group('symbol') 1528 if not function_name: 1529 function_name = mo.group('address') 1530 1531 module = mo.group('module') 1532 1533 function_id = function_name + ':' + module 1534 1535 try: 1536 function = self.profile.functions[function_id] 1537 except KeyError: 1538 function = Function(function_id, function_name) 1539 function.module = os.path.basename(module) 1540 function[SAMPLES] = 0 1541 self.profile.add_function(function) 1542 1543 return function 1544 1545 1546class OprofileParser(LineParser): 1547 """Parser for oprofile callgraph output. 1548 1549 See also: 1550 - http://oprofile.sourceforge.net/doc/opreport.html#opreport-callgraph 1551 """ 1552 1553 _fields_re = { 1554 'samples': r'(\d+)', 1555 '%': r'(\S+)', 1556 'linenr info': r'(?P<source>\(no location information\)|\S+:\d+)', 1557 'image name': r'(?P<image>\S+(?:\s\(tgid:[^)]*\))?)', 1558 'app name': r'(?P<application>\S+)', 1559 'symbol name': r'(?P<symbol>\(no symbols\)|.+?)', 1560 } 1561 1562 def __init__(self, infile): 1563 LineParser.__init__(self, infile) 1564 self.entries = {} 1565 self.entry_re = None 1566 1567 def add_entry(self, callers, function, callees): 1568 try: 1569 entry = self.entries[function.id] 1570 except KeyError: 1571 self.entries[function.id] = (callers, function, callees) 1572 else: 1573 callers_total, function_total, callees_total = entry 1574 self.update_subentries_dict(callers_total, callers) 1575 function_total.samples += function.samples 1576 self.update_subentries_dict(callees_total, callees) 1577 1578 def update_subentries_dict(self, totals, partials): 1579 for partial in partials.itervalues(): 1580 try: 1581 total = totals[partial.id] 1582 except KeyError: 1583 totals[partial.id] = partial 1584 else: 1585 total.samples += partial.samples 1586 1587 def parse(self): 1588 # read lookahead 1589 self.readline() 1590 1591 self.parse_header() 1592 while self.lookahead(): 1593 self.parse_entry() 1594 1595 profile = Profile() 1596 1597 reverse_call_samples = {} 1598 1599 # populate the profile 1600 profile[SAMPLES] = 0 1601 for _callers, _function, _callees in self.entries.itervalues(): 1602 function = Function(_function.id, _function.name) 1603 function[SAMPLES] = _function.samples 1604 profile.add_function(function) 1605 profile[SAMPLES] += _function.samples 1606 1607 if _function.application: 1608 function.process = os.path.basename(_function.application) 1609 if _function.image: 1610 function.module = os.path.basename(_function.image) 1611 1612 total_callee_samples = 0 1613 for _callee in _callees.itervalues(): 1614 total_callee_samples += _callee.samples 1615 1616 for _callee in _callees.itervalues(): 1617 if not _callee.self: 1618 call = Call(_callee.id) 1619 call[SAMPLES2] = _callee.samples 1620 function.add_call(call) 1621 1622 # compute derived data 1623 profile.validate() 1624 profile.find_cycles() 1625 profile.ratio(TIME_RATIO, SAMPLES) 1626 profile.call_ratios(SAMPLES2) 1627 profile.integrate(TOTAL_TIME_RATIO, TIME_RATIO) 1628 1629 return profile 1630 1631 def parse_header(self): 1632 while not self.match_header(): 1633 self.consume() 1634 line = self.lookahead() 1635 fields = re.split(r'\s\s+', line) 1636 entry_re = r'^\s*' + r'\s+'.join([self._fields_re[field] for field in fields]) + r'(?P<self>\s+\[self\])?$' 1637 self.entry_re = re.compile(entry_re) 1638 self.skip_separator() 1639 1640 def parse_entry(self): 1641 callers = self.parse_subentries() 1642 if self.match_primary(): 1643 function = self.parse_subentry() 1644 if function is not None: 1645 callees = self.parse_subentries() 1646 self.add_entry(callers, function, callees) 1647 self.skip_separator() 1648 1649 def parse_subentries(self): 1650 subentries = {} 1651 while self.match_secondary(): 1652 subentry = self.parse_subentry() 1653 subentries[subentry.id] = subentry 1654 return subentries 1655 1656 def parse_subentry(self): 1657 entry = Struct() 1658 line = self.consume() 1659 mo = self.entry_re.match(line) 1660 if not mo: 1661 raise ParseError('failed to parse', line) 1662 fields = mo.groupdict() 1663 entry.samples = int(mo.group(1)) 1664 if 'source' in fields and fields['source'] != '(no location information)': 1665 source = fields['source'] 1666 filename, lineno = source.split(':') 1667 entry.filename = filename 1668 entry.lineno = int(lineno) 1669 else: 1670 source = '' 1671 entry.filename = None 1672 entry.lineno = None 1673 entry.image = fields.get('image', '') 1674 entry.application = fields.get('application', '') 1675 if 'symbol' in fields and fields['symbol'] != '(no symbols)': 1676 entry.symbol = fields['symbol'] 1677 else: 1678 entry.symbol = '' 1679 if entry.symbol.startswith('"') and entry.symbol.endswith('"'): 1680 entry.symbol = entry.symbol[1:-1] 1681 entry.id = ':'.join((entry.application, entry.image, source, entry.symbol)) 1682 entry.self = fields.get('self', None) != None 1683 if entry.self: 1684 entry.id += ':self' 1685 if entry.symbol: 1686 entry.name = entry.symbol 1687 else: 1688 entry.name = entry.image 1689 return entry 1690 1691 def skip_separator(self): 1692 while not self.match_separator(): 1693 self.consume() 1694 self.consume() 1695 1696 def match_header(self): 1697 line = self.lookahead() 1698 return line.startswith('samples') 1699 1700 def match_separator(self): 1701 line = self.lookahead() 1702 return line == '-'*len(line) 1703 1704 def match_primary(self): 1705 line = self.lookahead() 1706 return not line[:1].isspace() 1707 1708 def match_secondary(self): 1709 line = self.lookahead() 1710 return line[:1].isspace() 1711 1712 1713class HProfParser(LineParser): 1714 """Parser for java hprof output 1715 1716 See also: 1717 - http://java.sun.com/developer/technicalArticles/Programming/HPROF.html 1718 """ 1719 1720 trace_re = re.compile(r'\t(.*)\((.*):(.*)\)') 1721 trace_id_re = re.compile(r'^TRACE (\d+):$') 1722 1723 def __init__(self, infile): 1724 LineParser.__init__(self, infile) 1725 self.traces = {} 1726 self.samples = {} 1727 1728 def parse(self): 1729 # read lookahead 1730 self.readline() 1731 1732 while not self.lookahead().startswith('------'): self.consume() 1733 while not self.lookahead().startswith('TRACE '): self.consume() 1734 1735 self.parse_traces() 1736 1737 while not self.lookahead().startswith('CPU'): 1738 self.consume() 1739 1740 self.parse_samples() 1741 1742 # populate the profile 1743 profile = Profile() 1744 profile[SAMPLES] = 0 1745 1746 functions = {} 1747 1748 # build up callgraph 1749 for id, trace in self.traces.iteritems(): 1750 if not id in self.samples: continue 1751 mtime = self.samples[id][0] 1752 last = None 1753 1754 for func, file, line in trace: 1755 if not func in functions: 1756 function = Function(func, func) 1757 function[SAMPLES] = 0 1758 profile.add_function(function) 1759 functions[func] = function 1760 1761 function = functions[func] 1762 # allocate time to the deepest method in the trace 1763 if not last: 1764 function[SAMPLES] += mtime 1765 profile[SAMPLES] += mtime 1766 else: 1767 c = function.get_call(last) 1768 c[SAMPLES2] += mtime 1769 1770 last = func 1771 1772 # compute derived data 1773 profile.validate() 1774 profile.find_cycles() 1775 profile.ratio(TIME_RATIO, SAMPLES) 1776 profile.call_ratios(SAMPLES2) 1777 profile.integrate(TOTAL_TIME_RATIO, TIME_RATIO) 1778 1779 return profile 1780 1781 def parse_traces(self): 1782 while self.lookahead().startswith('TRACE '): 1783 self.parse_trace() 1784 1785 def parse_trace(self): 1786 l = self.consume() 1787 mo = self.trace_id_re.match(l) 1788 tid = mo.group(1) 1789 last = None 1790 trace = [] 1791 1792 while self.lookahead().startswith('\t'): 1793 l = self.consume() 1794 match = self.trace_re.search(l) 1795 if not match: 1796 #sys.stderr.write('Invalid line: %s\n' % l) 1797 break 1798 else: 1799 function_name, file, line = match.groups() 1800 trace += [(function_name, file, line)] 1801 1802 self.traces[int(tid)] = trace 1803 1804 def parse_samples(self): 1805 self.consume() 1806 self.consume() 1807 1808 while not self.lookahead().startswith('CPU'): 1809 rank, percent_self, percent_accum, count, traceid, method = self.lookahead().split() 1810 self.samples[int(traceid)] = (int(count), method) 1811 self.consume() 1812 1813 1814class SysprofParser(XmlParser): 1815 1816 def __init__(self, stream): 1817 XmlParser.__init__(self, stream) 1818 1819 def parse(self): 1820 objects = {} 1821 nodes = {} 1822 1823 self.element_start('profile') 1824 while self.token.type == XML_ELEMENT_START: 1825 if self.token.name_or_data == 'objects': 1826 assert not objects 1827 objects = self.parse_items('objects') 1828 elif self.token.name_or_data == 'nodes': 1829 assert not nodes 1830 nodes = self.parse_items('nodes') 1831 else: 1832 self.parse_value(self.token.name_or_data) 1833 self.element_end('profile') 1834 1835 return self.build_profile(objects, nodes) 1836 1837 def parse_items(self, name): 1838 assert name[-1] == 's' 1839 items = {} 1840 self.element_start(name) 1841 while self.token.type == XML_ELEMENT_START: 1842 id, values = self.parse_item(name[:-1]) 1843 assert id not in items 1844 items[id] = values 1845 self.element_end(name) 1846 return items 1847 1848 def parse_item(self, name): 1849 attrs = self.element_start(name) 1850 id = int(attrs['id']) 1851 values = self.parse_values() 1852 self.element_end(name) 1853 return id, values 1854 1855 def parse_values(self): 1856 values = {} 1857 while self.token.type == XML_ELEMENT_START: 1858 name = self.token.name_or_data 1859 value = self.parse_value(name) 1860 assert name not in values 1861 values[name] = value 1862 return values 1863 1864 def parse_value(self, tag): 1865 self.element_start(tag) 1866 value = self.character_data() 1867 self.element_end(tag) 1868 if value.isdigit(): 1869 return int(value) 1870 if value.startswith('"') and value.endswith('"'): 1871 return value[1:-1] 1872 return value 1873 1874 def build_profile(self, objects, nodes): 1875 profile = Profile() 1876 1877 profile[SAMPLES] = 0 1878 for id, object in objects.iteritems(): 1879 # Ignore fake objects (process names, modules, "Everything", "kernel", etc.) 1880 if object['self'] == 0: 1881 continue 1882 1883 function = Function(id, object['name']) 1884 function[SAMPLES] = object['self'] 1885 profile.add_function(function) 1886 profile[SAMPLES] += function[SAMPLES] 1887 1888 for id, node in nodes.iteritems(): 1889 # Ignore fake calls 1890 if node['self'] == 0: 1891 continue 1892 1893 # Find a non-ignored parent 1894 parent_id = node['parent'] 1895 while parent_id != 0: 1896 parent = nodes[parent_id] 1897 caller_id = parent['object'] 1898 if objects[caller_id]['self'] != 0: 1899 break 1900 parent_id = parent['parent'] 1901 if parent_id == 0: 1902 continue 1903 1904 callee_id = node['object'] 1905 1906 assert objects[caller_id]['self'] 1907 assert objects[callee_id]['self'] 1908 1909 function = profile.functions[caller_id] 1910 1911 samples = node['self'] 1912 try: 1913 call = function.calls[callee_id] 1914 except KeyError: 1915 call = Call(callee_id) 1916 call[SAMPLES2] = samples 1917 function.add_call(call) 1918 else: 1919 call[SAMPLES2] += samples 1920 1921 # Compute derived events 1922 profile.validate() 1923 profile.find_cycles() 1924 profile.ratio(TIME_RATIO, SAMPLES) 1925 profile.call_ratios(SAMPLES2) 1926 profile.integrate(TOTAL_TIME_RATIO, TIME_RATIO) 1927 1928 return profile 1929 1930 1931class SharkParser(LineParser): 1932 """Parser for MacOSX Shark output. 1933 1934 Author: tom@dbservice.com 1935 """ 1936 1937 def __init__(self, infile): 1938 LineParser.__init__(self, infile) 1939 self.stack = [] 1940 self.entries = {} 1941 1942 def add_entry(self, function): 1943 try: 1944 entry = self.entries[function.id] 1945 except KeyError: 1946 self.entries[function.id] = (function, { }) 1947 else: 1948 function_total, callees_total = entry 1949 function_total.samples += function.samples 1950 1951 def add_callee(self, function, callee): 1952 func, callees = self.entries[function.id] 1953 try: 1954 entry = callees[callee.id] 1955 except KeyError: 1956 callees[callee.id] = callee 1957 else: 1958 entry.samples += callee.samples 1959 1960 def parse(self): 1961 self.readline() 1962 self.readline() 1963 self.readline() 1964 self.readline() 1965 1966 match = re.compile(r'(?P<prefix>[|+ ]*)(?P<samples>\d+), (?P<symbol>[^,]+), (?P<image>.*)') 1967 1968 while self.lookahead(): 1969 line = self.consume() 1970 mo = match.match(line) 1971 if not mo: 1972 raise ParseError('failed to parse', line) 1973 1974 fields = mo.groupdict() 1975 prefix = len(fields.get('prefix', 0)) / 2 - 1 1976 1977 symbol = str(fields.get('symbol', 0)) 1978 image = str(fields.get('image', 0)) 1979 1980 entry = Struct() 1981 entry.id = ':'.join([symbol, image]) 1982 entry.samples = int(fields.get('samples', 0)) 1983 1984 entry.name = symbol 1985 entry.image = image 1986 1987 # adjust the callstack 1988 if prefix < len(self.stack): 1989 del self.stack[prefix:] 1990 1991 if prefix == len(self.stack): 1992 self.stack.append(entry) 1993 1994 # if the callstack has had an entry, it's this functions caller 1995 if prefix > 0: 1996 self.add_callee(self.stack[prefix - 1], entry) 1997 1998 self.add_entry(entry) 1999 2000 profile = Profile() 2001 profile[SAMPLES] = 0 2002 for _function, _callees in self.entries.itervalues(): 2003 function = Function(_function.id, _function.name) 2004 function[SAMPLES] = _function.samples 2005 profile.add_function(function) 2006 profile[SAMPLES] += _function.samples 2007 2008 if _function.image: 2009 function.module = os.path.basename(_function.image) 2010 2011 for _callee in _callees.itervalues(): 2012 call = Call(_callee.id) 2013 call[SAMPLES] = _callee.samples 2014 function.add_call(call) 2015 2016 # compute derived data 2017 profile.validate() 2018 profile.find_cycles() 2019 profile.ratio(TIME_RATIO, SAMPLES) 2020 profile.call_ratios(SAMPLES) 2021 profile.integrate(TOTAL_TIME_RATIO, TIME_RATIO) 2022 2023 return profile 2024 2025 2026class XPerfParser(Parser): 2027 """Parser for CSVs generted by XPerf, from Microsoft Windows Performance Tools. 2028 """ 2029 2030 def __init__(self, stream): 2031 Parser.__init__(self) 2032 self.stream = stream 2033 self.profile = Profile() 2034 self.profile[SAMPLES] = 0 2035 self.column = {} 2036 2037 def parse(self): 2038 import csv 2039 reader = csv.reader( 2040 self.stream, 2041 delimiter = ',', 2042 quotechar = None, 2043 escapechar = None, 2044 doublequote = False, 2045 skipinitialspace = True, 2046 lineterminator = '\r\n', 2047 quoting = csv.QUOTE_NONE) 2048 it = iter(reader) 2049 row = reader.next() 2050 self.parse_header(row) 2051 for row in it: 2052 self.parse_row(row) 2053 2054 # compute derived data 2055 self.profile.validate() 2056 self.profile.find_cycles() 2057 self.profile.ratio(TIME_RATIO, SAMPLES) 2058 self.profile.call_ratios(SAMPLES2) 2059 self.profile.integrate(TOTAL_TIME_RATIO, TIME_RATIO) 2060 2061 return self.profile 2062 2063 def parse_header(self, row): 2064 for column in range(len(row)): 2065 name = row[column] 2066 assert name not in self.column 2067 self.column[name] = column 2068 2069 def parse_row(self, row): 2070 fields = {} 2071 for name, column in self.column.iteritems(): 2072 value = row[column] 2073 for factory in int, float: 2074 try: 2075 value = factory(value) 2076 except ValueError: 2077 pass 2078 else: 2079 break 2080 fields[name] = value 2081 2082 process = fields['Process Name'] 2083 symbol = fields['Module'] + '!' + fields['Function'] 2084 weight = fields['Weight'] 2085 count = fields['Count'] 2086 2087 function = self.get_function(process, symbol) 2088 function[SAMPLES] += weight * count 2089 self.profile[SAMPLES] += weight * count 2090 2091 stack = fields['Stack'] 2092 if stack != '?': 2093 stack = stack.split('/') 2094 assert stack[0] == '[Root]' 2095 if stack[-1] != symbol: 2096 # XXX: some cases the sampled function does not appear in the stack 2097 stack.append(symbol) 2098 caller = None 2099 for symbol in stack[1:]: 2100 callee = self.get_function(process, symbol) 2101 if caller is not None: 2102 try: 2103 call = caller.calls[callee.id] 2104 except KeyError: 2105 call = Call(callee.id) 2106 call[SAMPLES2] = count 2107 caller.add_call(call) 2108 else: 2109 call[SAMPLES2] += count 2110 caller = callee 2111 2112 def get_function(self, process, symbol): 2113 function_id = process + '!' + symbol 2114 2115 try: 2116 function = self.profile.functions[function_id] 2117 except KeyError: 2118 module, name = symbol.split('!', 1) 2119 function = Function(function_id, name) 2120 function.process = process 2121 function.module = module 2122 function[SAMPLES] = 0 2123 self.profile.add_function(function) 2124 2125 return function 2126 2127 2128class SleepyParser(Parser): 2129 """Parser for GNU gprof output. 2130 2131 See also: 2132 - http://www.codersnotes.com/sleepy/ 2133 - http://sleepygraph.sourceforge.net/ 2134 """ 2135 2136 def __init__(self, filename): 2137 Parser.__init__(self) 2138 2139 from zipfile import ZipFile 2140 2141 self.database = ZipFile(filename) 2142 2143 self.version_0_7 = 'Version 0.7 required' in self.database.namelist() 2144 2145 self.symbols = {} 2146 self.calls = {} 2147 2148 self.profile = Profile() 2149 2150 _symbol_re = re.compile( 2151 r'^(?P<id>\w+)' + 2152 r'\s+"(?P<module>[^"]*)"' + 2153 r'\s+"(?P<procname>[^"]*)"' + 2154 r'\s+"(?P<sourcefile>[^"]*)"' + 2155 r'\s+(?P<sourceline>\d+)$' 2156 ) 2157 2158 def parse_symbols(self): 2159 if self.version_0_7: 2160 symbols_txt = 'Symbols.txt' 2161 else: 2162 symbols_txt = 'symbols.txt' 2163 lines = self.database.read(symbols_txt).splitlines() 2164 for line in lines: 2165 mo = self._symbol_re.match(line) 2166 if mo: 2167 symbol_id, module, procname, sourcefile, sourceline = mo.groups() 2168 2169 function_id = ':'.join([module, procname]) 2170 2171 try: 2172 function = self.profile.functions[function_id] 2173 except KeyError: 2174 function = Function(function_id, procname) 2175 function.module = module 2176 function[SAMPLES] = 0 2177 self.profile.add_function(function) 2178 2179 self.symbols[symbol_id] = function 2180 2181 def parse_callstacks(self): 2182 if self.version_0_7: 2183 callstacks_txt = 'Callstacks.txt' 2184 else: 2185 callstacks_txt = 'callstacks.txt' 2186 lines = self.database.read(callstacks_txt).splitlines() 2187 for line in lines: 2188 fields = line.split() 2189 samples = float(fields[0]) 2190 callstack = fields[1:] 2191 2192 callstack = [self.symbols[symbol_id] for symbol_id in callstack] 2193 2194 callee = callstack[0] 2195 2196 callee[SAMPLES] += samples 2197 self.profile[SAMPLES] += samples 2198 2199 for caller in callstack[1:]: 2200 try: 2201 call = caller.calls[callee.id] 2202 except KeyError: 2203 call = Call(callee.id) 2204 call[SAMPLES2] = samples 2205 caller.add_call(call) 2206 else: 2207 call[SAMPLES2] += samples 2208 2209 callee = caller 2210 2211 def parse(self): 2212 profile = self.profile 2213 profile[SAMPLES] = 0 2214 2215 self.parse_symbols() 2216 self.parse_callstacks() 2217 2218 # Compute derived events 2219 profile.validate() 2220 profile.find_cycles() 2221 profile.ratio(TIME_RATIO, SAMPLES) 2222 profile.call_ratios(SAMPLES2) 2223 profile.integrate(TOTAL_TIME_RATIO, TIME_RATIO) 2224 2225 return profile 2226 2227 2228class AQtimeTable: 2229 2230 def __init__(self, name, fields): 2231 self.name = name 2232 2233 self.fields = fields 2234 self.field_column = {} 2235 for column in range(len(fields)): 2236 self.field_column[fields[column]] = column 2237 self.rows = [] 2238 2239 def __len__(self): 2240 return len(self.rows) 2241 2242 def __iter__(self): 2243 for values, children in self.rows: 2244 fields = {} 2245 for name, value in zip(self.fields, values): 2246 fields[name] = value 2247 children = dict([(child.name, child) for child in children]) 2248 yield fields, children 2249 raise StopIteration 2250 2251 def add_row(self, values, children=()): 2252 self.rows.append((values, children)) 2253 2254 2255class AQtimeParser(XmlParser): 2256 2257 def __init__(self, stream): 2258 XmlParser.__init__(self, stream) 2259 self.tables = {} 2260 2261 def parse(self): 2262 self.element_start('AQtime_Results') 2263 self.parse_headers() 2264 results = self.parse_results() 2265 self.element_end('AQtime_Results') 2266 return self.build_profile(results) 2267 2268 def parse_headers(self): 2269 self.element_start('HEADERS') 2270 while self.token.type == XML_ELEMENT_START: 2271 self.parse_table_header() 2272 self.element_end('HEADERS') 2273 2274 def parse_table_header(self): 2275 attrs = self.element_start('TABLE_HEADER') 2276 name = attrs['NAME'] 2277 id = int(attrs['ID']) 2278 field_types = [] 2279 field_names = [] 2280 while self.token.type == XML_ELEMENT_START: 2281 field_type, field_name = self.parse_table_field() 2282 field_types.append(field_type) 2283 field_names.append(field_name) 2284 self.element_end('TABLE_HEADER') 2285 self.tables[id] = name, field_types, field_names 2286 2287 def parse_table_field(self): 2288 attrs = self.element_start('TABLE_FIELD') 2289 type = attrs['TYPE'] 2290 name = self.character_data() 2291 self.element_end('TABLE_FIELD') 2292 return type, name 2293 2294 def parse_results(self): 2295 self.element_start('RESULTS') 2296 table = self.parse_data() 2297 self.element_end('RESULTS') 2298 return table 2299 2300 def parse_data(self): 2301 rows = [] 2302 attrs = self.element_start('DATA') 2303 table_id = int(attrs['TABLE_ID']) 2304 table_name, field_types, field_names = self.tables[table_id] 2305 table = AQtimeTable(table_name, field_names) 2306 while self.token.type == XML_ELEMENT_START: 2307 row, children = self.parse_row(field_types) 2308 table.add_row(row, children) 2309 self.element_end('DATA') 2310 return table 2311 2312 def parse_row(self, field_types): 2313 row = [None]*len(field_types) 2314 children = [] 2315 self.element_start('ROW') 2316 while self.token.type == XML_ELEMENT_START: 2317 if self.token.name_or_data == 'FIELD': 2318 field_id, field_value = self.parse_field(field_types) 2319 row[field_id] = field_value 2320 elif self.token.name_or_data == 'CHILDREN': 2321 children = self.parse_children() 2322 else: 2323 raise XmlTokenMismatch("<FIELD ...> or <CHILDREN ...>", self.token) 2324 self.element_end('ROW') 2325 return row, children 2326 2327 def parse_field(self, field_types): 2328 attrs = self.element_start('FIELD') 2329 id = int(attrs['ID']) 2330 type = field_types[id] 2331 value = self.character_data() 2332 if type == 'Integer': 2333 value = int(value) 2334 elif type == 'Float': 2335 value = float(value) 2336 elif type == 'Address': 2337 value = int(value) 2338 elif type == 'String': 2339 pass 2340 else: 2341 assert False 2342 self.element_end('FIELD') 2343 return id, value 2344 2345 def parse_children(self): 2346 children = [] 2347 self.element_start('CHILDREN') 2348 while self.token.type == XML_ELEMENT_START: 2349 table = self.parse_data() 2350 assert table.name not in children 2351 children.append(table) 2352 self.element_end('CHILDREN') 2353 return children 2354 2355 def build_profile(self, results): 2356 assert results.name == 'Routines' 2357 profile = Profile() 2358 profile[TIME] = 0.0 2359 for fields, tables in results: 2360 function = self.build_function(fields) 2361 children = tables['Children'] 2362 for fields, _ in children: 2363 call = self.build_call(fields) 2364 function.add_call(call) 2365 profile.add_function(function) 2366 profile[TIME] = profile[TIME] + function[TIME] 2367 profile[TOTAL_TIME] = profile[TIME] 2368 profile.ratio(TOTAL_TIME_RATIO, TOTAL_TIME) 2369 return profile 2370 2371 def build_function(self, fields): 2372 function = Function(self.build_id(fields), self.build_name(fields)) 2373 function[TIME] = fields['Time'] 2374 function[TOTAL_TIME] = fields['Time with Children'] 2375 #function[TIME_RATIO] = fields['% Time']/100.0 2376 #function[TOTAL_TIME_RATIO] = fields['% with Children']/100.0 2377 return function 2378 2379 def build_call(self, fields): 2380 call = Call(self.build_id(fields)) 2381 call[TIME] = fields['Time'] 2382 call[TOTAL_TIME] = fields['Time with Children'] 2383 #call[TIME_RATIO] = fields['% Time']/100.0 2384 #call[TOTAL_TIME_RATIO] = fields['% with Children']/100.0 2385 return call 2386 2387 def build_id(self, fields): 2388 return ':'.join([fields['Module Name'], fields['Unit Name'], fields['Routine Name']]) 2389 2390 def build_name(self, fields): 2391 # TODO: use more fields 2392 return fields['Routine Name'] 2393 2394 2395class PstatsParser: 2396 """Parser python profiling statistics saved with te pstats module.""" 2397 2398 def __init__(self, *filename): 2399 import pstats 2400 try: 2401 self.stats = pstats.Stats(*filename) 2402 except ValueError: 2403 import hotshot.stats 2404 self.stats = hotshot.stats.load(filename[0]) 2405 self.profile = Profile() 2406 self.function_ids = {} 2407 2408 def get_function_name(self, (filename, line, name)): 2409 module = os.path.splitext(filename)[0] 2410 module = os.path.basename(module) 2411 return "%s:%d:%s" % (module, line, name) 2412 2413 def get_function(self, key): 2414 try: 2415 id = self.function_ids[key] 2416 except KeyError: 2417 id = len(self.function_ids) 2418 name = self.get_function_name(key) 2419 function = Function(id, name) 2420 self.profile.functions[id] = function 2421 self.function_ids[key] = id 2422 else: 2423 function = self.profile.functions[id] 2424 return function 2425 2426 def parse(self): 2427 self.profile[TIME] = 0.0 2428 self.profile[TOTAL_TIME] = self.stats.total_tt 2429 for fn, (cc, nc, tt, ct, callers) in self.stats.stats.iteritems(): 2430 callee = self.get_function(fn) 2431 callee.called = nc 2432 callee[TOTAL_TIME] = ct 2433 callee[TIME] = tt 2434 self.profile[TIME] += tt 2435 self.profile[TOTAL_TIME] = max(self.profile[TOTAL_TIME], ct) 2436 for fn, value in callers.iteritems(): 2437 caller = self.get_function(fn) 2438 call = Call(callee.id) 2439 if isinstance(value, tuple): 2440 for i in xrange(0, len(value), 4): 2441 nc, cc, tt, ct = value[i:i+4] 2442 if CALLS in call: 2443 call[CALLS] += cc 2444 else: 2445 call[CALLS] = cc 2446 2447 if TOTAL_TIME in call: 2448 call[TOTAL_TIME] += ct 2449 else: 2450 call[TOTAL_TIME] = ct 2451 2452 else: 2453 call[CALLS] = value 2454 call[TOTAL_TIME] = ratio(value, nc)*ct 2455 2456 caller.add_call(call) 2457 #self.stats.print_stats() 2458 #self.stats.print_callees() 2459 2460 # Compute derived events 2461 self.profile.validate() 2462 self.profile.ratio(TIME_RATIO, TIME) 2463 self.profile.ratio(TOTAL_TIME_RATIO, TOTAL_TIME) 2464 2465 return self.profile 2466 2467 2468class Theme: 2469 2470 def __init__(self, 2471 bgcolor = (0.0, 0.0, 1.0), 2472 mincolor = (0.0, 0.0, 0.0), 2473 maxcolor = (0.0, 0.0, 1.0), 2474 fontname = "Arial", 2475 minfontsize = 10.0, 2476 maxfontsize = 10.0, 2477 minpenwidth = 0.5, 2478 maxpenwidth = 4.0, 2479 gamma = 2.2, 2480 skew = 1.0): 2481 self.bgcolor = bgcolor 2482 self.mincolor = mincolor 2483 self.maxcolor = maxcolor 2484 self.fontname = fontname 2485 self.minfontsize = minfontsize 2486 self.maxfontsize = maxfontsize 2487 self.minpenwidth = minpenwidth 2488 self.maxpenwidth = maxpenwidth 2489 self.gamma = gamma 2490 self.skew = skew 2491 2492 def graph_bgcolor(self): 2493 return self.hsl_to_rgb(*self.bgcolor) 2494 2495 def graph_fontname(self): 2496 return self.fontname 2497 2498 def graph_fontsize(self): 2499 return self.minfontsize 2500 2501 def node_bgcolor(self, weight): 2502 return self.color(weight) 2503 2504 def node_fgcolor(self, weight): 2505 return self.graph_bgcolor() 2506 2507 def node_fontsize(self, weight): 2508 return self.fontsize(weight) 2509 2510 def edge_color(self, weight): 2511 return self.color(weight) 2512 2513 def edge_fontsize(self, weight): 2514 return self.fontsize(weight) 2515 2516 def edge_penwidth(self, weight): 2517 return max(weight*self.maxpenwidth, self.minpenwidth) 2518 2519 def edge_arrowsize(self, weight): 2520 return 0.5 * math.sqrt(self.edge_penwidth(weight)) 2521 2522 def fontsize(self, weight): 2523 return max(weight**2 * self.maxfontsize, self.minfontsize) 2524 2525 def color(self, weight): 2526 weight = min(max(weight, 0.0), 1.0) 2527 2528 hmin, smin, lmin = self.mincolor 2529 hmax, smax, lmax = self.maxcolor 2530 2531 if self.skew < 0: 2532 raise ValueError("Skew must be greater than 0") 2533 elif self.skew == 1.0: 2534 h = hmin + weight*(hmax - hmin) 2535 s = smin + weight*(smax - smin) 2536 l = lmin + weight*(lmax - lmin) 2537 else: 2538 base = self.skew 2539 h = hmin + ((hmax-hmin)*(-1.0 + (base ** weight)) / (base - 1.0)) 2540 s = smin + ((smax-smin)*(-1.0 + (base ** weight)) / (base - 1.0)) 2541 l = lmin + ((lmax-lmin)*(-1.0 + (base ** weight)) / (base - 1.0)) 2542 2543 return self.hsl_to_rgb(h, s, l) 2544 2545 def hsl_to_rgb(self, h, s, l): 2546 """Convert a color from HSL color-model to RGB. 2547 2548 See also: 2549 - http://www.w3.org/TR/css3-color/#hsl-color 2550 """ 2551 2552 h = h % 1.0 2553 s = min(max(s, 0.0), 1.0) 2554 l = min(max(l, 0.0), 1.0) 2555 2556 if l <= 0.5: 2557 m2 = l*(s + 1.0) 2558 else: 2559 m2 = l + s - l*s 2560 m1 = l*2.0 - m2 2561 r = self._hue_to_rgb(m1, m2, h + 1.0/3.0) 2562 g = self._hue_to_rgb(m1, m2, h) 2563 b = self._hue_to_rgb(m1, m2, h - 1.0/3.0) 2564 2565 # Apply gamma correction 2566 r **= self.gamma 2567 g **= self.gamma 2568 b **= self.gamma 2569 2570 return (r, g, b) 2571 2572 def _hue_to_rgb(self, m1, m2, h): 2573 if h < 0.0: 2574 h += 1.0 2575 elif h > 1.0: 2576 h -= 1.0 2577 if h*6 < 1.0: 2578 return m1 + (m2 - m1)*h*6.0 2579 elif h*2 < 1.0: 2580 return m2 2581 elif h*3 < 2.0: 2582 return m1 + (m2 - m1)*(2.0/3.0 - h)*6.0 2583 else: 2584 return m1 2585 2586 2587TEMPERATURE_COLORMAP = Theme( 2588 mincolor = (2.0/3.0, 0.80, 0.25), # dark blue 2589 maxcolor = (0.0, 1.0, 0.5), # satured red 2590 gamma = 1.0 2591) 2592 2593PINK_COLORMAP = Theme( 2594 mincolor = (0.0, 1.0, 0.90), # pink 2595 maxcolor = (0.0, 1.0, 0.5), # satured red 2596) 2597 2598GRAY_COLORMAP = Theme( 2599 mincolor = (0.0, 0.0, 0.85), # light gray 2600 maxcolor = (0.0, 0.0, 0.0), # black 2601) 2602 2603BW_COLORMAP = Theme( 2604 minfontsize = 8.0, 2605 maxfontsize = 24.0, 2606 mincolor = (0.0, 0.0, 0.0), # black 2607 maxcolor = (0.0, 0.0, 0.0), # black 2608 minpenwidth = 0.1, 2609 maxpenwidth = 8.0, 2610) 2611 2612 2613class DotWriter: 2614 """Writer for the DOT language. 2615 2616 See also: 2617 - "The DOT Language" specification 2618 http://www.graphviz.org/doc/info/lang.html 2619 """ 2620 2621 strip = False 2622 wrap = False 2623 2624 def __init__(self, fp): 2625 self.fp = fp 2626 2627 def wrap_function_name(self, name): 2628 """Split the function name on multiple lines.""" 2629 2630 if len(name) > 32: 2631 ratio = 2.0/3.0 2632 height = max(int(len(name)/(1.0 - ratio) + 0.5), 1) 2633 width = max(len(name)/height, 32) 2634 # TODO: break lines in symbols 2635 name = textwrap.fill(name, width, break_long_words=False) 2636 2637 # Take away spaces 2638 name = name.replace(", ", ",") 2639 name = name.replace("> >", ">>") 2640 name = name.replace("> >", ">>") # catch consecutive 2641 2642 return name 2643 2644 def graph(self, profile, theme): 2645 self.begin_graph() 2646 2647 fontname = theme.graph_fontname() 2648 2649 self.attr('graph', fontname=fontname, ranksep=0.25, nodesep=0.125) 2650 self.attr('node', fontname=fontname, shape="box", style="filled", fontcolor="white", width=0, height=0) 2651 self.attr('edge', fontname=fontname) 2652 2653 for function in profile.functions.itervalues(): 2654 labels = [] 2655 if function.process is not None: 2656 labels.append(function.process) 2657 if function.module is not None: 2658 labels.append(function.module) 2659 2660 if self.strip: 2661 function_name = function.stripped_name() 2662 else: 2663 function_name = function.name 2664 if self.wrap: 2665 function_name = self.wrap_function_name(function_name) 2666 labels.append(function_name) 2667 2668 for event in TOTAL_TIME_RATIO, TIME_RATIO: 2669 if event in function.events: 2670 label = event.format(function[event]) 2671 labels.append(label) 2672 if function.called is not None: 2673 labels.append(u"%u\xd7" % (function.called,)) 2674 2675 if function.weight is not None: 2676 weight = function.weight 2677 else: 2678 weight = 0.0 2679 2680 label = '\n'.join(labels) 2681 self.node(function.id, 2682 label = label, 2683 color = self.color(theme.node_bgcolor(weight)), 2684 fontcolor = self.color(theme.node_fgcolor(weight)), 2685 fontsize = "%.2f" % theme.node_fontsize(weight), 2686 ) 2687 2688 for call in function.calls.itervalues(): 2689 callee = profile.functions[call.callee_id] 2690 2691 labels = [] 2692 for event in TOTAL_TIME_RATIO, CALLS: 2693 if event in call.events: 2694 label = event.format(call[event]) 2695 labels.append(label) 2696 2697 if call.weight is not None: 2698 weight = call.weight 2699 elif callee.weight is not None: 2700 weight = callee.weight 2701 else: 2702 weight = 0.0 2703 2704 label = '\n'.join(labels) 2705 2706 self.edge(function.id, call.callee_id, 2707 label = label, 2708 color = self.color(theme.edge_color(weight)), 2709 fontcolor = self.color(theme.edge_color(weight)), 2710 fontsize = "%.2f" % theme.edge_fontsize(weight), 2711 penwidth = "%.2f" % theme.edge_penwidth(weight), 2712 labeldistance = "%.2f" % theme.edge_penwidth(weight), 2713 arrowsize = "%.2f" % theme.edge_arrowsize(weight), 2714 ) 2715 2716 self.end_graph() 2717 2718 def begin_graph(self): 2719 self.write('digraph {\n') 2720 2721 def end_graph(self): 2722 self.write('}\n') 2723 2724 def attr(self, what, **attrs): 2725 self.write("\t") 2726 self.write(what) 2727 self.attr_list(attrs) 2728 self.write(";\n") 2729 2730 def node(self, node, **attrs): 2731 self.write("\t") 2732 self.id(node) 2733 self.attr_list(attrs) 2734 self.write(";\n") 2735 2736 def edge(self, src, dst, **attrs): 2737 self.write("\t") 2738 self.id(src) 2739 self.write(" -> ") 2740 self.id(dst) 2741 self.attr_list(attrs) 2742 self.write(";\n") 2743 2744 def attr_list(self, attrs): 2745 if not attrs: 2746 return 2747 self.write(' [') 2748 first = True 2749 for name, value in attrs.iteritems(): 2750 if first: 2751 first = False 2752 else: 2753 self.write(", ") 2754 self.id(name) 2755 self.write('=') 2756 self.id(value) 2757 self.write(']') 2758 2759 def id(self, id): 2760 if isinstance(id, (int, float)): 2761 s = str(id) 2762 elif isinstance(id, basestring): 2763 if id.isalnum() and not id.startswith('0x'): 2764 s = id 2765 else: 2766 s = self.escape(id) 2767 else: 2768 raise TypeError 2769 self.write(s) 2770 2771 def color(self, (r, g, b)): 2772 2773 def float2int(f): 2774 if f <= 0.0: 2775 return 0 2776 if f >= 1.0: 2777 return 255 2778 return int(255.0*f + 0.5) 2779 2780 return "#" + "".join(["%02x" % float2int(c) for c in (r, g, b)]) 2781 2782 def escape(self, s): 2783 s = s.encode('utf-8') 2784 s = s.replace('\\', r'\\') 2785 s = s.replace('\n', r'\n') 2786 s = s.replace('\t', r'\t') 2787 s = s.replace('"', r'\"') 2788 return '"' + s + '"' 2789 2790 def write(self, s): 2791 self.fp.write(s) 2792 2793 2794class Main: 2795 """Main program.""" 2796 2797 themes = { 2798 "color": TEMPERATURE_COLORMAP, 2799 "pink": PINK_COLORMAP, 2800 "gray": GRAY_COLORMAP, 2801 "bw": BW_COLORMAP, 2802 } 2803 2804 def main(self): 2805 """Main program.""" 2806 2807 parser = optparse.OptionParser( 2808 usage="\n\t%prog [options] [file] ...", 2809 version="%%prog %s" % __version__) 2810 parser.add_option( 2811 '-o', '--output', metavar='FILE', 2812 type="string", dest="output", 2813 help="output filename [stdout]") 2814 parser.add_option( 2815 '-n', '--node-thres', metavar='PERCENTAGE', 2816 type="float", dest="node_thres", default=0.5, 2817 help="eliminate nodes below this threshold [default: %default]") 2818 parser.add_option( 2819 '-e', '--edge-thres', metavar='PERCENTAGE', 2820 type="float", dest="edge_thres", default=0.1, 2821 help="eliminate edges below this threshold [default: %default]") 2822 parser.add_option( 2823 '-f', '--format', 2824 type="choice", choices=('prof', 'callgrind', 'perf', 'oprofile', 'hprof', 'sysprof', 'pstats', 'shark', 'sleepy', 'aqtime', 'xperf'), 2825 dest="format", default="prof", 2826 help="profile format: prof, callgrind, oprofile, hprof, sysprof, shark, sleepy, aqtime, pstats, or xperf [default: %default]") 2827 parser.add_option( 2828 '-c', '--colormap', 2829 type="choice", choices=('color', 'pink', 'gray', 'bw'), 2830 dest="theme", default="color", 2831 help="color map: color, pink, gray, or bw [default: %default]") 2832 parser.add_option( 2833 '-s', '--strip', 2834 action="store_true", 2835 dest="strip", default=False, 2836 help="strip function parameters, template parameters, and const modifiers from demangled C++ function names") 2837 parser.add_option( 2838 '-w', '--wrap', 2839 action="store_true", 2840 dest="wrap", default=False, 2841 help="wrap function names") 2842 # add option to create subtree or show paths 2843 parser.add_option( 2844 '-z', '--root', 2845 type="string", 2846 dest="root", default="", 2847 help="prun call graph to show only decedents of specified root function") 2848 parser.add_option( 2849 '-l', '--leaf', 2850 type="string", 2851 dest="leaf", default="", 2852 help="prun call graph to show only ancestors of specified leaf function") 2853 # add a new option to control skew of the colorization curve 2854 parser.add_option( 2855 '--skew', 2856 type="float", dest="theme_skew", default=1.0, 2857 help="skew the colorization curve. Values < 1.0 give more variety to lower percentages. Value > 1.0 give less variety to lower percentages") 2858 (self.options, self.args) = parser.parse_args(sys.argv[1:]) 2859 2860 if len(self.args) > 1 and self.options.format != 'pstats': 2861 parser.error('incorrect number of arguments') 2862 2863 try: 2864 self.theme = self.themes[self.options.theme] 2865 except KeyError: 2866 parser.error('invalid colormap \'%s\'' % self.options.theme) 2867 2868 # set skew on the theme now that it has been picked. 2869 if self.options.theme_skew: 2870 self.theme.skew = self.options.theme_skew 2871 2872 stdinFormats = { 2873 "prof": GprofParser, 2874 "callgrind": CallgrindParser, 2875 "perf": PerfParser, 2876 "oprofile": OprofileParser, 2877 "sysprof": SysprofParser, 2878 "hprof": HProfParser, 2879 "xperf": XPerfParser, 2880 "shark": SharkParser, 2881 "aqtime": AQtimeParser 2882 } 2883 2884 if self.options.format in stdinFormats: 2885 if not self.args: 2886 fp = sys.stdin 2887 else: 2888 fp = open(self.args[0], 'rt') 2889 parser = stdinFormats[self.options.format](fp) 2890 elif self.options.format == 'pstats': 2891 if not self.args: 2892 parser.error('at least a file must be specified for pstats input') 2893 parser = PstatsParser(*self.args) 2894 elif self.options.format == 'sleepy': 2895 if len(self.args) != 1: 2896 parser.error('exactly one file must be specified for sleepy input') 2897 parser = SleepyParser(self.args[0]) 2898 else: 2899 parser.error('invalid format \'%s\'' % self.options.format) 2900 2901 self.profile = parser.parse() 2902 2903 if self.options.output is None: 2904 self.output = sys.stdout 2905 else: 2906 self.output = open(self.options.output, 'wt') 2907 2908 self.write_graph() 2909 2910 def write_graph(self): 2911 dot = DotWriter(self.output) 2912 dot.strip = self.options.strip 2913 dot.wrap = self.options.wrap 2914 2915 profile = self.profile 2916 profile.prune(self.options.node_thres/100.0, self.options.edge_thres/100.0) 2917 2918 if self.options.root: 2919 rootId = profile.getFunctionId(self.options.root) 2920 if not rootId: 2921 sys.stderr.write('root node ' + self.options.root + ' not found (might already be pruned : try -e0 -n0 flags)\n') 2922 sys.exit(1) 2923 profile.prune_root(rootId) 2924 if self.options.leaf: 2925 leafId = profile.getFunctionId(self.options.leaf) 2926 if not leafId: 2927 sys.stderr.write('leaf node ' + self.options.leaf + ' not found (maybe already pruned : try -e0 -n0 flags)\n') 2928 sys.exit(1) 2929 profile.prune_leaf(leafId) 2930 2931 dot.graph(profile, self.theme) 2932 2933 2934if __name__ == '__main__': 2935 Main().main()