1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 package graph
17
18 import (
19 "fmt"
20 "math"
21 "path/filepath"
22 "regexp"
23 "sort"
24 "strconv"
25 "strings"
26
27 "github.com/google/pprof/profile"
28 )
29
30 var (
31
32
33 javaRegExp = regexp.MustCompile(`^(?:[a-z]\w*\.)*([A-Z][\w\$]*\.(?:<init>|[a-z][\w\$]*(?:\$\d+)?))(?:(?:\()|$)`)
34
35
36 goRegExp = regexp.MustCompile(`^(?:[\w\-\.]+\/)+([^.]+\..+)`)
37
38 goVerRegExp = regexp.MustCompile(`^(.*?)/v(?:[2-9]|[1-9][0-9]+)([./].*)$`)
39
40
41
42
43
44 cppRegExp = regexp.MustCompile(`^(?:[_a-zA-Z]\w*::)+(_*[A-Z]\w*::~?[_a-zA-Z]\w*(?:<.*>)?)`)
45 cppAnonymousPrefixRegExp = regexp.MustCompile(`^\(anonymous namespace\)::`)
46 )
47
48
49
50 type Graph struct {
51 Nodes Nodes
52 }
53
54
55 type Options struct {
56 SampleValue func(s []int64) int64
57 SampleMeanDivisor func(s []int64) int64
58 FormatTag func(int64, string) string
59 ObjNames bool
60 OrigFnNames bool
61
62 CallTree bool
63 DropNegative bool
64
65 KeptNodes NodeSet
66 }
67
68
69 type Nodes []*Node
70
71
72
73 type Node struct {
74
75 Info NodeInfo
76
77
78
79
80
81
82 Function *Node
83
84
85
86 Flat, FlatDiv, Cum, CumDiv int64
87
88
89
90 In, Out EdgeMap
91
92
93 LabelTags TagMap
94
95
96
97
98
99 NumericTags map[string]TagMap
100 }
101
102
103
104 func (n *Node) FlatValue() int64 {
105 if n.FlatDiv == 0 {
106 return n.Flat
107 }
108 return n.Flat / n.FlatDiv
109 }
110
111
112
113 func (n *Node) CumValue() int64 {
114 if n.CumDiv == 0 {
115 return n.Cum
116 }
117 return n.Cum / n.CumDiv
118 }
119
120
121
122 func (n *Node) AddToEdge(to *Node, v int64, residual, inline bool) {
123 n.AddToEdgeDiv(to, 0, v, residual, inline)
124 }
125
126
127
128 func (n *Node) AddToEdgeDiv(to *Node, dv, v int64, residual, inline bool) {
129 if n.Out[to] != to.In[n] {
130 panic(fmt.Errorf("asymmetric edges %v %v", *n, *to))
131 }
132
133 if e := n.Out[to]; e != nil {
134 e.WeightDiv += dv
135 e.Weight += v
136 if residual {
137 e.Residual = true
138 }
139 if !inline {
140 e.Inline = false
141 }
142 return
143 }
144
145 info := &Edge{Src: n, Dest: to, WeightDiv: dv, Weight: v, Residual: residual, Inline: inline}
146 n.Out[to] = info
147 to.In[n] = info
148 }
149
150
151 type NodeInfo struct {
152 Name string
153 OrigName string
154 Address uint64
155 File string
156 StartLine, Lineno int
157 Columnno int
158 Objfile string
159 }
160
161
162 func (i *NodeInfo) PrintableName() string {
163 return strings.Join(i.NameComponents(), " ")
164 }
165
166
167 func (i *NodeInfo) NameComponents() []string {
168 var name []string
169 if i.Address != 0 {
170 name = append(name, fmt.Sprintf("%016x", i.Address))
171 }
172 if fun := i.Name; fun != "" {
173 name = append(name, fun)
174 }
175
176 switch {
177 case i.Lineno != 0:
178 s := fmt.Sprintf("%s:%d", i.File, i.Lineno)
179 if i.Columnno != 0 {
180 s += fmt.Sprintf(":%d", i.Columnno)
181 }
182
183 name = append(name, s)
184 case i.File != "":
185
186 name = append(name, i.File)
187 case i.Name != "":
188
189 case i.Objfile != "":
190
191 name = append(name, "["+filepath.Base(i.Objfile)+"]")
192 default:
193
194 name = append(name, "<unknown>")
195 }
196 return name
197 }
198
199
200
201 type NodeMap map[NodeInfo]*Node
202
203
204 type NodeSet map[NodeInfo]bool
205
206
207
208
209
210
211
212
213
214 type NodePtrSet map[*Node]bool
215
216
217
218
219 func (nm NodeMap) FindOrInsertNode(info NodeInfo, kept NodeSet) *Node {
220 if kept != nil {
221 if _, ok := kept[info]; !ok {
222 return nil
223 }
224 }
225
226 if n, ok := nm[info]; ok {
227 return n
228 }
229
230 n := &Node{
231 Info: info,
232 In: make(EdgeMap),
233 Out: make(EdgeMap),
234 LabelTags: make(TagMap),
235 NumericTags: make(map[string]TagMap),
236 }
237 nm[info] = n
238 if info.Address == 0 && info.Lineno == 0 {
239
240
241 n.Function = n
242 return n
243 }
244
245 info.Address = 0
246 info.Lineno = 0
247 info.Columnno = 0
248 n.Function = nm.FindOrInsertNode(info, nil)
249 return n
250 }
251
252
253 type EdgeMap map[*Node]*Edge
254
255
256 type Edge struct {
257 Src, Dest *Node
258
259 Weight, WeightDiv int64
260
261
262
263 Residual bool
264
265 Inline bool
266 }
267
268
269
270 func (e *Edge) WeightValue() int64 {
271 if e.WeightDiv == 0 {
272 return e.Weight
273 }
274 return e.Weight / e.WeightDiv
275 }
276
277
278 type Tag struct {
279 Name string
280 Unit string
281 Value int64
282 Flat, FlatDiv int64
283 Cum, CumDiv int64
284 }
285
286
287
288 func (t *Tag) FlatValue() int64 {
289 if t.FlatDiv == 0 {
290 return t.Flat
291 }
292 return t.Flat / t.FlatDiv
293 }
294
295
296
297 func (t *Tag) CumValue() int64 {
298 if t.CumDiv == 0 {
299 return t.Cum
300 }
301 return t.Cum / t.CumDiv
302 }
303
304
305 type TagMap map[string]*Tag
306
307
308 func SortTags(t []*Tag, flat bool) []*Tag {
309 ts := tags{t, flat}
310 sort.Sort(ts)
311 return ts.t
312 }
313
314
315 func New(prof *profile.Profile, o *Options) *Graph {
316 if o.CallTree {
317 return newTree(prof, o)
318 }
319 g, _ := newGraph(prof, o)
320 return g
321 }
322
323
324
325
326 func newGraph(prof *profile.Profile, o *Options) (*Graph, map[uint64]Nodes) {
327 nodes, locationMap := CreateNodes(prof, o)
328 seenNode := make(map[*Node]bool)
329 seenEdge := make(map[nodePair]bool)
330 for _, sample := range prof.Sample {
331 var w, dw int64
332 w = o.SampleValue(sample.Value)
333 if o.SampleMeanDivisor != nil {
334 dw = o.SampleMeanDivisor(sample.Value)
335 }
336 if dw == 0 && w == 0 {
337 continue
338 }
339 clear(seenNode)
340 clear(seenEdge)
341 var parent *Node
342
343 residual := false
344
345 labels := joinLabels(sample)
346
347 for i := len(sample.Location) - 1; i >= 0; i-- {
348 l := sample.Location[i]
349 locNodes := locationMap[l.ID]
350 for ni := len(locNodes) - 1; ni >= 0; ni-- {
351 n := locNodes[ni]
352 if n == nil {
353 residual = true
354 continue
355 }
356
357 if _, ok := seenNode[n]; !ok {
358 seenNode[n] = true
359 n.addSample(dw, w, labels, sample.NumLabel, sample.NumUnit, o.FormatTag, false)
360 }
361
362 if _, ok := seenEdge[nodePair{n, parent}]; !ok && parent != nil && n != parent {
363 seenEdge[nodePair{n, parent}] = true
364 parent.AddToEdgeDiv(n, dw, w, residual, ni != len(locNodes)-1)
365 }
366 parent = n
367 residual = false
368 }
369 }
370 if parent != nil && !residual {
371
372 parent.addSample(dw, w, labels, sample.NumLabel, sample.NumUnit, o.FormatTag, true)
373 }
374 }
375
376 return selectNodesForGraph(nodes, o.DropNegative), locationMap
377 }
378
379 func selectNodesForGraph(nodes Nodes, dropNegative bool) *Graph {
380
381 gNodes := make(Nodes, 0, len(nodes))
382 for _, n := range nodes {
383 if n == nil {
384 continue
385 }
386 if n.Cum == 0 && n.Flat == 0 {
387 continue
388 }
389 if dropNegative && isNegative(n) {
390 continue
391 }
392 gNodes = append(gNodes, n)
393 }
394 return &Graph{gNodes}
395 }
396
397 type nodePair struct {
398 src, dest *Node
399 }
400
401 func newTree(prof *profile.Profile, o *Options) (g *Graph) {
402 parentNodeMap := make(map[*Node]NodeMap, len(prof.Sample))
403 for _, sample := range prof.Sample {
404 var w, dw int64
405 w = o.SampleValue(sample.Value)
406 if o.SampleMeanDivisor != nil {
407 dw = o.SampleMeanDivisor(sample.Value)
408 }
409 if dw == 0 && w == 0 {
410 continue
411 }
412 var parent *Node
413 labels := joinLabels(sample)
414
415 for i := len(sample.Location) - 1; i >= 0; i-- {
416 l := sample.Location[i]
417 lines := l.Line
418 if len(lines) == 0 {
419 lines = []profile.Line{{}}
420 }
421 for lidx := len(lines) - 1; lidx >= 0; lidx-- {
422 nodeMap := parentNodeMap[parent]
423 if nodeMap == nil {
424 nodeMap = make(NodeMap)
425 parentNodeMap[parent] = nodeMap
426 }
427 n := nodeMap.findOrInsertLine(l, lines[lidx], o)
428 if n == nil {
429 continue
430 }
431 n.addSample(dw, w, labels, sample.NumLabel, sample.NumUnit, o.FormatTag, false)
432 if parent != nil {
433 parent.AddToEdgeDiv(n, dw, w, false, lidx != len(lines)-1)
434 }
435 parent = n
436 }
437 }
438 if parent != nil {
439 parent.addSample(dw, w, labels, sample.NumLabel, sample.NumUnit, o.FormatTag, true)
440 }
441 }
442
443 nodes := make(Nodes, 0, len(prof.Location))
444 for _, nm := range parentNodeMap {
445 nodes = append(nodes, nm.nodes()...)
446 }
447 return selectNodesForGraph(nodes, o.DropNegative)
448 }
449
450
451 func ShortenFunctionName(f string) string {
452 f = cppAnonymousPrefixRegExp.ReplaceAllString(f, "")
453 f = goVerRegExp.ReplaceAllString(f, `${1}${2}`)
454 for _, re := range []*regexp.Regexp{goRegExp, javaRegExp, cppRegExp} {
455 if matches := re.FindStringSubmatch(f); len(matches) >= 2 {
456 return strings.Join(matches[1:], "")
457 }
458 }
459 return f
460 }
461
462
463
464 func (g *Graph) TrimTree(kept NodePtrSet) {
465
466 oldNodes := g.Nodes
467 g.Nodes = make(Nodes, 0, len(kept))
468
469 for _, cur := range oldNodes {
470
471 if len(cur.In) > 1 {
472 panic("TrimTree only works on trees")
473 }
474
475
476 if _, ok := kept[cur]; ok {
477 g.Nodes = append(g.Nodes, cur)
478 continue
479 }
480
481
482
483 if len(cur.In) == 0 {
484 for _, outEdge := range cur.Out {
485 delete(outEdge.Dest.In, cur)
486 }
487 continue
488 }
489
490
491
492 if len(cur.In) != 1 {
493 panic("Get parent assertion failed. cur.In expected to be of length 1.")
494 }
495 var parent *Node
496 for _, edge := range cur.In {
497 parent = edge.Src
498 }
499
500 parentEdgeInline := parent.Out[cur].Inline
501
502
503 delete(parent.Out, cur)
504
505
506 for _, outEdge := range cur.Out {
507 child := outEdge.Dest
508
509 delete(child.In, cur)
510 child.In[parent] = outEdge
511 parent.Out[child] = outEdge
512
513 outEdge.Src = parent
514 outEdge.Residual = true
515
516
517
518 outEdge.Inline = parentEdgeInline && outEdge.Inline
519 }
520 }
521 g.RemoveRedundantEdges()
522 }
523
524 func joinLabels(s *profile.Sample) string {
525 if len(s.Label) == 0 {
526 return ""
527 }
528
529 var labels []string
530 for key, vals := range s.Label {
531 for _, v := range vals {
532 labels = append(labels, key+":"+v)
533 }
534 }
535 sort.Strings(labels)
536 return strings.Join(labels, `\n`)
537 }
538
539
540
541 func isNegative(n *Node) bool {
542 switch {
543 case n.Flat < 0:
544 return true
545 case n.Flat == 0 && n.Cum < 0:
546 return true
547 default:
548 return false
549 }
550 }
551
552
553
554
555 func CreateNodes(prof *profile.Profile, o *Options) (Nodes, map[uint64]Nodes) {
556 locations := make(map[uint64]Nodes, len(prof.Location))
557 nm := make(NodeMap, len(prof.Location))
558 for _, l := range prof.Location {
559 lines := l.Line
560 if len(lines) == 0 {
561 lines = []profile.Line{{}}
562 }
563 nodes := make(Nodes, len(lines))
564 for ln := range lines {
565 nodes[ln] = nm.findOrInsertLine(l, lines[ln], o)
566 }
567 locations[l.ID] = nodes
568 }
569 return nm.nodes(), locations
570 }
571
572 func (nm NodeMap) nodes() Nodes {
573 nodes := make(Nodes, 0, len(nm))
574 for _, n := range nm {
575 nodes = append(nodes, n)
576 }
577 return nodes
578 }
579
580 func (nm NodeMap) findOrInsertLine(l *profile.Location, li profile.Line, o *Options) *Node {
581 var objfile string
582 if m := l.Mapping; m != nil && m.File != "" {
583 objfile = m.File
584 }
585
586 if ni := nodeInfo(l, li, objfile, o); ni != nil {
587 return nm.FindOrInsertNode(*ni, o.KeptNodes)
588 }
589 return nil
590 }
591
592 func nodeInfo(l *profile.Location, line profile.Line, objfile string, o *Options) *NodeInfo {
593 if line.Function == nil {
594 return &NodeInfo{Address: l.Address, Objfile: objfile}
595 }
596 ni := &NodeInfo{
597 Address: l.Address,
598 Lineno: int(line.Line),
599 Columnno: int(line.Column),
600 Name: line.Function.Name,
601 }
602 if fname := line.Function.Filename; fname != "" {
603 ni.File = filepath.Clean(fname)
604 }
605 if o.OrigFnNames {
606 ni.OrigName = line.Function.SystemName
607 }
608 if o.ObjNames || (ni.Name == "" && ni.OrigName == "") {
609 ni.Objfile = objfile
610 ni.StartLine = int(line.Function.StartLine)
611 }
612 return ni
613 }
614
615 type tags struct {
616 t []*Tag
617 flat bool
618 }
619
620 func (t tags) Len() int { return len(t.t) }
621 func (t tags) Swap(i, j int) { t.t[i], t.t[j] = t.t[j], t.t[i] }
622 func (t tags) Less(i, j int) bool {
623 if !t.flat {
624 if t.t[i].Cum != t.t[j].Cum {
625 return abs64(t.t[i].Cum) > abs64(t.t[j].Cum)
626 }
627 }
628 if t.t[i].Flat != t.t[j].Flat {
629 return abs64(t.t[i].Flat) > abs64(t.t[j].Flat)
630 }
631 return t.t[i].Name < t.t[j].Name
632 }
633
634
635 func (ns Nodes) Sum() (flat int64, cum int64) {
636 for _, n := range ns {
637 flat += n.Flat
638 cum += n.Cum
639 }
640 return
641 }
642
643 func (n *Node) addSample(dw, w int64, labels string, numLabel map[string][]int64, numUnit map[string][]string, format func(int64, string) string, flat bool) {
644
645 if flat {
646 n.FlatDiv += dw
647 n.Flat += w
648 } else {
649 n.CumDiv += dw
650 n.Cum += w
651 }
652
653
654 if labels != "" {
655 t := n.LabelTags.findOrAddTag(labels, "", 0)
656 if flat {
657 t.FlatDiv += dw
658 t.Flat += w
659 } else {
660 t.CumDiv += dw
661 t.Cum += w
662 }
663 }
664
665 numericTags := n.NumericTags[labels]
666 if numericTags == nil {
667 numericTags = TagMap{}
668 n.NumericTags[labels] = numericTags
669 }
670
671 if format == nil {
672 format = defaultLabelFormat
673 }
674 for k, nvals := range numLabel {
675 units := numUnit[k]
676 for i, v := range nvals {
677 var t *Tag
678 if len(units) > 0 {
679 t = numericTags.findOrAddTag(format(v, units[i]), units[i], v)
680 } else {
681 t = numericTags.findOrAddTag(format(v, k), k, v)
682 }
683 if flat {
684 t.FlatDiv += dw
685 t.Flat += w
686 } else {
687 t.CumDiv += dw
688 t.Cum += w
689 }
690 }
691 }
692 }
693
694 func defaultLabelFormat(v int64, key string) string {
695 return strconv.FormatInt(v, 10)
696 }
697
698 func (m TagMap) findOrAddTag(label, unit string, value int64) *Tag {
699 l := m[label]
700 if l == nil {
701 l = &Tag{
702 Name: label,
703 Unit: unit,
704 Value: value,
705 }
706 m[label] = l
707 }
708 return l
709 }
710
711
712 func (g *Graph) String() string {
713 var s []string
714
715 nodeIndex := make(map[*Node]int, len(g.Nodes))
716
717 for i, n := range g.Nodes {
718 nodeIndex[n] = i + 1
719 }
720
721 for i, n := range g.Nodes {
722 name := n.Info.PrintableName()
723 var in, out []int
724
725 for _, from := range n.In {
726 in = append(in, nodeIndex[from.Src])
727 }
728 for _, to := range n.Out {
729 out = append(out, nodeIndex[to.Dest])
730 }
731 s = append(s, fmt.Sprintf("%d: %s[flat=%d cum=%d] %x -> %v ", i+1, name, n.Flat, n.Cum, in, out))
732 }
733 return strings.Join(s, "\n")
734 }
735
736
737
738 func (g *Graph) DiscardLowFrequencyNodes(nodeCutoff int64) NodeSet {
739 return makeNodeSet(g.Nodes, nodeCutoff)
740 }
741
742
743
744 func (g *Graph) DiscardLowFrequencyNodePtrs(nodeCutoff int64) NodePtrSet {
745 cutNodes := getNodesAboveCumCutoff(g.Nodes, nodeCutoff)
746 kept := make(NodePtrSet, len(cutNodes))
747 for _, n := range cutNodes {
748 kept[n] = true
749 }
750 return kept
751 }
752
753 func makeNodeSet(nodes Nodes, nodeCutoff int64) NodeSet {
754 cutNodes := getNodesAboveCumCutoff(nodes, nodeCutoff)
755 kept := make(NodeSet, len(cutNodes))
756 for _, n := range cutNodes {
757 kept[n.Info] = true
758 }
759 return kept
760 }
761
762
763
764 func getNodesAboveCumCutoff(nodes Nodes, nodeCutoff int64) Nodes {
765 cutoffNodes := make(Nodes, 0, len(nodes))
766 for _, n := range nodes {
767 if abs64(n.Cum) < nodeCutoff {
768 continue
769 }
770 cutoffNodes = append(cutoffNodes, n)
771 }
772 return cutoffNodes
773 }
774
775
776
777 func (g *Graph) TrimLowFrequencyTags(tagCutoff int64) {
778
779 for _, n := range g.Nodes {
780 n.LabelTags = trimLowFreqTags(n.LabelTags, tagCutoff)
781 for s, nt := range n.NumericTags {
782 n.NumericTags[s] = trimLowFreqTags(nt, tagCutoff)
783 }
784 }
785 }
786
787 func trimLowFreqTags(tags TagMap, minValue int64) TagMap {
788 kept := TagMap{}
789 for s, t := range tags {
790 if abs64(t.Flat) >= minValue || abs64(t.Cum) >= minValue {
791 kept[s] = t
792 }
793 }
794 return kept
795 }
796
797
798
799 func (g *Graph) TrimLowFrequencyEdges(edgeCutoff int64) int {
800 var droppedEdges int
801 for _, n := range g.Nodes {
802 for src, e := range n.In {
803 if abs64(e.Weight) < edgeCutoff {
804 delete(n.In, src)
805 delete(src.Out, n)
806 droppedEdges++
807 }
808 }
809 }
810 return droppedEdges
811 }
812
813
814 func (g *Graph) SortNodes(cum bool, visualMode bool) {
815
816 switch {
817 case visualMode:
818
819 g.Nodes.Sort(EntropyOrder)
820 case cum:
821 g.Nodes.Sort(CumNameOrder)
822 default:
823 g.Nodes.Sort(FlatNameOrder)
824 }
825 }
826
827
828 func (g *Graph) SelectTopNodePtrs(maxNodes int, visualMode bool) NodePtrSet {
829 set := make(NodePtrSet)
830 for _, node := range g.selectTopNodes(maxNodes, visualMode) {
831 set[node] = true
832 }
833 return set
834 }
835
836
837 func (g *Graph) SelectTopNodes(maxNodes int, visualMode bool) NodeSet {
838 return makeNodeSet(g.selectTopNodes(maxNodes, visualMode), 0)
839 }
840
841
842 func (g *Graph) selectTopNodes(maxNodes int, visualMode bool) Nodes {
843 if maxNodes > 0 {
844 if visualMode {
845 var count int
846
847
848 for i, n := range g.Nodes {
849 tags := min(countTags(n), maxNodelets)
850 if count += tags + 1; count >= maxNodes {
851 maxNodes = i + 1
852 break
853 }
854 }
855 }
856 }
857 if maxNodes > len(g.Nodes) {
858 maxNodes = len(g.Nodes)
859 }
860 return g.Nodes[:maxNodes]
861 }
862
863
864
865 func countTags(n *Node) int {
866 count := 0
867 for _, e := range n.LabelTags {
868 if e.Flat != 0 {
869 count++
870 }
871 }
872 for _, t := range n.NumericTags {
873 for _, e := range t {
874 if e.Flat != 0 {
875 count++
876 }
877 }
878 }
879 return count
880 }
881
882
883
884
885 func (g *Graph) RemoveRedundantEdges() {
886
887
888 for i := len(g.Nodes); i > 0; i-- {
889 n := g.Nodes[i-1]
890 in := n.In.Sort()
891 for j := len(in); j > 0; j-- {
892 e := in[j-1]
893 if !e.Residual {
894
895
896 break
897 }
898 if isRedundantEdge(e) {
899 delete(e.Src.Out, e.Dest)
900 delete(e.Dest.In, e.Src)
901 }
902 }
903 }
904 }
905
906
907
908 func isRedundantEdge(e *Edge) bool {
909 src, n := e.Src, e.Dest
910 seen := map[*Node]bool{n: true}
911 queue := Nodes{n}
912 for len(queue) > 0 {
913 n := queue[0]
914 queue = queue[1:]
915 for _, ie := range n.In {
916 if e == ie || seen[ie.Src] {
917 continue
918 }
919 if ie.Src == src {
920 return true
921 }
922 seen[ie.Src] = true
923 queue = append(queue, ie.Src)
924 }
925 }
926 return false
927 }
928
929
930
931 type nodeSorter struct {
932 rs Nodes
933 less func(l, r *Node) bool
934 }
935
936 func (s nodeSorter) Len() int { return len(s.rs) }
937 func (s nodeSorter) Swap(i, j int) { s.rs[i], s.rs[j] = s.rs[j], s.rs[i] }
938 func (s nodeSorter) Less(i, j int) bool { return s.less(s.rs[i], s.rs[j]) }
939
940
941
942
943
944 func (ns Nodes) Sort(o NodeOrder) error {
945 var s nodeSorter
946
947 switch o {
948 case FlatNameOrder:
949 s = nodeSorter{ns,
950 func(l, r *Node) bool {
951 if iv, jv := abs64(l.Flat), abs64(r.Flat); iv != jv {
952 return iv > jv
953 }
954 if iv, jv := l.Info.PrintableName(), r.Info.PrintableName(); iv != jv {
955 return iv < jv
956 }
957 if iv, jv := abs64(l.Cum), abs64(r.Cum); iv != jv {
958 return iv > jv
959 }
960 return compareNodes(l, r)
961 },
962 }
963 case FlatCumNameOrder:
964 s = nodeSorter{ns,
965 func(l, r *Node) bool {
966 if iv, jv := abs64(l.Flat), abs64(r.Flat); iv != jv {
967 return iv > jv
968 }
969 if iv, jv := abs64(l.Cum), abs64(r.Cum); iv != jv {
970 return iv > jv
971 }
972 if iv, jv := l.Info.PrintableName(), r.Info.PrintableName(); iv != jv {
973 return iv < jv
974 }
975 return compareNodes(l, r)
976 },
977 }
978 case NameOrder:
979 s = nodeSorter{ns,
980 func(l, r *Node) bool {
981 if iv, jv := l.Info.Name, r.Info.Name; iv != jv {
982 return iv < jv
983 }
984 return compareNodes(l, r)
985 },
986 }
987 case FileOrder:
988 s = nodeSorter{ns,
989 func(l, r *Node) bool {
990 if iv, jv := l.Info.File, r.Info.File; iv != jv {
991 return iv < jv
992 }
993 if iv, jv := l.Info.StartLine, r.Info.StartLine; iv != jv {
994 return iv < jv
995 }
996 return compareNodes(l, r)
997 },
998 }
999 case AddressOrder:
1000 s = nodeSorter{ns,
1001 func(l, r *Node) bool {
1002 if iv, jv := l.Info.Address, r.Info.Address; iv != jv {
1003 return iv < jv
1004 }
1005 return compareNodes(l, r)
1006 },
1007 }
1008 case CumNameOrder, EntropyOrder:
1009
1010 var score map[*Node]int64
1011 scoreOrder := func(l, r *Node) bool {
1012 if iv, jv := abs64(score[l]), abs64(score[r]); iv != jv {
1013 return iv > jv
1014 }
1015 if iv, jv := l.Info.PrintableName(), r.Info.PrintableName(); iv != jv {
1016 return iv < jv
1017 }
1018 if iv, jv := abs64(l.Flat), abs64(r.Flat); iv != jv {
1019 return iv > jv
1020 }
1021 return compareNodes(l, r)
1022 }
1023
1024 switch o {
1025 case CumNameOrder:
1026 score = make(map[*Node]int64, len(ns))
1027 for _, n := range ns {
1028 score[n] = n.Cum
1029 }
1030 s = nodeSorter{ns, scoreOrder}
1031 case EntropyOrder:
1032 score = make(map[*Node]int64, len(ns))
1033 for _, n := range ns {
1034 score[n] = entropyScore(n)
1035 }
1036 s = nodeSorter{ns, scoreOrder}
1037 }
1038 default:
1039 return fmt.Errorf("report: unrecognized sort ordering: %d", o)
1040 }
1041 sort.Sort(s)
1042 return nil
1043 }
1044
1045
1046
1047 func compareNodes(l, r *Node) bool {
1048 return fmt.Sprint(l.Info) < fmt.Sprint(r.Info)
1049 }
1050
1051
1052
1053
1054
1055
1056
1057
1058 func entropyScore(n *Node) int64 {
1059 score := float64(0)
1060
1061 if len(n.In) == 0 {
1062 score++
1063 } else {
1064 score += edgeEntropyScore(n, n.In, 0)
1065 }
1066
1067 if len(n.Out) == 0 {
1068 score++
1069 } else {
1070 score += edgeEntropyScore(n, n.Out, n.Flat)
1071 }
1072
1073 return int64(score*float64(n.Cum)) + n.Flat
1074 }
1075
1076
1077
1078
1079
1080
1081 func edgeEntropyScore(n *Node, edges EdgeMap, self int64) float64 {
1082 score := float64(0)
1083 total := self
1084 for _, e := range edges {
1085 if e.Weight > 0 {
1086 total += abs64(e.Weight)
1087 }
1088 }
1089 if total != 0 {
1090 for _, e := range edges {
1091 frac := float64(abs64(e.Weight)) / float64(total)
1092 score += -frac * math.Log2(frac)
1093 }
1094 if self > 0 {
1095 frac := float64(abs64(self)) / float64(total)
1096 score += -frac * math.Log2(frac)
1097 }
1098 }
1099 return score
1100 }
1101
1102
1103 type NodeOrder int
1104
1105
1106 const (
1107 FlatNameOrder NodeOrder = iota
1108 FlatCumNameOrder
1109 CumNameOrder
1110 NameOrder
1111 FileOrder
1112 AddressOrder
1113 EntropyOrder
1114 )
1115
1116
1117
1118
1119 func (e EdgeMap) Sort() []*Edge {
1120 el := make(edgeList, 0, len(e))
1121 for _, w := range e {
1122 el = append(el, w)
1123 }
1124
1125 sort.Sort(el)
1126 return el
1127 }
1128
1129
1130 func (e EdgeMap) Sum() int64 {
1131 var ret int64
1132 for _, edge := range e {
1133 ret += edge.Weight
1134 }
1135 return ret
1136 }
1137
1138 type edgeList []*Edge
1139
1140 func (el edgeList) Len() int {
1141 return len(el)
1142 }
1143
1144 func (el edgeList) Less(i, j int) bool {
1145 if el[i].Weight != el[j].Weight {
1146 return abs64(el[i].Weight) > abs64(el[j].Weight)
1147 }
1148
1149 from1 := el[i].Src.Info.PrintableName()
1150 from2 := el[j].Src.Info.PrintableName()
1151 if from1 != from2 {
1152 return from1 < from2
1153 }
1154
1155 to1 := el[i].Dest.Info.PrintableName()
1156 to2 := el[j].Dest.Info.PrintableName()
1157
1158 return to1 < to2
1159 }
1160
1161 func (el edgeList) Swap(i, j int) {
1162 el[i], el[j] = el[j], el[i]
1163 }
1164
1165 func abs64(i int64) int64 {
1166 if i < 0 {
1167 return -i
1168 }
1169 return i
1170 }
1171
View as plain text