src/internal/trace/gc_test.go

   1 // Copyright 2017 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 package trace
   6
   7 import (
   8         "bytes"
   9         "internal/trace/v2/testtrace"
  10         "math"
  11         "os"
  12         "testing"
  13         "time"
  14 )
  15
  16 // aeq returns true if x and y are equal up to 8 digits (1 part in 100
  17 // million).
  18 func aeq(x, y float64) bool {
  19         if x < 0 && y < 0 {
  20                 x, y = -x, -y
  21         }
  22         const digits = 8
  23         factor := 1 - math.Pow(10, -digits+1)
  24         return x*factor <= y && y*factor <= x
  25 }
  26
  27 func TestMMU(t *testing.T) {
  28         t.Parallel()
  29
  30         // MU
  31         // 1.0  *****   *****   *****
  32         // 0.5      *   *   *   *
  33         // 0.0      *****   *****
  34         //      0   1   2   3   4   5
  35         util := [][]MutatorUtil{{
  36                 {0e9, 1},
  37                 {1e9, 0},
  38                 {2e9, 1},
  39                 {3e9, 0},
  40                 {4e9, 1},
  41                 {5e9, 0},
  42         }}
  43         mmuCurve := NewMMUCurve(util)
  44
  45         for _, test := range []struct {
  46                 window time.Duration
  47                 want   float64
  48                 worst  []float64
  49         }{
  50                 {0, 0, []float64{}},
  51                 {time.Millisecond, 0, []float64{0, 0}},
  52                 {time.Second, 0, []float64{0, 0}},
  53                 {2 * time.Second, 0.5, []float64{0.5, 0.5}},
  54                 {3 * time.Second, 1 / 3.0, []float64{1 / 3.0}},
  55                 {4 * time.Second, 0.5, []float64{0.5}},
  56                 {5 * time.Second, 3 / 5.0, []float64{3 / 5.0}},
  57                 {6 * time.Second, 3 / 5.0, []float64{3 / 5.0}},
  58         } {
  59                 if got := mmuCurve.MMU(test.window); !aeq(test.want, got) {
  60                         t.Errorf("for %s window, want mu = %f, got %f", test.window, test.want, got)
  61                 }
  62                 worst := mmuCurve.Examples(test.window, 2)
  63                 // Which exact windows are returned is unspecified
  64                 // (and depends on the exact banding), so we just
  65                 // check that we got the right number with the right
  66                 // utilizations.
  67                 if len(worst) != len(test.worst) {
  68                         t.Errorf("for %s window, want worst %v, got %v", test.window, test.worst, worst)
  69                 } else {
  70                         for i := range worst {
  71                                 if worst[i].MutatorUtil != test.worst[i] {
  72                                         t.Errorf("for %s window, want worst %v, got %v", test.window, test.worst, worst)
  73                                         break
  74                                 }
  75                         }
  76                 }
  77         }
  78 }
  79
  80 func TestMMUTrace(t *testing.T) {
  81         // Can't be t.Parallel() because it modifies the
  82         // testingOneBand package variable.
  83         if testing.Short() {
  84                 // test input too big for all.bash
  85                 t.Skip("skipping in -short mode")
  86         }
  87         check := func(t *testing.T, mu [][]MutatorUtil) {
  88                 mmuCurve := NewMMUCurve(mu)
  89
  90                 // Test the optimized implementation against the "obviously
  91                 // correct" implementation.
  92                 for window := time.Nanosecond; window < 10*time.Second; window *= 10 {
  93                         want := mmuSlow(mu[0], window)
  94                         got := mmuCurve.MMU(window)
  95                         if !aeq(want, got) {
  96                                 t.Errorf("want %f, got %f mutator utilization in window %s", want, got, window)
  97                         }
  98                 }
  99
 100                 // Test MUD with band optimization against MUD without band
 101                 // optimization. We don't have a simple testing implementation
 102                 // of MUDs (the simplest implementation is still quite
 103                 // complex), but this is still a pretty good test.
 104                 defer func(old int) { bandsPerSeries = old }(bandsPerSeries)
 105                 bandsPerSeries = 1
 106                 mmuCurve2 := NewMMUCurve(mu)
 107                 quantiles := []float64{0, 1 - .999, 1 - .99}
 108                 for window := time.Microsecond; window < time.Second; window *= 10 {
 109                         mud1 := mmuCurve.MUD(window, quantiles)
 110                         mud2 := mmuCurve2.MUD(window, quantiles)
 111                         for i := range mud1 {
 112                                 if !aeq(mud1[i], mud2[i]) {
 113                                         t.Errorf("for quantiles %v at window %v, want %v, got %v", quantiles, window, mud2, mud1)
 114                                         break
 115                                 }
 116                         }
 117                 }
 118         }
 119         t.Run("V1", func(t *testing.T) {
 120                 data, err := os.ReadFile("testdata/stress_1_10_good")
 121                 if err != nil {
 122                         t.Fatalf("failed to read input file: %v", err)
 123                 }
 124                 events, err := Parse(bytes.NewReader(data), "")
 125                 if err != nil {
 126                         t.Fatalf("failed to parse trace: %s", err)
 127                 }
 128                 check(t, MutatorUtilization(events.Events, UtilSTW|UtilBackground|UtilAssist))
 129         })
 130         t.Run("V2", func(t *testing.T) {
 131                 testPath := "v2/testdata/tests/go122-gc-stress.test"
 132                 r, _, err := testtrace.ParseFile(testPath)
 133                 if err != nil {
 134                         t.Fatalf("malformed test %s: bad trace file: %v", testPath, err)
 135                 }
 136                 // Pass the trace through MutatorUtilizationV2.
 137                 mu, err := MutatorUtilizationV2(r, UtilSTW|UtilBackground|UtilAssist)
 138                 if err != nil {
 139                         t.Fatalf("failed to compute mutator utilization or parse trace: %v", err)
 140                 }
 141                 check(t, mu)
 142         })
 143 }
 144
 145 func BenchmarkMMU(b *testing.B) {
 146         data, err := os.ReadFile("testdata/stress_1_10_good")
 147         if err != nil {
 148                 b.Fatalf("failed to read input file: %v", err)
 149         }
 150         events, err := Parse(bytes.NewReader(data), "")
 151         if err != nil {
 152                 b.Fatalf("failed to parse trace: %s", err)
 153         }
 154         mu := MutatorUtilization(events.Events, UtilSTW|UtilBackground|UtilAssist|UtilSweep)
 155         b.ResetTimer()
 156
 157         for i := 0; i < b.N; i++ {
 158                 mmuCurve := NewMMUCurve(mu)
 159                 xMin, xMax := time.Microsecond, time.Second
 160                 logMin, logMax := math.Log(float64(xMin)), math.Log(float64(xMax))
 161                 const samples = 100
 162                 for i := 0; i < samples; i++ {
 163                         window := time.Duration(math.Exp(float64(i)/(samples-1)*(logMax-logMin) + logMin))
 164                         mmuCurve.MMU(window)
 165                 }
 166         }
 167 }
 168
 169 func mmuSlow(util []MutatorUtil, window time.Duration) (mmu float64) {
 170         if max := time.Duration(util[len(util)-1].Time - util[0].Time); window > max {
 171                 window = max
 172         }
 173
 174         mmu = 1.0
 175
 176         // muInWindow returns the mean mutator utilization between
 177         // util[0].Time and end.
 178         muInWindow := func(util []MutatorUtil, end int64) float64 {
 179                 total := 0.0
 180                 var prevU MutatorUtil
 181                 for _, u := range util {
 182                         if u.Time > end {
 183                                 total += prevU.Util * float64(end-prevU.Time)
 184                                 break
 185                         }
 186                         total += prevU.Util * float64(u.Time-prevU.Time)
 187                         prevU = u
 188                 }
 189                 return total / float64(end-util[0].Time)
 190         }
 191         update := func() {
 192                 for i, u := range util {
 193                         if u.Time+int64(window) > util[len(util)-1].Time {
 194                                 break
 195                         }
 196                         mmu = math.Min(mmu, muInWindow(util[i:], u.Time+int64(window)))
 197                 }
 198         }
 199
 200         // Consider all left-aligned windows.
 201         update()
 202         // Reverse the trace. Slightly subtle because each MutatorUtil
 203         // is a *change*.
 204         rutil := make([]MutatorUtil, len(util))
 205         if util[len(util)-1].Util != 0 {
 206                 panic("irreversible trace")
 207         }
 208         for i, u := range util {
 209                 util1 := 0.0
 210                 if i != 0 {
 211                         util1 = util[i-1].Util
 212                 }
 213                 rutil[len(rutil)-i-1] = MutatorUtil{Time: -u.Time, Util: util1}
 214         }
 215         util = rutil
 216         // Consider all right-aligned windows.
 217         update()
 218         return
 219 }