Go: bytes: generic Index too slow

[randall77]

For non-amd64/s390x, we have a generic version of Index, written in Go.
It can be slow because it uses a combination of IndexByte (for the first byte of the needle string) and Equal. When the first byte appears in most of the haystack string, it can be really slow.
For some reason this code doesn't use Rabin-Karp, the standard solution to this problem. The amd64 and s390x cases do.
I think we just need to update the generic Index to use Rabin-Karp.

Noticed while looking at CL 76050.

[gopherbot]

Change https://golang.org/cl/76070 mentions this issue: bytes,strings: in generic Index, use mix of IndexByte and Rabin-Karp

[randall77]

And strings.Index has the opposite problem, it uses Rabin-Karp but never IndexByte, even when it would be faster.

[dongweigogo]

And strings.Index has the opposite problem, it uses Rabin-Karp but never IndexByte, even when it would be faster.

I've seen many gophers complaining about that.

[vielmetti]

Also noted here:

https://blog.cloudflare.com/arm-takes-wing/

Go regexp performance is not very good on Falkor. In the medium and hard tests it takes second place, thanks to the higher core count, but Skylake is significantly faster still.

Doing some profiling shows that a lot of the time is spent in the function bytes.IndexByte. This function has an assembly implementation for amd64 (runtime.indexbytebody), but generic implementation for Go. The easy regexp tests spend most of time in this function, which explains the even wider gap.