Optimize StringImpl::find when searching for patterns with length > 1

Optimize StringImpl::find when searching for patterns with length > 1

StringImpl::find for any pattern that has a length greater than one
uses a running hash algorithm which can be quite expensive when the
search string is not present at all, for example when looking for
\r characters when doing replace("\r\n", "\n");

We can optimize this case by first looking for the first chararcter
since a single letter search is very fast, then starting the search
from there. This is not very different from what v8 does in
v8/src/string-search.h where they do a single letter scan to find the
first letter and then do a naive search several times (at least 10)
before switching to a better search algorithm like Boyer-Moore-Horspool.
We should consider doing something fancy like that too, but for now
lets just start by doing the single letter search at the start.

In blink the primary user of find on long strings is actually replacing
\r\n with \n anyway, and \r is pretty rare, so this optimization makes
sense. Long term we should both consider a better search algorithm like
v8 uses and also consider a specialized routine for normalizing new
lines.

This patch results in a 125% speed up on the DOM/textarea-dom benchmark
on my 2013 Mac Pro.

[esprehn, 2016-07-02 02:12:56]

Description was changed from

==========
Optimize StringImpl::find when searching for patterns with length > 1

StringImpl::find for any pattern that has a length greater than one
uses a running hash algorithm which can be quite expensive when the
search string is not present at all, for example when looking for
\r characters when doing replace("\r\n", "\n");

We can optimize this case by first looking for the first chararcter
since a single letter search is very fast, then starting the search
from there. This is not very different from what v8 does in
v8/src/string-search.h where they do a single letter scan to find the
first letter and then do a naive search several times (at least 10)
before switching to a better search algorithm like Boyer-Moore-Horspool.
We should consider doing something fancy like that too, but for now
lets just start by doing the single letter search at the start.

In blink the primary user of find on long strings is actually replacing
\r\n with \n anyway, and \r is pretty rare, so this optimization makes
sense. Long term we should both consider a better search algorithm like
v8 uses and also consider a specialized routine for normalizing new
lines.

This patch results in a 125% speed up on the DOM/textarea-dom benchmark.
==========

to

==========
Optimize StringImpl::find when searching for patterns with length > 1

StringImpl::find for any pattern that has a length greater than one
uses a running hash algorithm which can be quite expensive when the
search string is not present at all, for example when looking for
\r characters when doing replace("\r\n", "\n");

We can optimize this case by first looking for the first chararcter
since a single letter search is very fast, then starting the search
from there. This is not very different from what v8 does in
v8/src/string-search.h where they do a single letter scan to find the
first letter and then do a naive search several times (at least 10)
before switching to a better search algorithm like Boyer-Moore-Horspool.
We should consider doing something fancy like that too, but for now
lets just start by doing the single letter search at the start.

In blink the primary user of find on long strings is actually replacing
\r\n with \n anyway, and \r is pretty rare, so this optimization makes
sense. Long term we should both consider a better search algorithm like
v8 uses and also consider a specialized routine for normalizing new
lines.

This patch results in a 125% speed up on the DOM/textarea-dom benchmark
on my 2013 Mac Pro.
==========

[esprehn, 2016-07-02 02:13:00]

The CQ bit was checked by esprehn@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-07-02 02:13:11]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[esprehn, 2016-07-02 02:19:16]

The CQ bit was unchecked by esprehn@chromium.org

[esprehn, 2016-07-02 02:21:48]

The CQ bit was checked by esprehn@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-07-02 02:22:07]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-07-02 03:37:28]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-07-02 03:37:28]

Dry run: This issue passed the CQ dry run.