pgo

package standard library
go1.20 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Feb 1, 2023 License: BSD-3-Clause Imports: 11 Imported by: 0

Documentation

Overview

Original file location: https://github.com/google/pprof/tree/main/internal/graph/graph.go

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func NodeLineOffset 

func NodeLineOffset(n ir.Node, fn *ir.Func) int

NodeLineOffset returns the line offset of n in fn.

func WeightInPercentage 

func WeightInPercentage(value int64, total int64) float64

WeightInPercentage converts profile weights to a percentage.

Types

type CallSiteInfo 

type CallSiteInfo struct {
	LineOffset int // Line offset from function start line.
	Caller     *ir.Func
	Callee     *ir.Func
}

CallSiteInfo captures call-site information and its caller/callee.

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 []*Edge

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

func (*EdgeMap) Add 

func (em *EdgeMap) Add(e *Edge)

func (*EdgeMap) Delete 

func (em *EdgeMap) Delete(e *Edge)

func (EdgeMap) FindTo 

func (em EdgeMap) FindTo(n *Node) *Edge

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

type IREdge 

type IREdge struct {
	// Source and destination of the edge in IRNode.
	Src, Dst       *IRNode
	Weight         int64
	CallSiteOffset int // Line offset from function start line.
}

IREdge represents a call edge in the IRGraph with source, destination, weight, callsite, and line number information.

type IREdgeMap 

type IREdgeMap map[*IRNode][]*IREdge

IREdgeMap maps an IRNode to its successors.

type IRGraph 

type IRGraph struct {
	// Nodes of the graph
	IRNodes  map[string]*IRNode
	OutEdges IREdgeMap
	InEdges  IREdgeMap
}

IRGraph is the key datastrcture that is built from profile. It is essentially a call graph with nodes pointing to IRs of functions and edges carrying weights and callsite information. The graph is bidirectional that helps in removing nodes efficiently.

type IRNode 

type IRNode struct {
	// Pointer to the IR of the Function represented by this node.
	AST *ir.Func
	// Flat weight of the IRNode, obtained from profile.
	Flat int64
	// Cumulative weight of the IRNode.
	Cum int64
}

IRNode represents a node in the IRGraph.

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
}

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
	Address           uint64
	StartLine, Lineno int
}

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 NodeMapKey 

type NodeMapKey struct {
	CallerName     string
	CalleeName     string
	CallSiteOffset int // Line offset from function start line.
}

NodeMapKey represents a hash key to identify unique call-edges in profile and in IR. Used for deduplication of call edges found in profile.

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

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

	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 Profile 

type Profile struct {
	// Aggregated NodeWeights and EdgeWeights across the profile. This
	// helps us determine the percentage threshold for hot/cold
	// partitioning.
	TotalNodeWeight int64
	TotalEdgeWeight int64

	// NodeMap contains all unique call-edges in the profile and their
	// aggregated weight.
	NodeMap map[NodeMapKey]*Weights

	// WeightedCG represents the IRGraph built from profile, which we will
	// update as part of inlining.
	WeightedCG *IRGraph
}

Profile contains the processed PGO profile and weighted call graph used for PGO optimizations.

func New 

func New(profileFile string) *Profile

New generates a profile-graph from the profile.

func (*Profile) PrintWeightedCallGraphDOT 

func (p *Profile) PrintWeightedCallGraphDOT(edgeThreshold float64)

PrintWeightedCallGraphDOT prints IRGraph in DOT format.

func (*Profile) RedirectEdges 

func (p *Profile) RedirectEdges(cur *IRNode, inlinedCallSites map[CallSiteInfo]struct{})

RedirectEdges deletes and redirects out-edges from node cur based on inlining information via inlinedCallSites.

CallSiteInfo.Callee must be nil.

func (*Profile) VisitIR 

func (p *Profile) VisitIR(fn *ir.Func, recursive bool)

VisitIR traverses the body of each ir.Func and use NodeMap to determine if we need to add an edge from ir.Func and any node in the ir.Func body.

type Weights 

type Weights struct {
	NFlat   int64
	NCum    int64
	EWeight int64
}

Weights capture both node weight and edge weight.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.