code review 102560043: strings: use Rabin-Karp algorithm for LastIndex

strings: use Robin-Karp algorithm for LastIndex

benchmark                  old ns/op     new ns/op     delta
BenchmarkSingleMatch       49443         52275         +5.73%
BenchmarkIndex             28.8          27.4          -4.86%
BenchmarkLastIndex         14.5          14.0          -3.45%
BenchmarkLastIndexHard1    3982782       2309200       -42.02%
BenchmarkLastIndexHard2    3985562       2287715       -42.60%
BenchmarkLastIndexHard3    3555259       2282866       -35.79%

[ruiu, 2014-06-20 05:58:01]

Hello golang-codereviews@googlegroups.com,

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

[ality, 2014-06-20 07:37:49]

s/Robin/Rabin/ in the CL description.

  Anthony

[josharian, 2014-06-23 19:30:24]

Naive question: Wikipedia says "The Rabin–Karp algorithm is inferior for single
pattern searching to Knuth–Morris–Pratt algorithm, Boyer–Moore string search
algorithm and other faster single pattern string searching algorithms because of
its slow worst case behavior." If that is so, should one of the other algorithms
be considered instead?

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

https://codereview.appspot.com/102560043/diff/60001/src/pkg/strings/strings.g...
src/pkg/strings/strings.go:214: h *= primeRK
This is the third copy/paste of the hash updating code, which might be enough to
warrant an unexported RK type with a few methods.

[ruiu, 2014-06-23 20:10:31]

On 2014/06/23 19:30:24, josharian wrote:
> Naive question: Wikipedia says "The Rabin–Karp algorithm is inferior for
single
> pattern searching to Knuth–Morris–Pratt algorithm, Boyer–Moore string search
> algorithm and other faster single pattern string searching algorithms because
of
> its slow worst case behavior." If that is so, should one of the other
algorithms
> be considered instead?

Boyer-Moore algorithm's preprocessing overhead is much larger than the
Rabin-Karp algorithm, and BM is not fast if a pattern is short. I once tried to
use RK instead of BM in strings/search.go for short patterns (len(pattern)<8),
and it was faster than BM.

It's hard to say RK is a better fit than BM here because it depends on pattern
and text strings. I also don't know why RK was chosen in the first place.
However I guess pattern is usually short, so RK is at least not a bad choice.

> https://codereview.appspot.com/102560043/diff/60001/src/pkg/strings/strings.go
> File src/pkg/strings/strings.go (right):
> 
>
https://codereview.appspot.com/102560043/diff/60001/src/pkg/strings/strings.g...
> src/pkg/strings/strings.go:214: h *= primeRK
> This is the third copy/paste of the hash updating code, which might be enough
to
> warrant an unexported RK type with a few methods.

Will do.

[josharian, 2014-06-23 20:33:14]

> However I guess pattern is usually short, so RK is at least not a bad choice.

I just checked and empirically, this is true. Of 3489 instances of
strings.LastIndex in a recent corpus of public code, 3310 used a constant
separator. Of those, the head of the length distribution was:

count		separator length
2880		1
 148		5
 126		3
 104		2

These numbers are a bit fuzzy, since I was using
awk/grep/eyeball-sanity-checking instead of an AST parser, but they're
order-of-magnitude correct.

Thanks for the explanation.

[ruiu, 2014-06-24 04:26:37]

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

https://codereview.appspot.com/102560043/diff/60001/src/pkg/strings/strings.g...
src/pkg/strings/strings.go:214: h *= primeRK
These repetitions are actually different enough that abstracting them will
complicates the code instead of simplify. But I found that this code can be
shorter and simpler -- I sent it out as a separate refactoring CL 109160044.
Please review.

[josharian, 2014-06-24 16:34:07]

Donovan's comments in CL 109160044 led me to run the Count benchmarks with this
CL:

benchmark                            old ns/op     new ns/op     delta       
BenchmarkCountHard1                  1708868       1892391       +10.74%     
BenchmarkCountHard2                  1712510       1847561       +7.89%      
BenchmarkCountHard3                  1726918       1867820       +8.16%      
BenchmarkCountTorture                11981         12157         +1.47%      
BenchmarkCountTortureOverlapping     5531017       6302287       +13.94%

[ruiu, 2014-06-24 16:57:02]

Huh, interesting. What architecture is your CPU?

[josharian, 2014-06-24 17:18:17]

> Huh, interesting. What architecture is your CPU?

x86_64. It's a recent retina MBP.

[ruiu, 2014-06-25 06:17:47]

The slowdown was caused by the same reason as CL 109160044
(the last refactoring change I sent to you). Looks like
we shouldn't touch the existing code at least for now, so I
just added for LastIndex. Pasted the results of all benchmark
tests in strings.

[josharian, 2014-06-26 18:22:56]

LGTM but I'd like a fresh set of eyes to also have a look

[dave_cheney.net, 2014-07-01 00:54:49]

Nigel, do you have time to review this ?

[gobot, 2014-07-01 00:55:18]

R=nigeltao@golang.org (assigned by dave@cheney.net)

[josharian, 2014-08-29 00:41:17]

Ping, Nigel.

[ioe, 2014-08-29 06:54:40]

One testing bug and an possible optimization.

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

https://codereview.appspot.com/102560043/diff/100001/src/pkg/strings/strings....
src/pkg/strings/strings.go:195: case n >= len(s):
Please split the n > len(s) case out like in Index. 
It was separate because "s == sep" is a (possibly expensive for larger sep)
string compare and the length compare is much cheaper.

https://codereview.appspot.com/102560043/diff/100001/src/pkg/strings/strings_...
File src/pkg/strings/strings_test.go (right):

https://codereview.appspot.com/102560043/diff/100001/src/pkg/strings/strings_...
src/pkg/strings/strings_test.go:178: }
This is testing Index instead of LastIndex. Copy'n'Paste error?

[ruiu, 2014-08-29 18:32:38]

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

https://codereview.appspot.com/102560043/diff/100001/src/pkg/strings/strings....
src/pkg/strings/strings.go:195: case n >= len(s):
On 2014/08/29 06:54:40, ioe wrote:
> Please split the n > len(s) case out like in Index. 
> It was separate because "s == sep" is a (possibly expensive for larger sep)
> string compare and the length compare is much cheaper.

Done.

https://codereview.appspot.com/102560043/diff/100001/src/pkg/strings/strings_...
File src/pkg/strings/strings_test.go (right):

https://codereview.appspot.com/102560043/diff/100001/src/pkg/strings/strings_...
src/pkg/strings/strings_test.go:178: }
On 2014/08/29 06:54:40, ioe wrote:
> This is testing Index instead of LastIndex. Copy'n'Paste error?

Done.

[nigeltao, 2014-09-01 07:43:41]

LGTM.

[nigeltao, 2014-09-01 07:48:30]

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

strings: use Rabin-Karp algorithm for LastIndex.

benchmark                  old ns/op     new ns/op     delta
BenchmarkSingleMatch       49443         52275         +5.73%
BenchmarkIndex             28.8          27.4          -4.86%
BenchmarkLastIndex         14.5          14.0          -3.45%
BenchmarkLastIndexHard1    3982782       2309200       -42.02%
BenchmarkLastIndexHard2    3985562       2287715       -42.60%
BenchmarkLastIndexHard3    3555259       2282866       -35.79%

LGTM=josharian, nigeltao
R=golang-codereviews, ality, josharian, bradfitz, dave, nigeltao, gobot,
nightlyone
CC=golang-codereviews
https://codereview.appspot.com/102560043

Committer: Nigel Tao <nigeltao@golang.org>