Implement Math.sin, cos and tan using table lookup and spline interpolation.

Implement Math.sin, cos and tan using table lookup and spline interpolation.

R=jkummerow@chromium.org
BUG=

Committed: https://code.google.com/p/v8/source/detail?r=17594

[Yang, 2013-10-29 15:56:15]

Please take a look.

For the record, the root mean square of the absolute error with the existing
(FPU) sin and cos on the chose test input values is 8.6962e-15, the new
implementation achieves 8.7320e-15.

[Jakob Kummerow, 2013-10-29 17:17:53]

LGTM with comments.

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

https://codereview.chromium.org/50563003/diff/1/src/math.js#newcode220
src/math.js:220: var samples = 2048;  // Table size;
nit: s/size;/size./

https://codereview.chromium.org/50563003/diff/1/src/objects.cc
File src/objects.cc (right):

https://codereview.chromium.org/50563003/diff/1/src/objects.cc#newcode9960
src/objects.cc:9960: if (code()->kind() == Code::OPTIMIZED_FUNCTION) return
true;
I know you just moved this line around, but I think this never can and never
could happen.

https://codereview.chromium.org/50563003/diff/1/src/runtime.cc
File src/runtime.cc (right):

https://codereview.chromium.org/50563003/diff/1/src/runtime.cc#newcode7879
src/runtime.cc:7879: for (int i = 1; i < samples + 1; i++) {
i = 1? Why not i = 0?

https://codereview.chromium.org/50563003/diff/1/test/mjsunit/sin-cos.js
File test/mjsunit/sin-cos.js (right):

https://codereview.chromium.org/50563003/diff/1/test/mjsunit/sin-cos.js#newco...
test/mjsunit/sin-cos.js:70: var terms = [];
Might wanna add a comment here that the reason for the "needless" allocation is
that we sum up the terms in reverse order for increased precision.

https://codereview.chromium.org/50563003/diff/1/test/mjsunit/sin-cos.js#newco...
test/mjsunit/sin-cos.js:123: // Sum squares up by adding them pairwise, to avoid
not losing precision.
s/not // ;-)

[Sven Panne, 2013-10-30 07:51:56]

DBC

https://codereview.chromium.org/50563003/diff/80001/src/math.js
File src/math.js (right):

https://codereview.chromium.org/50563003/diff/80001/src/math.js#newcode207
src/math.js:207: var MathSinImpl = function(x) {
Why do we do this "poor man's lazy evaluation" instead of initializing the
tables directly at startup? This would have the additional benefit that the
table is directly in the snapshot, and things would be much clearer and simpler.

[Jakob Kummerow, 2013-10-30 08:04:44]

https://codereview.chromium.org/50563003/diff/80001/src/math.js
File src/math.js (right):

https://codereview.chromium.org/50563003/diff/80001/src/math.js#newcode207
src/math.js:207: var MathSinImpl = function(x) {
On 2013/10/30 07:51:56, Sven Panne wrote:
> Why do we do this "poor man's lazy evaluation" instead of initializing the
> tables directly at startup? This would have the additional benefit that the
> table is directly in the snapshot, and things would be much clearer and
simpler.

The thinking was that trigonometric functions are not important enough to
warrant the snapshot/binary size increase. FWIW, Math.exp also follows the
pattern of initializing the lookup table on first use. A potential follow-up CL
is to entirely skip using lookup tables when FLAG_optimize_for_size, e.g. by
using direct uncached library calls.

https://codereview.chromium.org/50563003/diff/80001/src/math.js#newcode221
src/math.js:221: var pi = 3.1415926535897932;
Does it make a speed difference if you move all these constants into the
MathSinImpl function literal below?

https://codereview.chromium.org/50563003/diff/80001/test/mjsunit/sin-cos.js
File test/mjsunit/sin-cos.js (right):

https://codereview.chromium.org/50563003/diff/80001/test/mjsunit/sin-cos.js#n...
test/mjsunit/sin-cos.js:65: print(e)
nit: debugging leftover

[Sven Panne, 2013-10-30 08:19:10]

https://codereview.chromium.org/50563003/diff/80001/src/math.js
File src/math.js (right):

https://codereview.chromium.org/50563003/diff/80001/src/math.js#newcode207
src/math.js:207: var MathSinImpl = function(x) {
On 2013/10/30 08:04:44, Jakob wrote:
> The thinking was that trigonometric functions are not important enough to
> warrant the snapshot/binary size increase. FWIW, Math.exp also follows the
> pattern of initializing the lookup table on first use. A potential follow-up
CL
> is to entirely skip using lookup tables when FLAG_optimize_for_size, e.g. by
> using direct uncached library calls.

Hmmm, are we really already at the point where saving 32kB is important compared
to increased code complexity? I somehow doubt that. And even if this was the
case, using the common polynomial approximation (used e.g. in
http://www.netlib.org/fdlibm/k_sin.c) would remove the need for any table and
any kind of interpolation.

Another point is: How can we assure that the sin/cos/... call sites are still
monomorphic with the "lazy eval" approach in this CL? Perhaps there is some
magic, but I fail to see it...

[Yang, 2013-10-30 12:33:19]

On 2013/10/30 08:19:10, Sven Panne wrote:
> https://codereview.chromium.org/50563003/diff/80001/src/math.js
> File src/math.js (right):
> 
> https://codereview.chromium.org/50563003/diff/80001/src/math.js#newcode207
> src/math.js:207: var MathSinImpl = function(x) {
> On 2013/10/30 08:04:44, Jakob wrote:
> > The thinking was that trigonometric functions are not important enough to
> > warrant the snapshot/binary size increase. FWIW, Math.exp also follows the
> > pattern of initializing the lookup table on first use. A potential follow-up
> CL
> > is to entirely skip using lookup tables when FLAG_optimize_for_size, e.g. by
> > using direct uncached library calls.
> 
> Hmmm, are we really already at the point where saving 32kB is important
compared
> to increased code complexity? I somehow doubt that. And even if this was the
> case, using the common polynomial approximation (used e.g. in
> http://www.netlib.org/fdlibm/k_sin.c) would remove the need for any table and
> any kind of interpolation.
> 
> Another point is: How can we assure that the sin/cos/... call sites are still
> monomorphic with the "lazy eval" approach in this CL? Perhaps there is some
> magic, but I fail to see it...

Loading from the context and loading constants from two immediates are roughly
equally fast, there is no point in preferring one to the other, and the current
way is easier on the eye imo.

Call sites are monomorphic because, as Jakob mentioned offline, we have a
premonomorphic state prior to monomorphic.

If we pre-calculate the table and include it in the snapshot, we eagerly pay for
it during deserialization of the snapshot.

[Yang, 2013-11-08 13:10:51]

Committed patchset #6 manually as r17594 (presubmit successful).