Cache results in SearchRegExpMultiple.

src/runtime.cc

 // Copyright 2012 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 2394 matching lines @@
   }
 
   int length() {
     return length_;
   }
 
   int capacity() {
     return array_->length();
   }
 
-  Handle<JSArray> ToJSArray() {
-    Handle<JSArray> result_array = FACTORY->NewJSArrayWithElements(array_);
-    result_array->set_length(Smi::FromInt(length_));
-    return result_array;
-  }
-
   Handle<JSArray> ToJSArray(Handle<JSArray> target_array) {
     FACTORY->SetContent(target_array, array_);
     target_array->set_length(Smi::FromInt(length_));
     return target_array;
   }
 
+
+  static int GetFinalLength(Handle<FixedArray> array) {

[ulan, 2012/08/28 08:44:03]

The function name is a bit obscure. Maybe just inline the expression at the
call-site?

+    // Get final length from last element.
+    return Smi::cast(array->get(array->length() - 1))->value();
+  }
+
+
  private:
   Handle<FixedArray> array_;
   int length_;
   bool has_non_smi_elements_;
 };
 
 
 // Forward declarations.
 const int kStringBuilderConcatHelperLengthBits = 11;
 const int kStringBuilderConcatHelperPositionBits = 19;
@@ skipping 98 matching lines @@
   }
 
 
   void IncrementCharacterCount(int by) {
     if (character_count_ > String::kMaxLength - by) {
       V8::FatalProcessOutOfMemory("String.replace result too large.");
     }
     character_count_ += by;
   }
 
-  Handle<JSArray> GetParts() {
-    return array_builder_.ToJSArray();
-  }
-
  private:
   Handle<SeqAsciiString> NewRawAsciiString(int length) {
     return heap_->isolate()->factory()->NewRawAsciiString(length);
   }
 
 
   Handle<SeqTwoByteString> NewRawTwoByteString(int length) {
     return heap_->isolate()->factory()->NewRawTwoByteString(length);
   }
 
@@ skipping 1100 matching lines @@
   }
   Handle<JSArray> result = isolate->factory()->NewJSArrayWithElements(elements);
   result->set_length(Smi::FromInt(matches));
   return *result;
 }
 
 
 // Only called from Runtime_RegExpExecMultiple so it doesn't need to maintain
 // separate last match info.  See comment on that function.
 template<bool has_capture>
