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