Avoid the KMP overhead for simple indexOf() operations.

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 893 matching lines @@
 
 
 static Object* Runtime_StringIndexOf(Arguments args) {
   NoHandleAllocation ha;
   ASSERT(args.length() == 3);
 
   CONVERT_CHECKED(String, sub, args[0]);
   CONVERT_CHECKED(String, pat, args[1]);
   Object* index = args[2];
 
+  sub->TryFlatten();
+  pat->TryFlatten();
+
   int subject_length = sub->length();
   int pattern_length = pat->length();
 
-  sub->TryFlatten();
-  pat->TryFlatten();
-
   uint32_t start_index;
   if (!Array::IndexFromObject(index, &start_index)) return Smi::FromInt(-1);
   if (pattern_length == 0) return Smi::FromInt(start_index);
 
   // Searching for one specific character is common.  For one
   // character patterns the KMP algorithm is guaranteed to slow down
   // the search, so we just run through the subject string.
   if (pattern_length == 1) {
     uint16_t pattern_char = pat->Get(0);
     for (int i = start_index; i < subject_length; i++) {
       if (sub->Get(i) == pattern_char) {
         return Smi::FromInt(i);
       }
     }
     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);
   ComputeKMPNextTable(pat, next_table);
   // Search using the 'next' table.
   int pattern_index = 0;
   // We would like to use StringInputBuffer here, but it does not have
   // the ability to start anywhere but the first character of a
   // string.  It would be nice to have efficient forward-seeking
   // support on StringInputBuffers.
@@ skipping 4012 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