Optimize randBool() and randString() by jake-ciolek · Pull Request #41 · google/gofuzz

jake-ciolek · 2020-06-04T17:29:18Z

I love this library, small but gets the job done! :)

I have tinkered a bit with the functions to generate bools and strings and made them a bit faster. Hopefully it will save someone some clocks when running tests.

The code speeds up bool generation 3-fold. I've ran some benchmarks on GCP VM's and my local MacBook:

My MacBook Pro:

BenchmarkRandBool-8 75312272 14.5 ns/op
BenchmarkRandBoolNew-8 235223112 5.06 ns/op
BenchmarkRandStringStock-8 1439635 841 ns/op
BenchmarkRandStringBuilder-8 1541736 775 ns/op

8 core GCP E2:

BenchmarkRandBool-8 70003590 16.6 ns/op
BenchmarkRandBoolNew-8 236062108 5.08 ns/op
BenchmarkRandStringStock-8 1370116 874 ns/op
BenchmarkRandStringBuilder-8 1484086 807 ns/op

8 core GCP N2 (Intel Cascade Lake):

BenchmarkRandBool-8 91276062 13.1 ns/op
BenchmarkRandBoolNew-8 301435986 3.98 ns/op
BenchmarkRandStringStock-8 1743852 688 ns/op
BenchmarkRandStringBuilder-8 1883102 638 ns/op

8 core GCP N1 (Intel Skylake):

BenchmarkRandBool-8 71896552 16.5 ns/op
BenchmarkRandBoolNew-8 239149131 5.03 ns/op
BenchmarkRandStringStock-8 1375860 873 ns/op
BenchmarkRandStringBuilder-8 1484378 808 ns/op

randString() will be 5-7% due to less data being moved around (thanks to strings.Builder)

randString() memory usage change:

BenchmarkRandStringStock-8 1543179 772 ns/op 71 B/op 1 allocs/op
BenchmarkRandStringBuilder-8 1639436 735 ns/op 48 B/op 1 allocs/op

Previous time: 15.175 ns/op New time: 4.78 ns/op

30% less memory used and a 5 to 7% higher throughput.

googlebot · 2020-06-04T17:29:23Z

Thanks for your pull request. It looks like this may be your first contribution to a Google open source project (if not, look below for help). Before we can look at your pull request, you'll need to sign a Contributor License Agreement (CLA).

📝 Please visit https://cla.developers.google.com/ to sign.

Once you've signed (or fixed any issues), please reply here with @googlebot I signed it! and we'll verify it.

What to do if you already signed the CLA

Individual signers

It's possible we don't have your GitHub username or you're using a different email address on your commit. Check your existing CLA data and verify that your email is set on your git commits.

Corporate signers

Your company has a Point of Contact who decides which employees are authorized to participate. Ask your POC to be added to the group of authorized contributors. If you don't know who your Point of Contact is, direct the Google project maintainer to go/cla#troubleshoot (Public version).
The email used to register you as an authorized contributor must be the email used for the Git commit. Check your existing CLA data and verify that your email is set on your git commits.
The email used to register you as an authorized contributor must also be attached to your GitHub account.

ℹ️ Googlers: Go here for more info.

jake-ciolek · 2020-06-04T17:32:34Z

@googlebot I signed it!

googlebot · 2020-06-04T17:32:36Z

CLAs look good, thanks!

ℹ️ Googlers: Go here for more info.

lavalamp · 2020-06-04T17:42:36Z

-		return true
-	}
-	return false
+	return r.Int31()&(1<<30) == 0


Why bit 31 and not some other bit?

I had to pick one and I believe there was no better choice :)

Yeah, they should all be the same. I just wasn't sure if the change from bit 0 was significant for the speed up--it shouldn't be, right?

From my benchmarks, on my local machine I've found this bit to be faster from bit 0 by 1-2% - why, I don't know - probably some CPU arch black magic.

hm... you can use https://godoc.org/golang.org/x/tools/cmd/benchcmp to tell if it's significant or not. (not shown in the help: you can put multiple runs in both the old and new file and it will give you the std dev so you can tell if it's significant or not)

lavalamp · 2020-06-04T17:44:14Z

Thanks! Can you add your benchmark, too?

jake-ciolek · 2020-06-04T17:59:02Z

Sure!

import (
	"math/rand"

	"testing"
	"strings"
)

func randBoolOld(r *rand.Rand) bool {
	if r.Int()&1 == 1 {
		return true
	}
	return false
}

func randBoolNew(r *rand.Rand) bool {
	return r.Int31()&(1<<30) == 0
}

func randStringOld(r *rand.Rand) string {
	n := r.Intn(20)
	runes := make([]rune, n)
	for i := range runes {
		runes[i] = unicodeRanges[r.Intn(len(unicodeRanges))].choose(r)
	}
	return string(runes)
}

