all: spot optimizations

A bunch of spot optmizations after cpu/memory profiling:
1. Optimize hot-path coverage comparison in fuzzer.
2. Don't allocate and copy serialized program, serialize directly into shmem.
3. Reduce allocations during parsing of output shmem (encoding/binary sucks).
4. Don't allocate and copy coverage arrays, refer directly to the shmem region
   (we are not going to mutate them).
5. Don't validate programs outside of tests, validation allocates tons of memory.
6. Replace the choose primitive with simpler switches.
   Choose allocates fullload of memory (for int, func, and everything the func refers).
7. Other minor optimizations.

2 files changed, 54 insertions, 9 deletions

diff --git a/cover/cover.go b/cover/cover.go
index 12b005964..4a4ea619e 100644
--- a/cover/cover.go
+++ b/cover/cover.go
@@ -101,6 +101,21 @@ func foreach(cov0, cov1 Cover, f func(uint32, uint32) uint32) Cover {
 	return res
 }
 
+// HasDifference returns true if cov0 has some coverage that is not present in cov1.
+// This is called on fuzzer hot path.
+func HasDifference(cov0, cov1 Cover) bool {
+	i1 := 0
+	for _, v0 := range cov0 {
+		for ; i1 < len(cov1) && cov1[i1] < v0; i1++ {
+		}
+		if i1 == len(cov1) || cov1[i1] > v0 {
+			return true
+		}
+		i1++
+	}
+	return false
+}
+
 // Minimize returns a minimal set of inputs that give the same coverage as the full corpus.
 func Minimize(corpus []Cover) []int {
 	inputs := make([]*minInput, len(corpus))
diff --git a/cover/cover_test.go b/cover/cover_test.go
index 73dc7581b..5297de66d 100644
--- a/cover/cover_test.go
+++ b/cover/cover_test.go
@@ -12,9 +12,9 @@ import (
 )
 
 func initTest(t *testing.T) (*rand.Rand, int) {
-	iters := 1000
+	iters := 100000
 	if testing.Short() {
-		iters = 100
+		iters = 1000
 	}
 	seed := int64(time.Now().UnixNano())
 	rs := rand.NewSource(seed)
@@ -167,17 +167,21 @@ func TestMinimize(t *testing.T) {
 	}
 }
 
+func randCover(rnd *rand.Rand, maxLen int) Cover {
+	tmp := make(Cover, rnd.Intn(maxLen))
+	for j := range tmp {
+		tmp[j] = uint32(rnd.Intn(100))
+	}
+	return Canonicalize(tmp)
+}
+
 func TestMinimizeRandom(t *testing.T) {
 	rnd, iters := initTest(t)
 	for i := 0; i < iters; i++ {
 		n := rnd.Intn(20)
 		cov := make([]Cover, n)
 		for i := range cov {
-			tmp := make(Cover, rnd.Intn(10))
-			for j := range tmp {
-				tmp[j] = uint32(rnd.Intn(100))
-			}
-			cov[i] = Canonicalize(tmp)
+			cov[i] = randCover(rnd, 10)
 		}
 		var total Cover
 		for _, c := range cov {
@@ -188,8 +192,8 @@ func TestMinimizeRandom(t *testing.T) {
 		for _, idx := range mini {
 			minimized = Union(minimized, cov[idx])
 		}
-		t.Logf("minimized %v -> %v", len(cov), len(mini))
 		if !reflect.DeepEqual(total, minimized) {
+			t.Logf("minimized %v -> %v", len(cov), len(mini))
 			t.Logf("corpus:")
 			for _, in := range cov {
 				t.Logf("  %+v", in)
@@ -198,8 +202,34 @@ func TestMinimizeRandom(t *testing.T) {
 			for _, in := range cov {
 				t.Logf("  %+v", in)
 			}
-
 			t.Fatalf("better luck next time")
 		}
 	}
 }
+
+func TestHasDifference(t *testing.T) {
+	rnd, iters := initTest(t)
+	for i := 0; i < iters; i++ {
+		cov1 := randCover(rnd, 20)
+		cov2 := randCover(rnd, 20)
+		diff := Difference(cov1, cov2)
+		hasDiff := HasDifference(cov1, cov2)
+		if len(diff) != 0 != hasDiff {
+			t.Fatalf("cov1=%+v cov2=%+v diff=%+v hasDiff=%v", cov1, cov2, diff, hasDiff)
+		}
+	}
+}
+
+func BenchmarkHasDifference(b *testing.B) {
+	rnd := rand.New(rand.NewSource(0))
+	cov0 := make(Cover, 70000)
+	for i := range cov0 {
+		cov0[i] = uint32(rnd.Intn(1 << 30))
+	}
+	cov1 := Canonicalize(append(Cover{}, cov0[:500]...))
+	cov0 = Canonicalize(cov0)
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		_ = HasDifference(cov1, cov0)
+	}
+}