graph

Documentation

Overview

Package graph collects a set of samples into a directed graph.

Index

• func ComposeDot(w io.Writer, g *Graph, a *DotAttributes, c *DotConfig)
• func ShortenFunctionName(f string) string
• type DotAttributes
• type DotConfig
• type DotNodeAttributes
• type Edge
  • func (e *Edge) WeightValue() int64
• type EdgeMap
  • func (e EdgeMap) Sort() []*Edge
  • func (e EdgeMap) Sum() int64
• type Graph
  • func New(prof *profile.Profile, o *Options) *Graph
  • func (g *Graph) DiscardLowFrequencyNodePtrs(nodeCutoff int64) NodePtrSet
  • func (g *Graph) DiscardLowFrequencyNodes(nodeCutoff int64) NodeSet
  • func (g *Graph) RemoveRedundantEdges()
  • func (g *Graph) SelectTopNodePtrs(maxNodes int, visualMode bool) NodePtrSet
  • func (g *Graph) SelectTopNodes(maxNodes int, visualMode bool) NodeSet
  • func (g *Graph) SortNodes(cum bool, visualMode bool)
  • func (g *Graph) String() string
  • func (g *Graph) TrimLowFrequencyEdges(edgeCutoff int64) int
  • func (g *Graph) TrimLowFrequencyTags(tagCutoff int64)
  • func (g *Graph) TrimTree(kept NodePtrSet)
• type Node
  • func (n *Node) AddToEdge(to *Node, v int64, residual, inline bool)
  • func (n *Node) AddToEdgeDiv(to *Node, dv, v int64, residual, inline bool)
  • func (n *Node) CumValue() int64
  • func (n *Node) FlatValue() int64
• type NodeInfo
  • func (i *NodeInfo) NameComponents() []string
  • func (i *NodeInfo) PrintableName() string
• type NodeMap
  • func (nm NodeMap) FindOrInsertNode(info NodeInfo, kept NodeSet) *Node
• type NodeOrder
• type NodePtrSet
• type NodeSet
• type Nodes
  • func CreateNodes(prof *profile.Profile, o *Options) (Nodes, map[uint64]Nodes)
  • func (ns Nodes) Sort(o NodeOrder) error
  • func (ns Nodes) Sum() (flat int64, cum int64)
• type Options
• type Tag
  • func SortTags(t []*Tag, flat bool) []*Tag
  • func (t *Tag) CumValue() int64
  • func (t *Tag) FlatValue() int64
• type TagMap

Functions

func ComposeDot

func ComposeDot(w io.Writer, g *Graph, a *DotAttributes, c *DotConfig)

ComposeDot creates and writes a in the DOT format to the writer, using the configurations given.

func ShortenFunctionName

func ShortenFunctionName(f string) string

ShortenFunctionName returns a shortened version of a function's name.

Types

type DotAttributes

type DotAttributes struct {
	Nodes map[*Node]*DotNodeAttributes // A map allowing each Node to have its own visualization option
}

DotAttributes contains details about the graph itself, giving insight into how its elements should be rendered.

type DotConfig

type DotConfig struct {
	Title     string   // The title of the DOT graph
	LegendURL string   // The URL to link to from the legend.
	Labels    []string // The labels for the DOT's legend

	FormatValue func(int64) string // A formatting function for values
	Total       int64              // The total weight of the graph, used to compute percentages
}

DotConfig contains attributes about how a graph should be constructed and how it should look.

type DotNodeAttributes

type DotNodeAttributes struct {
	Shape       string                 // The optional shape of the node when rendered visually
	Bold        bool                   // If the node should be bold or not
	Peripheries int                    // An optional number of borders to place around a node
	URL         string                 // An optional url link to add to a node
	Formatter   func(*NodeInfo) string // An optional formatter for the node's label
}

DotNodeAttributes contains Node specific visualization options.

type Edge

type Edge struct {
	Src, Dest *Node
	// The summary weight of the edge
	Weight, WeightDiv int64

	// residual edges connect nodes that were connected through a
	// separate node, which has been removed from the report.
	Residual bool
	// An inline edge represents a call that was inlined into the caller.
	Inline bool
}

Edge contains any attributes to be represented about edges in a graph.

func (*Edge) WeightValue

func (e *Edge) WeightValue() int64

WeightValue returns the weight value for this edge, normalizing if a divisor is available.

