Sorting a dense Smi array takes about one third of the time that it used to.
On Fri, Sep 5, 2008 at 11:09 PM, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote: > > In runtime.cc: "from the smis" should be "from the Smis" and "suffic" > should be "suffix". > In array-sort.js: "on a Smis" should be "on Smis". > Otherwise, LGTM. How much does it speed up sorting Smi arrays? > > On Sep 5, 8:50 pm, [EMAIL PROTECTED] wrote: >> Erik, >> >> I'd like you to do a code review. To review this change, run >> >> gvn review --projecthttps://v8.googlecode.com/[EMAIL PROTECTED]/[EMAIL >> PROTECTED] >> >> Alternatively, to review the latest snapshot of this change >> branch, run >> >> gvn --projecthttps://v8.googlecode.com/svnreview [EMAIL >> PROTECTED]/smi-array-sort >> >> to review the following change: >> >> [EMAIL PROTECTED]/[EMAIL PROTECTED] | [EMAIL PROTECTED] | 2008-09-05 >> 19:46:46 +-100 (Fri, 05 Sep 2008) >> >> Description: >> >> Avoid string conversion when comparing Smis during sorting. >> >> Avoid runtime calls for trivial object equality checks. >> >> Minor style cleanups. >> >> Affected Paths: >> M //branches/bleeding_edge/src/array.js >> M //branches/bleeding_edge/src/codegen-arm.cc >> M //branches/bleeding_edge/src/codegen-ia32.cc >> M //branches/bleeding_edge/src/codegen.cc >> M //branches/bleeding_edge/src/codegen.h >> M //branches/bleeding_edge/src/mirror-delay.js >> M //branches/bleeding_edge/src/runtime.cc >> M //branches/bleeding_edge/src/runtime.h >> M //branches/bleeding_edge/src/runtime.js >> M //branches/bleeding_edge/test/mjsunit/array-sort.js >> >> This is a semiautomated message from "gvn mail". See >> <http://code.google.com/p/gvn/> to learn more. >> >> Index: src/array.js >> =================================================================== >> --- src/array.js (^/branches/bleeding_edge/src/[EMAIL PROTECTED]) >> +++ src/array.js (^/changes/[EMAIL >> PROTECTED]/smi-array-sort/bleeding_edge/src/[EMAIL PROTECTED]) >> @@ -219,8 +219,9 @@ function SmartMove(array, start_i, del_count, len, >> // %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 @@ function SmartMove(array, start_i, del_count, len, >> // 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 @@ function SmartMove(array, start_i, del_count, len, >> // %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 @@ function ArraySort(comparefn) { >> 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 @@ function ArraySort(comparefn) { >> 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; >> Index: src/codegen-arm.cc >> =================================================================== >> --- src/codegen-arm.cc (^/branches/bleeding_edge/src/[EMAIL PROTECTED]) >> +++ src/codegen-arm.cc (^/changes/[EMAIL >> PROTECTED]/smi-array-sort/bleeding_edge/src/[EMAIL PROTECTED]) >> @@ -295,6 +295,8 @@ class ArmCodeGenerator: public CodeGenerator { >> virtual void GenerateSetValueOf(ZoneList<Expression*>* args); >> >> virtual void GenerateFastCharCodeAt(ZoneList<Expression*>* args); >> + >> + virtual void GenerateObjectEquals(ZoneList<Expression*>* args); >> }; >> >> @@ -3998,6 +4000,19 @@ void ArmCodeGenerator::GenerateArgumentsAccess(Zon >> } >> >> +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; >> +} >> + >> + >> void ArmCodeGenerator::GenerateShiftDownAndTailCall( >> ZoneList<Expression*>* args) { >> // r0 = number of arguments >> Index: src/codegen-ia32.cc >> =================================================================== >> --- src/codegen-ia32.cc (^/branches/bleeding_edge/src/[EMAIL PROTECTED]) >> +++ src/codegen-ia32.cc (^/changes/[EMAIL >> PROTECTED]/smi-array-sort/bleeding_edge/src/[EMAIL PROTECTED]) >> @@ -314,6 +314,8 @@ class Ia32CodeGenerator: public CodeGenerator { >> virtual void GenerateSetValueOf(ZoneList<Expression*>* args); >> >> virtual void GenerateFastCharCodeAt(ZoneList<Expression*>* args); >> + >> + virtual void GenerateObjectEquals(ZoneList<Expression*>* args); >> }; >> >> @@ -4264,7 +4266,19 @@ void Ia32CodeGenerator::GenerateArgumentsAccess(Zo >> } >> >> +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) { >> if (CheckForInlineRuntimeCall(node)) return; >> >> Index: src/codegen.cc >> =================================================================== >> --- src/codegen.cc (^/branches/bleeding_edge/src/[EMAIL PROTECTED]) >> +++ src/codegen.cc (^/changes/[EMAIL >> PROTECTED]/smi-array-sort/bleeding_edge/src/[EMAIL PROTECTED]) >> @@ -256,7 +256,9 @@ bool CodeGenerator::CheckForInlineRuntimeCall(Call >> {&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; >> Index: src/codegen.h >> =================================================================== >> --- src/codegen.h (^/branches/bleeding_edge/src/[EMAIL PROTECTED]) >> +++ src/codegen.h (^/changes/[EMAIL >> PROTECTED]/smi-array-sort/bleeding_edge/src/[EMAIL PROTECTED]) >> @@ -173,6 +173,9 @@ class CodeGenerator: public Visitor { >> // 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_; >> Index: src/mirror-delay.js >> =================================================================== >> --- src/mirror-delay.js (^/branches/bleeding_edge/src/[EMAIL PROTECTED]) >> +++ src/mirror-delay.js (^/changes/[EMAIL >> PROTECTED]/smi-array-sort/bleeding_edge/src/[EMAIL PROTECTED]) >> @@ -708,7 +708,7 @@ ObjectMirror.prototype.lookupProperty = function(v >> // 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.lookupProperty = function(v >> 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; >> }; >> >> Index: src/runtime.cc >> =================================================================== >> --- src/runtime.cc (^/branches/bleeding_edge/src/[EMAIL PROTECTED]) >> +++ src/runtime.cc (^/changes/[EMAIL >> PROTECTED]/smi-array-sort/bleeding_edge/src/[EMAIL PROTECTED]) >> @@ -2309,14 +2309,6 @@ static Object* Runtime_NumberSar(Arguments args) { >> } >> >> -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); >> @@ -2387,6 +2379,66 @@ static Object* Runtime_NumberCompare(Arguments arg >> } >> >> +// 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 suffic 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); >> +} >> + >> + >> static Object* Runtime_StringCompare(Arguments args) { >> NoHandleAllocation ha; >> ASSERT(args.length() == 2); >> Index: src/runtime.h >> =================================================================== >> --- src/runtime.h (^/branches/bleeding_edge/src/[EMAIL PROTECTED]) >> +++ src/runtime.h (^/changes/[EMAIL >> PROTECTED]/smi-array-sort/bleeding_edge/src/[EMAIL PROTECTED]) >> @@ -106,11 +106,11 @@ namespace v8 { namespace internal { >> F(NumberSar, 2) \ >> \ >> /* Comparisons */ \ >> - F(ObjectEquals, 2) \ >> F(NumberEquals, 2) \ >> F(StringEquals, 2) \ >> \ >> F(NumberCompare, 3) \ >> + F(SmiLexicographicCompare, 2) \ >> F(StringCompare, 2) \ >> \ >> /* Math */ \ >> Index: src/runtime.js >> =================================================================== >> --- src/runtime.js (^/branches/bleeding_edge/src/[EMAIL PROTECTED]) >> +++ src/runtime.js (^/changes/[EMAIL >> PROTECTED]/smi-array-sort/bleeding_edge/src/[EMAIL PROTECTED]) >> @@ -57,13 +57,13 @@ function EQUALS(y) { >> // 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 @@ function EQUALS(y) { >> 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 @@ function STRICT_EQUALS(x) { >> 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 @@ function COMPARE(x, ncr) { >> 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)) { >> Index: test/mjsunit/array-sort.js >> =================================================================== >> --- test/mjsunit/array-sort.js >> (^/branches/bleeding_edge/test/mjsunit/[EMAIL PROTECTED]) >> +++ test/mjsunit/array-sort.js (^/changes/[EMAIL >> PROTECTED]/smi-array-sort/bleeding_edge/test/mjsunit/[EMAIL PROTECTED]) >> @@ -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 a 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 -~----------~----~----~----~------~----~------~--~---
