code review 6545049: strings: implement a faster single-string Replacer

strings: implement a faster single-string Replacer

The string searching is implemented separately so other functions
may make use of it in the future.

benchmark                        old ns/op    new ns/op    delta
BenchmarkSingleMaxSkipping          125889         2474  -98.03%
BenchmarkSingleLongSuffixFail        16252         1996  -87.72%
BenchmarkSingleMatch                260793       136266  -47.75%

benchmark                         old MB/s     new MB/s  speedup
BenchmarkSingleMaxSkipping           79.43      4041.57   50.88x
BenchmarkSingleLongSuffixFail        61.65       501.81    8.14x
BenchmarkSingleMatch                 57.52       110.08    1.91x

[Eric Roshan Eisner, 2012-09-21 01:19:34]

Hello golang-dev@googlegroups.com,

I'd like you to review this change to
https://code.google.com/p/go

[nigeltao, 2012-09-21 02:00:23]

Can we have before/after benchmark numbers?

https://codereview.appspot.com/6545049/diff/4001/src/pkg/strings/replace.go
File src/pkg/strings/replace.go (right):

https://codereview.appspot.com/6545049/diff/4001/src/pkg/strings/replace.go#n...
src/pkg/strings/replace.go:366: var buf []byte
Call WriteString, like genericReplacer.Replace.

https://codereview.appspot.com/6545049/diff/4001/src/pkg/strings/search_test.go
File src/pkg/strings/search_test.go (right):