-static int SearchRegExpMultiple(
+static MaybeObject* SearchRegExpMultiple(
     Isolate* isolate,
     Handle<String> subject,
     Handle<JSRegExp> regexp,
     Handle<JSArray> last_match_array,
-    FixedArrayBuilder* builder) {
+    Handle<JSArray> result_array) {
   ASSERT(subject->IsFlat());
   ASSERT_NE(has_capture, regexp->CaptureCount() == 0);
 
-  RegExpImpl::GlobalCache global_cache(regexp, subject, true, isolate);
-  if (global_cache.HasException()) return RegExpImpl::RE_EXCEPTION;
-
   int capture_count = regexp->CaptureCount();
   int subject_length = subject->length();
 
+  static const int kMinLengthToCache = 0x1000;
+
+  if (subject_length > kMinLengthToCache) {
+    Handle<Object> cached_answer(RegExpResultsCache::Lookup(
+        isolate->heap()->regexp_multiple_cache(),
+        *subject,
+        regexp->data()));
+    if (*cached_answer != Smi::FromInt(0)) {
+      Handle<FixedArray> cached_fixed_array =
+          Handle<FixedArray>(FixedArray::cast(*cached_answer));
+      isolate->factory()->SetContent(result_array, cached_fixed_array);

[ulan, 2012/08/28 08:44:03]

A comment that the cached_fixed_array is COW would be helpful here.

+      int length = FixedArrayBuilder::GetFinalLength(cached_fixed_array);
+      result_array->set_length(Smi::FromInt(length));
+      RegExpImpl::SetLastMatchInfo(
+          last_match_array, subject, capture_count, NULL);
+      return *result_array;
+    }
+  }
+
+  RegExpImpl::GlobalCache global_cache(regexp, subject, true, isolate);
+  if (global_cache.HasException()) return Failure::Exception();
+
+  Handle<FixedArray> result_elements;
+  if (result_array->HasFastObjectElements()) {
+    result_elements =
+        Handle<FixedArray>(FixedArray::cast(result_array->elements()));
+  }
+  if (result_elements.is_null() || result_elements->length() < 16) {
+    result_elements = isolate->factory()->NewFixedArrayWithHoles(16);
+  }
+
+  FixedArrayBuilder builder(result_elements);
+
   // Position to search from.
   int match_start = -1;
   int match_end = 0;
   bool first = true;
 
   // Two smis before and after the match, for very long strings.
   static const int kMaxBuilderEntriesPerRegExpMatch = 5;
 
   while (true) {
     int32_t* current_match = global_cache.FetchNext();
     if (current_match == NULL) break;
     match_start = current_match[0];
-    builder->EnsureCapacity(kMaxBuilderEntriesPerRegExpMatch);
+    builder.EnsureCapacity(kMaxBuilderEntriesPerRegExpMatch);
     if (match_end < match_start) {
-      ReplacementStringBuilder::AddSubjectSlice(builder,
+      ReplacementStringBuilder::AddSubjectSlice(&builder,
                                                 match_end,
                                                 match_start);
     }
     match_end = current_match[1];
     {
       // Avoid accumulating new handles inside loop.
       HandleScope temp_scope(isolate);
       Handle<String> match;
       if (!first) {
         match = isolate->factory()->NewProperSubString(subject,
@@ skipping 21 matching lines @@
             Handle<String> substring =
                 isolate->factory()->NewSubString(subject, start, end);
             elements->set(i, *substring);
           } else {
             ASSERT(current_match[i * 2 + 1] < 0);
             elements->set(i, isolate->heap()->undefined_value());
           }
         }
         elements->set(capture_count + 1, Smi::FromInt(match_start));
         elements->set(capture_count + 2, *subject);
-        builder->Add(*isolate->factory()->NewJSArrayWithElements(elements));
+        builder.Add(*isolate->factory()->NewJSArrayWithElements(elements));
       } else {
-        builder->Add(*match);
+        builder.Add(*match);
       }
     }
   }
 
-  if (global_cache.HasException()) return RegExpImpl::RE_EXCEPTION;
+  if (global_cache.HasException()) return Failure::Exception();
 
   if (match_start >= 0) {
     // Finished matching, with at least one match.
     if (match_end < subject_length) {
-      ReplacementStringBuilder::AddSubjectSlice(builder,
+      ReplacementStringBuilder::AddSubjectSlice(&builder,
                                                 match_end,
                                                 subject_length);
     }
 
     RegExpImpl::SetLastMatchInfo(
         last_match_array, subject, capture_count, NULL);
 
-    return RegExpImpl::RE_SUCCESS;
+    if (subject_length > kMinLengthToCache) {
+      // Store the length of the result array into the last element of the
+      // backing FixedArray.
+      builder.EnsureCapacity(1);
+      Handle<FixedArray> fixed_array = builder.array();
+      fixed_array->set(fixed_array->length() - 1,
+                       Smi::FromInt(builder.length()));
+      // Cache the result and turn the FixedArray into a COW array.
+      RegExpResultsCache::Enter(isolate->heap(),
+                                isolate->heap()->regexp_multiple_cache(),
+                                *subject,
+                                regexp->data(),
+                                *fixed_array);
+    }
+    return *builder.ToJSArray(result_array);
   } else {
-    return RegExpImpl::RE_FAILURE;  // No matches at all.
+    return isolate->heap()->null_value();  // No matches at all.
   }
 }
 
 
 // This is only called for StringReplaceGlobalRegExpWithFunction.  This sets
 // lastMatchInfoOverride to maintain the last match info, so we don't need to
 // set any other last match array info.
 RUNTIME_FUNCTION(MaybeObject*, Runtime_RegExpExecMultiple) {
   ASSERT(args.length() == 4);
   HandleScope handles(isolate);
 
   CONVERT_ARG_HANDLE_CHECKED(String, subject, 1);
   if (!subject->IsFlat()) FlattenString(subject);
   CONVERT_ARG_HANDLE_CHECKED(JSRegExp, regexp, 0);
   CONVERT_ARG_HANDLE_CHECKED(JSArray, last_match_info, 2);
   CONVERT_ARG_HANDLE_CHECKED(JSArray, result_array, 3);
 
   ASSERT(last_match_info->HasFastObjectElements());
   ASSERT(regexp->GetFlags().is_global());
-  Handle<FixedArray> result_elements;
-  if (result_array->HasFastObjectElements()) {
-    result_elements =
-        Handle<FixedArray>(FixedArray::cast(result_array->elements()));
+
+  if (regexp->CaptureCount() == 0) {
+    return SearchRegExpMultiple<false>(
+        isolate, subject, regexp, last_match_info, result_array);
+  } else {
+    return SearchRegExpMultiple<true>(
+        isolate, subject, regexp, last_match_info, result_array);
   }
-  if (result_elements.is_null() || result_elements->length() < 16) {
-    result_elements = isolate->factory()->NewFixedArrayWithHoles(16);
-  }
-  FixedArrayBuilder builder(result_elements);
-
-  int result;
-  if (regexp->CaptureCount() == 0) {
-    result = SearchRegExpMultiple<false>(
-        isolate, subject, regexp, last_match_info, &builder);
-  } else {
-    result = SearchRegExpMultiple<true>(
-        isolate, subject, regexp, last_match_info, &builder);
-  }
-
-  if (result == RegExpImpl::RE_SUCCESS) return *builder.ToJSArray(result_array);
-  if (result == RegExpImpl::RE_FAILURE) return isolate->heap()->null_value();
-  ASSERT_EQ(result, RegExpImpl::RE_EXCEPTION);
-  return Failure::Exception();
 }
 
 
 RUNTIME_FUNCTION(MaybeObject*, Runtime_NumberToRadixString) {
   NoHandleAllocation ha;
   ASSERT(args.length() == 2);
   CONVERT_SMI_ARG_CHECKED(radix, 1);
   RUNTIME_ASSERT(2 <= radix && radix <= 36);
 
   // Fast case where the result is a one character string.
@@ skipping 2296 matching lines @@
   HandleScope handle_scope(isolate);
   CONVERT_ARG_HANDLE_CHECKED(String, subject, 0);
   CONVERT_ARG_HANDLE_CHECKED(String, pattern, 1);
   CONVERT_NUMBER_CHECKED(uint32_t, limit, Uint32, args[2]);
 
   int subject_length = subject->length();
   int pattern_length = pattern->length();
   RUNTIME_ASSERT(pattern_length > 0);
 
   if (limit == 0xffffffffu) {
-    Handle<Object> cached_answer(StringSplitCache::Lookup(
+    Handle<Object> cached_answer(RegExpResultsCache::Lookup(
         isolate->heap()->string_split_cache(),
         *subject,
         *pattern));
     if (*cached_answer != Smi::FromInt(0)) {
       Handle<JSArray> result =
           isolate->factory()->NewJSArrayWithElements(
               Handle<FixedArray>::cast(cached_answer));
       return *result;
     }
   }
@@ skipping 43 matching lines @@
     HandleScope local_loop_handle;
     int part_end = indices.at(i);
     Handle<String> substring =
         isolate->factory()->NewProperSubString(subject, part_start, part_end);
     elements->set(i, *substring);
     part_start = part_end + pattern_length;
   }
 
   if (limit == 0xffffffffu) {
     if (result->HasFastObjectElements()) {
-      StringSplitCache::Enter(isolate->heap(),
-                              isolate->heap()->string_split_cache(),
-                              *subject,
-                              *pattern,
-                              *elements);
+      RegExpResultsCache::Enter(isolate->heap(),
+                                isolate->heap()->string_split_cache(),
+                                *subject,
+                                *pattern,
+                                *elements);
     }
   }
 
   return *result;
 }
 
 
 // Copies ASCII characters to the given fixed array looking up
 // one-char strings in the cache. Gives up on the first char that is
 // not in the cache and fills the remainder with smi zeros. Returns
@@ skipping 7147 matching lines @@
     // Handle last resort GC and make sure to allow future allocations
     // to grow the heap without causing GCs (if possible).
     isolate->counters()->gc_last_resort_from_js()->Increment();
     isolate->heap()->CollectAllGarbage(Heap::kNoGCFlags,
                                        "Runtime::PerformGC");
   }
 }
 
 
 } }  // namespace v8::internal