Optimized special case of not matching the last char of the needle in BM string match.

src/runtime.cc

 // Copyright 2006-2008 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 937 matching lines @@
       return Heap::LookupSingleCharacterStringFromCode(code);
     }
   }
   return Heap::empty_string();
 }
 
 
 // Cap on the maximal shift in the Boyer-Moore implementation. By setting a
 // limit, we can fix the size of tables.
 static const int kBMMaxShift = 0xff;
-static const int kBMAlphabetSize = 0x100;  // Reduce alphabet to this size.
+// Reduce alphabet to this size.
+static const int kBMAlphabetSize = 0x100;
+// For patterns below this length, the skip length of Boyer-Moore is too short
+// to compensate for the algorithmic overhead compared to simple brute force.
+static const int kBMMinPatternLength = 5;
 
 // Holds the two buffers used by Boyer-Moore string search's Good Suffix
 // shift. Only allows the last kBMMaxShift characters of the needle
 // to be indexed.
 class BMGoodSuffixBuffers: public AllStatic {
  public:
   BMGoodSuffixBuffers() {}
   inline void init(int needle_length) {
     ASSERT(needle_length > 1);
     int start = needle_length < kBMMaxShift ? 0 : needle_length - kBMMaxShift;
@@ skipping 18 matching lines @@
   int *biased_suffixes_;
   int *biased_good_suffix_shift_;
   DISALLOW_COPY_AND_ASSIGN(BMGoodSuffixBuffers);
 };
 
 // buffers reused by BoyerMoore
 static int bad_char_occurence[kBMAlphabetSize];
 static BMGoodSuffixBuffers bmgs_buffers;
 
 // Compute the bad-char table for Boyer-Moore in the static buffer.
-// Return false if the pattern contains non-ASCII characters that cannot be
-// in the searched string.
 template <typename pchar>
 static void BoyerMoorePopulateBadCharTable(Vector<const pchar> pattern,
                                           int start) {
   // Run forwards to populate bad_char_table, so that *last* instance
   // of character equivalence class is the one registered.
   // Notice: Doesn't include the last character.
   for (int i = 0; i < kBMAlphabetSize; i++) {
     bad_char_occurence[i] = start - 1;
   }
-  for (int i = start; i < pattern.length(); i++) {
-    bad_char_occurence[pattern[i] % kBMAlphabetSize] = i;
+  for (int i = start; i < pattern.length() - 1; i++) {
+    pchar c = pattern[i];
+    int bucket = c % kBMAlphabetSize;
+    bad_char_occurence[bucket] = i;
   }
 }
 
 template <typename pchar>
 static void BoyerMoorePopulateGoodSuffixTable(Vector<const pchar> pattern,
-                                              int start,
-                                              int len) {
+                                              int start) {
   int m = pattern.length();
+  int len = m - start;
   // Compute Good Suffix tables.
   bmgs_buffers.init(m);
 
   bmgs_buffers.shift(m-1) = 1;
   bmgs_buffers.suffix(m) = m + 1;
   pchar last_char = pattern[m - 1];
   int suffix = m + 1;
   for (int i = m; i > start;) {
     for (pchar c = pattern[i - 1]; suffix <= m && c != pattern[suffix - 1];) {
       if (bmgs_buffers.shift(suffix) == len) {
@@ skipping 25 matching lines @@
       if (bmgs_buffers.shift(i) == len) {
         bmgs_buffers.shift(i) = suffix - start;
       }
       if (i == suffix) {
         suffix = bmgs_buffers.suffix(suffix);
       }
     }
   }
 }
 
-// Restricted Boyer-Moore string matching. Restricts tables to a
+
+// Restricted simplified Boyer-Moore string matching. Restricts tables to a
 // suffix of long pattern strings and handles only equivalence classes
 // of the full alphabet. This allows us to ensure that tables take only
 // a fixed amount of space.
 template <typename schar, typename pchar>
-static int BoyerMooreIndexOf(Vector<const schar> subject,
-                             Vector<const pchar> pattern,
-                             int start_index) {
+static int BoyerMooreSimplified(Vector<const schar> subject,
+                                Vector<const pchar> pattern,
+                                int start_index,
+                                bool& complete) {
+  int n = subject.length();
   int m = pattern.length();
-  int n = subject.length();
-
   // Only preprocess at most kBMMaxShift last characters of pattern.
   int start = m < kBMMaxShift ? 0 : m - kBMMaxShift;
-  int len = m - start;
 
   BoyerMoorePopulateBadCharTable(pattern, start);
 
-  int badness = 0;  // How bad we are doing without a good-suffix table.
+  int badness = -m;  // How bad we are doing without a good-suffix table.
   int idx;  // No matches found prior to this index.
+  pchar last_char = pattern[m - 1];
   // Perform search
   for (idx = start_index; idx <= n - m;) {
     int j = m - 1;
-    schar c;
+    int c;
+    while (last_char != (c = subject[idx + j])) {
+      int bc_occ = bad_char_occurence[c % kBMAlphabetSize];
+      int shift = j - bc_occ;
+      idx += shift;
+      badness += 1 - shift;  // at most zero, so badness cannot increase.
+      if (idx > n - m) {
+        complete = true;
+        return -1;
+      }
+    }
+    j--;
     while (j >= 0 && pattern[j] == (c = subject[idx + j])) j--;
     if (j < 0) {
+      complete = true;
       return idx;
     } else {
       int bc_occ = bad_char_occurence[c % kBMAlphabetSize];
       int shift = bc_occ < j ? j - bc_occ : 1;
       idx += shift;
       // Badness increases by the number of characters we have
       // checked, and decreases by the number of characters we
       // can skip by shifting. It's a measure of how we are doing
       // compared to reading each character exactly once.
       badness += (m - j) - shift;
-      if (badness > m) break;
+      if (badness > 0) {
+        complete = false;
+        return idx;
+      }
     }
   }
+  complete = true;
+  return -1;
+}
 
-  // If we are not done, we got here because we should build the Good Suffix
-  // table and continue searching.
-  if (idx <= n - m) {
-    BoyerMoorePopulateGoodSuffixTable(pattern, start, len);
-    // Continue search from i.
-    do {
-      int j = m - 1;
-      schar c;
-      while (j >= 0 && pattern[j] == (c = subject[idx + j])) j--;
-      if (j < 0) {
-        return idx;
-      } else if (j < start) {
-        // we have matched more than our tables allow us to be smart about.
-        idx += 1;
-      } else {
-        int gs_shift = bmgs_buffers.shift(j + 1);
-        int bc_occ = bad_char_occurence[c % kBMAlphabetSize];
-        int bc_shift = j - bc_occ;
-        idx += (gs_shift > bc_shift) ? gs_shift : bc_shift;
+
+template <typename schar, typename pchar>
+static int BoyerMooreIndexOf(Vector<const schar> subject,
+                             Vector<const pchar> pattern,
+                             int idx) {
+  int n = subject.length();
+  int m = pattern.length();
+  // Only preprocess at most kBMMaxShift last characters of pattern.
+  int start = m < kBMMaxShift ? 0 : m - kBMMaxShift;
+
+  // Build the Good Suffix table and continue searching.
+  BoyerMoorePopulateGoodSuffixTable(pattern, start);
+  pchar last_char = pattern[m - 1];
+  // Continue search from i.
+  do {
+    int j = m - 1;
+    schar c;
+    while (last_char != (c = subject[idx + j])) {
+      int shift = j - bad_char_occurence[c % kBMAlphabetSize];
+      idx += shift;
+      if (idx > n - m) {
+        return -1;
       }
-    } while (idx <= n - m);
-  }
+    }
+    while (j >= 0 && pattern[j] == (c = subject[idx + j])) j--;
+    if (j < 0) {
+      return idx;
+    } else if (j < start) {
+      // we have matched more than our tables allow us to be smart about.
+      idx += 1;
+    } else {
+      int gs_shift = bmgs_buffers.shift(j + 1);       // Good suffix shift.
+      int bc_occ = bad_char_occurence[c % kBMAlphabetSize];
+      int shift = j - bc_occ;                         // Bad-char shift.
+      shift = (gs_shift > shift) ? gs_shift : shift;
+      idx += shift;
+    }
+  } while (idx <= n - m);
 
   return -1;
 }
 
-template <typename schar, typename pchar>
+
+template <typename schar>
 static int SingleCharIndexOf(Vector<const schar> string,
-                             pchar pattern_char,
+                             uc16 pattern_char,
                              int start_index) {
+  if (sizeof(schar) == 1 && pattern_char > String::kMaxAsciiCharCode) {
+    return -1;
+  }
   for (int i = start_index, n = string.length(); i < n; i++) {
     if (pattern_char == string[i]) {
       return i;
     }
   }
   return -1;
 }
 
 // Trivial string search for shorter strings.
 // On return, if "complete" is set to true, the return value is the
 // final result of searching for the patter in the subject.
 // If "complete" is set to false, the return value is the index where
 // further checking should start, i.e., it's guaranteed that the pattern
 // does not occur at a position prior to the returned index.
 template <typename pchar, typename schar>
 static int SimpleIndexOf(Vector<const schar> subject,
                          Vector<const pchar> pattern,
-                         int start_index,
+                         int idx,
                          bool &complete) {
-  int pattern_length = pattern.length();
-  int subject_length = subject.length();
-  // Badness is a count of how many extra times the same character
-  // is checked. We compare it to the index counter, so we start
-  // it at the start_index, and give it a little discount to avoid
-  // very early bail-outs.
-  int badness = start_index - 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.
   pchar pattern_first_char = pattern[0];
 
-  for (int i = start_index, n = subject_length - pattern_length; i <= n; i++) {
+  for (int i = idx, n = subject.length() - pattern.length(); i <= n; i++) {
+    badness++;
+    if (badness > 0) {
+      complete = false;
+      return (i);
+    }
     if (subject[i] != pattern_first_char) continue;
     int j = 1;
     do {
       if (pattern[j] != subject[i+j]) {
         break;
       }
       j++;
-    } while (j < pattern_length);
-    if (j == pattern_length) {
+    } while (j < pattern.length());
+    if (j == pattern.length()) {
       complete = true;
       return i;
     }
     badness += j;
-    if (badness > i) {  // More than one extra character on average.
-      complete = false;
-      return (i + 1);  // No matches up to index i+1.
-    }
   }
   complete = true;
   return -1;
 }
 
-// Dispatch to different algorithms for different length of pattern/subject
+// Simple indexOf that never bails out. For short patterns only.
+template <typename pchar, typename schar>
+static int SimpleIndexOf(Vector<const schar> subject,
+                         Vector<const pchar> pattern,
+                         int idx) {
+  pchar pattern_first_char = pattern[0];
+  for (int i = idx, n = subject.length() - pattern.length(); i <= n; i++) {
+    if (subject[i] != pattern_first_char) continue;
+    int j = 1;
+    do {
+      if (pattern[j] != subject[i+j]) {
+        break;
+      }
+      j++;
+    } while (j < pattern.length());
+    if (j == pattern.length()) {
+      return i;
+    }
+  }
+  return -1;
+}
+
+
+// Dispatch to different algorithms.
 template <typename schar, typename pchar>
 static int StringMatchStrategy(Vector<const schar> sub,
                                Vector<const pchar> pat,
                                int start_index) {
   ASSERT(pat.length() > 1);
 
   // We have an ASCII haystack and a non-ASCII needle. Check if there
   // really is a non-ASCII character in the needle and bail out if there
   // is.
   if (sizeof(pchar) > 1 && sizeof(schar) == 1) {
     for (int i = 0; i < pat.length(); i++) {
       uc16 c = pat[i];
       if (c > String::kMaxAsciiCharCode) {
         return -1;
       }
     }
   }
-  // For small searches, a complex sort is not worth the setup overhead.
+  if (pat.length() < kBMMinPatternLength) {
+    // We don't believe fancy searching can ever be more efficient.
+    // The max shift of Boyer-Moore on a pattern of this length does
+    // not compensate for the overhead.
+    return SimpleIndexOf(sub, pat, start_index);
+  }
+  // Try algorithms in order of increasing setup cost and expected performance.
   bool complete;
   int idx = SimpleIndexOf(sub, pat, start_index, complete);
   if (complete) return idx;
+  idx = BoyerMooreSimplified(sub, pat, idx, complete);
+  if (complete) return idx;
   return BoyerMooreIndexOf(sub, pat, idx);
 }
 
 // Perform string match of pattern on subject, starting at start index.
 // Caller must ensure that 0 <= start_index <= sub->length(),
 // and should check that pat->length() + start_index <= sub->length()
 int Runtime::StringMatch(Handle<String> sub,
                          Handle<String> pat,
                          int start_index) {
   ASSERT(0 <= start_index);
@@ skipping 4113 matching lines @@
 
 void Runtime::PerformGC(Object* result) {
   Failure* failure = Failure::cast(result);
   // Try to do a garbage collection; ignore it if it fails. The C
   // entry stub will throw an out-of-memory exception in that case.
   Heap::CollectGarbage(failure->requested(), failure->allocation_space());
 }
 
 
 } }  // namespace v8::internal