Leverage Lasse's StringSearch object to speed up calculations of script ...

src/handles.cc

 // Copyright 2009 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 18 matching lines @@
 
 #include "accessors.h"
 #include "api.h"
 #include "arguments.h"
 #include "bootstrapper.h"
 #include "compiler.h"
 #include "debug.h"
 #include "execution.h"
 #include "global-handles.h"
 #include "natives.h"
+#include "string-search.h"
 #include "runtime.h"
 #include "stub-cache.h"
 
 namespace v8 {
 namespace internal {
 
 
 v8::ImplementationUtilities::HandleScopeData HandleScope::current_ =
     { NULL, NULL, 0 };
 
@@ skipping 448 matching lines @@
 
   Handle<String> src(String::cast(script->source()));
 
   Handle<FixedArray> array = CalculateLineEnds(src, true);
 
   script->set_line_ends(*array);
   ASSERT(script->line_ends()->IsFixedArray());
 }
 
 
-Handle<FixedArray> CalculateLineEnds(Handle<String> src,
-                                     bool with_imaginary_last_new_line) {
-  const int src_len = src->length();
-  Handle<String> new_line = Factory::NewStringFromAscii(CStrVector("\n"));
+template <typename SourceChar>
+static Handle<FixedArray> CalculateLineEnds(Vector<const SourceChar> src,
+                                            bool with_last_line) {

[Lasse Reichstein, 2010/11/18 08:11:47]

I wonder whether this function is performance critical or not.

[sandholm, 2010/11/18 08:39:10]

Me too. Let's see what happens. 

+  const int src_len = src.length();
+  StringSearch<char, SourceChar> search(CStrVector("\n"));
 
   // Pass 1: Identify line count.
   int line_count = 0;
   int position = 0;
   while (position != -1 && position < src_len) {
-    position = Runtime::StringMatch(src, new_line, position);
+    position = search.Search(src, position);

[Lasse Reichstein, 2010/11/18 08:11:47]

Not calling Runtime::StringMatch is good (it's an "externally visible" function,
so it shouldn't be reused).

However, if the function is performance critical, this seems overkill for a
single-character string.
It will always do the "SingleCharSearch", which boils down to something like:
 int index;
 if (sizeof(SourceChar) == 1) { 
   char* pos = reinterpret_cast<char*>(
         memchr(src.start() + position, '\n', src.length()));
   index = pos ? static_cast<, n = , n = int>(pos - src.start()) : -1;
 } else { 
   ASSERT(sizeof(SourceChar) == 2);
   int n = src.length();
   for (index = position; index < n; index++) {
     if (src[i] == '\n') {
       break;
     }
   }
   if (index == n) index = -1;
 }

(not tested!)

I'd rather inline thee code, or extract it from SingleCharSearch to a static
function/template that can be called from outside the string-search object as
well.

[sandholm, 2010/11/18 08:39:10]

Makes sense. If there is any performance gain from this change, I'll inline in
another change.

     if (position != -1) {
       position++;
-    }
-    if (position != -1) {
       line_count++;
-    } else if (with_imaginary_last_new_line) {
+    } else if (with_last_line) {
       // Even if the last line misses a line end, it is counted.
       line_count++;
     }
   }
 
   // Pass 2: Fill in line ends positions

[Lasse Reichstein, 2010/11/18 08:11:47]

On the other hand, if the function isn't performance critical, then doing two
iterations to first find the count and then collect the values seems overly
complex, compared to just collecting the values in a List or Collector during
the first iteration.
Performance-wise it also seems like doing double the work in iteration instead
double the work copying the result afterwards.
It does save (C-heap) memory, though.

[sandholm, 2010/11/18 08:39:10]

Agree. That's why I suggested using Fixed ArrayBuilder as a next step. Sounds
like using a List or Collector would be even better.

   Handle<FixedArray> array = Factory::NewFixedArray(line_count);
   int array_index = 0;
   position = 0;
   while (position != -1 && position < src_len) {
-    position = Runtime::StringMatch(src, new_line, position);
+    position = search.Search(src, position);
     if (position != -1) {
       array->set(array_index++, Smi::FromInt(position++));
-    } else if (with_imaginary_last_new_line) {
+    } else if (with_last_line) {
       // If the script does not end with a line ending add the final end
       // position as just past the last line ending.
       array->set(array_index++, Smi::FromInt(src_len));
     }
   }
   ASSERT(array_index == line_count);
 
   return array;
 }
 
+Handle<FixedArray> CalculateLineEnds(Handle<String> src,
+                                     bool with_last_line) {
+  if (!src->IsFlat()) FlattenString(src);
+  AssertNoAllocation no_heap_allocation;  // ensure vectors stay valid
+  // Extract flattened substring of cons string before determining asciiness.
+  String* seq_src = *src;
+  if (seq_src->IsConsString()) seq_src = ConsString::cast(seq_src)->first();
+  // Dispatch on type of strings.
+  if (seq_src->IsAsciiRepresentation()) {
+    return CalculateLineEnds(seq_src->ToAsciiVector(), with_last_line);
+  }
+  return CalculateLineEnds(seq_src->ToUC16Vector(), with_last_line);
+}
+
 
 // Convert code position into line number.
 int GetScriptLineNumber(Handle<Script> script, int code_pos) {
   InitScriptLineEnds(script);
   AssertNoAllocation no_allocation;
   FixedArray* line_ends_array = FixedArray::cast(script->line_ends());
   const int line_ends_len = line_ends_array->length();
 
   if (!line_ends_len)
     return -1;
@@ skipping 307 matching lines @@
 
 OptimizedObjectForAddingMultipleProperties::
 ~OptimizedObjectForAddingMultipleProperties() {
   // Reoptimize the object to allow fast property access.
   if (has_been_transformed_) {
     TransformToFastProperties(object_, unused_property_fields_);
   }
 }
 
 } }  // namespace v8::internal