Author: [EMAIL PROTECTED]
Date: Sun Sep 7 23:17:38 2008
New Revision: 185
Removed:
changes/[EMAIL PROTECTED]/smi-array-sort/
Modified:
branches/bleeding_edge/src/array.js
branches/bleeding_edge/src/codegen-arm.cc
branches/bleeding_edge/src/codegen-ia32.cc
branches/bleeding_edge/src/codegen.cc
branches/bleeding_edge/src/codegen.h
branches/bleeding_edge/src/mirror-delay.js
branches/bleeding_edge/src/runtime.cc
branches/bleeding_edge/src/runtime.h
branches/bleeding_edge/src/runtime.js
branches/bleeding_edge/test/mjsunit/array-sort.js
Log:
Avoid string conversion when comparing Smis during sorting.
Avoid runtime calls for trivial object equality checks.
Minor style cleanups.
Modified: branches/bleeding_edge/src/array.js
==============================================================================
--- branches/bleeding_edge/src/array.js (original)
+++ branches/bleeding_edge/src/array.js Sun Sep 7 23:17:38 2008
@@ -219,8 +219,9 @@
// %HasLocalProperty would be the appropriate test. We follow
// KJS in consulting the prototype.
var current = array[j];
- if (!IS_UNDEFINED(current) || j in array)
+ if (!IS_UNDEFINED(current) || j in array) {
new_array[j] = current;
+ }
j++;
}
j = start_i + del_count;
@@ -230,8 +231,9 @@
// appropriate test. We follow KJS in consulting the
// prototype.
var current = array[j];
- if (!IS_UNDEFINED(current) || j in array)
+ if (!IS_UNDEFINED(current) || j in array) {
new_array[j - del_count + num_additional_args] = current;
+ }
j++;
}
} else {
@@ -241,16 +243,18 @@
// %HasLocalProperty would be the appropriate test. We follow
// KJS in consulting the prototype.
var current = array[key];
- if (!IS_UNDEFINED(current) || key in array)
+ if (!IS_UNDEFINED(current) || key in array) {
new_array[key] = current;
+ }
} else if (key >= start_i + del_count) {
// ECMA-262 15.4.4.12 lines 24 and 41. The spec could also
// be interpreted such that %HasLocalProperty would be the
// appropriate test. We follow KJS in consulting the
// prototype.
var current = array[key];
- if (!IS_UNDEFINED(current) || key in array)
+ if (!IS_UNDEFINED(current) || key in array) {
new_array[key - del_count + num_additional_args] = current;
+ }
}
}
}
@@ -658,6 +662,9 @@
if (IS_FUNCTION(comparefn)) {
return comparefn.call(null, x, y);
}
+ if (%_IsSmi(x) && %_IsSmi(y)) {
+ return %SmiLexicographicCompare(x, y);
+ }
x = ToString(x);
y = ToString(y);
if (x == y) return 0;
@@ -677,7 +684,7 @@
var parent_index = ((child_index + 1) >> 1) - 1;
var parent_value = this[parent_index], child_value =
this[child_index];
if (Compare(parent_value, child_value) < 0) {
- this[parent_index] = child_value;
+ this[parent_index] = child_value;
this[child_index] = parent_value;
} else {
break;
Modified: branches/bleeding_edge/src/codegen-arm.cc
==============================================================================
--- branches/bleeding_edge/src/codegen-arm.cc (original)
+++ branches/bleeding_edge/src/codegen-arm.cc Sun Sep 7 23:17:38 2008
@@ -295,6 +295,8 @@
virtual void GenerateSetValueOf(ZoneList<Expression*>* args);
virtual void GenerateFastCharCodeAt(ZoneList<Expression*>* args);
+
+ virtual void GenerateObjectEquals(ZoneList<Expression*>* args);
};
@@ -3995,6 +3997,19 @@
ArgumentsAccessStub stub(false);
__ CallStub(&stub);
__ push(r0);
+}
+
+
+void ArmCodeGenerator::GenerateObjectEquals(ZoneList<Expression*>* args) {
+ ASSERT(args->length() == 2);
+
+ // Load the two objects into registers and perform the comparison.
+ Load(args->at(0));
+ Load(args->at(1));
+ __ pop(r0);
+ __ pop(r1);
+ __ cmp(r0, Operand(r1));
+ cc_reg_ = eq;
}
Modified: branches/bleeding_edge/src/codegen-ia32.cc
==============================================================================
--- branches/bleeding_edge/src/codegen-ia32.cc (original)
+++ branches/bleeding_edge/src/codegen-ia32.cc Sun Sep 7 23:17:38 2008
@@ -314,6 +314,8 @@
virtual void GenerateSetValueOf(ZoneList<Expression*>* args);
virtual void GenerateFastCharCodeAt(ZoneList<Expression*>* args);
+
+ virtual void GenerateObjectEquals(ZoneList<Expression*>* args);
};
@@ -4263,6 +4265,18 @@
__ mov(TOS, eax);
}
+
+void Ia32CodeGenerator::GenerateObjectEquals(ZoneList<Expression*>* args) {
+ ASSERT(args->length() == 2);
+
+ // Load the two objects into registers and perform the comparison.
+ Load(args->at(0));
+ Load(args->at(1));
+ __ pop(eax);
+ __ pop(ecx);
+ __ cmp(eax, Operand(ecx));
+ cc_reg_ = equal;
+}
void Ia32CodeGenerator::VisitCallRuntime(CallRuntime* node) {
Modified: branches/bleeding_edge/src/codegen.cc
==============================================================================
--- branches/bleeding_edge/src/codegen.cc (original)
+++ branches/bleeding_edge/src/codegen.cc Sun Sep 7 23:17:38 2008
@@ -256,7 +256,9 @@
{&v8::internal::CodeGenerator::GenerateSetValueOf,
"_SetValueOf"},
{&v8::internal::CodeGenerator::GenerateFastCharCodeAt,
- "_FastCharCodeAt"}
+ "_FastCharCodeAt"},
+ {&v8::internal::CodeGenerator::GenerateObjectEquals,
+ "_ObjectEquals"}
};
if (node->name()->length() > 0 && node->name()->Get(0) == '_') {
for (unsigned i = 0;
Modified: branches/bleeding_edge/src/codegen.h
==============================================================================
--- branches/bleeding_edge/src/codegen.h (original)
+++ branches/bleeding_edge/src/codegen.h Sun Sep 7 23:17:38 2008
@@ -173,6 +173,9 @@
// Fast support for charCodeAt(n).
virtual void GenerateFastCharCodeAt(ZoneList<Expression*>* args) = 0;
+ // Fast support for object equality testing.
+ virtual void GenerateObjectEquals(ZoneList<Expression*>* args) = 0;
+
private:
bool is_eval_; // Tells whether code is generated for eval.
Handle<Script> script_;
Modified: branches/bleeding_edge/src/mirror-delay.js
==============================================================================
--- branches/bleeding_edge/src/mirror-delay.js (original)
+++ branches/bleeding_edge/src/mirror-delay.js Sun Sep 7 23:17:38 2008
@@ -708,7 +708,7 @@
// Skip properties which are defined through assessors.
var property = properties[i];
if (property.propertyType() != PropertyType.Callbacks) {
- if (%ObjectEquals(property.value_, value.value_) == 0) {
+ if (%_ObjectEquals(property.value_, value.value_)) {
return property;
}
}
@@ -728,12 +728,12 @@
ObjectMirror.prototype.referencedBy = function(opt_max_instances) {
// Find all objects constructed from this function.
var result = %DebugReferencedBy(this.value_, Mirror.prototype,
opt_max_instances || 0);
-
+
// Make mirrors for all the instances found.
for (var i = 0; i < result.length; i++) {
result[i] = MakeMirror(result[i]);
}
-
+
return result;
};
Modified: branches/bleeding_edge/src/runtime.cc
==============================================================================
--- branches/bleeding_edge/src/runtime.cc (original)
+++ branches/bleeding_edge/src/runtime.cc Sun Sep 7 23:17:38 2008
@@ -2309,14 +2309,6 @@
}
-static Object* Runtime_ObjectEquals(Arguments args) {
- NoHandleAllocation ha;
- ASSERT(args.length() == 2);
-
- return Smi::FromInt(args[0] == args[1] ? EQUAL : NOT_EQUAL);
-}
-
-
static Object* Runtime_NumberEquals(Arguments args) {
NoHandleAllocation ha;
ASSERT(args.length() == 2);
@@ -2384,6 +2376,66 @@
if (x == y) return Smi::FromInt(EQUAL);
if (isless(x, y)) return Smi::FromInt(LESS);
return Smi::FromInt(GREATER);
+}
+
+
+// Compare two Smis as if they were converted to strings and then
+// compared lexicographically.
+static Object* Runtime_SmiLexicographicCompare(Arguments args) {
+ NoHandleAllocation ha;
+ ASSERT(args.length() == 2);
+
+ // Arrays for the individual characters of the two Smis. Smis are
+ // 31 bit integers and 10 decimal digits are therefore enough.
+ static int x_elms[10];
+ static int y_elms[10];
+
+ // Extract the integer values from the Smis.
+ CONVERT_CHECKED(Smi, x, args[0]);
+ CONVERT_CHECKED(Smi, y, args[1]);
+ int x_value = x->value();
+ int y_value = y->value();
+
+ // If the integers are equal so are the string representations.
+ if (x_value == y_value) return Smi::FromInt(EQUAL);
+
+ // If one of the integers are zero the normal integer order is the
+ // same as the lexicographic order of the string representations.
+ if (x_value == 0 || y_value == 0) return Smi::FromInt(x_value - y_value);
+
+ // If only one of the intergers is negative the negative number is
+ // smallest because the char code of '-' is less than the char code
+ // of any digit. Otherwise, we make both values positive.
+ if (x_value < 0 || y_value < 0) {
+ if (y_value >= 0) return Smi::FromInt(LESS);
+ if (x_value >= 0) return Smi::FromInt(GREATER);
+ x_value = -x_value;
+ y_value = -y_value;
+ }
+
+ // Convert the integers to arrays of their decimal digits.
+ int x_index = 0;
+ int y_index = 0;
+ while (x_value > 0) {
+ x_elms[x_index++] = x_value % 10;
+ x_value /= 10;
+ }
+ while (y_value > 0) {
+ y_elms[y_index++] = y_value % 10;
+ y_value /= 10;
+ }
+
+ // Loop through the arrays of decimal digits finding the first place
+ // where they differ.
+ while (--x_index >= 0 && --y_index >= 0) {
+ int diff = x_elms[x_index] - y_elms[y_index];
+ if (diff != 0) return Smi::FromInt(diff);
+ }
+
+ // If one array is a suffix of the other array, the longest array is
+ // the representation of the largest of the Smis in the
+ // lexicographic ordering.
+ return Smi::FromInt(x_index - y_index);
}
Modified: branches/bleeding_edge/src/runtime.h
==============================================================================
--- branches/bleeding_edge/src/runtime.h (original)
+++ branches/bleeding_edge/src/runtime.h Sun Sep 7 23:17:38 2008
@@ -106,11 +106,11 @@
F(NumberSar, 2) \
\
/* Comparisons */ \
- F(ObjectEquals, 2) \
F(NumberEquals, 2) \
F(StringEquals, 2) \
\
F(NumberCompare, 3) \
+ F(SmiLexicographicCompare, 2) \
F(StringCompare, 2) \
\
/* Math */ \
Modified: branches/bleeding_edge/src/runtime.js
==============================================================================
--- branches/bleeding_edge/src/runtime.js (original)
+++ branches/bleeding_edge/src/runtime.js Sun Sep 7 23:17:38 2008
@@ -57,13 +57,13 @@
// NOTE: We use iteration instead of recursion, because it is
// difficult to call EQUALS with the correct setting of 'this' in
// an efficient way.
-
+
while (true) {
-
+
if (IS_NUMBER(x)) {
if (y == null) return 1; // not equal
return %NumberEquals(x, %ToNumber(y));
-
+
} else if (IS_STRING(x)) {
if (IS_STRING(y)) return %StringEquals(x, y);
if (IS_NUMBER(y)) return %NumberEquals(%ToNumber(x), y);
@@ -72,19 +72,25 @@
y = %ToPrimitive(y, NO_HINT);
} else if (IS_BOOLEAN(x)) {
- if (IS_BOOLEAN(y)) return %ObjectEquals(x, y);
+ if (IS_BOOLEAN(y)) {
+ return %_ObjectEquals(x, y) ? 0 : 1;
+ }
if (y == null) return 1; // not equal
return %NumberEquals(%ToNumber(x), %ToNumber(y));
-
+
} else if (x == null) {
// NOTE: This checks for both null and undefined.
return (y == null) ? 0 : 1;
-
+
} else {
- if (IS_OBJECT(y)) return %ObjectEquals(x, y);
- if (IS_FUNCTION(y)) return %ObjectEquals(x, y);
+ if (IS_OBJECT(y)) {
+ return %_ObjectEquals(x, y) ? 0 : 1;
+ }
+ if (IS_FUNCTION(y)) {
+ return %_ObjectEquals(x, y) ? 0 : 1;
+ }
x = %ToPrimitive(x, NO_HINT);
-
+
}
}
};
@@ -96,23 +102,23 @@
if (!IS_NUMBER(x)) return 1; // not equal
return %NumberEquals(this, x);
}
-
+
if (IS_STRING(this)) {
if (!IS_STRING(x)) return 1; // not equal
return %StringEquals(this, x);
}
-
+
if (IS_BOOLEAN(this)) {
if (!IS_BOOLEAN(x)) return 1; // not equal
if (this) return x ? 0 : 1;
else return x ? 1 : 0;
}
-
+
if (IS_UNDEFINED(this)) { // both undefined and undetectable
return IS_UNDEFINED(x) ? 0 : 1;
}
-
- return %ObjectEquals(this, x);
+
+ return %_ObjectEquals(this, x) ? 0 : 1;
};
@@ -123,7 +129,7 @@
if (IS_NUMBER(this) && IS_NUMBER(x)) {
return %NumberCompare(this, x, ncr);
}
-
+
var a = %ToPrimitive(this, NUMBER_HINT);
var b = %ToPrimitive(x, NUMBER_HINT);
if (IS_STRING(a) && IS_STRING(b)) {
Modified: branches/bleeding_edge/test/mjsunit/array-sort.js
==============================================================================
--- branches/bleeding_edge/test/mjsunit/array-sort.js (original)
+++ branches/bleeding_edge/test/mjsunit/array-sort.js Sun Sep 7 23:17:38
2008
@@ -30,13 +30,29 @@
// Test counter-intuitive default number sorting.
function TestNumberSort() {
var a = [ 200, 45, 7 ];
- // Default sort calls toString on each element and orders
+
+ // Default sort converts each element to string and orders
// lexicographically.
a.sort();
assertArrayEquals([ 200, 45, 7 ], a);
// Sort numbers by value using a compare functions.
a.sort(function(x, y) { return x - y; });
assertArrayEquals([ 7, 45, 200 ], a);
+
+ // Default sort on negative numbers.
+ a = [-12345,-123,-1234,-123456];
+ a.sort();
+ assertArrayEquals([-123,-1234,-12345,-123456], a);
+
+ // Default sort on negative and non-negative numbers.
+ a = [123456,0,-12345,-123,123,1234,-1234,0,12345,-123456];
+ a.sort();
+ assertArrayEquals([-123,-1234,-12345,-123456,0,0,123,1234,12345,123456],
a);
+
+ // Default sort on Smis and non-Smis.
+ a = [1000000000, 10000000000, 1000000001, -1000000000, -10000000000,
-1000000001];
+ a.sort();
+ assertArrayEquals([-1000000000, -10000000000, -1000000001, 1000000000,
10000000000, 1000000001], a);
}
TestNumberSort();
--~--~---------~--~----~------------~-------~--~----~
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
-~----------~----~----~----~------~----~------~--~---
