From 75dadbec1eff08120662d82d9c5962de29c6d0dc Mon Sep 17 00:00:00 2001 From: Austin Clements Date: Sat, 21 Apr 2018 15:40:56 -0400 Subject: [PATCH] cmd/compile: make LivenessMap dense MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Currently liveness information is kept in a map keyed by *ssa.Value. This made sense when liveness information was sparse, but now we have liveness for nearly every ssa.Value. There's a fair amount of memory and CPU overhead to this map now. This CL replaces this map with a slice indexed by value ID. Passes toolstash -cmp. name old time/op new time/op delta Template 197ms ± 1% 194ms ± 1% -1.60% (p=0.000 n=9+10) Unicode 100ms ± 2% 99ms ± 1% -1.31% (p=0.012 n=8+10) GoTypes 695ms ± 1% 689ms ± 0% -0.94% (p=0.000 n=10+10) Compiler 3.34s ± 2% 3.29s ± 1% -1.26% (p=0.000 n=10+9) SSA 8.08s ± 0% 8.02s ± 2% -0.70% (p=0.034 n=8+10) Flate 133ms ± 1% 131ms ± 1% -1.04% (p=0.006 n=10+9) GoParser 163ms ± 1% 162ms ± 1% -0.79% (p=0.034 n=8+10) Reflect 459ms ± 1% 454ms ± 0% -1.06% (p=0.000 n=10+8) Tar 186ms ± 1% 185ms ± 1% -0.87% (p=0.003 n=9+9) XML 238ms ± 1% 235ms ± 1% -1.01% (p=0.004 n=8+9) [Geo mean] 418ms 414ms -1.06% name old alloc/op new alloc/op delta Template 36.4MB ± 0% 35.6MB ± 0% -2.29% (p=0.000 n=9+10) Unicode 29.7MB ± 0% 29.5MB ± 0% -0.68% (p=0.000 n=10+10) GoTypes 119MB ± 0% 117MB ± 0% -2.30% (p=0.000 n=9+9) Compiler 546MB ± 0% 532MB ± 0% -2.47% (p=0.000 n=10+10) SSA 1.59GB ± 0% 1.55GB ± 0% -2.41% (p=0.000 n=10+10) Flate 24.9MB ± 0% 24.5MB ± 0% -1.77% (p=0.000 n=8+10) GoParser 29.5MB ± 0% 28.7MB ± 0% -2.60% (p=0.000 n=9+10) Reflect 81.7MB ± 0% 80.5MB ± 0% -1.49% (p=0.000 n=10+10) Tar 35.7MB ± 0% 35.1MB ± 0% -1.64% (p=0.000 n=10+10) XML 45.0MB ± 0% 43.7MB ± 0% -2.76% (p=0.000 n=9+10) [Geo mean] 80.1MB 78.4MB -2.04% name old allocs/op new allocs/op delta Template 336k ± 0% 335k ± 0% -0.31% (p=0.000 n=9+10) Unicode 339k ± 0% 339k ± 0% -0.05% (p=0.000 n=10+10) GoTypes 1.18M ± 0% 1.18M ± 0% -0.26% (p=0.000 n=10+10) Compiler 4.96M ± 0% 4.94M ± 0% -0.24% (p=0.000 n=10+10) SSA 12.6M ± 0% 12.5M ± 0% -0.30% (p=0.000 n=10+10) Flate 224k ± 0% 223k ± 0% -0.30% (p=0.000 n=10+10) GoParser 282k ± 0% 281k ± 0% -0.32% (p=0.000 n=10+10) Reflect 965k ± 0% 963k ± 0% -0.27% (p=0.000 n=9+10) Tar 331k ± 0% 330k ± 0% -0.27% (p=0.000 n=10+10) XML 393k ± 0% 392k ± 0% -0.26% (p=0.000 n=10+10) [Geo mean] 763k 761k -0.26% Updates #24543. Change-Id: I4cfd2461510d3c026a262760bca225dc37482341 Reviewed-on: https://go-review.googlesource.com/110178 Run-TryBot: Austin Clements TryBot-Result: Gobot Gobot Reviewed-by: Keith Randall --- src/cmd/compile/internal/gc/plive.go | 41 ++++++++++++++++++++-------- 1 file changed, 30 insertions(+), 11 deletions(-) diff --git a/src/cmd/compile/internal/gc/plive.go b/src/cmd/compile/internal/gc/plive.go index 4228e80c4d..07b1354a89 100644 --- a/src/cmd/compile/internal/gc/plive.go +++ b/src/cmd/compile/internal/gc/plive.go @@ -126,9 +126,6 @@ type Liveness struct { // livenessMap maps from safe points (i.e., CALLs) to their // liveness map indexes. - // - // TODO(austin): Now that we have liveness at almost every PC, - // should this be a dense structure? livenessMap LivenessMap stackMapSet bvecSet stackMaps []bvec @@ -140,12 +137,30 @@ type Liveness struct { // LivenessMap maps from *ssa.Value to LivenessIndex. type LivenessMap struct { - m map[*ssa.Value]LivenessIndex + m []LivenessIndex +} + +func (m *LivenessMap) reset(ids int) { + m2 := m.m + if ids > cap(m2) { + m2 = make([]LivenessIndex, ids) + } else { + m2 = m2[:ids] + } + none := LivenessInvalid + for i := range m2 { + m2[i] = none + } + m.m = m2 +} + +func (m *LivenessMap) set(v *ssa.Value, i LivenessIndex) { + m.m[v.ID] = i } func (m LivenessMap) Get(v *ssa.Value) LivenessIndex { - if i, ok := m.m[v]; ok { - return i + if int(v.ID) < len(m.m) { + return m.m[int(v.ID)] } // Not a safe point. return LivenessInvalid @@ -497,8 +512,7 @@ func newliveness(fn *Node, f *ssa.Func, vars []*Node, idx map[*Node]int32, stkpt stkptrsize: stkptrsize, be: make([]BlockEffects, f.NumBlocks()), - livenessMap: LivenessMap{make(map[*ssa.Value]LivenessIndex)}, - regMapSet: make(map[liveRegMask]int), + regMapSet: make(map[liveRegMask]int), } nblocks := int32(len(f.Blocks)) @@ -515,6 +529,7 @@ func newliveness(fn *Node, f *ssa.Func, vars []*Node, idx map[*Node]int32, stkpt be.avarinitany = bulk.next() be.avarinitall = bulk.next() } + lv.livenessMap.reset(lv.f.NumValues()) lv.markUnsafePoints() return lv @@ -1346,7 +1361,7 @@ func (lv *Liveness) compact(b *ssa.Block) { } for _, v := range b.Values { if lv.issafepoint(v) { - lv.livenessMap.m[v] = add(lv.livevars[pos]) + lv.livenessMap.set(v, add(lv.livevars[pos])) pos++ } } @@ -1656,8 +1671,12 @@ func liveness(e *ssafn, f *ssa.Func) LivenessMap { lv.clobber() if debuglive > 0 { lv.showlive(nil, lv.stackMaps[0]) - for val, idx := range lv.livenessMap.m { - lv.showlive(val, lv.stackMaps[idx.stackMapIndex]) + for _, b := range f.Blocks { + for _, val := range b.Values { + if idx := lv.livenessMap.Get(val); idx.Valid() { + lv.showlive(val, lv.stackMaps[idx.stackMapIndex]) + } + } } } if debuglive >= 2 { -- 2.48.1