You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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.
The text was updated successfully, but these errors were encountered:
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.
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.
The text was updated successfully, but these errors were encountered: