code review 7314095: strings: better mean complexity for Count and Index.

strings: better mean complexity for Count and Index.

The O(n+m) complexity is obtained probabilistically
by using Rabin-Karp algorithm, which provides the needed complexity
unless exceptional collisions occur, without memory allocation.

benchmark                 old ns/op    new ns/op    delta
BenchmarkIndexHard1         6532331      4045886  -38.06%
BenchmarkIndexHard2         8178173      4038975  -50.61%
BenchmarkIndexHard3         6973687      4042591  -42.03%
BenchmarkCountHard1         6270864      4071090  -35.08%
BenchmarkCountHard2         7838039      4072853  -48.04%
BenchmarkCountHard3         6697828      4071964  -39.20%
BenchmarkIndexTorture       2730546        28934  -98.94%
BenchmarkCountTorture       2729622        29064  -98.94%

Fixes issue 4600.

[remyoudompheng, 2013-02-14 00:01:22]

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

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

[remyoudompheng, 2013-02-14 00:02:33]

I would be interested in benchmark comparisons with, for example, KMP-like
algorithms which I think were proposed last year to replace strings.Index

[rsc, 2013-02-14 02:44:07]

Regardless of how it compares to KMP, I think this is worth doing.

https://codereview.appspot.com/7314095/diff/5001/src/pkg/strings/strings.go
File src/pkg/strings/strings.go (right):

https://codereview.appspot.com/7314095/diff/5001/src/pkg/strings/strings.go#n...
src/pkg/strings/strings.go:45: l := len(sep)
There's no benefit to this anymore, now that len(sep) registerizes, and it's
confusing to remember what l is. Please change the code to use len(sep)
everywhere.

https://codereview.appspot.com/7314095/diff/5001/src/pkg/strings/strings.go#n...
src/pkg/strings/strings.go:59: const Prime = 16777619
// Rabin-Karp string matching.
const Prime = 16777619

https://codereview.appspot.com/7314095/diff/5001/src/pkg/strings/strings.go#n...
src/pkg/strings/strings.go:60: // Hash sep.
Pull this into a function.

seph, pow := hashstr(sep)

https://codereview.appspot.com/7314095/diff/5001/src/pkg/strings/strings.go#n...
src/pkg/strings/strings.go:77: h *= Prime
this will be easier to skim - since it appears multiple times - on one line

h = h*Prime + uint32(s[i])

