blob: 4f9c77041a942bee05136190790a34c3b09b58da [file] [log] [blame]
 // Copyright 2017 The Go Authors. All rights reserved. // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. package trace import ( "bytes" "io/ioutil" "math" "testing" "time" ) // aeq returns true if x and y are equal up to 8 digits (1 part in 100 // million). func aeq(x, y float64) bool { if x < 0 && y < 0 { x, y = -x, -y } const digits = 8 factor := 1 - math.Pow(10, -digits+1) return x*factor <= y && y*factor <= x } func TestMMU(t *testing.T) { t.Parallel() // MU // 1.0 ***** ***** ***** // 0.5 * * * * // 0.0 ***** ***** // 0 1 2 3 4 5 util := [][]MutatorUtil{{ {0e9, 1}, {1e9, 0}, {2e9, 1}, {3e9, 0}, {4e9, 1}, {5e9, 0}, }} mmuCurve := NewMMUCurve(util) for _, test := range []struct { window time.Duration want float64 worst []float64 }{ {0, 0, []float64{}}, {time.Millisecond, 0, []float64{0, 0}}, {time.Second, 0, []float64{0, 0}}, {2 * time.Second, 0.5, []float64{0.5, 0.5}}, {3 * time.Second, 1 / 3.0, []float64{1 / 3.0}}, {4 * time.Second, 0.5, []float64{0.5}}, {5 * time.Second, 3 / 5.0, []float64{3 / 5.0}}, {6 * time.Second, 3 / 5.0, []float64{3 / 5.0}}, } { if got := mmuCurve.MMU(test.window); !aeq(test.want, got) { t.Errorf("for %s window, want mu = %f, got %f", test.window, test.want, got) } worst := mmuCurve.Examples(test.window, 2) // Which exact windows are returned is unspecified // (and depends on the exact banding), so we just // check that we got the right number with the right // utilizations. if len(worst) != len(test.worst) { t.Errorf("for %s window, want worst %v, got %v", test.window, test.worst, worst) } else { for i := range worst { if worst[i].MutatorUtil != test.worst[i] { t.Errorf("for %s window, want worst %v, got %v", test.window, test.worst, worst) break } } } } } func TestMMUTrace(t *testing.T) { // Can't be t.Parallel() because it modifies the // testingOneBand package variable. if testing.Short() { // test input too big for all.bash t.Skip("skipping in -short mode") } data, err := ioutil.ReadFile("testdata/stress_1_10_good") if err != nil { t.Fatalf("failed to read input file: %v", err) } _, events, err := parse(bytes.NewReader(data), "") if err != nil { t.Fatalf("failed to parse trace: %s", err) } mu := MutatorUtilization(events.Events, UtilSTW|UtilBackground|UtilAssist) mmuCurve := NewMMUCurve(mu) // Test the optimized implementation against the "obviously // correct" implementation. for window := time.Nanosecond; window < 10*time.Second; window *= 10 { want := mmuSlow(mu[0], window) got := mmuCurve.MMU(window) if !aeq(want, got) { t.Errorf("want %f, got %f mutator utilization in window %s", want, got, window) } } // Test MUD with band optimization against MUD without band // optimization. We don't have a simple testing implementation // of MUDs (the simplest implementation is still quite // complex), but this is still a pretty good test. defer func(old int) { bandsPerSeries = old }(bandsPerSeries) bandsPerSeries = 1 mmuCurve2 := NewMMUCurve(mu) quantiles := []float64{0, 1 - .999, 1 - .99} for window := time.Microsecond; window < time.Second; window *= 10 { mud1 := mmuCurve.MUD(window, quantiles) mud2 := mmuCurve2.MUD(window, quantiles) for i := range mud1 { if !aeq(mud1[i], mud2[i]) { t.Errorf("for quantiles %v at window %v, want %v, got %v", quantiles, window, mud2, mud1) break } } } } func BenchmarkMMU(b *testing.B) { data, err := ioutil.ReadFile("testdata/stress_1_10_good") if err != nil { b.Fatalf("failed to read input file: %v", err) } _, events, err := parse(bytes.NewReader(data), "") if err != nil { b.Fatalf("failed to parse trace: %s", err) } mu := MutatorUtilization(events.Events, UtilSTW|UtilBackground|UtilAssist|UtilSweep) b.ResetTimer() for i := 0; i < b.N; i++ { mmuCurve := NewMMUCurve(mu) xMin, xMax := time.Microsecond, time.Second logMin, logMax := math.Log(float64(xMin)), math.Log(float64(xMax)) const samples = 100 for i := 0; i < samples; i++ { window := time.Duration(math.Exp(float64(i)/(samples-1)*(logMax-logMin) + logMin)) mmuCurve.MMU(window) } } } func mmuSlow(util []MutatorUtil, window time.Duration) (mmu float64) { if max := time.Duration(util[len(util)-1].Time - util[0].Time); window > max { window = max } mmu = 1.0 // muInWindow returns the mean mutator utilization between // util[0].Time and end. muInWindow := func(util []MutatorUtil, end int64) float64 { total := 0.0 var prevU MutatorUtil for _, u := range util { if u.Time > end { total += prevU.Util * float64(end-prevU.Time) break } total += prevU.Util * float64(u.Time-prevU.Time) prevU = u } return total / float64(end-util[0].Time) } update := func() { for i, u := range util { if u.Time+int64(window) > util[len(util)-1].Time { break } mmu = math.Min(mmu, muInWindow(util[i:], u.Time+int64(window))) } } // Consider all left-aligned windows. update() // Reverse the trace. Slightly subtle because each MutatorUtil // is a *change*. rutil := make([]MutatorUtil, len(util)) if util[len(util)-1].Util != 0 { panic("irreversible trace") } for i, u := range util { util1 := 0.0 if i != 0 { util1 = util[i-1].Util } rutil[len(rutil)-i-1] = MutatorUtil{Time: -u.Time, Util: util1} } util = rutil // Consider all right-aligned windows. update() return }