type EdgeMap

type EdgeMap map[*Node]*Edge

EdgeMap is used to represent the incoming/outgoing edges from a node.

func (EdgeMap) Sort

func (e EdgeMap) Sort() []*Edge

Sort returns a slice of the edges in the map, in a consistent order. The sort order is first based on the edge weight (higher-to-lower) and then by the node names to avoid flakiness.

func (EdgeMap) Sum

func (e EdgeMap) Sum() int64

Sum returns the total weight for a set of nodes.

type Graph

type Graph struct {
	Nodes Nodes
}

Graph summarizes a performance profile into a format that is suitable for visualization.

func New

func New(prof *profile.Profile, o *Options) *Graph

New summarizes performance data from a profile into a graph.

func (*Graph) DiscardLowFrequencyNodePtrs

func (g *Graph) DiscardLowFrequencyNodePtrs(nodeCutoff int64) NodePtrSet

DiscardLowFrequencyNodePtrs returns a NodePtrSet of nodes at or over a specific cum value cutoff.

func (*Graph) DiscardLowFrequencyNodes

func (g *Graph) DiscardLowFrequencyNodes(nodeCutoff int64) NodeSet

DiscardLowFrequencyNodes returns a set of the nodes at or over a specific cum value cutoff.

func (*Graph) RemoveRedundantEdges

func (g *Graph) RemoveRedundantEdges()

RemoveRedundantEdges removes residual edges if the destination can be reached through another path. This is done to simplify the graph while preserving connectivity.

func (*Graph) SelectTopNodePtrs

func (g *Graph) SelectTopNodePtrs(maxNodes int, visualMode bool) NodePtrSet

SelectTopNodePtrs returns a set of the top maxNodes *Node in a graph.

func (*Graph) SelectTopNodes

func (g *Graph) SelectTopNodes(maxNodes int, visualMode bool) NodeSet

SelectTopNodes returns a set of the top maxNodes nodes in a graph.

func (*Graph) SortNodes

func (g *Graph) SortNodes(cum bool, visualMode bool)

SortNodes sorts the nodes in a graph based on a specific heuristic.

func (*Graph) String

func (g *Graph) String() string

String returns a text representation of a graph, for debugging purposes.

func (*Graph) TrimLowFrequencyEdges

func (g *Graph) TrimLowFrequencyEdges(edgeCutoff int64) int

TrimLowFrequencyEdges removes edges that have less than the specified weight. Returns the number of edges removed

func (*Graph) TrimLowFrequencyTags

func (g *Graph) TrimLowFrequencyTags(tagCutoff int64)

TrimLowFrequencyTags removes tags that have less than the specified weight.

func (*Graph) TrimTree

func (g *Graph) TrimTree(kept NodePtrSet)

TrimTree trims a Graph in forest form, keeping only the nodes in kept. This will not work correctly if even a single node has multiple parents.

type Node

type Node struct {
	// Info describes the source location associated to this node.
	Info NodeInfo

	// Function represents the function that this node belongs to. On
	// graphs with sub-function resolution (eg line number or
	// addresses), two nodes in a NodeMap that are part of the same
	// function have the same value of Node.Function. If the Node
	// represents the whole function, it points back to itself.
	Function *Node

	// Values associated to this node. Flat is exclusive to this node,
	// Cum includes all descendents.
	Flat, FlatDiv, Cum, CumDiv int64

	// In and out Contains the nodes immediately reaching or reached by
	// this node.
	In, Out EdgeMap

	// LabelTags provide additional information about subsets of a sample.
	LabelTags TagMap

	// NumericTags provide additional values for subsets of a sample.
	// Numeric tags are optionally associated to a label tag. The key
	// for NumericTags is the name of the LabelTag they are associated
	// to, or "" for numeric tags not associated to a label tag.
	NumericTags map[string]TagMap
}

Node is an entry on a profiling report. It represents a unique program location.

func (*Node) AddToEdge

func (n *Node) AddToEdge(to *Node, v int64, residual, inline bool)

AddToEdge increases the weight of an edge between two nodes. If there isn't such an edge one is created.

func (*Node) AddToEdgeDiv

func (n *Node) AddToEdgeDiv(to *Node, dv, v int64, residual, inline bool)

AddToEdgeDiv increases the weight of an edge between two nodes. If there isn't such an edge one is created.

func (*Node) CumValue

