container/intsets: add benchmark of AppendTo method.

Also:
- increase sparsity of sets in benchmarks.
- removed TODO in forEach.  Subword masks had no benefit.
- minor cleanup.

LGTM=crawshaw
R=crawshaw
CC=golang-codereviews
https://golang.org/cl/103470049

2 files changed, 20 insertions, 9 deletions

diff --git a/container/intsets/sparse.go b/container/intsets/sparse.go
index 0017ddfe8..4866aaa9c 100644
--- a/container/intsets/sparse.go
+++ b/container/intsets/sparse.go
@@ -178,8 +178,6 @@ func (b *block) min(take bool) int {
 func (b *block) forEach(f func(int)) {
 	for i, w := range b.bits {
 		offset := b.offset + i*bitsPerWord
-		// TODO(adonovan): opt: uses subword
-		// masks to avoid testing every bit.
 		for bi := 0; w != 0 && bi < bitsPerWord; bi++ {
 			if w&1 != 0 {
 				f(offset)
@@ -210,10 +208,11 @@ func offsetAndBitIndex(x int) (int, uint) {
 // initialized.
 //
 func (s *Sparse) start() *block {
-	if s.root.next == nil {
-		s.root.next = &s.root
-		s.root.prev = &s.root
-	} else if s.root.next.prev != &s.root {
+	root := &s.root
+	if root.next == nil {
+		root.next = root
+		root.prev = root
+	} else if root.next.prev != root {
 		// Copying a Sparse x leads to pernicious corruption: the
 		// new Sparse y shares the old linked list, but iteration
 		// on y will never encounter &y.root so it goes into a
@@ -221,7 +220,7 @@ func (s *Sparse) start() *block {
 		panic("A Sparse has been copied without (*Sparse).Copy()")
 	}
 
-	return s.root.next
+	return root.next
 }
 
 // IsEmpty reports whether the set s is empty.
diff --git a/container/intsets/sparse_test.go b/container/intsets/sparse_test.go
index bdbb8dfd5..727e1672d 100644
--- a/container/intsets/sparse_test.go
+++ b/container/intsets/sparse_test.go
@@ -466,7 +466,7 @@ func BenchmarkSparseBitVector(b *testing.B) {
 	for tries := 0; tries < b.N; tries++ {
 		var x, y, z intsets.Sparse
 		for i := 0; i < 1000; i++ {
-			n := int(prng.Int()) % 10000
+			n := int(prng.Int()) % 100000
 			if i%2 == 0 {
 				x.Insert(n)
 			} else {
@@ -483,7 +483,7 @@ func BenchmarkHashTable(b *testing.B) {
 	for tries := 0; tries < b.N; tries++ {
 		x, y, z := make(map[int]bool), make(map[int]bool), make(map[int]bool)
 		for i := 0; i < 1000; i++ {
-			n := int(prng.Int()) % 10000
+			n := int(prng.Int()) % 100000
 			if i%2 == 0 {
 				x[n] = true
 			} else {
@@ -506,3 +506,15 @@ func BenchmarkHashTable(b *testing.B) {
 		}
 	}
 }
+
+func BenchmarkAppendTo(b *testing.B) {
+	prng := rand.New(rand.NewSource(0))
+	var x intsets.Sparse
+	for i := 0; i < 1000; i++ {
+		x.Insert(int(prng.Int()) % 10000)
+	}
+	var space [1000]int
+	for tries := 0; tries < b.N; tries++ {
+		x.AppendTo(space[:0])
+	}
+}