KMP string search using direct memory access and templates for type specialization.

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 24 matching lines @@
 #include "compiler.h"
 #include "cpu.h"
 #include "dateparser.h"
 #include "debug.h"
 #include "execution.h"
 #include "jsregexp.h"
 #include "platform.h"
 #include "runtime.h"
 #include "scopeinfo.h"
 #include "v8threads.h"
+#include "smart-pointer.h"
 
 namespace v8 { namespace internal {
 
 
 #define RUNTIME_ASSERT(value) do {                                   \
   if (!(value)) return IllegalOperation();                           \
 } while (false)
 
 // Cast the given object to a value of the specified type and store
 // it in a variable with the given name.  If the object is not of the
@@ skipping 863 matching lines @@
   uint32_t code;
   if (Array::IndexFromObject(args[0], &code)) {
     if (code <= 0xffff) {
       return Heap::LookupSingleCharacterStringFromCode(code);
     }
   }
   return Heap::empty_string();
 }
 
 
-static inline void ComputeKMPNextTable(String* pattern, int next_table[]) {
+static Vector<const char> ToAsciiVector(String *string) {
+  ASSERT(string->IsAscii());
+  ASSERT(string->IsFlat());
+
+  int offset = 0;
+  int length = string->length();
+  for(;;) {

[Christian Plesner Hansen, 2008/10/06 12:47:19]

Flat strings are relatively simple in structure so it should be possible to get
a hold of the string contents with straight-line code.

[Lasse Reichstein, 2008/10/07 09:16:28]

Done.

+    switch(string->representation_tag()) {
+    case kSeqStringTag: {
+      AsciiString* seq = AsciiString::cast(string);
+      char* start = reinterpret_cast<char*>(seq->GetCharsAddress());
+      return Vector<const char>(start + offset, length);
+    }
+    case kExternalStringTag: {
+      ExternalAsciiString* ext = ExternalAsciiString::cast(string);
+      const char* start = ext->resource()->data();
+      return Vector<const char>(start + offset, length);
+    }
+    case kConsStringTag: {
+      ConsString* cons = ConsString::cast(string);
+      ASSERT(String::cast(cons->second())->length() == 0);
+      string = String::cast(cons->first());
+      continue;
+    }
+    case kSlicedStringTag: {
+      SlicedString* sliced = SlicedString::cast(string);
+      offset += sliced->start();
+      string = String::cast(sliced->buffer());
+      continue;
+    }
+    default:
+      UNREACHABLE();
+    }
+  }
+}
+
+
+static Vector<const uc16> ToUC16Vector(String *string) {
+  ASSERT(string->IsTwoByteString());
+  ASSERT(string->IsFlat());
+
+  int offset = 0;
+  int length = string->length();
+  for(;;) {
+    switch(string->representation_tag()) {
+    case kSeqStringTag: {
+      TwoByteString* seq = TwoByteString::cast(string);
+      uc16* start = reinterpret_cast<uc16*>(seq->GetCharsAddress());
+      return Vector<const uc16>(start + offset, length);
+    }
+    case kExternalStringTag: {
+      ExternalTwoByteString* ext = ExternalTwoByteString::cast(string);
+      const uc16* start =
+          reinterpret_cast<const uc16*>(ext->resource()->data());
+      return Vector<const uc16>(start + offset, length);
+    }
+    case kConsStringTag: {
+      ConsString* cons = ConsString::cast(string);
+      ASSERT(String::cast(cons->second())->length() == 0);
+      string = String::cast(cons->first());
+      continue;
+    }
+    case kSlicedStringTag: {
+      SlicedString* sliced = SlicedString::cast(string);
+      offset += sliced->start();
+      string = String::cast(sliced->buffer());
+      continue;
+    }
+    default:
+      UNREACHABLE();
+    }
+  }
+}
+
+
+template <typename schar, typename pchar>
+static int SingleCharIndexOf(
+    Vector<const schar> string,

[Christian Plesner Hansen, 2008/10/06 12:47:19]

This argument should be on the same line as the function header with the
remaining arguments below it, indented to the same level.

[Lasse Reichstein, 2008/10/07 09:16:28]

Done.

+    pchar pattern_char,
+    int start_index) {
+  for (int i = start_index, n = string.length(); i < n; i++) {

[Christian Plesner Hansen, 2008/10/06 12:47:19]

I would move the declaration of n out before the loop.

[Lasse Reichstein, 2008/10/07 09:16:28]

I consider
 for (int i = ..., n = ...; i<n; i++)
an idiom, and prefer to limit the scope of n to where it's needed.

+    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++) {

[Christian Plesner Hansen, 2008/10/06 12:47:19]

I would move the declaration of n out just before the loop.

+    if (subject[i] != pattern_first_char) continue;
+
+    bool failure = false;
+    for (int j = 1; j < pattern_length; j++) {
+      if (pattern[j] != subject[j+i]) {
+        failure = true;
+        break;
+      }
+    }
+    if (!failure) {
+      return i;
+    }
+  }
+  return -1;
+}
+
+// Full KMP pattern match.
+template <typename schar, typename pchar>  // Pattern & subject char types
+static int KMPIndexOf(
+    Vector<const schar> subject,
+    Vector<const pchar> pattern,
+    int start_index) {
+  int subject_length = subject.length();
+  int pattern_length = pattern.length();
+  SmartPointer<int> next_table(NewArray<int>(pattern_length));
+
+  // Compute KMP "next" table
   int i = 0;
   int j = -1;
   next_table[0] = -1;
 
-  Access<StringInputBuffer> buffer(&string_input_buffer);
-  buffer->Reset(pattern);
-  int length = pattern->length();
-  uint16_t p = buffer->GetNext();
+  int length = pattern.length();

[Christian Plesner Hansen, 2008/10/06 12:47:19]

Isn't this identical to pattern_length?

[Lasse Reichstein, 2008/10/07 09:16:28]

Indeed, it should be removed. Done.

+  pchar p = pattern[0];
   while (i < length - 1) {
-    while (j > -1 && p != pattern->Get(j)) {
+    while (j > -1 && p != pattern[j]) {
       j = next_table[j];
     }
     i++;
     j++;
-    p = buffer->GetNext();
-    if (p == pattern->Get(j)) {
+    p = pattern[i];
+    if (p == pattern[j]) {
       next_table[i] = next_table[j];
     } else {
       next_table[i] = j;
     }
   }
-}
-
-
-int Runtime::StringMatchKmp(String* sub, String* pat, int start_index) {
-  sub->TryFlatten();
-  pat->TryFlatten();
-
-  int subject_length = sub->length();
-  int pattern_length = pat->length();
-
-  if (start_index > subject_length) return -1;
-  if (pattern_length == 0) return start_index;
+
+  // Search using the 'next' table.
+  int pattern_index = 0;
+  int subject_index = start_index;
+  while (subject_index < subject_length) {
+    schar subject_char = subject[subject_index];
+    while (pattern_index > -1 && pattern[pattern_index] != subject_char) {
+      pattern_index = next_table[pattern_index];
+    }
+    pattern_index++;
+    subject_index++;
+    if (pattern_index >= pattern_length) {
+      return subject_index - pattern_index;
+    }
+  }
+  return -1;
+}
+
+// Dispatch to different algorithms for different length of pattern/subject
+template <typename schar, typename pchar>
+static int StringMatchKMP(Vector<const schar> sub, Vector<const pchar> pat, int 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 i;
-      }
-    }
-    return -1;
+  if (pat.length() == 1) {
+    return SingleCharIndexOf(sub, pat[0], start_index);
   }
 
   // For small searches, KMP is not worth the setup overhead.
-  if (subject_length < 100) {
-    // 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.
-    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++) {
-        if (pat->Get(j) != sub->Get(j + i)) break;
-        if (j == pattern_length - 1) return i;
-      }
-    }
-    return -1;
+  if (sub.length() - start_index < 100) {
+    return SimpleIndexOf(sub, pat, start_index);
   }
 
   // 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.
-  int subject_index = start_index;
-  while (subject_index < subject_length) {
-    uint16_t subject_char = sub->Get(subject_index);
-    while (pattern_index > -1 && pat->Get(pattern_index) != subject_char) {
-      pattern_index = next_table[pattern_index];
-    }
-    pattern_index++;
-    subject_index++;
-    if (pattern_index >= pattern_length) {
-      DeleteArray(next_table);
-      return subject_index - pattern_index;
-    }
-  }
-  DeleteArray(next_table);
-  return -1;
+  return KMPIndexOf(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::StringMatchKmp(String* sub, String* pat, int start_index) {
+  ASSERT(0 <= start_index);
+  ASSERT(start_index <= sub->length());
+
+  if (pat->length() == 0) return start_index;
+
+  sub->TryFlatten();

[Lasse Reichstein, 2008/10/07 09:16:28]

Doesn't handle failure to flatten.
Changed to the handle based FlattenString.

+  pat->TryFlatten();
+  AssertNoAllocation heap_allocation_block;  // ensure vectors stay valid
+  // dispatch on type of strings
+  if (pat->is_ascii()) {
+    Vector<const char> pat_vector = ToAsciiVector(pat);
+    if (sub->is_ascii()) {
+      return StringMatchKMP(ToAsciiVector(sub), pat_vector, start_index);
+    }
+    return StringMatchKMP(ToUC16Vector(sub), pat_vector, start_index);
+  }
+  Vector<const uc16> pat_vector = ToUC16Vector(pat);
+  if (sub->is_ascii()) {
+    return StringMatchKMP(ToAsciiVector(sub), pat_vector, start_index);
+  }
+  return StringMatchKMP(ToUC16Vector(sub), pat_vector, start_index);
 }
 
 
 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];
@@ skipping 4022 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