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