func (n *Node) CumValue() int64

CumValue returns the inclusive value for this node, computing the mean if a divisor is available.

func (*Node) FlatValue

func (n *Node) FlatValue() int64

FlatValue returns the exclusive value for this node, computing the mean if a divisor is available.

type NodeInfo

type NodeInfo struct {
	Name              string
	OrigName          string
	Address           uint64
	File              string
	StartLine, Lineno int
	Objfile           string
}

NodeInfo contains the attributes for a node.

func (*NodeInfo) NameComponents

func (i *NodeInfo) NameComponents() []string

NameComponents returns the components of the printable name to be used for a node.

func (*NodeInfo) PrintableName

func (i *NodeInfo) PrintableName() string

PrintableName calls the Node's Formatter function with a single space separator.

type NodeMap

type NodeMap map[NodeInfo]*Node

NodeMap maps from a node info struct to a node. It is used to merge report entries with the same info.

func (NodeMap) FindOrInsertNode

func (nm NodeMap) FindOrInsertNode(info NodeInfo, kept NodeSet) *Node

FindOrInsertNode takes the info for a node and either returns a matching node from the node map if one exists, or adds one to the map if one does not. If kept is non-nil, nodes are only added if they can be located on it.

type NodeOrder

type NodeOrder int

NodeOrder sets the ordering for a Sort operation

const (
	FlatNameOrder NodeOrder = iota
	FlatCumNameOrder
	CumNameOrder
	NameOrder
	FileOrder
	AddressOrder
	EntropyOrder
)

Sorting options for node sort.

type NodePtrSet

type NodePtrSet map[*Node]bool

NodePtrSet is a collection of nodes. Trimming a graph or tree requires a set of objects which uniquely identify the nodes to keep. In a graph, NodeInfo works as a unique identifier; however, in a tree multiple nodes may share identical NodeInfos. A *Node does uniquely identify a node so we can use that instead. Though a *Node also uniquely identifies a node in a graph, currently, during trimming, graphs are rebuilt from scratch using only the NodeSet, so there would not be the required context of the initial graph to allow for the use of *Node.

type NodeSet

type NodeSet map[NodeInfo]bool

NodeSet is a collection of node info structs.

type Nodes

type Nodes []*Node

Nodes is an ordered collection of graph nodes.

func CreateNodes

func CreateNodes(prof *profile.Profile, o *Options) (Nodes, map[uint64]Nodes)

CreateNodes creates graph nodes for all locations in a profile. It returns set of all nodes, plus a mapping of each location to the set of corresponding nodes (one per location.Line).

func (Nodes) Sort

func (ns Nodes) Sort(o NodeOrder) error

Sort reorders a slice of nodes based on the specified ordering criteria. The result is sorted in decreasing order for (absolute) numeric quantities, alphabetically for text, and increasing for addresses.

func (Nodes) Sum

func (ns Nodes) Sum() (flat int64, cum int64)

Sum adds the flat and cum values of a set of nodes.

type Options

type Options struct {
	SampleValue       func(s []int64) int64      // Function to compute the value of a sample
	SampleMeanDivisor func(s []int64) int64      // Function to compute the divisor for mean graphs, or nil
	FormatTag         func(int64, string) string // Function to format a sample tag value into a string
	ObjNames          bool                       // Always preserve obj filename
	OrigFnNames       bool                       // Preserve original (eg mangled) function names

	CallTree     bool // Build a tree instead of a graph
	DropNegative bool // Drop nodes with overall negative values

	KeptNodes NodeSet // If non-nil, only use nodes in this set
}

Options encodes the options for constructing a graph

type Tag

type Tag struct {
	Name          string
	Unit          string // Describe the value, "" for non-numeric tags
	Value         int64
	Flat, FlatDiv int64
	Cum, CumDiv   int64
}

Tag represent sample annotations

func SortTags

func SortTags(t []*Tag, flat bool) []*Tag

SortTags sorts a slice of tags based on their weight.

func (*Tag) CumValue

func (t *Tag) CumValue() int64

CumValue returns the inclusive value for this tag, computing the mean if a divisor is available.

func (*Tag) FlatValue

func (t *Tag) FlatValue() int64

FlatValue returns the exclusive value for this tag, computing the mean if a divisor is available.

type TagMap

type TagMap map[string]*Tag

TagMap is a collection of tags, classified by their name.