code review 5040048: suffixarray: add benchmarks for construction

suffixarray: add benchmarks for construction

[Eric Roshan Eisner, 2011-09-18 21:53:06]

Hello gri@golang.org (cc: golang-dev@googlegroups.com),

I'd like you to review this change to
https://go.googlecode.com/hg

[jmhodges, 2011-09-19 06:23:30]

When writing benchmarks, don't forget to use b.N. Also, would it be
better to test qsufsort(data) directly?

    for i := 0; i < b.N; i++ {
        New(data) // or qsufsort(data)
    }

On Sun, Sep 18, 2011 at 2:53 PM,  <eric.d.eisner@gmail.com> wrote:
> Reviewers: gri,
>
> Message:
> Hello gri@golang.org (cc: golang-dev@googlegroups.com),
>
> I'd like you to review this change to
> https://go.googlecode.com/hg
>
>
> Description:
> suffixarray: add benchmarks for construction
>
> Please review this at http://codereview.appspot.com/5040048/
>
> Affected files:
>  M src/pkg/index/suffixarray/suffixarray_test.go
>
>
> Index: src/pkg/index/suffixarray/suffixarray_test.go
> ===================================================================
> --- a/src/pkg/index/suffixarray/suffixarray_test.go
> +++ b/src/pkg/index/suffixarray/suffixarray_test.go
> @@ -7,6 +7,7 @@ package suffixarray
>  import (
>        "bytes"
>        "exp/regexp"
> +       "rand"
>        "sort"
>        "strings"
>        "testing"
> @@ -255,3 +256,25 @@ func TestIndex(t *testing.T) {
>                testLookups(t, &tc, x, -1)
>        }
>  }
> +
> +// These two benchmarks are the least and the most possible substring
> +// repetition respectively. For most algorithms, the runtime of every input
> +// will be between these two runtimes.
> +const benchmarkSize = 1e6
> +
> +func BenchmarkNewIndexRandom(b *testing.B) {
> +       b.StopTimer()
> +       data := make([]byte, benchmarkSize)
> +       for i := range data {
> +               data[i] = byte(rand.Intn(256))
> +       }
> +       b.StartTimer()
> +       New(data)
> +}
> +
> +func BenchmarkNewIndexRepeat(b *testing.B) {
> +       b.StopTimer()
> +       data := make([]byte, benchmarkSize)
> +       b.StartTimer()
> +       New(data)
> +}
>
>
>

[gri, 2011-09-19 18:01:09]

Please also address Jeff Hodges' comments (b.N, qsufsort).

http://codereview.appspot.com/5040048/diff/5001/src/pkg/index/suffixarray/suf...
File src/pkg/index/suffixarray/suffixarray_test.go (right):

http://codereview.appspot.com/5040048/diff/5001/src/pkg/index/suffixarray/suf...
src/pkg/index/suffixarray/suffixarray_test.go:260: // These two benchmarks are
the least and the most possible substring
s/possible/likely/?

http://codereview.appspot.com/5040048/diff/5001/src/pkg/index/suffixarray/suf...
src/pkg/index/suffixarray/suffixarray_test.go:261: // repetition respectively.
For most algorithms, the runtime of every input
s/runtime/running time/

http://codereview.appspot.com/5040048/diff/5001/src/pkg/index/suffixarray/suf...
src/pkg/index/suffixarray/suffixarray_test.go:262: // will be between these two
runtimes.
s/ runtimes//

[Eric Roshan Eisner, 2011-09-20 05:57:12]

Hello gri@golang.org, jeff@somethingsimilar.com (cc:
golang-dev@googlegroups.com),

Please take another look.

[Eric Roshan Eisner, 2011-09-20 06:01:28]

I've made these changes, but I don't see why the benchmarks should be timing
the private function qsufsort instead of the public interface, New. They are
doing an almost identical amount of work anyway.

On Mon, Sep 19, 2011 at 11:01, <gri@golang.org> wrote:

