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_test
     6  
     7  import (
     8  	"internal/trace"
     9  	"internal/trace/testtrace"
    10  	"io"
    11  	"math"
    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 := [][]trace.MutatorUtil{{
    36  		{0e9, 1},
    37  		{1e9, 0},
    38  		{2e9, 1},
    39  		{3e9, 0},
    40  		{4e9, 1},
    41  		{5e9, 0},
    42  	}}
    43  	mmuCurve := trace.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 [][]trace.MutatorUtil) {
    88  		mmuCurve := trace.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) { trace.BandsPerSeries = old }(trace.BandsPerSeries)
   105  		trace.BandsPerSeries = 1
   106  		mmuCurve2 := trace.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("V2", func(t *testing.T) {
   120  		testPath := "testdata/tests/go122-gc-stress.test"
   121  		r, _, err := testtrace.ParseFile(testPath)
   122  		if err != nil {
   123  			t.Fatalf("malformed test %s: bad trace file: %v", testPath, err)
   124  		}
   125  		var events []trace.Event
   126  		tr, err := trace.NewReader(r)
   127  		if err != nil {
   128  			t.Fatalf("malformed test %s: bad trace file: %v", testPath, err)
   129  		}
   130  		for {
   131  			ev, err := tr.ReadEvent()
   132  			if err == io.EOF {
   133  				break
   134  			}
   135  			if err != nil {
   136  				t.Fatalf("malformed test %s: bad trace file: %v", testPath, err)
   137  			}
   138  			events = append(events, ev)
   139  		}
   140  		// Pass the trace through MutatorUtilizationV2 and check it.
   141  		check(t, trace.MutatorUtilizationV2(events, trace.UtilSTW|trace.UtilBackground|trace.UtilAssist))
   142  	})
   143  }
   144  
   145  func mmuSlow(util []trace.MutatorUtil, window time.Duration) (mmu float64) {
   146  	if max := time.Duration(util[len(util)-1].Time - util[0].Time); window > max {
   147  		window = max
   148  	}
   149  
   150  	mmu = 1.0
   151  
   152  	// muInWindow returns the mean mutator utilization between
   153  	// util[0].Time and end.
   154  	muInWindow := func(util []trace.MutatorUtil, end int64) float64 {
   155  		total := 0.0
   156  		var prevU trace.MutatorUtil
   157  		for _, u := range util {
   158  			if u.Time > end {
   159  				total += prevU.Util * float64(end-prevU.Time)
   160  				break
   161  			}
   162  			total += prevU.Util * float64(u.Time-prevU.Time)
   163  			prevU = u
   164  		}
   165  		return total / float64(end-util[0].Time)
   166  	}
   167  	update := func() {
   168  		for i, u := range util {
   169  			if u.Time+int64(window) > util[len(util)-1].Time {
   170  				break
   171  			}
   172  			mmu = math.Min(mmu, muInWindow(util[i:], u.Time+int64(window)))
   173  		}
   174  	}
   175  
   176  	// Consider all left-aligned windows.
   177  	update()
   178  	// Reverse the trace. Slightly subtle because each MutatorUtil
   179  	// is a *change*.
   180  	rutil := make([]trace.MutatorUtil, len(util))
   181  	if util[len(util)-1].Util != 0 {
   182  		panic("irreversible trace")
   183  	}
   184  	for i, u := range util {
   185  		util1 := 0.0
   186  		if i != 0 {
   187  			util1 = util[i-1].Util
   188  		}
   189  		rutil[len(rutil)-i-1] = trace.MutatorUtil{Time: -u.Time, Util: util1}
   190  	}
   191  	util = rutil
   192  	// Consider all right-aligned windows.
   193  	update()
   194  	return
   195  }
   196
View as plain text