hashtable_test.go

Documentation: go.starlark.net/starlark

     1  // Copyright 2017 The Bazel 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 starlark
     6  
     7  import (
     8  	"fmt"
     9  	"math/rand"
    10  	"sync"
    11  	"testing"
    12  )
    13  
    14  func TestHashtable(t *testing.T) {
    15  	makeTestIntsOnce.Do(makeTestInts)
    16  	testHashtable(t, make(map[int]bool))
    17  }
    18  
    19  func BenchmarkStringHash(b *testing.B) {
    20  	for len := 1; len <= 1024; len *= 2 {
    21  		buf := make([]byte, len)
    22  		rand.New(rand.NewSource(0)).Read(buf)
    23  		s := string(buf)
    24  
    25  		b.Run(fmt.Sprintf("hard-%d", len), func(b *testing.B) {
    26  			for i := 0; i < b.N; i++ {
    27  				hashString(s)
    28  			}
    29  		})
    30  		b.Run(fmt.Sprintf("soft-%d", len), func(b *testing.B) {
    31  			for i := 0; i < b.N; i++ {
    32  				softHashString(s)
    33  			}
    34  		})
    35  	}
    36  }
    37  
    38  func BenchmarkHashtable(b *testing.B) {
    39  	makeTestIntsOnce.Do(makeTestInts)
    40  	b.ResetTimer()
    41  	for i := 0; i < b.N; i++ {
    42  		testHashtable(b, nil)
    43  	}
    44  }
    45  
    46  const testIters = 10000
    47  
    48  var (
    49  	// testInts is a zipf-distributed array of Ints and corresponding ints.
    50  	// This removes the cost of generating them on the fly during benchmarking.
    51  	// Without this, Zipf and MakeInt dominate CPU and memory costs, respectively.
    52  	makeTestIntsOnce sync.Once
    53  	testInts         [3 * testIters]struct {
    54  		Int   Int
    55  		goInt int
    56  	}
    57  )
    58  
    59  func makeTestInts() {
    60  	zipf := rand.NewZipf(rand.New(rand.NewSource(0)), 1.1, 1.0, 1000.0)
    61  	for i := range &testInts {
    62  		r := int(zipf.Uint64())
    63  		testInts[i].goInt = r
    64  		testInts[i].Int = MakeInt(r)
    65  	}
    66  }
    67  
    68  // testHashtable is both a test and a benchmark of hashtable.
    69  // When sane != nil, it acts as a test against the semantics of Go's map.
    70  func testHashtable(tb testing.TB, sane map[int]bool) {
    71  	var i int // index into testInts
    72  
    73  	var ht hashtable
    74  
    75  	// Insert 10000 random ints into the map.
    76  	for j := 0; j < testIters; j++ {
    77  		k := testInts[i]
    78  		i++
    79  		if err := ht.insert(k.Int, None); err != nil {
    80  			tb.Fatal(err)
    81  		}
    82  		if sane != nil {
    83  			sane[k.goInt] = true
    84  		}
    85  	}
    86  
    87  	// Do 10000 random lookups in the map.
    88  	for j := 0; j < testIters; j++ {
    89  		k := testInts[i]
    90  		i++
    91  		_, found, err := ht.lookup(k.Int)
    92  		if err != nil {
    93  			tb.Fatal(err)
    94  		}
    95  		if sane != nil {
    96  			_, found2 := sane[k.goInt]
    97  			if found != found2 {
    98  				tb.Fatal("sanity check failed")
    99  			}
   100  		}
   101  	}
   102  
   103  	// Do 10000 random deletes from the map.
   104  	for j := 0; j < testIters; j++ {
   105  		k := testInts[i]
   106  		i++
   107  		_, found, err := ht.delete(k.Int)
   108  		if err != nil {
   109  			tb.Fatal(err)
   110  		}
   111  		if sane != nil {
   112  			_, found2 := sane[k.goInt]
   113  			if found != found2 {
   114  				tb.Fatal("sanity check failed")
   115  			}
   116  			delete(sane, k.goInt)
   117  		}
   118  	}
   119  
   120  	if sane != nil {
   121  		if int(ht.len) != len(sane) {
   122  			tb.Fatal("sanity check failed")
   123  		}
   124  	}
   125  }
   126
View as plain text