Reviewers: rossberg,
Message:
Please take a look.
When replacing a single character by a string, instead of flattening the
string
for search and copying the string to replace, we can avoid flattening by
depth-first traversal of the cons-string tree and replace the affected part
by a
cons string consisting of slices of the original string.
Description:
Fast path for string.replace that replaces a single character by a string.
BUG=
TEST=
Please review this at http://codereview.chromium.org/9213002/
SVN Base: https://v8.googlecode.com/svn/branches/bleeding_edge
Affected files:
M src/heap.cc
M src/runtime.h
M src/runtime.cc
M src/string.js
Index: src/heap.cc
diff --git a/src/heap.cc b/src/heap.cc
index
6295788f0af9a2f4d1e772143ff684362b568d75..7a8f8668fa5dc330d47967da3a09e977de14eb3e
100644
--- a/src/heap.cc
+++ b/src/heap.cc
@@ -3011,7 +3011,7 @@ MaybeObject* Heap::AllocateSubString(String* buffer,
int end,
PretenureFlag pretenure) {
int length = end - start;
- if (length == 0) {
+ if (length <= 0) {
return empty_string();
} else if (length == 1) {
return LookupSingleCharacterStringFromCode(buffer->Get(start));
Index: src/runtime.cc
diff --git a/src/runtime.cc b/src/runtime.cc
index
df37174c51a499ea3ca31aca47d09139884b91d6..0dc17c5a9ddd6973f7d826639ea402150ecaf9b9
100644
--- a/src/runtime.cc
+++ b/src/runtime.cc
@@ -3233,6 +3233,59 @@ RUNTIME_FUNCTION(MaybeObject*,
Runtime_StringReplaceRegExpWithString) {
}
+Handle<String> Runtime::StringReplaceOneCharWithString(Isolate* isolate,
+ Handle<String>
subject,
+ Handle<String>
search,
+ Handle<String>
replace,
+ bool* found) {
+ if (subject->IsConsString()) {
+ ConsString* cons = ConsString::cast(*subject);
+ Handle<String> first = Handle<String>(cons->first());
+ Handle<String> second = Handle<String>(cons->second());
+ Handle<String> new_first = StringReplaceOneCharWithString(isolate,
+ first,
+ search,
+ replace,
+ found);
+ if (*found) {
+ return isolate->factory()->NewConsString(new_first, second);
+ } else {
+ Handle<String> new_second = StringReplaceOneCharWithString(isolate,
+ second,
+ search,
+ replace,
+ found);
+ return isolate->factory()->NewConsString(first, new_second);
+ }
+ } else {
+ int index = StringMatch(isolate, subject, search, 0);
+ if (index == -1) return subject;
+ *found = true;
+ Handle<String> first = isolate->factory()->NewSubString(subject, 0,
index);
+ Handle<String> cons1 = isolate->factory()->NewConsString(first,
replace);
+ Handle<String> second =
+ isolate->factory()->NewSubString(subject, index + 1,
subject->length());
+ return isolate->factory()->NewConsString(cons1, second);
+ }
+}
+
+
+RUNTIME_FUNCTION(MaybeObject*, Runtime_StringReplaceOneCharWithString) {
+ ASSERT(args.length() == 3);
+ HandleScope scope(isolate);
+ CONVERT_ARG_CHECKED(String, subject, 0);
+ CONVERT_ARG_CHECKED(String, search, 1);
+ CONVERT_ARG_CHECKED(String, replace, 2);
+ bool found = false;
+
+ return *(Runtime::StringReplaceOneCharWithString(isolate,
+ subject,
+ search,
+ replace,
+ &found));
+}
+
+
// 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().
Index: src/runtime.h
diff --git a/src/runtime.h b/src/runtime.h
index
c915cf38da4f9b1bd0d075d49391aaafb4fcde68..3056217ea6734c4e1575f7b0e0980bb6d660f019
100644
--- a/src/runtime.h
+++ b/src/runtime.h
@@ -197,6 +197,7 @@ namespace internal {
F(StringLocaleCompare, 2, 1) \
F(SubString, 3, 1) \
F(StringReplaceRegExpWithString, 4, 1) \
+ F(StringReplaceOneCharWithString, 3, 1) \
F(StringMatch, 3, 1) \
F(StringTrim, 3, 1) \
F(StringToArray, 2, 1) \
@@ -629,6 +630,12 @@ class Runtime : public AllStatic {
// Get the intrinsic function with the given FunctionId.
static const Function* FunctionForId(FunctionId id);
+ static Handle<String> StringReplaceOneCharWithString(Isolate* isolate,
+ Handle<String>
subject,
+ Handle<String>
search,
+ Handle<String>
replace,
+ bool* found);
+
// General-purpose helper functions for runtime system.
static int StringMatch(Isolate* isolate,
Handle<String> sub,
Index: src/string.js
diff --git a/src/string.js b/src/string.js
index
3608bac8facc279b0d0c31cd299cec641e58d714..e858b0fd526e7c8b8995981460bf7130b5974228
100644
--- a/src/string.js
+++ b/src/string.js
@@ -244,6 +244,11 @@ function StringReplace(search, replace) {
// Convert the search argument to a string and search for it.
search = TO_STRING_INLINE(search);
+ if (search.length == 1 &&
+ IS_STRING(replace) &&
+ %StringIndexOf(replace, '$', 0) < 0) {
+ return %StringReplaceOneCharWithString(subject, search, replace);
+ }
var start = %StringIndexOf(subject, search, 0);
if (start < 0) return subject;
var end = start + search.length;
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