> Please also address Jeff Hodges' comments (b.N, qsufsort).
>
>
>
> http://codereview.appspot.com/**5040048/diff/5001/src/pkg/**
>
index/suffixarray/suffixarray_**test.go<http://codereview.appspot.com/5040048/diff/5001/src/pkg/index/suffixarray/suffixarray_test.go>
> File src/pkg/index/suffixarray/**suffixarray_test.go (right):
>
> http://codereview.appspot.com/**5040048/diff/5001/src/pkg/**
>
index/suffixarray/suffixarray_**test.go#newcode260<http://codereview.appspot.com/5040048/diff/5001/src/pkg/index/suffixarray/suffixarray_test.go#newcode260>
> src/pkg/index/suffixarray/**suffixarray_test.go:260: // These two
>
> benchmarks are the least and the most possible substring
> s/possible/likely/?
>
> http://codereview.appspot.com/**5040048/diff/5001/src/pkg/**
>
index/suffixarray/suffixarray_**test.go#newcode261<http://codereview.appspot.com/5040048/diff/5001/src/pkg/index/suffixarray/suffixarray_test.go#newcode261>
> src/pkg/index/suffixarray/**suffixarray_test.go:261: // repetition
>
> respectively. For most algorithms, the runtime of every input
> s/runtime/running time/
>
> http://codereview.appspot.com/**5040048/diff/5001/src/pkg/**
>
index/suffixarray/suffixarray_**test.go#newcode262<http://codereview.appspot.com/5040048/diff/5001/src/pkg/index/suffixarray/suffixarray_test.go#newcode262>
> src/pkg/index/suffixarray/**suffixarray_test.go:262: // will be between
> these two runtimes.
> s/ runtimes//
>
>
>
http://codereview.appspot.com/**5040048/<http://codereview.appspot.com/5040048/>
>

[jmhodges, 2011-09-20 09:46:39]

LGTM

Not a committer, however.

[gri, 2011-09-20 21:22:07]

This can be vastly simplified. I'm sorry I missed this in the first round.
- gri

http://codereview.appspot.com/5040048/diff/10001/src/pkg/index/suffixarray/su...
File src/pkg/index/suffixarray/suffixarray_test.go (right):

http://codereview.appspot.com/5040048/diff/10001/src/pkg/index/suffixarray/su...
src/pkg/index/suffixarray/suffixarray_test.go:270: for i := range data {
The data is never modified by New() so this is not necessary. Just do:

b.StopTimer()
data := make([]byte, benchmarkSize)
for i := range data {
    data[i] = byte(rand.Intn(256))
}
b.StartTimer()
for i := 0; i < b.N; i++ {
   New(data)
}

In fact, both routines are now almost identical (the first has an initialization
loop) that it makes sense to factor them out into a separate function

func benchmarkNew(n int, random bool) {
   b.StopTimer()
   data := make([]byte, benchmarkSize)
   if random {
      for i := range data {
          data[i] = byte(rand.Intn(256))
      }
   }
   b.StartTimer()
   for i := 0; i < b.N; i++ {
      New(data)
   }
}

and then call

benchmarkNew(b.N, false) and
benchmarkNew(b.N, true)

respectively.

http://codereview.appspot.com/5040048/diff/10001/src/pkg/index/suffixarray/su...
src/pkg/index/suffixarray/suffixarray_test.go:283: for i := range data {
Please make the same change as above. Also there's no need for the
initialization loop, new slices are zero initialized.

[Eric Roshan Eisner, 2011-09-23 05:08:37]

Hello gri@golang.org, jeff@somethingsimilar.com (cc:
golang-dev@googlegroups.com),

Please take another look.

[gri, 2011-09-23 16:14:52]

LGTM.
Thanks.
- gri

[gri, 2011-09-23 16:18:22]

*** Submitted as http://code.google.com/p/go/source/detail?r=fb86ba0354a5 ***

suffixarray: add benchmarks for construction

R=gri, jeff
CC=golang-dev
http://codereview.appspot.com/5040048

Committer: Robert Griesemer <gri@golang.org>