Implement Math.random() purely in JavaScript.

Implement Math.random() purely in JavaScript.

This removes tons of architecture-specific code and makes it easy to
experiment with other pseudo-RNG algorithms. The crankshafted code is
extremely good, keeping all things unboxed and doing only minimal
checks, so it is basically equivalent to the handwritten code.

When benchmarks are run without parallel recompilation, we get a few
percent regression on SunSpider's string-validate-input and
string-base64, but these benchmarks run so fast that the overall
SunSpider score is hardly affected and within the usual jitter. Note
that these benchmarks actually run even faster when we don't
crankshaft at all on the main thread (the regression is not caused by
bad code, it is caused by Crankshaft needing a few hundred microsecond
for compilation of a trivial function). Luckily, when parallel
recompilation is enabled, i.e. in the browser, we see no regression at
all!

R=mstarzinger@chromium.org

Committed: http://code.google.com/p/v8/source/detail?r=17955

[Sven Panne, 2013-11-11 13:36:52]

Almost red-only... :-)

[Michael Starzinger, 2013-11-11 14:11:11]

LGTM with a few minor comments to address.

https://codereview.chromium.org/68723002/diff/1/src/assembler.cc
File src/assembler.cc (left):

https://codereview.chromium.org/68723002/diff/1/src/assembler.cc#oldcode1064
src/assembler.cc:1064: ExternalReference
ExternalReference::random_uint32_function(
Please also remove the declaration in the assembler.h file.

https://codereview.chromium.org/68723002/diff/1/src/bootstrapper.cc
File src/bootstrapper.cc (right):

https://codereview.chromium.org/68723002/diff/1/src/bootstrapper.cc#newcode2644
src/bootstrapper.cc:2644: factory()->NewHeapNumber(state[0]),
Better use Factory::NewNumberFromUint here and in the call below.

https://codereview.chromium.org/68723002/diff/1/src/math.js
File src/math.js (right):

https://codereview.chromium.org/68723002/diff/1/src/math.js#newcode180
src/math.js:180: random0 = r0;
I am not sure about the sequence of the initialization here. Can we make sure
that "random0" and "random1" are bound to global variables by explicitly
declaring them at the top-level a few lines above? Thereby it is more obvious to
where these two variables are bound.

[Sven Panne, 2013-11-12 07:09:12]

Addressed feedback. Need to look into some regressions in SunSpider's
string-base64 and string-validate-input benchmarks. Basically they seem to
measure Math.random's performance, which you can of course guess from the
benchmark's names and is of utmost importance for real-world JavaScript... :-P

https://codereview.chromium.org/68723002/diff/1/src/assembler.cc
File src/assembler.cc (left):

https://codereview.chromium.org/68723002/diff/1/src/assembler.cc#oldcode1064
src/assembler.cc:1064: ExternalReference
ExternalReference::random_uint32_function(
On 2013/11/11 14:11:12, Michael Starzinger wrote:
> Please also remove the declaration in the assembler.h file.

Done.

https://codereview.chromium.org/68723002/diff/1/src/bootstrapper.cc
File src/bootstrapper.cc (right):

https://codereview.chromium.org/68723002/diff/1/src/bootstrapper.cc#newcode2644
src/bootstrapper.cc:2644: factory()->NewHeapNumber(state[0]),
On 2013/11/11 14:11:12, Michael Starzinger wrote:
> Better use Factory::NewNumberFromUint here and in the call below.

Done.

https://codereview.chromium.org/68723002/diff/1/src/math.js
File src/math.js (right):

https://codereview.chromium.org/68723002/diff/1/src/math.js#newcode180
src/math.js:180: random0 = r0;
On 2013/11/11 14:11:12, Michael Starzinger wrote:
> I am not sure about the sequence of the initialization here. Can we make sure
> that "random0" and "random1" are bound to global variables by explicitly
> declaring them at the top-level a few lines above? Thereby it is more obvious
to
> where these two variables are bound.

Done.

[Yang, 2013-11-12 10:54:00]

On 2013/11/12 07:09:12, Sven Panne wrote:
> Addressed feedback. Need to look into some regressions in SunSpider's
> string-base64 and string-validate-input benchmarks. Basically they seem to
> measure Math.random's performance, which you can of course guess from the
> benchmark's names and is of utmost importance for real-world JavaScript... :-P
> 
> https://codereview.chromium.org/68723002/diff/1/src/assembler.cc
> File src/assembler.cc (left):
> 
> https://codereview.chromium.org/68723002/diff/1/src/assembler.cc#oldcode1064
> src/assembler.cc:1064: ExternalReference
> ExternalReference::random_uint32_function(
> On 2013/11/11 14:11:12, Michael Starzinger wrote:
> > Please also remove the declaration in the assembler.h file.
> 
> Done.
> 
> https://codereview.chromium.org/68723002/diff/1/src/bootstrapper.cc
> File src/bootstrapper.cc (right):
> 
>
https://codereview.chromium.org/68723002/diff/1/src/bootstrapper.cc#newcode2644
> src/bootstrapper.cc:2644: factory()->NewHeapNumber(state[0]),
> On 2013/11/11 14:11:12, Michael Starzinger wrote:
> > Better use Factory::NewNumberFromUint here and in the call below.
> 
> Done.
> 
> https://codereview.chromium.org/68723002/diff/1/src/math.js
> File src/math.js (right):
> 
> https://codereview.chromium.org/68723002/diff/1/src/math.js#newcode180
> src/math.js:180: random0 = r0;
> On 2013/11/11 14:11:12, Michael Starzinger wrote:
> > I am not sure about the sequence of the initialization here. Can we make
sure
> > that "random0" and "random1" are bound to global variables by explicitly
> > declaring them at the top-level a few lines above? Thereby it is more
obvious
> to
> > where these two variables are bound.
> 
> Done.

I have two things in mind that could improve performance, both of which also
apply to the javascript implementation of Math.sin
- Math.random is no longer inlined with this CL, which is very important for
performance. Inlining builtins seems to be a tricky business, and so far, we
manually chose them for inlining via TryInlining{Builtin|Method}Call. Simply
using our inlining heuristics to also automatically choose builtins for inlining
does not work out well. With my math.sin CL, I'm introducing a
%SetInlineBuiltinFlag, mirroring %SetNativeFlag, as compiler hint to force
inline the specified function. This is no different than what we do with
TryInlining{Builtin|Method}Call anyways.
- You are using division by 0x100000000 at the end, which is slightly more
expensive than multiplying with the inverse (I checked). Not sure if the result
is exactly the same, though (I think it is).

[Yang, 2013-11-12 11:02:53]

On 2013/11/12 10:54:00, Yang wrote:
> On 2013/11/12 07:09:12, Sven Panne wrote:
> > Addressed feedback. Need to look into some regressions in SunSpider's
> > string-base64 and string-validate-input benchmarks. Basically they seem to
> > measure Math.random's performance, which you can of course guess from the
> > benchmark's names and is of utmost importance for real-world JavaScript...
:-P
> > 
> > https://codereview.chromium.org/68723002/diff/1/src/assembler.cc
> > File src/assembler.cc (left):
> > 
> > https://codereview.chromium.org/68723002/diff/1/src/assembler.cc#oldcode1064
> > src/assembler.cc:1064: ExternalReference
> > ExternalReference::random_uint32_function(
> > On 2013/11/11 14:11:12, Michael Starzinger wrote:
> > > Please also remove the declaration in the assembler.h file.
> > 
> > Done.
> > 
> > https://codereview.chromium.org/68723002/diff/1/src/bootstrapper.cc
> > File src/bootstrapper.cc (right):
> > 
> >
>
https://codereview.chromium.org/68723002/diff/1/src/bootstrapper.cc#newcode2644
> > src/bootstrapper.cc:2644: factory()->NewHeapNumber(state[0]),
> > On 2013/11/11 14:11:12, Michael Starzinger wrote:
> > > Better use Factory::NewNumberFromUint here and in the call below.
> > 
> > Done.
> > 
> > https://codereview.chromium.org/68723002/diff/1/src/math.js
> > File src/math.js (right):
> > 
> > https://codereview.chromium.org/68723002/diff/1/src/math.js#newcode180
> > src/math.js:180: random0 = r0;
> > On 2013/11/11 14:11:12, Michael Starzinger wrote:
> > > I am not sure about the sequence of the initialization here. Can we make
> sure
> > > that "random0" and "random1" are bound to global variables by explicitly
> > > declaring them at the top-level a few lines above? Thereby it is more
> obvious
> > to
> > > where these two variables are bound.
> > 
> > Done.
> 
> I have two things in mind that could improve performance, both of which also
> apply to the javascript implementation of Math.sin
> - Math.random is no longer inlined with this CL, which is very important for
> performance. Inlining builtins seems to be a tricky business, and so far, we
> manually chose them for inlining via TryInlining{Builtin|Method}Call. Simply
> using our inlining heuristics to also automatically choose builtins for
inlining
> does not work out well. With my math.sin CL, I'm introducing a
> %SetInlineBuiltinFlag, mirroring %SetNativeFlag, as compiler hint to force
> inline the specified function. This is no different than what we do with
> TryInlining{Builtin|Method}Call anyways.
> - You are using division by 0x100000000 at the end, which is slightly more
> expensive than multiplying with the inverse (I checked). Not sure if the
result
> is exactly the same, though (I think it is).

Force-inlining MathRandom using %SetInlineBuiltinFlag, I was able to get the
runtime of the following microbenchmark from 310ms to 275ms.

var r = 0;
for (var i = 0; i < 10000000; i++) {
  r = Math.random();
}

Granted, this is not a good benchmark, but neither is sunspider.

[Sven Panne, 2013-11-15 13:50:21]

Now with typed arrays, which leads to much better code. PTAL again...

[Michael Starzinger, 2013-11-15 14:29:19]

Still LGTM.

[Sven Panne, 2013-11-21 09:55:37]

Committed patchset #5 manually as r17955 (presubmit successful).