Author: [EMAIL PROTECTED]
Date: Fri Sep 19 05:30:14 2008
New Revision: 349
Modified:
branches/bleeding_edge/src/runtime.cc
branches/bleeding_edge/src/string.js
Log:
Avoid the KMP overhead for simple indexOf() operations. Will look into
evaluating the best cutoff between a simple search and KMP in the future.
This improves some simple operations ~1.5x.
Modified: branches/bleeding_edge/src/runtime.cc
==============================================================================
--- branches/bleeding_edge/src/runtime.cc (original)
+++ branches/bleeding_edge/src/runtime.cc Fri Sep 19 05:30:14 2008
@@ -911,12 +911,12 @@
CONVERT_CHECKED(String, pat, args[1]);
Object* index = args[2];
- int subject_length = sub->length();
- int pattern_length = pat->length();
-
sub->TryFlatten();
pat->TryFlatten();
+ int subject_length = sub->length();
+ int pattern_length = pat->length();
+
uint32_t start_index;
if (!Array::IndexFromObject(index, &start_index)) return
Smi::FromInt(-1);
if (pattern_length == 0) return Smi::FromInt(start_index);
@@ -934,8 +934,23 @@
return Smi::FromInt(-1);
}
- // For patterns with a length larger than one character we use the KMP
- // algorithm.
+ // 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 Smi::FromInt(i);
+ }
+ }
+ return Smi::FromInt(-1);
+ }
+
+ // For patterns with a larger length we use the KMP algorithm.
//
// Compute the 'next' table.
int* next_table = NewArray<int>(pattern_length);
Modified: branches/bleeding_edge/src/string.js
==============================================================================
--- branches/bleeding_edge/src/string.js (original)
+++ branches/bleeding_edge/src/string.js Fri Sep 19 05:30:14 2008
@@ -332,6 +332,7 @@
// ECMA-262 section 15.5.4.7
%AddProperty($String.prototype, "indexOf", function(searchString /*
position */) { // length == 1
var str = ToString(this);
+ var str_len = str.length;
var searchStr = ToString(searchString);
var index = 0;
if (%_ArgumentsLength() > 1) {
@@ -339,8 +340,8 @@
index = TO_INTEGER(arg1);
}
if (index < 0) index = 0;
- if (index > str.length) index = str.length;
- if (searchStr.length + index > str.length) return -1;
+ if (index > str_len) index = str_len;
+ if (searchStr.length + index > str_len) return -1;
return %StringIndexOf(str, searchStr, index);
}, DONT_ENUM);
--~--~---------~--~----~------------~-------~--~----~
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
-~----------~----~----~----~------~----~------~--~---
