starlark/hashtable_test.go

// Copyright 2017 The Bazel Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package starlark

import (
	"fmt"
	"math/rand"
	"sync"
	"testing"
)

func TestHashtable(t *testing.T) {
	makeTestIntsOnce.Do(makeTestInts)
	testHashtable(t, make(map[int]bool))
}

func BenchmarkStringHash(b *testing.B) {
	for len := 1; len <= 1024; len *= 2 {
		buf := make([]byte, len)
		rand.New(rand.NewSource(0)).Read(buf)
		s := string(buf)

		b.Run(fmt.Sprintf("hard-%d", len), func(b *testing.B) {
			for i := 0; i < b.N; i++ {
				hashString(s)
			}
		})
		b.Run(fmt.Sprintf("soft-%d", len), func(b *testing.B) {
			for i := 0; i < b.N; i++ {
				softHashString(s)
			}
		})
	}
}

func BenchmarkHashtable(b *testing.B) {
	makeTestIntsOnce.Do(makeTestInts)
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		testHashtable(b, nil)
	}
}

const testIters = 10000

var (
	// testInts is a zipf-distributed array of Ints and corresponding ints.
	// This removes the cost of generating them on the fly during benchmarking.
	// Without this, Zipf and MakeInt dominate CPU and memory costs, respectively.
	makeTestIntsOnce sync.Once
	testInts         [3 * testIters]struct {
		Int   Int
		goInt int
	}
)

func makeTestInts() {
	zipf := rand.NewZipf(rand.New(rand.NewSource(0)), 1.1, 1.0, 1000.0)
	for i := range &testInts {
		r := int(zipf.Uint64())
		testInts[i].goInt = r
		testInts[i].Int = MakeInt(r)
	}
}

// testHashtable is both a test and a benchmark of hashtable.
// When sane != nil, it acts as a test against the semantics of Go's map.
func testHashtable(tb testing.TB, sane map[int]bool) {
	var i int // index into testInts

	var ht hashtable

	// Insert 10000 random ints into the map.
	for j := 0; j < testIters; j++ {
		k := testInts[i]
		i++
		if err := ht.insert(k.Int, None); err != nil {
			tb.Fatal(err)
		}
		if sane != nil {
			sane[k.goInt] = true
		}
	}

	// Do 10000 random lookups in the map.
	for j := 0; j < testIters; j++ {
		k := testInts[i]
		i++
		_, found, err := ht.lookup(k.Int)
		if err != nil {
			tb.Fatal(err)
		}
		if sane != nil {
			_, found2 := sane[k.goInt]
			if found != found2 {
				tb.Fatal("sanity check failed")
			}
		}
	}

	// Do 10000 random deletes from the map.
	for j := 0; j < testIters; j++ {
		k := testInts[i]
		i++
		_, found, err := ht.delete(k.Int)
		if err != nil {
			tb.Fatal(err)
		}
		if sane != nil {
			_, found2 := sane[k.goInt]
			if found != found2 {
				tb.Fatal("sanity check failed")
			}
			delete(sane, k.goInt)
		}
	}

	if sane != nil {
		if int(ht.len) != len(sane) {
			tb.Fatal("sanity check failed")
		}
	}
}