* Start string search with simple algorithm, and fall trough to 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 1132 matching lines @@
                              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.
+// 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 start_index,
+                         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;
   // 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;
     do {
-      if (pattern[j] != subject[j+i]) {
+      if (pattern[j] != subject[i+j]) {
         break;
       }
       j++;
     } 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
 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);
+  ASSERT(pat.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 < 8) {
-    return SimpleIndexOf(sub, pat, start_index);
-  }
-
-  return BoyerMooreIndexOf(sub, pat, start_index);
+  bool complete;
+  int idx = SimpleIndexOf(sub, pat, start_index, 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);
   ASSERT(start_index <= sub->length());
@@ skipping 4112 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