gc_test.go

Documentation: internal/trace

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