Source file src/go.mongodb.org/mongo-driver/internal/rand/rand_test.go

Documentation: go.mongodb.org/mongo-driver/internal/rand

     1  // Copied from https://cs.opensource.google/go/x/exp/+/24438e51023af3bfc1db8aed43c1342817e8cfcd:rand/rand_test.go
     2  
     3  // Copyright 2009 The Go Authors. All rights reserved.
     4  // Use of this source code is governed by a BSD-style
     5  // license that can be found in the LICENSE file.
     6  
     7  package rand
     8  
     9  import (
    10  	"bytes"
    11  	"errors"
    12  	"fmt"
    13  	"io"
    14  	"math"
    15  	"os"
    16  	"runtime"
    17  	"testing"
    18  	"testing/iotest"
    19  	"time"
    20  )
    21  
    22  const (
    23  	numTestSamples = 10000
    24  )
    25  
    26  type statsResults struct {
    27  	mean        float64
    28  	stddev      float64
    29  	closeEnough float64
    30  	maxError    float64
    31  }
    32  
    33  func max(a, b float64) float64 {
    34  	if a > b {
    35  		return a
    36  	}
    37  	return b
    38  }
    39  
    40  func nearEqual(a, b, closeEnough, maxError float64) bool {
    41  	absDiff := math.Abs(a - b)
    42  	if absDiff < closeEnough { // Necessary when one value is zero and one value is close to zero.
    43  		return true
    44  	}
    45  	return absDiff/max(math.Abs(a), math.Abs(b)) < maxError
    46  }
    47  
    48  var testSeeds = []uint64{1, 1754801282, 1698661970, 1550503961}
    49  
    50  // checkSimilarDistribution returns success if the mean and stddev of the
    51  // two statsResults are similar.
    52  func (this *statsResults) checkSimilarDistribution(expected *statsResults) error {
    53  	if !nearEqual(this.mean, expected.mean, expected.closeEnough, expected.maxError) {
    54  		s := fmt.Sprintf("mean %v != %v (allowed error %v, %v)", this.mean, expected.mean, expected.closeEnough, expected.maxError)
    55  		fmt.Println(s)
    56  		return errors.New(s)
    57  	}
    58  	if !nearEqual(this.stddev, expected.stddev, 0, expected.maxError) {
    59  		s := fmt.Sprintf("stddev %v != %v (allowed error %v, %v)", this.stddev, expected.stddev, expected.closeEnough, expected.maxError)
    60  		fmt.Println(s)
    61  		return errors.New(s)
    62  	}
    63  	return nil
    64  }
    65  
    66  func getStatsResults(samples []float64) *statsResults {
    67  	res := new(statsResults)
    68  	var sum, squaresum float64
    69  	for _, s := range samples {
    70  		sum += s
    71  		squaresum += s * s
    72  	}
    73  	res.mean = sum / float64(len(samples))
    74  	res.stddev = math.Sqrt(squaresum/float64(len(samples)) - res.mean*res.mean)
    75  	return res
    76  }
    77  
    78  func checkSampleDistribution(t *testing.T, samples []float64, expected *statsResults) {
    79  	t.Helper()
    80  	actual := getStatsResults(samples)
    81  	err := actual.checkSimilarDistribution(expected)
    82  	if err != nil {
    83  		t.Errorf(err.Error())
    84  	}
    85  }
    86  
    87  func checkSampleSliceDistributions(t *testing.T, samples []float64, nslices int, expected *statsResults) {
    88  	t.Helper()
    89  	chunk := len(samples) / nslices
    90  	for i := 0; i < nslices; i++ {
    91  		low := i * chunk
    92  		var high int
    93  		if i == nslices-1 {
    94  			high = len(samples) - 1
    95  		} else {
    96  			high = (i + 1) * chunk
    97  		}
    98  		checkSampleDistribution(t, samples[low:high], expected)
    99  	}
   100  }
   101  
   102  //
   103  // Normal distribution tests
   104  //
   105  
   106  func generateNormalSamples(nsamples int, mean, stddev float64, seed uint64) []float64 {
   107  	r := New(NewSource(seed))
   108  	samples := make([]float64, nsamples)
   109  	for i := range samples {
   110  		samples[i] = r.NormFloat64()*stddev + mean
   111  	}
   112  	return samples
   113  }
   114  
   115  func testNormalDistribution(t *testing.T, nsamples int, mean, stddev float64, seed uint64) {
   116  	//fmt.Printf("testing nsamples=%v mean=%v stddev=%v seed=%v\n", nsamples, mean, stddev, seed);
   117  
   118  	samples := generateNormalSamples(nsamples, mean, stddev, seed)
   119  	errorScale := max(1.0, stddev) // Error scales with stddev
   120  	expected := &statsResults{mean, stddev, 0.10 * errorScale, 0.08 * errorScale}
   121  
   122  	// Make sure that the entire set matches the expected distribution.
   123  	checkSampleDistribution(t, samples, expected)
   124  
   125  	// Make sure that each half of the set matches the expected distribution.
   126  	checkSampleSliceDistributions(t, samples, 2, expected)
   127  
   128  	// Make sure that each 7th of the set matches the expected distribution.
   129  	checkSampleSliceDistributions(t, samples, 7, expected)
   130  }
   131  
   132  // Actual tests
   133  
   134  func TestStandardNormalValues(t *testing.T) {
   135  	for _, seed := range testSeeds {
   136  		testNormalDistribution(t, numTestSamples, 0, 1, seed)
   137  	}
   138  }
   139  
   140  func TestNonStandardNormalValues(t *testing.T) {
   141  	sdmax := 1000.0
   142  	mmax := 1000.0
   143  	if testing.Short() {
   144  		sdmax = 5
   145  		mmax = 5
   146  	}
   147  	for sd := 0.5; sd < sdmax; sd *= 2 {
   148  		for m := 0.5; m < mmax; m *= 2 {
   149  			for _, seed := range testSeeds {
   150  				testNormalDistribution(t, numTestSamples, m, sd, seed)
   151  				if testing.Short() {
   152  					break
   153  				}
   154  			}
   155  		}
   156  	}
   157  }
   158  
   159  //
   160  // Exponential distribution tests
   161  //
   162  
   163  func generateExponentialSamples(nsamples int, rate float64, seed uint64) []float64 {
   164  	r := New(NewSource(seed))
   165  	samples := make([]float64, nsamples)
   166  	for i := range samples {
   167  		samples[i] = r.ExpFloat64() / rate
   168  	}
   169  	return samples
   170  }
   171  
   172  func testExponentialDistribution(t *testing.T, nsamples int, rate float64, seed uint64) {
   173  	//fmt.Printf("testing nsamples=%v rate=%v seed=%v\n", nsamples, rate, seed)
   174  
   175  	mean := 1 / rate
   176  	stddev := mean
   177  
   178  	samples := generateExponentialSamples(nsamples, rate, seed)
   179  	errorScale := max(1.0, 1/rate) // Error scales with the inverse of the rate
   180  	expected := &statsResults{mean, stddev, 0.10 * errorScale, 0.20 * errorScale}
   181  
   182  	// Make sure that the entire set matches the expected distribution.
   183  	checkSampleDistribution(t, samples, expected)
   184  
   185  	// Make sure that each half of the set matches the expected distribution.
   186  	checkSampleSliceDistributions(t, samples, 2, expected)
   187  
   188  	// Make sure that each 7th of the set matches the expected distribution.
   189  	checkSampleSliceDistributions(t, samples, 7, expected)
   190  }
   191  
   192  // Actual tests
   193  
   194  func TestStandardExponentialValues(t *testing.T) {
   195  	for _, seed := range testSeeds {
   196  		testExponentialDistribution(t, numTestSamples, 1, seed)
   197  	}
   198  }
   199  
   200  func TestNonStandardExponentialValues(t *testing.T) {
   201  	for rate := 0.05; rate < 10; rate *= 2 {
   202  		for _, seed := range testSeeds {
   203  			testExponentialDistribution(t, numTestSamples, rate, seed)
   204  			if testing.Short() {
   205  				break
   206  			}
   207  		}
   208  	}
   209  }
   210  
   211  //
   212  // Table generation tests
   213  //
   214  
   215  func initNorm() (testKn []uint32, testWn, testFn []float32) {
   216  	const m1 = 1 << 31
   217  	var (
   218  		dn float64 = rn
   219  		tn         = dn
   220  		vn float64 = 9.91256303526217e-3
   221  	)
   222  
   223  	testKn = make([]uint32, 128)
   224  	testWn = make([]float32, 128)
   225  	testFn = make([]float32, 128)
   226  
   227  	q := vn / math.Exp(-0.5*dn*dn)
   228  	testKn[0] = uint32((dn / q) * m1)
   229  	testKn[1] = 0
   230  	testWn[0] = float32(q / m1)
   231  	testWn[127] = float32(dn / m1)
   232  	testFn[0] = 1.0
   233  	testFn[127] = float32(math.Exp(-0.5 * dn * dn))
   234  	for i := 126; i >= 1; i-- {
   235  		dn = math.Sqrt(-2.0 * math.Log(vn/dn+math.Exp(-0.5*dn*dn)))
   236  		testKn[i+1] = uint32((dn / tn) * m1)
   237  		tn = dn
   238  		testFn[i] = float32(math.Exp(-0.5 * dn * dn))
   239  		testWn[i] = float32(dn / m1)
   240  	}
   241  	return
   242  }
   243  
   244  func initExp() (testKe []uint32, testWe, testFe []float32) {
   245  	const m2 = 1 << 32
   246  	var (
   247  		de float64 = re
   248  		te         = de
   249  		ve float64 = 3.9496598225815571993e-3
   250  	)
   251  
   252  	testKe = make([]uint32, 256)
   253  	testWe = make([]float32, 256)
   254  	testFe = make([]float32, 256)
   255  
   256  	q := ve / math.Exp(-de)
   257  	testKe[0] = uint32((de / q) * m2)
   258  	testKe[1] = 0
   259  	testWe[0] = float32(q / m2)
   260  	testWe[255] = float32(de / m2)
   261  	testFe[0] = 1.0
   262  	testFe[255] = float32(math.Exp(-de))
   263  	for i := 254; i >= 1; i-- {
   264  		de = -math.Log(ve/de + math.Exp(-de))
   265  		testKe[i+1] = uint32((de / te) * m2)
   266  		te = de
   267  		testFe[i] = float32(math.Exp(-de))
   268  		testWe[i] = float32(de / m2)
   269  	}
   270  	return
   271  }
   272  
   273  // compareUint32Slices returns the first index where the two slices
   274  // disagree, or <0 if the lengths are the same and all elements
   275  // are identical.
   276  func compareUint32Slices(s1, s2 []uint32) int {
   277  	if len(s1) != len(s2) {
   278  		if len(s1) > len(s2) {
   279  			return len(s2) + 1
   280  		}
   281  		return len(s1) + 1
   282  	}
   283  	for i := range s1 {
   284  		if s1[i] != s2[i] {
   285  			return i
   286  		}
   287  	}
   288  	return -1
   289  }
   290  
   291  // compareFloat32Slices returns the first index where the two slices
   292  // disagree, or <0 if the lengths are the same and all elements
   293  // are identical.
   294  func compareFloat32Slices(s1, s2 []float32) int {
   295  	if len(s1) != len(s2) {
   296  		if len(s1) > len(s2) {
   297  			return len(s2) + 1
   298  		}
   299  		return len(s1) + 1
   300  	}
   301  	for i := range s1 {
   302  		if !nearEqual(float64(s1[i]), float64(s2[i]), 0, 1e-7) {
   303  			return i
   304  		}
   305  	}
   306  	return -1
   307  }
   308  
   309  func TestNormTables(t *testing.T) {
   310  	testKn, testWn, testFn := initNorm()
   311  	if i := compareUint32Slices(kn[0:], testKn); i >= 0 {
   312  		t.Errorf("kn disagrees at index %v; %v != %v", i, kn[i], testKn[i])
   313  	}
   314  	if i := compareFloat32Slices(wn[0:], testWn); i >= 0 {
   315  		t.Errorf("wn disagrees at index %v; %v != %v", i, wn[i], testWn[i])
   316  	}
   317  	if i := compareFloat32Slices(fn[0:], testFn); i >= 0 {
   318  		t.Errorf("fn disagrees at index %v; %v != %v", i, fn[i], testFn[i])
   319  	}
   320  }
   321  
   322  func TestExpTables(t *testing.T) {
   323  	testKe, testWe, testFe := initExp()
   324  	if i := compareUint32Slices(ke[0:], testKe); i >= 0 {
   325  		t.Errorf("ke disagrees at index %v; %v != %v", i, ke[i], testKe[i])
   326  	}
   327  	if i := compareFloat32Slices(we[0:], testWe); i >= 0 {
   328  		t.Errorf("we disagrees at index %v; %v != %v", i, we[i], testWe[i])
   329  	}
   330  	if i := compareFloat32Slices(fe[0:], testFe); i >= 0 {
   331  		t.Errorf("fe disagrees at index %v; %v != %v", i, fe[i], testFe[i])
   332  	}
   333  }
   334  
   335  func hasSlowFloatingPoint() bool {
   336  	switch runtime.GOARCH {
   337  	case "arm":
   338  		return os.Getenv("GOARM") == "5"
   339  	case "mips", "mipsle", "mips64", "mips64le":
   340  		// Be conservative and assume that all mips boards
   341  		// have emulated floating point.
   342  		// TODO: detect what it actually has.
   343  		return true
   344  	}
   345  	return false
   346  }
   347  
   348  func TestFloat32(t *testing.T) {
   349  	// For issue 6721, the problem came after 7533753 calls, so check 10e6.
   350  	num := int(10e6)
   351  	// But do the full amount only on builders (not locally).
   352  	// But ARM5 floating point emulation is slow (Issue 10749), so
   353  	// do less for that builder:
   354  	if testing.Short() && hasSlowFloatingPoint() { // TODO: (testenv.Builder() == "" || hasSlowFloatingPoint())
   355  		num /= 100 // 1.72 seconds instead of 172 seconds
   356  	}
   357  
   358  	r := New(NewSource(1))
   359  	for ct := 0; ct < num; ct++ {
   360  		f := r.Float32()
   361  		if f >= 1 {
   362  			t.Fatal("Float32() should be in range [0,1). ct:", ct, "f:", f)
   363  		}
   364  	}
   365  }
   366  
   367  func testReadUniformity(t *testing.T, n int, seed uint64) {
   368  	r := New(NewSource(seed))
   369  	buf := make([]byte, n)
   370  	nRead, err := r.Read(buf)
   371  	if err != nil {
   372  		t.Errorf("Read err %v", err)
   373  	}
   374  	if nRead != n {
   375  		t.Errorf("Read returned unexpected n; %d != %d", nRead, n)
   376  	}
   377  
   378  	// Expect a uniform distribution of byte values, which lie in [0, 255].
   379  	var (
   380  		mean       = 255.0 / 2
   381  		stddev     = 256.0 / math.Sqrt(12.0)
   382  		errorScale = stddev / math.Sqrt(float64(n))
   383  	)
   384  
   385  	expected := &statsResults{mean, stddev, 0.10 * errorScale, 0.08 * errorScale}
   386  
   387  	// Cast bytes as floats to use the common distribution-validity checks.
   388  	samples := make([]float64, n)
   389  	for i, val := range buf {
   390  		samples[i] = float64(val)
   391  	}
   392  	// Make sure that the entire set matches the expected distribution.
   393  	checkSampleDistribution(t, samples, expected)
   394  }
   395  
   396  func TestReadUniformity(t *testing.T) {
   397  	testBufferSizes := []int{
   398  		2, 4, 7, 64, 1024, 1 << 16, 1 << 20,
   399  	}
   400  	for _, seed := range testSeeds {
   401  		for _, n := range testBufferSizes {
   402  			testReadUniformity(t, n, seed)
   403  		}
   404  	}
   405  }
   406  
   407  func TestReadEmpty(t *testing.T) {
   408  	r := New(NewSource(1))
   409  	buf := make([]byte, 0)
   410  	n, err := r.Read(buf)
   411  	if err != nil {
   412  		t.Errorf("Read err into empty buffer; %v", err)
   413  	}
   414  	if n != 0 {
   415  		t.Errorf("Read into empty buffer returned unexpected n of %d", n)
   416  	}
   417  }
   418  
   419  func TestReadByOneByte(t *testing.T) {
   420  	r := New(NewSource(1))
   421  	b1 := make([]byte, 100)
   422  	_, err := io.ReadFull(iotest.OneByteReader(r), b1)
   423  	if err != nil {
   424  		t.Errorf("read by one byte: %v", err)
   425  	}
   426  	r = New(NewSource(1))
   427  	b2 := make([]byte, 100)
   428  	_, err = r.Read(b2)
   429  	if err != nil {
   430  		t.Errorf("read: %v", err)
   431  	}
   432  	if !bytes.Equal(b1, b2) {
   433  		t.Errorf("read by one byte vs single read:\n%x\n%x", b1, b2)
   434  	}
   435  }
   436  
   437  func TestReadSeedReset(t *testing.T) {
   438  	r := New(NewSource(42))
   439  	b1 := make([]byte, 128)
   440  	_, err := r.Read(b1)
   441  	if err != nil {
   442  		t.Errorf("read: %v", err)
   443  	}
   444  	r.Seed(42)
   445  	b2 := make([]byte, 128)
   446  	_, err = r.Read(b2)
   447  	if err != nil {
   448  		t.Errorf("read: %v", err)
   449  	}
   450  	if !bytes.Equal(b1, b2) {
   451  		t.Errorf("mismatch after re-seed:\n%x\n%x", b1, b2)
   452  	}
   453  }
   454  
   455  func TestShuffleSmall(t *testing.T) {
   456  	// Check that Shuffle allows n=0 and n=1, but that swap is never called for them.
   457  	r := New(NewSource(1))
   458  	for n := 0; n <= 1; n++ {
   459  		r.Shuffle(n, func(i, j int) { t.Fatalf("swap called, n=%d i=%d j=%d", n, i, j) })
   460  	}
   461  }
   462  
   463  func TestPCGSourceRoundTrip(t *testing.T) {
   464  	var src PCGSource
   465  	src.Seed(uint64(time.Now().Unix()))
   466  
   467  	src.Uint64() // Step PRNG once to makes sure high and low are different.
   468  
   469  	buf, err := src.MarshalBinary()
   470  	if err != nil {
   471  		t.Errorf("unexpected error marshaling state: %v", err)
   472  	}
   473  
   474  	var dst PCGSource
   475  	// Get dst into a non-zero state.
   476  	dst.Seed(1)
   477  	for i := 0; i < 10; i++ {
   478  		dst.Uint64()
   479  	}
   480  
   481  	err = dst.UnmarshalBinary(buf)
   482  	if err != nil {
   483  		t.Errorf("unexpected error unmarshaling state: %v", err)
   484  	}
   485  
   486  	if dst != src {
   487  		t.Errorf("mismatch between generator states: got:%+v want:%+v", dst, src)
   488  	}
   489  }
   490  
   491  // Benchmarks
   492  
   493  func BenchmarkSource(b *testing.B) {
   494  	rng := NewSource(0)
   495  	for n := b.N; n > 0; n-- {
   496  		rng.Uint64()
   497  	}
   498  }
   499  
   500  func BenchmarkInt63Threadsafe(b *testing.B) {
   501  	for n := b.N; n > 0; n-- {
   502  		Int63()
   503  	}
   504  }
   505  
   506  func BenchmarkInt63ThreadsafeParallel(b *testing.B) {
   507  	b.RunParallel(func(pb *testing.PB) {
   508  		for pb.Next() {
   509  			Int63()
   510  		}
   511  	})
   512  }
   513  
   514  func BenchmarkInt63Unthreadsafe(b *testing.B) {
   515  	r := New(NewSource(1))
   516  	for n := b.N; n > 0; n-- {
   517  		r.Int63()
   518  	}
   519  }
   520  
   521  func BenchmarkIntn1000(b *testing.B) {
   522  	r := New(NewSource(1))
   523  	for n := b.N; n > 0; n-- {
   524  		r.Intn(1000)
   525  	}
   526  }
   527  
   528  func BenchmarkInt63n1000(b *testing.B) {
   529  	r := New(NewSource(1))
   530  	for n := b.N; n > 0; n-- {
   531  		r.Int63n(1000)
   532  	}
   533  }
   534  
   535  func BenchmarkInt31n1000(b *testing.B) {
   536  	r := New(NewSource(1))
   537  	for n := b.N; n > 0; n-- {
   538  		r.Int31n(1000)
   539  	}
   540  }
   541  
   542  func BenchmarkFloat32(b *testing.B) {
   543  	r := New(NewSource(1))
   544  	for n := b.N; n > 0; n-- {
   545  		r.Float32()
   546  	}
   547  }
   548  
   549  func BenchmarkFloat64(b *testing.B) {
   550  	r := New(NewSource(1))
   551  	for n := b.N; n > 0; n-- {
   552  		r.Float64()
   553  	}
   554  }
   555  
   556  func BenchmarkPerm3(b *testing.B) {
   557  	r := New(NewSource(1))
   558  	for n := b.N; n > 0; n-- {
   559  		r.Perm(3)
   560  	}
   561  }
   562  
   563  func BenchmarkPerm30(b *testing.B) {
   564  	r := New(NewSource(1))
   565  	for n := b.N; n > 0; n-- {
   566  		r.Perm(30)
   567  	}
   568  }
   569  
   570  func BenchmarkPerm30ViaShuffle(b *testing.B) {
   571  	r := New(NewSource(1))
   572  	for n := b.N; n > 0; n-- {
   573  		p := make([]int, 30)
   574  		for i := range p {
   575  			p[i] = i
   576  		}
   577  		r.Shuffle(30, func(i, j int) { p[i], p[j] = p[j], p[i] })
   578  	}
   579  }
   580  
   581  // BenchmarkShuffleOverhead uses a minimal swap function
   582  // to measure just the shuffling overhead.
   583  func BenchmarkShuffleOverhead(b *testing.B) {
   584  	r := New(NewSource(1))
   585  	for n := b.N; n > 0; n-- {
   586  		r.Shuffle(52, func(i, j int) {
   587  			if i < 0 || i >= 52 || j < 0 || j >= 52 {
   588  				b.Fatalf("bad swap(%d, %d)", i, j)
   589  			}
   590  		})
   591  	}
   592  }
   593  
   594  func BenchmarkRead3(b *testing.B) {
   595  	r := New(NewSource(1))
   596  	buf := make([]byte, 3)
   597  	b.ResetTimer()
   598  	for n := b.N; n > 0; n-- {
   599  		r.Read(buf)
   600  	}
   601  }
   602  
   603  func BenchmarkRead64(b *testing.B) {
   604  	r := New(NewSource(1))
   605  	buf := make([]byte, 64)
   606  	b.ResetTimer()
   607  	for n := b.N; n > 0; n-- {
   608  		r.Read(buf)
   609  	}
   610  }
   611  
   612  func BenchmarkRead1000(b *testing.B) {
   613  	r := New(NewSource(1))
   614  	buf := make([]byte, 1000)
   615  	b.ResetTimer()
   616  	for n := b.N; n > 0; n-- {
   617  		r.Read(buf)
   618  	}
   619  }
   620  

View as plain text