Performance improvement for Math.max and Math.min...

Performance improvement for Math.max and Math.min

The old code for Math.max was computing -Infinity for each call, and
doing N comparisons for N arguments, the first comparison guaranteed
to be fairly slow because it is against -Infinity.

The new code does N-1 comparisons, which are all SMI comparisons if
the arguments are all SMIs.

Timings, in ns/call over 2M calls. The functions were run on several
workloads - SMIs or heap nums, arguments ascending or descending.
Times quoted are the best of 5 runs, the high and low ranges for the
'easiest' and 'hardest' workload.

Old:
Arguments:   0      1      2       3        4
Math.min : 20-21  40-45  45-58   70-108   83-142
Math.max : 69-72  88-89  96-116 117-156  133-188

New:
Math.min : 19-20  19-24  26-47   42-88    52-112
Math.max : 19-20  19-23  26-46   41-85    52-111

Above times include timing loop and call overhead of:
              12     13      8      15       16

For typical use Math.max is 2.5-3.7x faster.
Math.min is 1.2-1.7x faster.

Committed as V8 bleeding edge revision 3433

[Erik Corry, 2009-12-07 08:17:40]

LGTM, thanks!

[William Hesse, 2009-12-08 00:37:21]

LGTM.  Possible (tiny) improvement:

http://codereview.chromium.org/470001/diff/4001/4002
File src/math.js (right):

http://codereview.chromium.org/470001/diff/4001/4002#newcode132
src/math.js:132: if (n > r || (r === 0 && n === 0 && !%_IsSmi(r))) r = n;
The only way this can give a wrong -0 answer is if the last 0 is -0 and there is
a +0.  Maybe the single test (!%_IsSmi(r) && r === 0) after the loop is faster,
going to a search for +0 if it fails.  It might not be worth it, but if -0 is
rare we don't need to test for on every iteration.  This is only possibly worth
it on Max, not Min.

[sra1, 2009-12-08 01:57:50]

http://codereview.chromium.org/470001/diff/4001/4002
File src/math.js (right):

http://codereview.chromium.org/470001/diff/4001/4002#newcode132
src/math.js:132: if (n > r || (r === 0 && n === 0 && !%_IsSmi(r))) r = n;
Interesting point.  Considering that almost all calls are 2 argument calls,
probably not worth the code bloat to 'avoid' doing work in the single iteration.

On 2009/12/08 00:37:21, William Hesse wrote:
> The only way this can give a wrong -0 answer is if the last 0 is -0 and there
is
> a +0.  Maybe the single test (!%_IsSmi(r) && r === 0) after the loop is
faster,
> going to a search for +0 if it fails.  It might not be worth it, but if -0 is
> rare we don't need to test for on every iteration.  This is only possibly
worth
> it on Max, not Min.

[sra1, 2009-12-08 06:01:12]

After thinking about Bill's comment, I realized there is a bug in change r2367
where the fast Smi test was originally introduced.
While it is necessary that a value needs to be non-Smi in order to be -0, it is
not sufficient because you can have a non-Smi positive zero.
Consider:
> var x = .3
> 1/Math.max(x-x, -0)
-Infinity   //Bug!
> 1/Math.max(-0, x-x)
Infinity

I have fixed this bug by putting the 1/x<0 test back in, and updated the tests
to cover this case.

[Erik Corry, 2009-12-08 10:16:30]

On 2009/12/08 06:01:12, sra1 wrote:
> After thinking about Bill's comment, I realized there is a bug in change r2367
> where the fast Smi test was originally introduced.
> While it is necessary that a value needs to be non-Smi in order to be -0, it
is
> not sufficient because you can have a non-Smi positive zero.
> Consider:
> > var x = .3
> > 1/Math.max(x-x, -0)
> -Infinity   //Bug!
> > 1/Math.max(-0, x-x)
> Infinity
> 
> I have fixed this bug by putting the 1/x<0 test back in, and updated the tests
> to cover this case.

[Erik Corry, 2009-12-08 10:18:56]

On 2009/12/08 06:01:12, sra1 wrote:
> After thinking about Bill's comment, I realized there is a bug in change r2367
> where the fast Smi test was originally introduced.
> While it is necessary that a value needs to be non-Smi in order to be -0, it
is
> not sufficient because you can have a non-Smi positive zero.
> Consider:
> > var x = .3
> > 1/Math.max(x-x, -0)
> -Infinity   //Bug!
> > 1/Math.max(-0, x-x)
> Infinity
> 
> I have fixed this bug by putting the 1/x<0 test back in, and updated the tests
> to cover this case.

(Sorry for empty reply).

Good catch.  Committed as bleeding edge 3433