https://codereview.appspot.com/7314095/diff/5001/src/pkg/strings/strings.go#n...
src/pkg/strings/strings.go:81: for i := l; i < len(s); i++ {
If you rotate the termination condition into the body you can avoid the
duplication after the loop.

for i := l;; i++ {
    if h == seph && i-len(sep) >= lastmatch && s[i-len(sep):i] == sep {
        n++
        lastmatch = i
    }
    if i >= len(s) {
        break;
    }
    h = h*Prime + uint32(s[i])
    h -= pow*uint32(s[i-len(sep)])
}

https://codereview.appspot.com/7314095/diff/5001/src/pkg/strings/strings.go#n...
src/pkg/strings/strings.go:96: if lastmatch <= len(s)-l && h == sephash &&
s[len(s)-l:] == sep {
drop

[nigeltao, 2013-02-14 08:13:59]

https://codereview.appspot.com/7314095/diff/5001/src/pkg/strings/strings.go
File src/pkg/strings/strings.go (right):

https://codereview.appspot.com/7314095/diff/5001/src/pkg/strings/strings.go#n...
src/pkg/strings/strings.go:59: const Prime = 16777619
On 2013/02/14 02:44:07, rsc wrote:
> // Rabin-Karp string matching.
> const Prime = 16777619

s/Prime/prime/ ?

[remyoudompheng, 2013-02-16 09:48:56]

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

Please take another look.

[remyoudompheng, 2013-02-16 09:49:35]

Somehow it was slowed down a bit by the changes: new benchcmp results

benchmark                old ns/op    new ns/op    delta
BenchmarkIndexHard1        6533916      4043108  -38.12%
BenchmarkIndexHard2        8175214      4030707  -50.70%
BenchmarkIndexHard3        6974282      4032687  -42.18%
BenchmarkCountHard1        6271606      4862624  -22.47%
BenchmarkCountHard2        7838938      4860459  -38.00%
BenchmarkCountHard3        6701418      4876190  -27.24%
BenchmarkIndexTorture      2731199        28922  -98.94%
BenchmarkCountTorture      2729458        31309  -98.85%

https://codereview.appspot.com/7314095/diff/5001/src/pkg/strings/strings.go
File src/pkg/strings/strings.go (right):

https://codereview.appspot.com/7314095/diff/5001/src/pkg/strings/strings.go#n...
src/pkg/strings/strings.go:45: l := len(sep)
On 2013/02/14 02:44:07, rsc wrote:
> There's no benefit to this anymore, now that len(sep) registerizes, and it's
> confusing to remember what l is. Please change the code to use len(sep)
> everywhere.

Done.

https://codereview.appspot.com/7314095/diff/5001/src/pkg/strings/strings.go#n...
src/pkg/strings/strings.go:59: const Prime = 16777619
On 2013/02/14 02:44:07, rsc wrote:
> // Rabin-Karp string matching.
> const Prime = 16777619

Done.

https://codereview.appspot.com/7314095/diff/5001/src/pkg/strings/strings.go#n...
src/pkg/strings/strings.go:59: const Prime = 16777619
On 2013/02/14 08:13:59, nigeltao wrote:
> On 2013/02/14 02:44:07, rsc wrote:
> > // Rabin-Karp string matching.
> > const Prime = 16777619
> 
> s/Prime/prime/ ?

Done.

https://codereview.appspot.com/7314095/diff/5001/src/pkg/strings/strings.go#n...
src/pkg/strings/strings.go:60: // Hash sep.
On 2013/02/14 02:44:07, rsc wrote:
> Pull this into a function.
> 
> seph, pow := hashstr(sep)
> 

Done.

https://codereview.appspot.com/7314095/diff/5001/src/pkg/strings/strings.go#n...
src/pkg/strings/strings.go:77: h *= Prime
On 2013/02/14 02:44:07, rsc wrote:
> this will be easier to skim - since it appears multiple times - on one line
> 
> h = h*Prime + uint32(s[i])

Done.

https://codereview.appspot.com/7314095/diff/5001/src/pkg/strings/strings.go#n...
src/pkg/strings/strings.go:81: for i := l; i < len(s); i++ {
On 2013/02/14 02:44:07, rsc wrote:
> If you rotate the termination condition into the body you can avoid the
> duplication after the loop.
> 
> for i := l;; i++ {
>     if h == seph && i-len(sep) >= lastmatch && s[i-len(sep):i] == sep {
>         n++
>         lastmatch = i
>     }
>     if i >= len(s) {
>         break;
>     }
>     h = h*Prime + uint32(s[i])
>     h -= pow*uint32(s[i-len(sep)])
> }

Done.

https://codereview.appspot.com/7314095/diff/5001/src/pkg/strings/strings.go#n...
src/pkg/strings/strings.go:96: if lastmatch <= len(s)-l && h == sephash &&
s[len(s)-l:] == sep {
On 2013/02/14 02:44:07, rsc wrote:
> drop

Done.

[rsc, 2013-02-16 13:43:36]

LGTM

Very nice.

[Donovan, 2013-02-16 16:19:14]

Some possible to changes to improve performance on the Count function.

Was intrigued to see this come up. I've applied the same algorithm for finding
longest common substrings in another project:

https://github.com/donovanhide/superfastmatch-go/blob/master/src/document/uti...

The (admittedly messy) Rabin Karp implementation hashes runes rather than bytes
and returns unicode positions rather than byte positions. It does need to
allocate a buffer though to store the previous hashes for the start rune
subtraction...

Rolling hashes are great :-)

https://codereview.appspot.com/7314095/diff/11001/src/pkg/strings/strings.go
File src/pkg/strings/strings.go (right):

https://codereview.appspot.com/7314095/diff/11001/src/pkg/strings/strings.go#...
src/pkg/strings/strings.go:87: if lastmatch <= i-len(sep) && h == hashsep &&
s[i-len(sep):i] == sep {
if h == hashsep && lastmatch <= i-len(sep) && s[i-len(sep):i] == sep 

Gives a more likely short-curcuit evaluation

https://codereview.appspot.com/7314095/diff/11001/src/pkg/strings/strings.go#...
src/pkg/strings/strings.go:95: h -= pow * uint32(s[i-len(sep)])
Reordered to:

		h *= primeRK
		if i >= len(s) {
			break
		}
		h += uint32(s[i])
		h -= pow * uint32(s[i-len(sep)])

gives better performance

[remyoudompheng, 2013-02-17 12:00:19]

Hello rsc@golang.org, donovanhide@gmail.com, remyoudompheng@gmail.com (cc:
golang-dev@googlegroups.com),

Please take another look.

[remyoudompheng, 2013-02-17 12:05:59]

Now:

benchmark                 old ns/op    new ns/op    delta
BenchmarkIndexHard1         6532331      4045886  -38.06%
BenchmarkIndexHard2         8178173      4038975  -50.61%
BenchmarkIndexHard3         6973687      4042591  -42.03%
BenchmarkCountHard1         6270864      4071090  -35.08%
BenchmarkCountHard2         7838039      4072853  -48.04%
BenchmarkCountHard3         6697828      4071964  -39.20%
BenchmarkIndexTorture       2730546        28934  -98.94%
BenchmarkCountTorture       2729622        29064  -98.94%


On 2013/02/16 16:19:14, Donovan wrote:
> Some possible to changes to improve performance on the Count function.
> 
> Was intrigued to see this come up. I've applied the same algorithm for finding
> longest common substrings in another project:
> 
>
https://github.com/donovanhide/superfastmatch-go/blob/master/src/document/uti...
> 
> The (admittedly messy) Rabin Karp implementation hashes runes rather than
bytes
> and returns unicode positions rather than byte positions. It does need to
> allocate a buffer though to store the previous hashes for the start rune
> subtraction...
> 
> Rolling hashes are great :-)

Git also uses Rabin-like hashes for its delta encoding, I have written a Go
implementation here:
https://github.com/remyoudompheng/gigot/blob/master/gitdelta/diff.go

> https://codereview.appspot.com/7314095/diff/11001/src/pkg/strings/strings.go
> File src/pkg/strings/strings.go (right):
> 
>
https://codereview.appspot.com/7314095/diff/11001/src/pkg/strings/strings.go#...
> src/pkg/strings/strings.go:87: if lastmatch <= i-len(sep) && h == hashsep &&
> s[i-len(sep):i] == sep {
> if h == hashsep && lastmatch <= i-len(sep) && s[i-len(sep):i] == sep 
> 
> Gives a more likely short-curcuit evaluation

Done.

>
https://codereview.appspot.com/7314095/diff/11001/src/pkg/strings/strings.go#...
> src/pkg/strings/strings.go:95: h -= pow * uint32(s[i-len(sep)])
> Reordered to:
> 
> 		h *= primeRK
> 		if i >= len(s) {
> 			break
> 		}
> 		h += uint32(s[i])
> 		h -= pow * uint32(s[i-len(sep)])
> 
> gives better performance

I did not observe a difference. If you did, I think the compiler should be
improved to push back MUL instructions.

[remyoudompheng, 2013-02-17 12:21:13]

*** Submitted as https://code.google.com/p/go/source/detail?r=6f23480a76e1 ***

strings: better mean complexity for Count and Index.

The O(n+m) complexity is obtained probabilistically
by using Rabin-Karp algorithm, which provides the needed complexity
unless exceptional collisions occur, without memory allocation.

benchmark                 old ns/op    new ns/op    delta
BenchmarkIndexHard1         6532331      4045886  -38.06%
BenchmarkIndexHard2         8178173      4038975  -50.61%
BenchmarkIndexHard3         6973687      4042591  -42.03%
BenchmarkCountHard1         6270864      4071090  -35.08%
BenchmarkCountHard2         7838039      4072853  -48.04%
BenchmarkCountHard3         6697828      4071964  -39.20%
BenchmarkIndexTorture       2730546        28934  -98.94%
BenchmarkCountTorture       2729622        29064  -98.94%

Fixes issue 4600.

R=rsc, donovanhide, remyoudompheng
CC=golang-dev
https://codereview.appspot.com/7314095