func randStringBuilder(r *rand.Rand) string {
	n := r.Intn(20)
	sb := strings.Builder{}
        sb.Grow(n)
	for i := 0 ;i<n; i++ {
                sb.WriteRune(unicodeRanges[r.Intn(len(unicodeRanges))].choose(r))
	}
	
	return sb.String()
}

type int63nPicker interface {
	Int63n(int64) int64
}

type charRange struct {
	first, last rune
}

// choose returns a random unicode character from the given range, using the
// given randomness source.
func (cr charRange) choose(r int63nPicker) rune {
	count := int64(cr.last - cr.first + 1)
	return cr.first + rune(r.Int63n(count))
}

var unicodeRanges = []charRange{
	{' ', '~'},           // ASCII characters
	{'\u00a0', '\u02af'}, // Multi-byte encoded characters
	{'\u4e00', '\u9fff'}, // Common CJK (even longer encodings)
}

func BenchmarkRandBool(b *testing.B) {
	rs := rand.New(rand.NewSource(123))
	for i := 0; i < b.N; i++ {
		randBoolOld(rs)
    }
}

func BenchmarkRandBoolNew(b *testing.B) {
	rs := rand.New(rand.NewSource(123))
	for i := 0; i < b.N; i++ {
		randBoolNew(rs)
    }
}

func BenchmarkRandStringStock(b *testing.B) {
	rs := rand.New(rand.NewSource(123))
	for i := 0; i < b.N; i++ {
		randStringOld(rs)
    }
}

func BenchmarkRandStringBuilder(b *testing.B) {
	rs := rand.New(rand.NewSource(123))
	for i := 0; i < b.N; i++ {
		randStringBuilder(rs)
    }
}

lavalamp · 2020-06-04T18:04:49Z

Can you add the benchmarks to the _test.go file? (just one for Bool and one for String; no need for old/new--we can just track that over time)

jake-ciolek · 2020-06-04T19:07:10Z

Added benchmarks :)

lavalamp · 2020-06-04T20:04:54Z

+	rs := rand.New(rand.NewSource(123))
+
+	for i := 0; i < b.N; i++ {
+			randBool(rs)


Looks good-- can you run gofmt?

lavalamp · 2020-06-04T20:15:52Z

-	for i := range runes {
-		runes[i] = unicodeRanges[r.Intn(len(unicodeRanges))].choose(r)
+	sb := strings.Builder{}
+	sb.Grow(n)


I bet n*2 or n*3 would avoid an extra allocation or two.

lavalamp · 2020-06-04T20:16:02Z

LGTM thanks!

jake-ciolek added 2 commits June 4, 2020 19:18

- Optimize the randBool() function.

ea77116

Previous time: 15.175 ns/op New time: 4.78 ns/op

- Optimize randString() by using strings.Builder.

b02383a

30% less memory used and a 5 to 7% higher throughput.

googlebot added the cla: no label Jun 4, 2020

googlebot added cla: yes and removed cla: no labels Jun 4, 2020

lavalamp reviewed Jun 4, 2020

View reviewed changes

- Add benchmarks for randBool() and randString().

82e8886

lavalamp reviewed Jun 4, 2020

View reviewed changes

- Ran go fmt

5726fe9

lavalamp reviewed Jun 4, 2020

View reviewed changes

lavalamp merged commit c04b05f into google:master Jun 4, 2020

Conversation

jake-ciolek commented Jun 4, 2020

Uh oh!

googlebot commented Jun 4, 2020

What to do if you already signed the CLA

Individual signers

Corporate signers

Uh oh!

jake-ciolek commented Jun 4, 2020

Uh oh!

googlebot commented Jun 4, 2020

Uh oh!

lavalamp Jun 4, 2020

Choose a reason for hiding this comment

Uh oh!

jake-ciolek Jun 4, 2020

Choose a reason for hiding this comment

Uh oh!

lavalamp Jun 4, 2020

Choose a reason for hiding this comment

Uh oh!

jake-ciolek Jun 4, 2020

Choose a reason for hiding this comment

Uh oh!

lavalamp Jun 4, 2020

Choose a reason for hiding this comment

Uh oh!

lavalamp commented Jun 4, 2020

Uh oh!

jake-ciolek commented Jun 4, 2020

Uh oh!

lavalamp commented Jun 4, 2020

Uh oh!

jake-ciolek commented Jun 4, 2020

Uh oh!

lavalamp Jun 4, 2020

Choose a reason for hiding this comment

Uh oh!

jake-ciolek Jun 4, 2020

Choose a reason for hiding this comment

Uh oh!

lavalamp Jun 4, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

lavalamp commented Jun 4, 2020

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

lavalamp Jun 4, 2020 •

edited

Loading