Avoid the KMP overhead for simple indexOf() operations.

src/runtime.cc

Index: src/runtime.cc
diff --git a/src/runtime.cc b/src/runtime.cc
index d1f5e9d253c97472a21b59a941e2779c5da49027..be7255f8ebec58969adf533b07f5c31c50ebe30e 100644
--- a/src/runtime.cc
+++ b/src/runtime.cc
@@ -911,12 +911,12 @@ static Object* Runtime_StringIndexOf(Arguments args) {
   CONVERT_CHECKED(String, pat, args[1]);
   Object* index = args[2];
 
-  int subject_length = sub->length();
-  int pattern_length = pat->length();
-
   sub->TryFlatten();
   pat->TryFlatten();
 
+  int subject_length = sub->length();
+  int pattern_length = pat->length();
+
   uint32_t start_index;
   if (!Array::IndexFromObject(index, &start_index)) return Smi::FromInt(-1);
   if (pattern_length == 0) return Smi::FromInt(start_index);
@@ -934,8 +934,24 @@ static Object* Runtime_StringIndexOf(Arguments args) {
     return Smi::FromInt(-1);
   }
 
-  // For patterns with a length larger than one character we use the KMP
-  // algorithm.
+  // For small searches, the ability to skip the search length is not worth
+  // the overhead of setting up KMP.  TODO get more accurate cutoffs here.

[Mads Ager (chromium), 2008/09/19 12:20:22]

Either leave out the TODO or report a bug and use the bug ID here: TODO(bugid):
get more...

+  if (subject_length < 100) {
+    // We know our pattern is at least 2 characters, we cache the first so the
+    // the common case of the first character not matching is fast.

[Mads Ager (chromium), 2008/09/19 12:20:22]

the the -> that the

+    uint16_t pattern_first_char = pat->Get(0);
+    for (int i = start_index; i + pattern_length <= subject_length; i++) {
+      if (sub->Get(i) != pattern_first_char) continue;
+
+      for (int j = 1; j < pattern_length; ++j) {

[Mads Ager (chromium), 2008/09/19 12:20:22]

I think we use j++ consistently in the rest of the code.  At least this should
be consistent with the outer for loop.

+        if (pat->Get(j) != sub->Get(j + i)) break;
+        if (j == pattern_length - 1) return Smi::FromInt(i);
+      }
+    }
+    return Smi::FromInt(-1);
+  }
+
+  // For patterns with a larger length we use the KMP algorithm.
   //
   // Compute the 'next' table.
   int* next_table = NewArray<int>(pattern_length);