Improvement to SmiLexicalCompare

Improvement to SmiLexicalCompare

If two positive Smis have the same number of decimal digits the
lexical order is the same as the numeric order.  Values with different
numbers of decimal digits are compared by pre-scaling with some power
of 10 to make the number of digits the same.

This approach avoids the expensive digit generation loop of the
previous approach.

Strengthened testing and fixed bugs.  There were several places where
the code was incorrect 32-bit Smis when one of the values is MIN_INT.

[sra1, 2011-06-25 00:23:03]

The benchmark below goes from ~10000 us to ~6000 us.
There does not appear to be a good benchmark for sorting on golem.
celtickane-array improves by a few percent.
http://spartan0.spb:9013/v8/r8424-v8-sra-scaled-try-3-base.html

I have tried to make the platform/compiler dependent parts work but I have no
way to build on anything but Goobuntu.  I did test default version of
IntegerLog2.

I tried uploading win7 and arm variants to golem but they never get built.


Benchmark:

function setup() {
  var a = [];
  for (var i = 0; i < 10000; i++) a[i] = i;
  return a;
}

// Reversible transformation: sign extend the low byte and xor into the high
// bits.
function flip(x) { return x ^ (((x & 127) - (x & 128)) << 23); }

function benchmark(a) {
  // Alternate passes sort small numbers and mixed large and small numbers.
  for (var i = 0; i < a.length; i++) a[i] = flip(a[i]);
  a.sort();
}

var arr = setup();
var elapsed = 0;
var start = new Date();
for (var n = 0; elapsed < 2000; n++) {
  benchmark(arr);
  elapsed = new Date() - start;
}
print('Time (sort-smi): ' + Math.floor(1000 * elapsed/n) + ' us.');

[Erik Corry, 2011-06-25 11:12:03]

Do we have adequate test coverage?  Cases that should be covered include:

One value is zero, other value is negative, positive, zero.
Values that would overflow like the example in the comments, 1e9 and 9.
All pairs on the power-of-10 borders like 99 vs. 100, 999 vs. 1000.
Max positive and negative ints and Smis together with a selection of other ints.
Please test on x64 where Smis are 32 bit.

LGTM with either tests or a pointer to an existing mjsunit test that covers all
this.

http://codereview.chromium.org/7261008/diff/1/src/misc-intrinsics.h
File src/misc-intrinsics.h (right):

http://codereview.chromium.org/7261008/diff/1/src/misc-intrinsics.h#newcode42
src/misc-intrinsics.h:42: } }  // namespace v8::internal
Instead of closing the name space here and then using explicit name spaces on
the definitions below you can just close it at the end.

http://codereview.chromium.org/7261008/diff/1/src/misc-intrinsics.h#newcode67
src/misc-intrinsics.h:67: shift = (value > 0xFFFF) << 4;  value >>= shift;  
result = shift;
This code won't pass presubmit.py.  See
http://code.google.com/p/v8/wiki/Contributing
Also, we don't normally allow booleans to be used in a numeric way.  Please
replace with ?:

http://codereview.chromium.org/7261008/diff/1/src/runtime.cc
File src/runtime.cc (right):

http://codereview.chromium.org/7261008/diff/1/src/runtime.cc#newcode6665
src/runtime.cc:6665: static const int powersOf10[] = { 1, 10, 100, 1000,
10*1000, 100*1000,
This is a constant so it should be named as a constant:  kPowersOf10.
Also, the indentation is wrong.  Newline-after { is the norm in the rest of the
code base and } gets its own line.

[sra1, 2011-06-25 19:31:33]

There are good tests in array-sort, but I think they miss some cases (max-smi,
min-smi).  I'll extend the tests.

What should I do about this presubmit warning?
I can't change long to some other type because it is passed by pointer, and that
is what the headers define the intrinsic as taking.

http://codereview.chromium.org/7261008/diff/1/src/misc-intrinsics.h
File src/misc-intrinsics.h (right):

http://codereview.chromium.org/7261008/diff/1/src/misc-intrinsics.h#newcode42
src/misc-intrinsics.h:42: } }  // namespace v8::internal
On 2011/06/25 11:12:03, Erik Corry wrote:
> Instead of closing the name space here and then using explicit name spaces on
> the definitions below you can just close it at the end.

Done.  Originally I was expecting to have to #include other files, like
atomicops.

http://codereview.chromium.org/7261008/diff/1/src/runtime.cc
File src/runtime.cc (right):

http://codereview.chromium.org/7261008/diff/1/src/runtime.cc#newcode6665
src/runtime.cc:6665: static const int powersOf10[] = { 1, 10, 100, 1000,
10*1000, 100*1000,
On 2011/06/25 11:12:03, Erik Corry wrote:
> This is a constant so it should be named as a constant:  kPowersOf10.
> Also, the indentation is wrong.  Newline-after { is the norm in the rest of
the
> code base and } gets its own line.

Done.

[sra1, 2011-06-25 22:04:10]

PTAL

[Erik Corry, 2011-06-27 07:27:30]

LGTM

[Lasse Reichstein, 2011-06-27 08:41:47]

drive-by comment.

http://codereview.chromium.org/7261008/diff/3004/test/mjsunit/array-sort.js
File test/mjsunit/array-sort.js (right):

http://codereview.chromium.org/7261008/diff/3004/test/mjsunit/array-sort.js#n...
test/mjsunit/array-sort.js:80: assertEquals(false, %_IsSmi(2147483648), 'Update
test for >32 bit Smi');
Use assertFalse instead of assertEquals(false,