Revision: 3545
Author: [email protected]
Date: Wed Jan 6 06:40:21 2010
Log: Improve performance of Array.prototype.join and
String.prototype.substring
by tweaking the JavaScript implementation of these functions.
Review URL: http://codereview.chromium.org/519061
http://code.google.com/p/v8/source/detail?r=3545
Modified:
/branches/bleeding_edge/src/array.js
/branches/bleeding_edge/src/macros.py
/branches/bleeding_edge/src/math.js
/branches/bleeding_edge/src/runtime.cc
/branches/bleeding_edge/src/runtime.h
/branches/bleeding_edge/src/runtime.js
/branches/bleeding_edge/src/string.js
/branches/bleeding_edge/test/mjsunit/fuzz-natives.js
=======================================
--- /branches/bleeding_edge/src/array.js Tue Dec 1 06:19:23 2009
+++ /branches/bleeding_edge/src/array.js Wed Jan 6 06:40:21 2010
@@ -70,19 +70,22 @@
// Optimized for sparse arrays if separator is ''.
function SparseJoin(array, len, convert) {
var keys = GetSortedArrayKeys(array, %GetArrayKeys(array, len));
- var builder = new StringBuilder();
var last_key = -1;
var keys_length = keys.length;
+
+ var elements = new $Array(keys_length);
+ var elements_length = 0;
+
for (var i = 0; i < keys_length; i++) {
var key = keys[i];
if (key != last_key) {
var e = array[key];
- if (typeof(e) !== 'string') e = convert(e);
- builder.add(e);
+ if (!IS_STRING(e)) e = convert(e);
+ elements[elements_length++] = e;
last_key = key;
}
}
- return builder.generate();
+ return %StringBuilderConcat(elements, elements_length, '');
}
@@ -107,7 +110,7 @@
// Attempt to convert the elements.
try {
- if (UseSparseVariant(array, length, is_array) && separator === '') {
+ if (UseSparseVariant(array, length, is_array) && (separator.length ==
0)) {
return SparseJoin(array, length, convert);
}
@@ -115,39 +118,37 @@
if (length == 1) {
var e = array[0];
if (!IS_UNDEFINED(e) || (0 in array)) {
- if (typeof(e) === 'string') return e;
+ if (IS_STRING(e)) return e;
return convert(e);
}
}
- var builder = new StringBuilder();
+ // Construct an array for the elements.
+ var elements;
+ var elements_length = 0;
// We pull the empty separator check outside the loop for speed!
if (separator.length == 0) {
+ elements = new $Array(length);
for (var i = 0; i < length; i++) {
var e = array[i];
if (!IS_UNDEFINED(e) || (i in array)) {
- if (typeof(e) !== 'string') e = convert(e);
- if (e.length > 0) {
- var elements = builder.elements;
- elements[elements.length] = e;
- }
+ if (!IS_STRING(e)) e = convert(e);
+ elements[elements_length++] = e;
}
}
} else {
+ elements = new $Array(length << 1);
for (var i = 0; i < length; i++) {
var e = array[i];
- if (i != 0) builder.add(separator);
+ if (i != 0) elements[elements_length++] = separator;
if (!IS_UNDEFINED(e) || (i in array)) {
- if (typeof(e) !== 'string') e = convert(e);
- if (e.length > 0) {
- var elements = builder.elements;
- elements[elements.length] = e;
- }
+ if (!IS_STRING(e)) e = convert(e);
+ elements[elements_length++] = e;
}
}
}
- return builder.generate();
+ return %StringBuilderConcat(elements, elements_length, '');
} finally {
// Make sure to pop the visited array no matter what happens.
if (is_array) visited_arrays.pop();
@@ -156,16 +157,15 @@
function ConvertToString(e) {
- if (typeof(e) === 'string') return e;
if (e == null) return '';
else return ToString(e);
}
function ConvertToLocaleString(e) {
- if (typeof(e) === 'string') return e;
- if (e == null) return '';
- else {
+ if (e == null) {
+ return '';
+ } else {
// e_obj's toLocaleString might be overwritten, check if it is a
function.
// Call ToString if toLocaleString is not a function.
// See issue 877615.
@@ -359,16 +359,20 @@
function ArrayJoin(separator) {
- if (IS_UNDEFINED(separator)) separator = ',';
- else separator = ToString(separator);
- return Join(this, ToUint32(this.length), separator, ConvertToString);
+ if (IS_UNDEFINED(separator)) {
+ separator = ',';
+ } else if (!IS_STRING(separator)) {
+ separator = ToString(separator);
+ }
+ var length = TO_UINT32(this.length);
+ return Join(this, length, separator, ConvertToString);
}
// Removes the last element from the array and returns it. See
// ECMA-262, section 15.4.4.6.
function ArrayPop() {
- var n = ToUint32(this.length);
+ var n = TO_UINT32(this.length);
if (n == 0) {
this.length = n;
return;
@@ -384,7 +388,7 @@
// Appends the arguments to the end of the array and returns the new
// length of the array. See ECMA-262, section 15.4.4.7.
function ArrayPush() {
- var n = ToUint32(this.length);
+ var n = TO_UINT32(this.length);
var m = %_ArgumentsLength();
for (var i = 0; i < m; i++) {
this[i+n] = %_Arguments(i);
@@ -452,7 +456,7 @@
function ArrayReverse() {
- var j = ToUint32(this.length) - 1;
+ var j = TO_UINT32(this.length) - 1;
if (UseSparseVariant(this, j, IS_ARRAY(this))) {
SparseReverse(this, j+1);
@@ -483,7 +487,7 @@
function ArrayShift() {
- var len = ToUint32(this.length);
+ var len = TO_UINT32(this.length);
if (len === 0) {
this.length = 0;
@@ -504,7 +508,7 @@
function ArrayUnshift(arg1) { // length == 1
- var len = ToUint32(this.length);
+ var len = TO_UINT32(this.length);
var num_arguments = %_ArgumentsLength();
if (IS_ARRAY(this))
@@ -523,7 +527,7 @@
function ArraySlice(start, end) {
- var len = ToUint32(this.length);
+ var len = TO_UINT32(this.length);
var start_i = TO_INTEGER(start);
var end_i = len;
@@ -568,7 +572,7 @@
// compatibility.
if (num_arguments == 0) return;
- var len = ToUint32(this.length);
+ var len = TO_UINT32(this.length);
var start_i = TO_INTEGER(start);
if (start_i < 0) {
@@ -850,7 +854,7 @@
return first_undefined;
}
- length = ToUint32(this.length);
+ length = TO_UINT32(this.length);
if (length < 2) return this;
var is_array = IS_ARRAY(this);
=======================================
--- /branches/bleeding_edge/src/macros.py Mon Dec 21 07:04:00 2009
+++ /branches/bleeding_edge/src/macros.py Wed Jan 6 06:40:21 2010
@@ -97,7 +97,8 @@
# Inline macros. Use %IS_VAR to make sure arg is evaluated only once.
macro NUMBER_IS_NAN(arg) = (!%_IsSmi(%IS_VAR(arg)) && !(arg == arg));
macro TO_INTEGER(arg) = (%_IsSmi(%IS_VAR(arg)) ? arg : ToInteger(arg));
-macro TO_INT32(arg) = (%_IsSmi(%IS_VAR(arg)) ? arg : ToInt32(arg));
+macro TO_INT32(arg) = (%_IsSmi(%IS_VAR(arg)) ? arg : (arg >> 0));
+macro TO_UINT32(arg) = (arg >>> 0);
# Macros implemented in Python.
python macro CHAR_CODE(str) = ord(str[1]);
=======================================
--- /branches/bleeding_edge/src/math.js Mon Dec 21 07:04:00 2009
+++ /branches/bleeding_edge/src/math.js Wed Jan 6 06:40:21 2010
@@ -103,7 +103,7 @@
// them to an unsigned 32-bit value using the shift operator.
// We avoid doing so for -0, because the result of Math.floor(-0)
// has to be -0, which wouldn't be the case with the shift.
- return x << 0;
+ return TO_UINT32(x);
} else {
return %Math_floor(x);
}
=======================================
--- /branches/bleeding_edge/src/runtime.cc Tue Jan 5 04:33:55 2010
+++ /branches/bleeding_edge/src/runtime.cc Wed Jan 6 06:40:21 2010
@@ -3914,20 +3914,19 @@
static Object* Runtime_StringBuilderConcat(Arguments args) {
NoHandleAllocation ha;
- ASSERT(args.length() == 2);
+ ASSERT(args.length() == 3);
CONVERT_CHECKED(JSArray, array, args[0]);
- CONVERT_CHECKED(String, special, args[1]);
+ if (!args[1]->IsSmi()) {
+ Top::context()->mark_out_of_memory();
+ return Failure::OutOfMemoryException();
+ }
+ int array_length = Smi::cast(args[1])->value();
+ CONVERT_CHECKED(String, special, args[2]);
// This assumption is used by the slice encoding in one or two smis.
ASSERT(Smi::kMaxValue >= String::kMaxLength);
int special_length = special->length();
- Object* smi_array_length = array->length();
- if (!smi_array_length->IsSmi()) {
- Top::context()->mark_out_of_memory();
- return Failure::OutOfMemoryException();
- }
- int array_length = Smi::cast(smi_array_length)->value();
if (!array->HasFastElements()) {
return Top::Throw(Heap::illegal_argument_symbol());
}
=======================================
--- /branches/bleeding_edge/src/runtime.h Wed Jan 6 01:22:36 2010
+++ /branches/bleeding_edge/src/runtime.h Wed Jan 6 06:40:21 2010
@@ -103,7 +103,7 @@
F(NumberUnaryMinus, 1, 1) \
\
F(StringAdd, 2, 1) \
- F(StringBuilderConcat, 2, 1) \
+ F(StringBuilderConcat, 3, 1) \
\
/* Bit operations */ \
F(NumberOr, 2, 1) \
=======================================
--- /branches/bleeding_edge/src/runtime.js Mon Dec 14 04:18:20 2009
+++ /branches/bleeding_edge/src/runtime.js Wed Jan 6 06:40:21 2010
@@ -427,7 +427,7 @@
}
}
- length = (args == null) ? 0 : %ToUint32(args.length);
+ length = (args == null) ? 0 : TO_UINT32(args.length);
// We can handle any number of apply arguments if the stack is
// big enough, but sanity check the value to avoid overflow when
=======================================
--- /branches/bleeding_edge/src/string.js Tue Nov 10 05:23:05 2009
+++ /branches/bleeding_edge/src/string.js Wed Jan 6 06:40:21 2010
@@ -505,7 +505,7 @@
// ECMA-262 section 15.5.4.14
function StringSplit(separator, limit) {
var subject = ToString(this);
- limit = (limit === void 0) ? 0xffffffff : ToUint32(limit);
+ limit = (IS_UNDEFINED(limit)) ? 0xffffffff : TO_UINT32(limit);
if (limit === 0) return [];
// ECMA-262 says that if separator is undefined, the result should
@@ -604,22 +604,30 @@
// ECMA-262 section 15.5.4.15
function StringSubstring(start, end) {
- var s = ToString(this);
+ var s = this;
+ if (!IS_STRING(s)) s = ToString(s);
var s_len = s.length;
+
var start_i = TO_INTEGER(start);
+ if (start_i < 0) {
+ start_i = 0;
+ } else if (start_i > s_len) {
+ start_i = s_len;
+ }
+
var end_i = s_len;
- if (!IS_UNDEFINED(end))
+ if (!IS_UNDEFINED(end)) {
end_i = TO_INTEGER(end);
-
- if (start_i < 0) start_i = 0;
- if (start_i > s_len) start_i = s_len;
- if (end_i < 0) end_i = 0;
- if (end_i > s_len) end_i = s_len;
-
- if (start_i > end_i) {
- var tmp = end_i;
- end_i = start_i;
- start_i = tmp;
+ if (end_i > s_len) {
+ end_i = s_len;
+ } else {
+ if (end_i < 0) end_i = 0;
+ if (start_i > end_i) {
+ var tmp = end_i;
+ end_i = start_i;
+ start_i = tmp;
+ }
+ }
}
return SubString(s, start_i, end_i);
@@ -790,21 +798,14 @@
}
-// StringBuilder support.
-
-function StringBuilder() {
- this.elements = new $Array();
-}
-
-
+// ReplaceResultBuilder support.
function ReplaceResultBuilder(str) {
this.elements = new $Array();
this.special_string = str;
}
-ReplaceResultBuilder.prototype.add =
-StringBuilder.prototype.add = function(str) {
+ReplaceResultBuilder.prototype.add = function(str) {
if (!IS_STRING(str)) str = ToString(str);
if (str.length > 0) {
var elements = this.elements;
@@ -826,15 +827,11 @@
elements[elements.length] = start;
}
}
-
-
-StringBuilder.prototype.generate = function() {
- return %StringBuilderConcat(this.elements, "");
-}
ReplaceResultBuilder.prototype.generate = function() {
- return %StringBuilderConcat(this.elements, this.special_string);
+ var elements = this.elements;
+ return %StringBuilderConcat(elements, elements.length,
this.special_string);
}
=======================================
--- /branches/bleeding_edge/test/mjsunit/fuzz-natives.js Thu Dec 10
10:33:34 2009
+++ /branches/bleeding_edge/test/mjsunit/fuzz-natives.js Wed Jan 6
06:40:21 2010
@@ -95,7 +95,11 @@
var knownProblems = {
"Abort": true,
-
+
+ // Avoid calling the concat operation, because weird lengths
+ // may lead to out-of-memory.
+ "StringBuilderConcat": true,
+
// These functions use pseudo-stack-pointers and are not robust
// to unexpected integer values.
"DebugEvaluate": true,
@@ -114,7 +118,7 @@
// the rest of the tests.
"DisableAccessChecks": true,
"EnableAccessChecks": true,
-
+
// These functions should not be callable as runtime functions.
"NewContext": true,
"NewArgumentsFast": true,
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
