Speedup stringsearch for two byte strings

Speedup stringsearch for two byte strings

Uses the lower byte with memchr which is
significantly faster than a naive compare

Performance difference with bench (http://hastebin.com/xuxexataso.js):

old                             new

single character                single character
Κ found at 922                  Κ found at 922
3324                            616
㎡ found at 13217               ㎡ found at 13217
42366                           4931
က found at 4096                 က found at 4096
13369                           9836
＀ found at 65280                ＀ found at 65280
207472                          36149
ﾥ found at 65445                ﾥ found at 65445
209344                          36666
  found at 8197                   found at 8197
26731                           11757
倂 found at 20482               倂 found at 20482
66071                           17193

linear search                   linear search
ΚΛ found at 922                 ΚΛ found at 922
4112                            504
㎡㎢ found at 13217             ㎡㎢ found at 13217
55105                           5119
ﾥﾦ found at 65445               ﾥﾦ found at 65445
268016                          35496

linear + bmh search             linear + bmh search
ΚΛΜΝΞΟΠΡ found at 922           ΚΛΜΝΞΟΠΡ found at 922
2897                            522
ﾥﾦﾧﾨﾩﾪﾫﾬ found at 65445         ﾥﾦﾧﾨﾩﾪﾫﾬ found at 65445
167687                          158465

Committed: https://crrev.com/fced280f37588f8a232a414201276e053117e9ea
Cr-Commit-Position: refs/heads/master@{#30587}

[skomski, 2015-09-02 22:24:05]

karl@skomski.com changed reviewers:
+ danno@chromium.org

[skomski, 2015-09-03 13:42:49]

karl@skomski.com changed reviewers:
+ mstarzinger@chromium.org

[Jakob Kummerow, 2015-09-03 16:46:32]

jkummerow@chromium.org changed reviewers:
+ jkummerow@chromium.org

[Jakob Kummerow, 2015-09-03 16:46:33]

https://codereview.chromium.org/1303033012/diff/1/src/string-search.h
File src/string-search.h (left):

https://codereview.chromium.org/1303033012/diff/1/src/string-search.h#oldcode196
src/string-search.h:196: 
nit: keep this line

https://codereview.chromium.org/1303033012/diff/1/src/string-search.h
File src/string-search.h (right):

https://codereview.chromium.org/1303033012/diff/1/src/string-search.h#newcode191
src/string-search.h:191: 
nit: two empty lines between top-level things

https://codereview.chromium.org/1303033012/diff/1/src/string-search.h#newcode197
src/string-search.h:197: 
nit: two empty lines between top-level things

https://codereview.chromium.org/1303033012/diff/1/src/string-search.h#newcode199
src/string-search.h:199: inline int FindFirstByte(Vector<const PatternChar>
pattern,
Since this works with two-byte strings too, I'd call it FindFirstCharacter
(especially if you fix it to actually find the first character and not just a
nonbinding guess, see below).

https://codereview.chromium.org/1303033012/diff/1/src/string-search.h#newcode214
src/string-search.h:214: pos = AlignDown(pos, sizeof(SubjectChar));
I don't think this is correct. If memchr() found the search_low_byte as the high
byte of one of the characters in the subject, it can't just AlignDown() and
return success. SingleCharSearch() below doesn't care because it performs the
necessary check itself, but the other two callers would compute bogus results.
You have two options:

(1) Keep the behavior of FindFirstByte, and robustify the callers. Since this
behavior is a rather surprising contract, it must be properly documented in the
method name and/or a comment ("MaybeFindFirstCharacter" or somesuch).

(2) Fix the behavior. You'll need to check if the found byte is the low byte of
a character, and if the high byte matches too, and loop (call memchr() again) if
either of those checks fails. I'd prefer this option. You can then drop line 245
below.

[skomski, 2015-09-03 22:28:17]

On 2015/09/03 16:46:33, Jakob wrote:
> https://codereview.chromium.org/1303033012/diff/1/src/string-search.h
> File src/string-search.h (left):
> 
>
https://codereview.chromium.org/1303033012/diff/1/src/string-search.h#oldcode196
> src/string-search.h:196: 
> nit: keep this line
> 
> https://codereview.chromium.org/1303033012/diff/1/src/string-search.h
> File src/string-search.h (right):
> 
>
https://codereview.chromium.org/1303033012/diff/1/src/string-search.h#newcode191
> src/string-search.h:191: 
> nit: two empty lines between top-level things
> 
>
https://codereview.chromium.org/1303033012/diff/1/src/string-search.h#newcode197
> src/string-search.h:197: 
> nit: two empty lines between top-level things
> 
>
https://codereview.chromium.org/1303033012/diff/1/src/string-search.h#newcode199
> src/string-search.h:199: inline int FindFirstByte(Vector<const PatternChar>
> pattern,
> Since this works with two-byte strings too, I'd call it FindFirstCharacter
> (especially if you fix it to actually find the first character and not just a
> nonbinding guess, see below).
> 
>
https://codereview.chromium.org/1303033012/diff/1/src/string-search.h#newcode214
> src/string-search.h:214: pos = AlignDown(pos, sizeof(SubjectChar));
> I don't think this is correct. If memchr() found the search_low_byte as the
high
> byte of one of the characters in the subject, it can't just AlignDown() and
> return success. SingleCharSearch() below doesn't care because it performs the
> necessary check itself, but the other two callers would compute bogus results.
> You have two options:
> 
> (1) Keep the behavior of FindFirstByte, and robustify the callers. Since this
> behavior is a rather surprising contract, it must be properly documented in
the
> method name and/or a comment ("MaybeFindFirstCharacter" or somesuch).
> 
> (2) Fix the behavior. You'll need to check if the found byte is the low byte
of
> a character, and if the high byte matches too, and loop (call memchr() again)
if
> either of those checks fails. I'd prefer this option. You can then drop line
245
> below.

Thanks; Updated based on your second suggestion and added a test to check the
alignment issue.

[Jakob Kummerow, 2015-09-04 12:14:01]

Thanks, LGTM.

[Jakob Kummerow, 2015-09-04 12:14:07]

The CQ bit was checked by jkummerow@chromium.org

[commit-bot: I haz the power, 2015-09-04 12:14:12]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1303033012/40001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1303033012/40001

[commit-bot: I haz the power, 2015-09-04 12:37:45]

Committed patchset #3 (id:40001)

[commit-bot: I haz the power, 2015-09-04 12:37:58]

Patchset 3 (id:??) landed as
https://crrev.com/fced280f37588f8a232a414201276e053117e9ea
Cr-Commit-Position: refs/heads/master@{#30587}

[Michael Achenbach, 2015-09-04 13:00:15]

A revert of this CL (patchset #3 id:40001) has been created in
https://codereview.chromium.org/1331433002/ by machenbach@chromium.org.

The reason for reverting is: [Sheriff] Breaks fuzzer and msan:
http://build.chromium.org/p/client.v8/builders/V8%20Fuzzer/builds/4773

Repro with:
tools/fuzz-harness.sh out/Debug/d8
(in a ninja Debug build)

Msan:
http://build.chromium.org/p/client.v8/builders/V8%20Linux%20-%20arm64%20-%20s....