mud_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  	"math"
     9  	"math/rand"
    10  	"testing"
    11  )
    12  
    13  func TestMUD(t *testing.T) {
    14  	// Insert random uniforms and check histogram mass and
    15  	// cumulative sum approximations.
    16  	rnd := rand.New(rand.NewSource(42))
    17  	mass := 0.0
    18  	var mud mud
    19  	for i := 0; i < 100; i++ {
    20  		area, l, r := rnd.Float64(), rnd.Float64(), rnd.Float64()
    21  		if rnd.Intn(10) == 0 {
    22  			r = l
    23  		}
    24  		t.Log(l, r, area)
    25  		mud.add(l, r, area)
    26  		mass += area
    27  
    28  		// Check total histogram weight.
    29  		hmass := 0.0
    30  		for _, val := range mud.hist {
    31  			hmass += val
    32  		}
    33  		if !aeq(mass, hmass) {
    34  			t.Fatalf("want mass %g, got %g", mass, hmass)
    35  		}
    36  
    37  		// Check inverse cumulative sum approximations.
    38  		for j := 0.0; j < mass; j += mass * 0.099 {
    39  			mud.setTrackMass(j)
    40  			l, u, ok := mud.approxInvCumulativeSum()
    41  			inv, ok2 := mud.invCumulativeSum(j)
    42  			if !ok || !ok2 {
    43  				t.Fatalf("inverse cumulative sum failed: approx %v, exact %v", ok, ok2)
    44  			}
    45  			if !(l <= inv && inv < u) {
    46  				t.Fatalf("inverse(%g) = %g, not ∈ [%g, %g)", j, inv, l, u)
    47  			}
    48  		}
    49  	}
    50  }
    51  
    52  func TestMUDTracking(t *testing.T) {
    53  	// Test that the tracked mass is tracked correctly across
    54  	// updates.
    55  	rnd := rand.New(rand.NewSource(42))
    56  	const uniforms = 100
    57  	for trackMass := 0.0; trackMass < uniforms; trackMass += uniforms / 50 {
    58  		var mud mud
    59  		mass := 0.0
    60  		mud.setTrackMass(trackMass)
    61  		for i := 0; i < uniforms; i++ {
    62  			area, l, r := rnd.Float64(), rnd.Float64(), rnd.Float64()
    63  			mud.add(l, r, area)
    64  			mass += area
    65  			l, u, ok := mud.approxInvCumulativeSum()
    66  			inv, ok2 := mud.invCumulativeSum(trackMass)
    67  
    68  			if mass < trackMass {
    69  				if ok {
    70  					t.Errorf("approx(%g) = [%g, %g), but mass = %g", trackMass, l, u, mass)
    71  				}
    72  				if ok2 {
    73  					t.Errorf("exact(%g) = %g, but mass = %g", trackMass, inv, mass)
    74  				}
    75  			} else {
    76  				if !ok {
    77  					t.Errorf("approx(%g) failed, but mass = %g", trackMass, mass)
    78  				}
    79  				if !ok2 {
    80  					t.Errorf("exact(%g) failed, but mass = %g", trackMass, mass)
    81  				}
    82  				if ok && ok2 && !(l <= inv && inv < u) {
    83  					t.Errorf("inverse(%g) = %g, not ∈ [%g, %g)", trackMass, inv, l, u)
    84  				}
    85  			}
    86  		}
    87  	}
    88  }
    89  
    90  // aeq returns true if x and y are equal up to 8 digits (1 part in 100
    91  // million).
    92  // TODO(amedee) dup of gc_test.go
    93  func aeq(x, y float64) bool {
    94  	if x < 0 && y < 0 {
    95  		x, y = -x, -y
    96  	}
    97  	const digits = 8
    98  	factor := 1 - math.Pow(10, -digits+1)
    99  	return x*factor <= y && y*factor <= x
   100  }
   101
View as plain text