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         "io/ioutil"
  10         "math"
  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
  83         data, err := ioutil.ReadFile("testdata/stress_1_10_good")
  84         if err != nil {
  85                 t.Fatalf("failed to read input file: %v", err)
  86         }
  87         _, events, err := parse(bytes.NewReader(data), "")
  88         if err != nil {
  89                 t.Fatalf("failed to parse trace: %s", err)
  90         }
  91         mu := MutatorUtilization(events.Events, UtilSTW|UtilBackground|UtilAssist)
  92         mmuCurve := NewMMUCurve(mu)
  93
  94         // Test the optimized implementation against the "obviously
  95         // correct" implementation.
  96         for window := time.Nanosecond; window < 10*time.Second; window *= 10 {
  97                 want := mmuSlow(mu[0], window)
  98                 got := mmuCurve.MMU(window)
  99                 if !aeq(want, got) {
 100                         t.Errorf("want %f, got %f mutator utilization in window %s", want, got, window)
 101                 }
 102         }
 103
 104         // Test MUD with band optimization against MUD without band
 105         // optimization. We don't have a simple testing implementation
 106         // of MUDs (the simplest implementation is still quite
 107         // complex), but this is still a pretty good test.
 108         defer func(old int) { bandsPerSeries = old }(bandsPerSeries)
 109         bandsPerSeries = 1
 110         mmuCurve2 := NewMMUCurve(mu)
 111         quantiles := []float64{0, 1 - .999, 1 - .99}
 112         for window := time.Microsecond; window < time.Second; window *= 10 {
 113                 mud1 := mmuCurve.MUD(window, quantiles)
 114                 mud2 := mmuCurve2.MUD(window, quantiles)
 115                 for i := range mud1 {
 116                         if !aeq(mud1[i], mud2[i]) {
 117                                 t.Errorf("for quantiles %v at window %v, want %v, got %v", quantiles, window, mud2, mud1)
 118                                 break
 119                         }
 120                 }
 121         }
 122 }
 123
 124 func BenchmarkMMU(b *testing.B) {
 125         data, err := ioutil.ReadFile("testdata/stress_1_10_good")
 126         if err != nil {
 127                 b.Fatalf("failed to read input file: %v", err)
 128         }
 129         _, events, err := parse(bytes.NewReader(data), "")
 130         if err != nil {
 131                 b.Fatalf("failed to parse trace: %s", err)
 132         }
 133         mu := MutatorUtilization(events.Events, UtilSTW|UtilBackground|UtilAssist|UtilSweep)
 134         b.ResetTimer()
 135
 136         for i := 0; i < b.N; i++ {
 137                 mmuCurve := NewMMUCurve(mu)
 138                 xMin, xMax := time.Microsecond, time.Second
 139                 logMin, logMax := math.Log(float64(xMin)), math.Log(float64(xMax))
 140                 const samples = 100
 141                 for i := 0; i < samples; i++ {
 142                         window := time.Duration(math.Exp(float64(i)/(samples-1)*(logMax-logMin) + logMin))
 143                         mmuCurve.MMU(window)
 144                 }
 145         }
 146 }
 147
 148 func mmuSlow(util []MutatorUtil, window time.Duration) (mmu float64) {
 149         if max := time.Duration(util[len(util)-1].Time - util[0].Time); window > max {
 150                 window = max
 151         }
 152
 153         mmu = 1.0
 154
 155         // muInWindow returns the mean mutator utilization between
 156         // util[0].Time and end.
 157         muInWindow := func(util []MutatorUtil, end int64) float64 {
 158                 total := 0.0
 159                 var prevU MutatorUtil
 160                 for _, u := range util {
 161                         if u.Time > end {
 162                                 total += prevU.Util * float64(end-prevU.Time)
 163                                 break
 164                         }
 165                         total += prevU.Util * float64(u.Time-prevU.Time)
 166                         prevU = u
 167                 }
 168                 return total / float64(end-util[0].Time)
 169         }
 170         update := func() {
 171                 for i, u := range util {
 172                         if u.Time+int64(window) > util[len(util)-1].Time {
 173                                 break
 174                         }
 175                         mmu = math.Min(mmu, muInWindow(util[i:], u.Time+int64(window)))
 176                 }
 177         }
 178
 179         // Consider all left-aligned windows.
 180         update()
 181         // Reverse the trace. Slightly subtle because each MutatorUtil
 182         // is a *change*.
 183         rutil := make([]MutatorUtil, len(util))
 184         if util[len(util)-1].Util != 0 {
 185                 panic("irreversible trace")
 186         }
 187         for i, u := range util {
 188                 util1 := 0.0
 189                 if i != 0 {
 190                         util1 = util[i-1].Util
 191                 }
 192                 rutil[len(rutil)-i-1] = MutatorUtil{Time: -u.Time, Util: util1}
 193         }
 194         util = rutil
 195         // Consider all right-aligned windows.
 196         update()
 197         return
 198 }