| // 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" |
| "internal/trace/v2" |
| tracev2 "internal/trace/v2" |
| "internal/trace/v2/testtrace" |
| "io" |
| "math" |
| "os" |
| "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") |
| } |
| check := func(t *testing.T, mu [][]MutatorUtil) { |
| 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 |
| } |
| } |
| } |
| } |
| t.Run("V1", func(t *testing.T) { |
| data, err := os.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) |
| } |
| check(t, MutatorUtilization(events.Events, UtilSTW|UtilBackground|UtilAssist)) |
| }) |
| t.Run("V2", func(t *testing.T) { |
| testPath := "v2/testdata/tests/go122-gc-stress.test" |
| r, _, err := testtrace.ParseFile(testPath) |
| if err != nil { |
| t.Fatalf("malformed test %s: bad trace file: %v", testPath, err) |
| } |
| var events []tracev2.Event |
| tr, err := trace.NewReader(r) |
| if err != nil { |
| t.Fatalf("malformed test %s: bad trace file: %v", testPath, err) |
| } |
| for { |
| ev, err := tr.ReadEvent() |
| if err == io.EOF { |
| break |
| } |
| if err != nil { |
| t.Fatalf("malformed test %s: bad trace file: %v", testPath, err) |
| } |
| events = append(events, ev) |
| } |
| // Pass the trace through MutatorUtilizationV2 and check it. |
| check(t, MutatorUtilizationV2(events, UtilSTW|UtilBackground|UtilAssist)) |
| }) |
| } |
| |
| func BenchmarkMMU(b *testing.B) { |
| data, err := os.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 |
| } |