Speedup stringsearch for two byte strings

src/string-search.h

 // Copyright 2011 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #ifndef V8_STRING_SEARCH_H_
 #define V8_STRING_SEARCH_H_
 
 #include "src/isolate.h"
 #include "src/vector.h"
 
@@ skipping 170 matching lines @@
   }
 
   Isolate* isolate_;
   // The pattern to search for.
   Vector<const PatternChar> pattern_;
   // Pointer to implementation of the search.
   SearchFunction strategy_;
   // Cache value of Max(0, pattern_length() - kBMMaxShift)
   int start_;
 };
 

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

nit: two empty lines between top-level things

+template <typename T, typename U>
+inline T AlignDown(T value, U alignment) {
+  return reinterpret_cast<T>(
+      (reinterpret_cast<uintptr_t>(value) & ~(alignment - 1)));
+}
+

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

nit: two empty lines between top-level things

+template <typename PatternChar, typename SubjectChar>
+inline int FindFirstByte(Vector<const PatternChar> pattern,

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

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).

+                         Vector<const SubjectChar> subject, int index) {
+  PatternChar pattern_first_char = pattern[0];
+
+  if (sizeof(SubjectChar) == 1 && sizeof(PatternChar) == 1) {
+    const SubjectChar* pos = reinterpret_cast<const SubjectChar*>(memchr(
+        subject.start() + index, pattern_first_char, subject.length() - index));
+    if (pos == NULL) return -1;
+    return static_cast<int>(pos - subject.start());
+  } else {
+    uint8_t search_low_byte = static_cast<uint8_t>(pattern_first_char & 0xFF);
+    const SubjectChar* pos = reinterpret_cast<const SubjectChar*>(
+        memchr(subject.start() + index, search_low_byte,
+               (subject.length() - index) * sizeof(SubjectChar)));
+    if (pos == NULL) return -1;
+    pos = AlignDown(pos, sizeof(SubjectChar));

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

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.

+    return static_cast<int>(pos - subject.start());
+  }
+  return -1;
+}
 
 //---------------------------------------------------------------------
 // Single Character Pattern Search Strategy
 //---------------------------------------------------------------------
-

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

nit: keep this line

 template <typename PatternChar, typename SubjectChar>
 int StringSearch<PatternChar, SubjectChar>::SingleCharSearch(
     StringSearch<PatternChar, SubjectChar>* search,
     Vector<const SubjectChar> subject,
     int index) {
   DCHECK_EQ(1, search->pattern_.length());
   PatternChar pattern_first_char = search->pattern_[0];
-  int i = index;
   if (sizeof(SubjectChar) == 1 && sizeof(PatternChar) == 1) {
-    const SubjectChar* pos = reinterpret_cast<const SubjectChar*>(
-        memchr(subject.start() + i,
-               pattern_first_char,
-               subject.length() - i));
-    if (pos == NULL) return -1;
-    return static_cast<int>(pos - subject.start());
+    return FindFirstByte(search->pattern_, subject, index);
   } else {
     if (sizeof(PatternChar) > sizeof(SubjectChar)) {
       if (exceedsOneByte(pattern_first_char)) {
         return -1;
       }
     }
     SubjectChar search_char = static_cast<SubjectChar>(pattern_first_char);
-    int n = subject.length();
+    const int n = subject.length();
+    int i = index;
     while (i < n) {
+      i = FindFirstByte(search->pattern_, subject, i);
+      if (i == -1) return -1;
+
       if (subject[i++] == search_char) return i - 1;
     }
     return -1;
   }
 }
 
 //---------------------------------------------------------------------
 // Linear Search Strategy
 //---------------------------------------------------------------------
 
@@ skipping 16 matching lines @@
 
 // Simple linear search for short patterns. Never bails out.
 template <typename PatternChar, typename SubjectChar>
 int StringSearch<PatternChar, SubjectChar>::LinearSearch(
     StringSearch<PatternChar, SubjectChar>* search,
     Vector<const SubjectChar> subject,
     int index) {
   Vector<const PatternChar> pattern = search->pattern_;
   DCHECK(pattern.length() > 1);
   int pattern_length = pattern.length();
-  PatternChar pattern_first_char = pattern[0];
   int i = index;
   int n = subject.length() - pattern_length;
   while (i <= n) {
-    if (sizeof(SubjectChar) == 1 && sizeof(PatternChar) == 1) {
-      const SubjectChar* pos = reinterpret_cast<const SubjectChar*>(
-          memchr(subject.start() + i,
-                 pattern_first_char,
-                 n - i + 1));
-      if (pos == NULL) return -1;
-      i = static_cast<int>(pos - subject.start()) + 1;
-    } else {
-      if (subject[i++] != pattern_first_char) continue;
-    }
+    i = FindFirstByte(pattern, subject, i);
+    if (i == -1) return -1;
+    i++;
     // Loop extracted to separate function to allow using return to do
     // a deeper break.
     if (CharCompare(pattern.start() + 1,
                     subject.start() + i,
                     pattern_length - 1)) {
       return i - 1;
     }
   }
   return -1;
 }
@@ skipping 217 matching lines @@
     int index) {
   Vector<const PatternChar> pattern = search->pattern_;
   int pattern_length = pattern.length();
   // Badness is a count of how much work we have done.  When we have
   // done enough work we decide it's probably worth switching to a better
   // algorithm.
   int badness = -10 - (pattern_length << 2);
 
   // We know our pattern is at least 2 characters, we cache the first so
   // the common case of the first character not matching is faster.
-  PatternChar pattern_first_char = pattern[0];
   for (int i = index, n = subject.length() - pattern_length; i <= n; i++) {
     badness++;
     if (badness <= 0) {
-      if (sizeof(SubjectChar) == 1 && sizeof(PatternChar) == 1) {
-        const SubjectChar* pos = reinterpret_cast<const SubjectChar*>(
-            memchr(subject.start() + i,
-                   pattern_first_char,
-                   n - i + 1));
-        if (pos == NULL) {
-          return -1;
-        }
-        i = static_cast<int>(pos - subject.start());
-      } else {
-        if (subject[i] != pattern_first_char) continue;
-      }
+      i = FindFirstByte(pattern, subject, i);
+      if (i == -1) return -1;
       int j = 1;
       do {
         if (pattern[j] != subject[i + j]) {
           break;
         }
         j++;
       } while (j < pattern_length);
       if (j == pattern_length) {
         return i;
       }
@@ skipping 17 matching lines @@
                  Vector<const SubjectChar> subject,
                  Vector<const PatternChar> pattern,
                  int start_index) {
   StringSearch<PatternChar, SubjectChar> search(isolate, pattern);
   return search.Search(subject, start_index);
 }
 
 }}  // namespace v8::internal
 
 #endif  // V8_STRING_SEARCH_H_