* Changed string search to full-blown Boyer-Moore.

Most operations are faster than before.

[Lasse Reichstein, 2008-10-13 14:06:43]

Please review the changes. 
Also let's consider whether our benchmarks are adequate. A lot of them seem to
repetitions of the same short string, which is bad for Boyer-Moore's shift
tables.

[Erik Corry, 2008-10-14 08:12:14]

LGTM

http://codereview.chromium.org/7114/diff/1/2
File src/runtime.cc (right):

http://codereview.chromium.org/7114/diff/1/2#newcode959
Line 959: static const int kMaxAsciiChar = 0x7f;
Please use String::kMaxAsciiChar

http://codereview.chromium.org/7114/diff/1/2#newcode962
Line 962: // shift. Only allow the last kBMMaxShift characters of the needle
allow -> allows

http://codereview.chromium.org/7114/diff/1/2#newcode964
Line 964: class BMGoodSuffixBuffers {
Should inherit from AllStatic

http://codereview.chromium.org/7114/diff/1/2#newcode965
Line 965: private:
Style guide dictates public before private.

http://codereview.chromium.org/7114/diff/1/2#newcode972
Line 972: void init(int needle_length) {
should be inline

http://codereview.chromium.org/7114/diff/1/2#newcode1028
Line 1028: // End of Bad Char computation
Terminate comments with '.'

http://codereview.chromium.org/7114/diff/1/2#newcode1084
Line 1084: // we have matched more than our tables allow us to be smart about.
It seems like here we could still use the bad char table?

http://codereview.chromium.org/7114/diff/1/2#newcode1121
Line 1121: while (pattern[j] == subject[j+i]) {
This reads one too far in pattern and subject, no?

[Lasse Reichstein, 2008-10-14 09:21:03]

http://codereview.chromium.org/7114/diff/1/2
File src/runtime.cc (right):

http://codereview.chromium.org/7114/diff/1/2#newcode959
Line 959: static const int kMaxAsciiChar = 0x7f;
On 2008/10/14 08:12:14, Erik Corry wrote:
> Please use String::kMaxAsciiChar

Done.
I did use it, just forgot to remove the old constant.

http://codereview.chromium.org/7114/diff/1/2#newcode962
Line 962: // shift. Only allow the last kBMMaxShift characters of the needle
On 2008/10/14 08:12:14, Erik Corry wrote:
> allow -> allows

Done.

http://codereview.chromium.org/7114/diff/1/2#newcode964
Line 964: class BMGoodSuffixBuffers {
On 2008/10/14 08:12:14, Erik Corry wrote:
> Should inherit from AllStatic

Done.

http://codereview.chromium.org/7114/diff/1/2#newcode965
Line 965: private:
On 2008/10/14 08:12:14, Erik Corry wrote:
> Style guide dictates public before private.

Done.

http://codereview.chromium.org/7114/diff/1/2#newcode972
Line 972: void init(int needle_length) {
On 2008/10/14 08:12:14, Erik Corry wrote:
> should be inline

Done.

http://codereview.chromium.org/7114/diff/1/2#newcode1028
Line 1028: // End of Bad Char computation
On 2008/10/14 08:12:14, Erik Corry wrote:
> Terminate comments with '.'

Done.

http://codereview.chromium.org/7114/diff/1/2#newcode1084
Line 1084: // we have matched more than our tables allow us to be smart about.
On 2008/10/14 08:12:14, Erik Corry wrote:
> It seems like here we could still use the bad char table?

Not currently, but we only index the last kBMMaxShift characters of the pattern.
At the time of failure, all recorded occurences are after the failing character,
and will cause a negative shift.
If we indexed the entire pattern, we might still be able to use bad-char shifts
on characters with a last occurence not in the last 256 chars.

http://codereview.chromium.org/7114/diff/1/2#newcode1121
Line 1121: while (pattern[j] == subject[j+i]) {
On 2008/10/14 08:12:14, Erik Corry wrote:
> This reads one too far in pattern and subject, no?

No, we know that the pattern is at least two chars long.
I'll add an ASSERT instead of just the comment.