Revision: 3922
Author: [email protected]
Date: Fri Feb 19 09:11:47 2010
Log: Land patch by Oleg Eterevsky ([email protected]).
Original review: http://codereview.chromium.org/646010/show
Change the implementation of lastIndexOf method of String. Convert the
strings in question to Vector<char> or Vector<uc16> and execute simple
search algorithm on them.
The difference in speed on 500k character string is about 10x.
[email protected]
Review URL: http://codereview.chromium.org/650036
http://code.google.com/p/v8/source/detail?r=3922
Modified:
/branches/bleeding_edge/src/runtime.cc
=======================================
--- /branches/bleeding_edge/src/runtime.cc Fri Feb 19 05:07:37 2010
+++ /branches/bleeding_edge/src/runtime.cc Fri Feb 19 09:11:47 2010
@@ -2366,7 +2366,7 @@
// We have an ASCII haystack and a non-ASCII needle. Check if there
// really is a non-ASCII character in the needle and bail out if there
// is.
- if (sizeof(pchar) > 1 && sizeof(schar) == 1) {
+ if (sizeof(schar) == 1 && sizeof(pchar) > 1) {
for (int i = 0; i < pat.length(); i++) {
uc16 c = pat[i];
if (c > String::kMaxAsciiCharCode) {
@@ -2468,30 +2468,67 @@
return Smi::FromInt(position);
}
+
+template <typename schar, typename pchar>
+static int StringMatchBackwards(Vector<const schar> sub,
+ Vector<const pchar> pat,
+ int idx) {
+ ASSERT(pat.length() >= 1);
+ ASSERT(idx + pat.length() <= sub.length());
+
+ if (sizeof(schar) == 1 && sizeof(pchar) > 1) {
+ for (int i = 0; i < pat.length(); i++) {
+ uc16 c = pat[i];
+ if (c > String::kMaxAsciiCharCode) {
+ return -1;
+ }
+ }
+ }
+
+ pchar pattern_first_char = pat[0];
+ for (int i = idx; i >= 0; i--) {
+ if (sub[i] != pattern_first_char) continue;
+ int j = 1;
+ while (j < pat.length()) {
+ if (pat[j] != sub[i+j]) {
+ break;
+ }
+ j++;
+ }
+ if (j == pat.length()) {
+ return i;
+ }
+ }
+ return -1;
+}
static Object* Runtime_StringLastIndexOf(Arguments args) {
- NoHandleAllocation ha;
+ HandleScope scope; // create a new handle scope
ASSERT(args.length() == 3);
CONVERT_ARG_CHECKED(String, sub, 0);
CONVERT_ARG_CHECKED(String, pat, 1);
- Object* index = args[2];
-
+
+ Object* index = args[2];
uint32_t start_index;
if (!Array::IndexFromObject(index, &start_index)) return
Smi::FromInt(-1);
- if (!sub->IsFlat()) {
- FlattenString(sub);
+ uint32_t pat_length = pat->length();
+ uint32_t sub_length = sub->length();
+
+ if (start_index + pat_length > sub_length) {
+ start_index = sub_length - pat_length;
}
- uint32_t pattern_length = pat->length();
- uint32_t sub_length = sub->length();
-
- if (start_index + pattern_length > sub_length) {
- start_index = sub_length - pattern_length;
+ if (pat_length == 0) {
+ return Smi::FromInt(start_index);
+ }
+
+ if (!sub->IsFlat()) {
+ FlattenString(sub);
}
- if (pattern_length == 1) {
+ if (pat_length == 1) {
AssertNoAllocation no_heap_allocation; // ensure vectors stay valid
if (sub->IsAsciiRepresentation()) {
uc16 pchar = pat->Get(0);
@@ -2508,20 +2545,39 @@
}
}
- pat->TryFlattenIfNotFlat();
-
- for (int i = start_index; i >= 0; i--) {
- bool found = true;
- for (uint32_t j = 0; j < pattern_length; j++) {
- if (sub->Get(i + j) != pat->Get(j)) {
- found = false;
- break;
- }
- }
- if (found) return Smi::FromInt(i);
+ if (!pat->IsFlat()) {
+ FlattenString(pat);
+ }
+
+ AssertNoAllocation no_heap_allocation; // ensure vectors stay valid
+
+ int position = -1;
+
+ if (pat->IsAsciiRepresentation()) {
+ Vector<const char> pat_vector = pat->ToAsciiVector();
+ if (sub->IsAsciiRepresentation()) {
+ position = StringMatchBackwards(sub->ToAsciiVector(),
+ pat_vector,
+ start_index);
+ } else {
+ position = StringMatchBackwards(sub->ToUC16Vector(),
+ pat_vector,
+ start_index);
+ }
+ } else {
+ Vector<const uc16> pat_vector = pat->ToUC16Vector();
+ if (sub->IsAsciiRepresentation()) {
+ position = StringMatchBackwards(sub->ToAsciiVector(),
+ pat_vector,
+ start_index);
+ } else {
+ position = StringMatchBackwards(sub->ToUC16Vector(),
+ pat_vector,
+ start_index);
+ }
}
- return Smi::FromInt(-1);
+ return Smi::FromInt(position);
}
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
