From b07e845e764806fa888cb4e99c8ace4625f0472f Mon Sep 17 00:00:00 2001 From: Cherry Mui Date: Tue, 1 Nov 2022 12:33:58 -0400 Subject: [PATCH] cmd/compile: use CDF to determine PGO inline threshold Currently in PGO we use a percentage threshold to determine if a callsite is hot. This CL uses a different method -- treating the hottest callsites that make up cumulatively top X% of total edge weights as hot (X=95 for now). This default might work better for a wider range of profiles. (The absolute threshold can still be changed by a flag.) For #55022. Change-Id: I7e3b6f0c3cf23f9a89dd5994c10075b498bf14ee Reviewed-on: https://go-review.googlesource.com/c/go/+/447016 TryBot-Result: Gopher Robot Run-TryBot: Cherry Mui Reviewed-by: Michael Pratt --- src/cmd/compile/internal/base/debug.go | 66 +++++++++++++------------- src/cmd/compile/internal/inline/inl.go | 52 +++++++++++++++++--- 2 files changed, 79 insertions(+), 39 deletions(-) diff --git a/src/cmd/compile/internal/base/debug.go b/src/cmd/compile/internal/base/debug.go index 18422256ab..6cb7a54cad 100644 --- a/src/cmd/compile/internal/base/debug.go +++ b/src/cmd/compile/internal/base/debug.go @@ -16,39 +16,39 @@ var Debug DebugFlags // The -d option takes a comma-separated list of settings. // Each setting is name=value; for ints, name is short for name=1. type DebugFlags struct { - Append int `help:"print information about append compilation"` - Checkptr int `help:"instrument unsafe pointer conversions\n0: instrumentation disabled\n1: conversions involving unsafe.Pointer are instrumented\n2: conversions to unsafe.Pointer force heap allocation"` - Closure int `help:"print information about closure compilation"` - DclStack int `help:"run internal dclstack check"` - Defer int `help:"print information about defer compilation"` - DisableNil int `help:"disable nil checks"` - DumpPtrs int `help:"show Node pointers values in dump output"` - DwarfInl int `help:"print information about DWARF inlined function creation"` - Export int `help:"print export data"` - GCProg int `help:"print dump of GC programs"` - Gossahash string `help:"hash value for use in debugging the compiler"` - InlFuncsWithClosures int `help:"allow functions with closures to be inlined"` - Libfuzzer int `help:"enable coverage instrumentation for libfuzzer"` - LocationLists int `help:"print information about DWARF location list creation"` - Nil int `help:"print information about nil checks"` - NoOpenDefer int `help:"disable open-coded defers"` - NoRefName int `help:"do not include referenced symbol names in object file"` - PCTab string `help:"print named pc-value table\nOne of: pctospadj, pctofile, pctoline, pctoinline, pctopcdata"` - Panic int `help:"show all compiler panics"` - Reshape int `help:"print information about expression reshaping"` - Shapify int `help:"print information about shaping recursive types"` - Slice int `help:"print information about slice compilation"` - SoftFloat int `help:"force compiler to emit soft-float code"` - SyncFrames int `help:"how many writer stack frames to include at sync points in unified export data"` - TypeAssert int `help:"print information about type assertion inlining"` - TypecheckInl int `help:"eager typechecking of inline function bodies"` - Unified int `help:"enable unified IR construction"` - WB int `help:"print information about write barriers"` - ABIWrap int `help:"print information about ABI wrapper generation"` - MayMoreStack string `help:"call named function before all stack growth checks"` - InlineHotCallSiteThreshold string `help:"threshold percentage for determining call sites as hot candidates for inlining"` - InlineHotBudget int `help:"inline budget for hot functions"` - PGOInline int `help:"debug profile-guided inlining"` + Append int `help:"print information about append compilation"` + Checkptr int `help:"instrument unsafe pointer conversions\n0: instrumentation disabled\n1: conversions involving unsafe.Pointer are instrumented\n2: conversions to unsafe.Pointer force heap allocation"` + Closure int `help:"print information about closure compilation"` + DclStack int `help:"run internal dclstack check"` + Defer int `help:"print information about defer compilation"` + DisableNil int `help:"disable nil checks"` + DumpPtrs int `help:"show Node pointers values in dump output"` + DwarfInl int `help:"print information about DWARF inlined function creation"` + Export int `help:"print export data"` + GCProg int `help:"print dump of GC programs"` + Gossahash string `help:"hash value for use in debugging the compiler"` + InlFuncsWithClosures int `help:"allow functions with closures to be inlined"` + Libfuzzer int `help:"enable coverage instrumentation for libfuzzer"` + LocationLists int `help:"print information about DWARF location list creation"` + Nil int `help:"print information about nil checks"` + NoOpenDefer int `help:"disable open-coded defers"` + NoRefName int `help:"do not include referenced symbol names in object file"` + PCTab string `help:"print named pc-value table\nOne of: pctospadj, pctofile, pctoline, pctoinline, pctopcdata"` + Panic int `help:"show all compiler panics"` + Reshape int `help:"print information about expression reshaping"` + Shapify int `help:"print information about shaping recursive types"` + Slice int `help:"print information about slice compilation"` + SoftFloat int `help:"force compiler to emit soft-float code"` + SyncFrames int `help:"how many writer stack frames to include at sync points in unified export data"` + TypeAssert int `help:"print information about type assertion inlining"` + TypecheckInl int `help:"eager typechecking of inline function bodies"` + Unified int `help:"enable unified IR construction"` + WB int `help:"print information about write barriers"` + ABIWrap int `help:"print information about ABI wrapper generation"` + MayMoreStack string `help:"call named function before all stack growth checks"` + InlineHotCallSiteCDFThreshold string `help:"cummulative threshold percentage for determining call sites as hot candidates for inlining"` + InlineHotBudget int `help:"inline budget for hot functions"` + PGOInline int `help:"debug profile-guided inlining"` ConcurrentOk bool // true if only concurrentOk flags seen } diff --git a/src/cmd/compile/internal/inline/inl.go b/src/cmd/compile/internal/inline/inl.go index 98bfb4e382..3f7ad34af3 100644 --- a/src/cmd/compile/internal/inline/inl.go +++ b/src/cmd/compile/internal/inline/inl.go @@ -29,6 +29,7 @@ package inline import ( "fmt" "go/constant" + "sort" "strconv" "strings" @@ -69,7 +70,13 @@ var ( inlinedCallSites = make(map[pgo.CallSiteInfo]struct{}) // Threshold in percentage for hot callsite inlining. - inlineHotCallSiteThresholdPercent = float64(0.1) + inlineHotCallSiteThresholdPercent float64 + + // Threshold in CDF percentage for hot callsite inlining, + // that is, for a threshold of X the hottest callsites that + // make up the top X% of total edge weight will be + // considered hot for inlining candidates. + inlineCDFHotCallSiteThresholdPercent = float64(95) // Budget increased due to hotness. inlineHotMaxBudget int32 = 160 @@ -77,11 +84,12 @@ var ( // pgoInlinePrologue records the hot callsites from ir-graph. func pgoInlinePrologue(p *pgo.Profile) { - if s, err := strconv.ParseFloat(base.Debug.InlineHotCallSiteThreshold, 64); err == nil { - inlineHotCallSiteThresholdPercent = s - if base.Debug.PGOInline > 0 { - fmt.Printf("hot-callsite-thres=%v\n", inlineHotCallSiteThresholdPercent) - } + if s, err := strconv.ParseFloat(base.Debug.InlineHotCallSiteCDFThreshold, 64); err == nil { + inlineCDFHotCallSiteThresholdPercent = s + } + inlineHotCallSiteThresholdPercent = computeThresholdFromCDF(p) + if base.Debug.PGOInline > 0 { + fmt.Printf("hot-callsite-thres-from-CDF=%v\n", inlineHotCallSiteThresholdPercent) } if base.Debug.InlineHotBudget != 0 { @@ -113,6 +121,38 @@ func pgoInlinePrologue(p *pgo.Profile) { } } +func computeThresholdFromCDF(p *pgo.Profile) float64 { + nodes := make([]pgo.NodeMapKey, len(p.NodeMap)) + i := 0 + for n := range p.NodeMap { + nodes[i] = n + i++ + } + sort.Slice(nodes, func(i, j int) bool { + ni, nj := nodes[i], nodes[j] + if wi, wj := p.NodeMap[ni].EWeight, p.NodeMap[nj].EWeight; wi != wj { + return wi > wj // want larger weight first + } + // same weight, order by name/line number + if ni.CallerName != nj.CallerName { + return ni.CallerName < nj.CallerName + } + if ni.CalleeName != nj.CalleeName { + return ni.CalleeName < nj.CalleeName + } + return ni.CallSite < nj.CallSite + }) + cum := int64(0) + for _, n := range nodes { + w := p.NodeMap[n].EWeight + cum += w + if pgo.WeightInPercentage(cum, p.TotalEdgeWeight) > inlineCDFHotCallSiteThresholdPercent { + return pgo.WeightInPercentage(w, p.TotalEdgeWeight) + } + } + return 100 +} + // pgoInlineEpilogue updates IRGraph after inlining. func pgoInlineEpilogue(p *pgo.Profile) { if base.Debug.PGOInline > 0 { -- 2.50.0