* Added badness-check to trigger computation of good-suffix table in Boyer-Moore.

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 980 matching lines @@
 
 // buffers reused by BoyerMoore
 static int bad_char_occurence[kBMAlphabetSize];
 static BMGoodSuffixBuffers bmgs_buffers;
 
 // Restricted 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,

[Erik Corry, 2008/10/14 12:42:05]

This function is too big now.  It has to be split up.  I would suggest:

BuildBadCharTable
BoyerMooreHorspool
BuildSuffixTable
BoyerMoore

                              Vector<const pchar> pattern,
                              int start_index) {
   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;
 
   // Run forwards to populate bad_char_table, so that *last* instance
   // of character equivalence class is the one registered.
   // Notice: Doesn't include last character.
   for (int i = 0; i < kBMAlphabetSize; i++) {
     bad_char_occurence[i] = start - 1;
   }
   for (int i = start; i < m; i++) {
     uc32 c = pattern[i];
     bad_char_occurence[c % kBMAlphabetSize] = i;
     if (sizeof(schar) == 1 &&
         sizeof(pchar) > 1 &&
         c > String::kMaxAsciiCharCode) {
       return -1;
     }
   }
   // End of Bad Char computation.
 
-  // Compute Good Suffix shift table.
-  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) {
-        bmgs_buffers.shift(suffix) = suffix - i;
+
+  int badness = 0;  // How bad we are doing without a good-suffix table.
+  int idx;  // No matches found prior to this index.
+  // Perform search
+  for (idx = start_index; idx <= n - m;) {
+    int j = m - 1;
+    schar c;
+    while (j >= 0 && pattern[j] == (c = subject[idx + j])) j--;
+    if (j < 0) {
+      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 we are not done, we got here because we should build the Good Suffix
+  // table and continue searching.
+  if (idx <= n - m) {
+    // 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) {
+          bmgs_buffers.shift(suffix) = suffix - i;
+        }
+        suffix = bmgs_buffers.suffix(suffix);
       }
-      suffix = bmgs_buffers.suffix(suffix);
-    }
-    i--;
-    suffix--;
-    bmgs_buffers.suffix(i) = suffix;
-    if (suffix == m) {
-      // no suffix to extend, so we check against last_char only.
-      while (i > start && pattern[i - 1] != last_char) {
-        if (bmgs_buffers.shift(m) == len) {
-          bmgs_buffers.shift(m) = m - i;
+      i--;
+      suffix--;
+      bmgs_buffers.suffix(i) = suffix;
+      if (suffix == m) {
+        // no suffix to extend, so we check against last_char only.
+        while (i > start && pattern[i - 1] != last_char) {
+          if (bmgs_buffers.shift(m) == len) {
+            bmgs_buffers.shift(m) = m - i;
+          }
+          i--;
+          bmgs_buffers.suffix(i) = m;
         }
-        i--;
-        bmgs_buffers.suffix(i) = m;
-      }
-      if (i > start) {
-        i--;
-        suffix--;
-        bmgs_buffers.suffix(i) = suffix;
+        if (i > start) {
+          i--;
+          suffix--;
+          bmgs_buffers.suffix(i) = suffix;
+        }
       }
     }
-  }
-  if (suffix < m) {
-    for (int i = start; i <= m; i++) {
-      if (bmgs_buffers.shift(i) == len) {
-        bmgs_buffers.shift(i) = suffix - start;
-      }
-      if (i == suffix) {
-        suffix = bmgs_buffers.suffix(suffix);
+    if (suffix < m) {
+      for (int i = start; i <= m; i++) {
+        if (bmgs_buffers.shift(i) == len) {
+          bmgs_buffers.shift(i) = suffix - start;
+        }
+        if (i == suffix) {
+          suffix = bmgs_buffers.suffix(suffix);
+        }
       }
     }
+    // End of Good Suffix computation.
+
+    // 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;
+      }
+    } while (idx <= n - m);
   }
-  // End of Good Suffix computation.
 
-
-  // Perform search
-  for (int i = start_index; i <= n - m;) {
-    int j = m - 1;
-    schar c;
-    while (j >= 0 && pattern[j] == (c = subject[i + j])) j--;
-    if (j < 0) {
-      return i;
-    } else if (j < start) {
-      // we have matched more than our tables allow us to be smart about.
-      i += 1;
-    } else {
-      int gs_shift = bmgs_buffers.shift(j + 1);
-      int bc_occ = bad_char_occurence[c % kBMAlphabetSize];
-      int bc_shift = j - bc_occ;
-      i += (gs_shift > bc_shift) ? gs_shift : bc_shift;
-    }
-  }
   return -1;
 }
 
 template <typename schar, typename pchar>
 static int SingleCharIndexOf(Vector<const schar> string,
                              pchar pattern_char,
                              int start_index) {
   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.
 template <typename pchar, typename schar>
 static int SimpleIndexOf(Vector<const schar> subject,
                          Vector<const pchar> pattern,
                          int start_index) {
   int pattern_length = pattern.length();
   int subject_length = subject.length();
   // 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++) {
     if (subject[i] != pattern_first_char) continue;
     int j = 1;
-    while (pattern[j] == subject[j+i]) {
+    do {
+      if (pattern[j] != subject[j+i]) {
+        break;
+      }
       j++;
-      if (j == pattern_length) {
-        return i;
-      }
+    } while (j < pattern_length);
+    if (j == pattern_length) {
+      return i;
     }
   }
   return -1;
 }
 
 // Dispatch to different algorithms for different length of pattern/subject
 template <typename schar, typename pchar>
 static int StringMatchStrategy(Vector<const schar> sub,
                                Vector<const pchar> pat,
                                int start_index) {
   int pattern_length = pat.length();
   ASSERT(pattern_length > 1);
 
   // For small searches, a complex sort is not worth the setup overhead.
   int subject_length = sub.length() - start_index;
-  if (subject_length < 100 || pattern_length < 4) {
+  if (subject_length < 100 || pattern_length < 8) {
     return SimpleIndexOf(sub, pat, start_index);
   }
 
   return BoyerMooreIndexOf(sub, pat, start_index);
 }
 
 // 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,
@@ skipping 4116 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