https://codereview.appspot.com/6545049/diff/4001/src/pkg/strings/search_test....
src/pkg/strings/search_test.go:46: {"mississi", [256]int{'i': 3, 'm': 7, 's':
1},
I'd format it as

{
  "mississi",
  [256]int{'i': 3, 'm': 7, 's': 1},
  []int{15, 14, 13, 7, 11, 10, 7, 1},
},

and similarly below.

https://codereview.appspot.com/6545049/diff/4001/src/pkg/strings/search_test....
src/pkg/strings/search_test.go:48: // From original paper.
// From http://www.cs.utexas.edu/~moore/publications/fstrpos.pdf

[nigeltao, 2012-09-21 02:00:30]

Can we have before/after benchmark numbers?

[Eric Roshan Eisner, 2012-09-21 05:00:34]

On 2012/09/21 02:00:23, nigeltao wrote:
> Can we have before/after benchmark numbers?

Added to cl description:

benchmark                        old ns/op    new ns/op    delta
BenchmarkSingleMaxSkipping          125889         2474  -98.03%
BenchmarkSingleLongSuffixFail        16252         1996  -87.72%
BenchmarkSingleMatch                260793       136266  -47.75%

benchmark                         old MB/s     new MB/s  speedup
BenchmarkSingleMaxSkipping           79.43      4041.57   50.88x
BenchmarkSingleLongSuffixFail        61.65       501.81    8.14x
BenchmarkSingleMatch                 57.52       110.08    1.91x

> 
> https://codereview.appspot.com/6545049/diff/4001/src/pkg/strings/replace.go
> File src/pkg/strings/replace.go (right):
> 
>
https://codereview.appspot.com/6545049/diff/4001/src/pkg/strings/replace.go#n...
> src/pkg/strings/replace.go:366: var buf []byte
> Call WriteString, like genericReplacer.Replace.

In this case, there is a considerable performance advantage if we can avoid
allocation when there is nothing to replace. This algorithm can avoid reading
most of the bytes in the source text, and allocating and copying all the bytes
when there's no match causes a 10x slowdown.
> 
>
https://codereview.appspot.com/6545049/diff/4001/src/pkg/strings/search_test.go
> File src/pkg/strings/search_test.go (right):
> 
>
https://codereview.appspot.com/6545049/diff/4001/src/pkg/strings/search_test....
> src/pkg/strings/search_test.go:46: {"mississi", [256]int{'i': 3, 'm': 7, 's':
> 1},
> I'd format it as
> 
> {
>   "mississi",
>   [256]int{'i': 3, 'm': 7, 's': 1},
>   []int{15, 14, 13, 7, 11, 10, 7, 1},
> },

I split these into lines.
> 
> and similarly below.
> 
>
https://codereview.appspot.com/6545049/diff/4001/src/pkg/strings/search_test....
> src/pkg/strings/search_test.go:48: // From original paper.
> // From http://www.cs.utexas.edu/%7Emoore/publications/fstrpos.pdf

Done.

[mtj1, 2012-09-21 06:03:04]

Is 50.88x the record?

On Fri, Sep 21, 2012 at 1:00 AM,  <eric.d.eisner@gmail.com> wrote:
> On 2012/09/21 02:00:23, nigeltao wrote:
>>
>> Can we have before/after benchmark numbers?
>
>
> Added to cl description:
>
> benchmark                        old ns/op    new ns/op    delta
> BenchmarkSingleMaxSkipping          125889         2474  -98.03%
> BenchmarkSingleLongSuffixFail        16252         1996  -87.72%
> BenchmarkSingleMatch                260793       136266  -47.75%
>
> benchmark                         old MB/s     new MB/s  speedup
> BenchmarkSingleMaxSkipping           79.43      4041.57   50.88x
> BenchmarkSingleLongSuffixFail        61.65       501.81    8.14x
> BenchmarkSingleMatch                 57.52       110.08    1.91x
>
>
>
>
> https://codereview.appspot.com/6545049/diff/4001/src/pkg/strings/replace.go
>>
>> File src/pkg/strings/replace.go (right):
>
>
>
>
https://codereview.appspot.com/6545049/diff/4001/src/pkg/strings/replace.go#n...
>>
>> src/pkg/strings/replace.go:366: var buf []byte
>> Call WriteString, like genericReplacer.Replace.
>
>
> In this case, there is a considerable performance advantage if we can
> avoid allocation when there is nothing to replace. This algorithm can
> avoid reading most of the bytes in the source text, and allocating and
> copying all the bytes when there's no match causes a 10x slowdown.
>
>
>
>
https://codereview.appspot.com/6545049/diff/4001/src/pkg/strings/search_test.go
>>
>> File src/pkg/strings/search_test.go (right):
>
>
>
>
https://codereview.appspot.com/6545049/diff/4001/src/pkg/strings/search_test....
>>
>> src/pkg/strings/search_test.go:46: {"mississi", [256]int{'i': 3, 'm':
>
> 7, 's':
>>
>> 1},
>> I'd format it as
>
>
>> {
>>    "mississi",
>>    [256]int{'i': 3, 'm': 7, 's': 1},
>>    []int{15, 14, 13, 7, 11, 10, 7, 1},
>> },
>
>
> I split these into lines.
>
>
>> and similarly below.
>
>
>
>
https://codereview.appspot.com/6545049/diff/4001/src/pkg/strings/search_test....
>>
>> src/pkg/strings/search_test.go:48: // From original paper.
>> // From http://www.cs.utexas.edu/%7Emoore/publications/fstrpos.pdf
>
>
> Done.
>
> https://codereview.appspot.com/6545049/



-- 
Michael T. Jones | Chief Technology Advocate  | mtj@google.com |  +1
650-335-5765

[nigeltao, 2012-09-25 12:18:37]

http://codereview.appspot.com/6545049/diff/4001/src/pkg/strings/search.go
File src/pkg/strings/search.go (right):

http://codereview.appspot.com/6545049/diff/4001/src/pkg/strings/search.go#new...
src/pkg/strings/search.go:18: 
Make the blank line a
    //
line, so the badCharSkip doc comment is connected to the declaration line.
Similarly for goodSuffixSkip.

http://codereview.appspot.com/6545049/diff/4001/src/pkg/strings/search.go#new...
src/pkg/strings/search.go:48: f := &stringFinder{pattern: pattern,
The usual formatting style is:

f := &stringFinder{
  pattern: pattern,
  goodSuffixSkip: make([]int, len(pattern)),
}

http://codereview.appspot.com/6545049/diff/9001/src/pkg/strings/search_test.go
File src/pkg/strings/search_test.go (right):

http://codereview.appspot.com/6545049/diff/9001/src/pkg/strings/search_test.g...
src/pkg/strings/search_test.go:24: {"abcd", "abc", -1},
Can I also get
{"bcd", "abcd", -1},

http://codereview.appspot.com/6545049/diff/9001/src/pkg/strings/search_test.g...
src/pkg/strings/search_test.go:46: {"mississi",
The usual style is for fields to line up, and for the closing } to align with
the start of the line containing the opening {. Thus:

{
  "mississi",
  [256]int{'i': 3, 'm': 7, 's': 1},
  []int{15, 14, 13, 7, 11, 10, 7, 1},
}

[Eric Roshan Eisner, 2012-09-25 14:50:18]

On Tue, Sep 25, 2012 at 5:18 AM,  <nigeltao@golang.org> wrote:
>
> http://codereview.appspot.com/6545049/diff/4001/src/pkg/strings/search.go
> File src/pkg/strings/search.go (right):
>
>
http://codereview.appspot.com/6545049/diff/4001/src/pkg/strings/search.go#new...
> src/pkg/strings/search.go:18:
> Make the blank line a
>     //
> line, so the badCharSkip doc comment is connected to the declaration
> line. Similarly for goodSuffixSkip.

Done
>
>
http://codereview.appspot.com/6545049/diff/4001/src/pkg/strings/search.go#new...
> src/pkg/strings/search.go:48: f := &stringFinder{pattern: pattern,
> The usual formatting style is:
>
> f := &stringFinder{
>   pattern: pattern,
>   goodSuffixSkip: make([]int, len(pattern)),
> }

Done.
>
>
http://codereview.appspot.com/6545049/diff/9001/src/pkg/strings/search_test.go
> File src/pkg/strings/search_test.go (right):
>
>
http://codereview.appspot.com/6545049/diff/9001/src/pkg/strings/search_test.g...
> src/pkg/strings/search_test.go:24: {"abcd", "abc", -1},
> Can I also get
> {"bcd", "abcd", -1},

Yours is swapped, but I added both versions.
>
>
http://codereview.appspot.com/6545049/diff/9001/src/pkg/strings/search_test.g...
> src/pkg/strings/search_test.go:46: {"mississi",
> The usual style is for fields to line up, and for the closing } to align
> with the start of the line containing the opening {. Thus:
>
>
> {
>   "mississi",
>   [256]int{'i': 3, 'm': 7, 's': 1},
>   []int{15, 14, 13, 7, 11, 10, 7, 1},
> }

Done.
>
> http://codereview.appspot.com/6545049/

[nigeltao, 2012-09-26 10:49:32]

http://codereview.appspot.com/6545049/diff/14001/src/pkg/strings/replace.go
File src/pkg/strings/replace.go (right):

http://codereview.appspot.com/6545049/diff/14001/src/pkg/strings/replace.go#n...
src/pkg/strings/replace.go:354: // one string to replace (and that string has
more than one character).
s/character/byte/

http://codereview.appspot.com/6545049/diff/14001/src/pkg/strings/search.go
File src/pkg/strings/search.go (right):

http://codereview.appspot.com/6545049/diff/14001/src/pkg/strings/search.go#ne...
src/pkg/strings/search.go:10: //
http://www.cs.utexas.edu/~moore/publications/fstrpos.pdf
It may be worth pointing out that (IIUC), that PDF file uses 1-based array
indexes, not 0-based.

http://codereview.appspot.com/6545049/diff/14001/src/pkg/strings/search.go#ne...
src/pkg/strings/search.go:30: // shift the matching frame to align with the next
suffix chunk.  does not
"does not occur again" is not a complete sentence.

http://codereview.appspot.com/6545049/diff/14001/src/pkg/strings/search.go#ne...
src/pkg/strings/search.go:32: // next occur at index 1, so goodSuffixSkip[3] ==
len(shift)+len(suffix)
s/next occur/which next occurs (in right-to-left order)/ ?

http://codereview.appspot.com/6545049/diff/14001/src/pkg/strings/search.go#ne...
src/pkg/strings/search.go:40: // from the back is found to be in position 4, the
matching suffix is not
It's probably worth mentioning that the suffix is "xabc". But I think it's
confusing how you say "position 4" and the suffix has length 4, but that's only
a concidence because the suffix is derived as pattern[4+1:]. I know that you're
referring to the examples from the actual Boyer-Moore paper, but is it possible
to use a different example that's less coincidental? Add that example to
search_test.go, but don't remove the Boyer-Moore examples.

http://codereview.appspot.com/6545049/diff/14001/src/pkg/strings/search.go#ne...
src/pkg/strings/search.go:41: // found elsewhere in the pattern. However, the
final "abc" is a prefix of
s/final/leftmost/, unless I've totally confused myself and you mean rightmost.

http://codereview.appspot.com/6545049/diff/14001/src/pkg/strings/search_test.go
File src/pkg/strings/search_test.go (right):

http://codereview.appspot.com/6545049/diff/14001/src/pkg/strings/search_test....
src/pkg/strings/search_test.go:12: var finderNextTests = []struct {
I'd move this into the TestFinderNext func; they don't need to be global.

func TestFinderNext(t *testing.T) {
  testCases := []struct{
    pat, text string
    index     int
  }{
    // etc
  }
  for _, tc := range testCases {
    // etc
  }
}

Similarly for tableCreationTests.

http://codereview.appspot.com/6545049/diff/14001/src/pkg/strings/search_test....
src/pkg/strings/search_test.go:38: t.Errorf("stringFinder(%q, %q) got %d, want
%d\n", tc.pat, tc.text, got, want)
s/stringFinder/StringFind/

http://codereview.appspot.com/6545049/diff/14001/src/pkg/strings/search_test....
src/pkg/strings/search_test.go:52: },
Can I get some tests where the final byte in pattern doesn't occur anywhere else
in pattern? For example: "abc", "ababbc".

http://codereview.appspot.com/6545049/diff/14001/src/pkg/strings/search_test....
src/pkg/strings/search_test.go:80: if len(tc.suf) != len(good) {
Would it be easier to say
if !reflect.DeepEqual(good, tc.suf) {
  // etc
}

[Eric Roshan Eisner, 2012-09-26 15:43:15]

PTAL

On 2012/09/26 10:49:32, nigeltao wrote:
> http://codereview.appspot.com/6545049/diff/14001/src/pkg/strings/replace.go
> File src/pkg/strings/replace.go (right):
> 
>
http://codereview.appspot.com/6545049/diff/14001/src/pkg/strings/replace.go#n...
> src/pkg/strings/replace.go:354: // one string to replace (and that string has
> more than one character).
> s/character/byte/

Done.
> 
> http://codereview.appspot.com/6545049/diff/14001/src/pkg/strings/search.go
> File src/pkg/strings/search.go (right):
> 
>
http://codereview.appspot.com/6545049/diff/14001/src/pkg/strings/search.go#ne...
> src/pkg/strings/search.go:10: //
> http://www.cs.utexas.edu/%7Emoore/publications/fstrpos.pdf
> It may be worth pointing out that (IIUC), that PDF file uses 1-based array
> indexes, not 0-based.

Done.
> 
>
http://codereview.appspot.com/6545049/diff/14001/src/pkg/strings/search.go#ne...
> src/pkg/strings/search.go:30: // shift the matching frame to align with the
next
> suffix chunk.  does not
> "does not occur again" is not a complete sentence.

Oops, done.
> 
>
http://codereview.appspot.com/6545049/diff/14001/src/pkg/strings/search.go#ne...
> src/pkg/strings/search.go:32: // next occur at index 1, so goodSuffixSkip[3]
==
> len(shift)+len(suffix)
> s/next occur/which next occurs (in right-to-left order)/ ?

Done.
> 
>
http://codereview.appspot.com/6545049/diff/14001/src/pkg/strings/search.go#ne...
> src/pkg/strings/search.go:40: // from the back is found to be in position 4,
the
> matching suffix is not
> It's probably worth mentioning that the suffix is "xabc". But I think it's
> confusing how you say "position 4" and the suffix has length 4, but that's
only
> a concidence because the suffix is derived as pattern[4+1:]. I know that
you're
> referring to the examples from the actual Boyer-Moore paper, but is it
possible
> to use a different example that's less coincidental? Add that example to
> search_test.go, but don't remove the Boyer-Moore examples.

I shifted the example down to index 3, so the numbers are all unique.
> 
>
http://codereview.appspot.com/6545049/diff/14001/src/pkg/strings/search.go#ne...
> src/pkg/strings/search.go:41: // found elsewhere in the pattern. However, the
> final "abc" is a prefix of
> s/final/leftmost/, unless I've totally confused myself and you mean rightmost.

It's "abc" as in the rightmost chunk of bytes in "xxabc". I would have said
suffix, but that sounded confusing as the suffix of the suffix.
> 
>
http://codereview.appspot.com/6545049/diff/14001/src/pkg/strings/search_test.go
> File src/pkg/strings/search_test.go (right):
> 
>
http://codereview.appspot.com/6545049/diff/14001/src/pkg/strings/search_test....
> src/pkg/strings/search_test.go:12: var finderNextTests = []struct {
> I'd move this into the TestFinderNext func; they don't need to be global.

Done.
> 
> func TestFinderNext(t *testing.T) {
>   testCases := []struct{
>     pat, text string
>     index     int
>   }{
>     // etc
>   }
>   for _, tc := range testCases {
>     // etc
>   }
> }
> 
> Similarly for tableCreationTests.
> 
>
http://codereview.appspot.com/6545049/diff/14001/src/pkg/strings/search_test....
> src/pkg/strings/search_test.go:38: t.Errorf("stringFinder(%q, %q) got %d, want
> %d\n", tc.pat, tc.text, got, want)
> s/stringFinder/StringFind/

Done.
> 
>
http://codereview.appspot.com/6545049/diff/14001/src/pkg/strings/search_test....
> src/pkg/strings/search_test.go:52: },
> Can I get some tests where the final byte in pattern doesn't occur anywhere
else
> in pattern? For example: "abc", "ababbc".

Done.
> 
>
http://codereview.appspot.com/6545049/diff/14001/src/pkg/strings/search_test....
> src/pkg/strings/search_test.go:80: if len(tc.suf) != len(good) {
> Would it be easier to say
> if !reflect.DeepEqual(good, tc.suf) {
>   // etc
> }

Done.

[nigeltao, 2012-09-27 07:16:40]

https://codereview.appspot.com/6545049/diff/18002/src/pkg/strings/search.go
File src/pkg/strings/search.go (right):

https://codereview.appspot.com/6545049/diff/18002/src/pkg/strings/search.go#n...
src/pkg/strings/search.go:17: // and the rightmost occurence of b in pattern. If
b is not in pattern,
Occurrence has two 'r's.

https://codereview.appspot.com/6545049/diff/18002/src/pkg/strings/search.go#n...
src/pkg/strings/search.go:34: // len(shift)+len(suffix) == 3+4 == 7.
s/len(shift)/shift/, since shift is an integer? Similarly below.

https://codereview.appspot.com/6545049/diff/18002/src/pkg/strings/search.go#n...
src/pkg/strings/search.go:43: // rightmost "abc" is a prefix of the whole
pattern, so goodSuffixSkip[3]
Maybe s/rightmost "abc"/rightmost "abc" (at position 6)/ to help explain why
shift == 6?

https://codereview.appspot.com/6545049/diff/18002/src/pkg/strings/search.go#n...
src/pkg/strings/search.go:61: // Do not set the last byte to have zero distance
to itself; finding this
Reword this to emphasize the subtle < instead of <= in the for loop?

// The loop condition is < instead of <= so that the last byte does not have
// zero distance to itself. Finding this byte out of place implies that it is
// not in the last position.

https://codereview.appspot.com/6545049/diff/18002/src/pkg/strings/search.go#n...
src/pkg/strings/search.go:75: f.goodSuffixSkip[i] = lastPrefix + last - i
Add a comment that, in the terminology of the detailed comment above, lastPrefix
is shift and (last-i) is len(suffix)?

https://codereview.appspot.com/6545049/diff/18002/src/pkg/strings/search.go#n...
src/pkg/strings/search.go:81: f.goodSuffixSkip[last-suffixLen] = suffixLen +
last - i
Add a comment that, in the terminology of the detailed comment above, (last-i)
is shift and suffixLen is len(suffix), right?? Maybe rename suffixLen as
lenSuffix?

https://codereview.appspot.com/6545049/diff/18002/src/pkg/strings/search_test.go
File src/pkg/strings/search_test.go (right):

https://codereview.appspot.com/6545049/diff/18002/src/pkg/strings/search_test...
src/pkg/strings/search_test.go:89: // if len(tc.suf) != len(good) {
Delete.

[Eric Roshan Eisner, 2012-09-27 15:24:19]

On 2012/09/27 07:16:40, nigeltao wrote:
> https://codereview.appspot.com/6545049/diff/18002/src/pkg/strings/search.go
> File src/pkg/strings/search.go (right):
> 
>
https://codereview.appspot.com/6545049/diff/18002/src/pkg/strings/search.go#n...
> src/pkg/strings/search.go:17: // and the rightmost occurence of b in pattern.
If
> b is not in pattern,
> Occurrence has two 'r's.

Done.
> 
>
https://codereview.appspot.com/6545049/diff/18002/src/pkg/strings/search.go#n...
> src/pkg/strings/search.go:34: // len(shift)+len(suffix) == 3+4 == 7.
> s/len(shift)/shift/, since shift is an integer? Similarly below.

Done.
> 
>
https://codereview.appspot.com/6545049/diff/18002/src/pkg/strings/search.go#n...
> src/pkg/strings/search.go:43: // rightmost "abc" is a prefix of the whole
> pattern, so goodSuffixSkip[3]
> Maybe s/rightmost "abc"/rightmost "abc" (at position 6)/ to help explain why
> shift == 6?

Done.
> 
>
https://codereview.appspot.com/6545049/diff/18002/src/pkg/strings/search.go#n...
> src/pkg/strings/search.go:61: // Do not set the last byte to have zero
distance
> to itself; finding this
> Reword this to emphasize the subtle < instead of <= in the for loop?
> 
> // The loop condition is < instead of <= so that the last byte does not have
> // zero distance to itself. Finding this byte out of place implies that it is
> // not in the last position.

Done.
> 
>
https://codereview.appspot.com/6545049/diff/18002/src/pkg/strings/search.go#n...
> src/pkg/strings/search.go:75: f.goodSuffixSkip[i] = lastPrefix + last - i
> Add a comment that, in the terminology of the detailed comment above,
lastPrefix
> is shift and (last-i) is len(suffix)?

Done. Would it be easier to follow if I inlined the detailed comments with the
construction code instead of the struct?
> 
>
https://codereview.appspot.com/6545049/diff/18002/src/pkg/strings/search.go#n...
> src/pkg/strings/search.go:81: f.goodSuffixSkip[last-suffixLen] = suffixLen +
> last - i
> Add a comment that, in the terminology of the detailed comment above, (last-i)
> is shift and suffixLen is len(suffix), right?? Maybe rename suffixLen as
> lenSuffix?

Done.
> 
>
https://codereview.appspot.com/6545049/diff/18002/src/pkg/strings/search_test.go
> File src/pkg/strings/search_test.go (right):
> 
>
https://codereview.appspot.com/6545049/diff/18002/src/pkg/strings/search_test...
> src/pkg/strings/search_test.go:89: // if len(tc.suf) != len(good) {
> Delete.

Done.

[nigeltao, 2012-09-28 02:32:57]

LGTM.

Submitting...

https://codereview.appspot.com/6545049/diff/14002/src/pkg/strings/search.go
File src/pkg/strings/search.go (right):

https://codereview.appspot.com/6545049/diff/14002/src/pkg/strings/search.go#n...
src/pkg/strings/search.go:76: // lastPrefix is the shift, and (last-i) is
len(suffix)
Add a full stop.

https://codereview.appspot.com/6545049/diff/14002/src/pkg/strings/search.go#n...
src/pkg/strings/search.go:83: // (last-i) is the shift, and lenSuffix is
len(suffix)
Add a full stop.

https://codereview.appspot.com/6545049/diff/14002/src/pkg/strings/search_test.go
File src/pkg/strings/search_test.go (right):

https://codereview.appspot.com/6545049/diff/14002/src/pkg/strings/search_test...
src/pkg/strings/search_test.go:82: t.Errorf("boyerMoore(%q) bad char table for
byte %c got %d want %d", tc.pattern, i, got, want)
s/bad char table for byte %c/bad['%c']/

[nigeltao, 2012-09-28 02:34:40]

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

strings: implement a faster single-string Replacer

The string searching is implemented separately so other functions
may make use of it in the future.

benchmark                        old ns/op    new ns/op    delta
BenchmarkSingleMaxSkipping          125889         2474  -98.03%
BenchmarkSingleLongSuffixFail        16252         1996  -87.72%
BenchmarkSingleMatch                260793       136266  -47.75%

benchmark                         old MB/s     new MB/s  speedup
BenchmarkSingleMaxSkipping           79.43      4041.57   50.88x
BenchmarkSingleLongSuffixFail        61.65       501.81    8.14x
BenchmarkSingleMatch                 57.52       110.08    1.91x

R=nigeltao
CC=golang-dev
http://codereview.appspot.com/6545049

Committer: Nigel Tao <nigeltao@golang.org>