This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: [PATCH 02/10] Improve performance of sincosf
- From: Wilco Dijkstra <Wilco dot Dijkstra at arm dot com>
- To: Joseph Myers <joseph at codesourcery dot com>, Szabolcs Nagy <Szabolcs dot Nagy at arm dot com>
- Cc: GNU C Library <libc-alpha at sourceware dot org>, nd <nd at arm dot com>
- Date: Fri, 10 Aug 2018 12:12:38 +0000
- Subject: Re: [PATCH 02/10] Improve performance of sincosf
- References: <d4963b4e-0013-adaf-df2f-698cf421a487@arm.com> <725dd4a7-f002-65da-4e5c-370cb78c3e77@arm.com> <e9ca9a7b-05df-715e-0e4b-b5c80be344b2@arm.com>,<alpine.DEB.2.20.1808071952350.20640@digraph.polyomino.org.uk>
Joseph Myers wrote:
>> +/* Fast sincosf implementation. Worst-case ULP is 0.56072, maximum relative
>> + error is 0.5303p-23. A single-step signed range reduction is used for
>
> I don't think this funny mixture of decimal and hex float notation, not a
> valid constant in C, is a good idea. (Saying 0.5303*0x1p-23 or similar
> would be fine, if that's what you mean.)
Fixed.
>> +#if WANT_ERRNO
>> + /* Needed to set errno for +-Inf, the add is a hack to work
>> + around a gcc register allocation issue: just passing y
>> + affects code generation in the fast path. */
>> + __math_invalidf (y + y);
>
> Is there a GCC bug filed for this? A reference to a specific bug number
> is much better than "a gcc register allocation issue" for anyone trying to
> tell in future if the issue is still relevant or not.
I've created PR86901 for this.
>> +/* PI * 2^-64. */
>> +static const double pi64 = 0x1.921FB54442D18p-62;
>
> That's actually PI * 2^-63, so the comment and variable name are
> misleading.
Yes I guess I changed the exponent at some point but not the name - fixed.
>> + Use round/lround if inlined, otherwise convert to int. To avoid inaccuracies
>> + introduced by truncating negative values, compute the quadrant * 2^24. */
>
> I think this last statement is actually describing what the
> [!TOINT_INTRINSICS] code does, rather than part of the interface of the
> function. So it should be inside that part of the #if inside the
> function; the comment above the function should be about what the
> function's interface is, not avoid such details of the implementation.
I've added comments describing the implementation details inside the function.
> However, the comment relates to *another* interface - that is, what the
> semantics of the hpi_inv member of sincos_t are. So I think the
> definition of the sincos_t struct should have comments explaining the
> semantics of its members, and the one on hpi_inv would explain the
> dependence on TOINT_INTRINSICS.
I've added comments for all members of the struct. Also sincosf_data.c now
uses TOINT_INTRINSICS to select the right scale.
>> +/* Reduce the range of XI to a multiple of PI/4 using fast integer arithmetic.
>> + XI is a reinterpreted float and must be >= 2.0f (the sign bit is ignored).
>> + Return the modulo between -PI/4 and PI/4 and store the quadrant in NP.
>
> Aren't you actually reducing to an interval of length PI/2 (not PI/4)
> (it's not really clear to me what "to a multiple of PI/4" is meant to
> mean), with the result thus in the range -PI/4 and PI/4?
It's true the quadrant returned is a multiple of PI/2, however it is shifted by PI/4 from
the most obvious definition of x MOD PI/2. Internally we need to consider multiples
of PI/4. As for the table, yes it's just bits without a clear fixed point.
Wilco
Version 6: improve comments based on review.
This patch is a complete rewrite of sinf, cosf and sincosf. The new version
is significantly faster, as well as simple and accurate.
The worst-case ULP is 0.5607, maximum relative error is 0.5303 * 2^-23 over
all 4 billion inputs. In non-nearest rounding modes the error is 1ULP.
The algorithm uses 3 main cases: small inputs which don't need argument
reduction, small inputs which need a simple range reduction and large inputs
requiring complex range reduction. The code uses approximate integer
comparisons to quickly decide between these cases.
The small range reducer uses a single reduction step to handle values up to
120.0. It is fastest on targets which support inlined round instructions.
The large range reducer uses integer arithmetic for simplicity. It does a
32x96 bit multiply to compute a 64-bit modulo result. This is more than
accurate enough to handle the worst-case cancellation for values close to
an integer multiple of PI/4. It could be further optimized, however it is
already much faster than necessary.
sincosf throughput gains on Cortex-A72:
* |x| < 0x1p-12 : 1.6x
* |x| < M_PI_4 : 1.7x
* |x| < 2 * M_PI: 1.5x
* |x| < 120.0 : 1.8x
* |x| < Inf : 2.3x
On a benchmark with significant use of sincosf the overall speedup is >33%.
ChangeLog:
2018-08-10 Wilco Dijkstra <wdijkstr@arm.com>
Szabolcs Nagy <szabolcs.nagy@arm.com>
* math/Makefile: Add s_sincosf_data.c.
* sysdeps/ia64/fpu/s_sincosf_data.c: New file.
* sysdeps/ieee754/flt-32/s_sincosf.h (abstop12): Add new function.
(sincosf_poly): Likewise.
(reduce_small): Likewise.
(reduce_large): Likewise.
* sysdeps/ieee754/flt-32/s_sincosf.c (sincosf): Rewrite.
* sysdeps/ieee754/flt-32/s_sincosf_data.c: New file with sincosf data.
* sysdeps/m68k/m680x0/fpu/s_sincosf_data.c: New file.
* sysdeps/x86_64/fpu/s_sincosf_data.c: New file.
--
diff --git a/math/Makefile b/math/Makefile
index 90b3b68916e12d8563ed57772013f4420415928b..e73ceb8d4e8d520c3047f63bf6c6d05856a89186 100644
--- a/math/Makefile
+++ b/math/Makefile
@@ -131,7 +131,7 @@ type-double-routines := branred doasin dosincos mpa mpatan2 \
# float support
type-float-suffix := f
type-float-routines := k_rem_pio2f math_errf e_exp2f_data e_logf_data \
- e_log2f_data e_powf_log2_data
+ e_log2f_data e_powf_log2_data s_sincosf_data
# _Float128 support
type-float128-suffix := f128
diff --git a/sysdeps/ia64/fpu/s_sincosf_data.c b/sysdeps/ia64/fpu/s_sincosf_data.c
new file mode 100644
index 0000000000000000000000000000000000000000..1cc8931700702e65d29a6e2af287175d23c6b182
--- /dev/null
+++ b/sysdeps/ia64/fpu/s_sincosf_data.c
@@ -0,0 +1 @@
+/* Not needed. */
diff --git a/sysdeps/ieee754/flt-32/s_sincosf.h b/sysdeps/ieee754/flt-32/s_sincosf.h
index 35b5eee536ef0ca55e68e3d3a091486dca39d36a..d3d7b4d6f3139033ef4a3bf70fe754ed4d03727a 100644
--- a/sysdeps/ieee754/flt-32/s_sincosf.h
+++ b/sysdeps/ieee754/flt-32/s_sincosf.h
@@ -16,6 +16,10 @@
License along with the GNU C Library; if not, see
<http://www.gnu.org/licenses/>. */
+#include <stdint.h>
+#include <math.h>
+#include "math_config.h"
+
/* Chebyshev constants for cos, range -PI/4 - PI/4. */
static const double C0 = -0x1.ffffffffe98aep-2;
static const double C1 = 0x1.55555545c50c7p-5;
@@ -153,3 +157,117 @@ reduced_cos (double theta, unsigned int n)
}
return sign * cx;
}
+
+
+/* 2PI * 2^-64. */
+static const double pi63 = 0x1.921FB54442D18p-62;
+/* PI / 4. */
+static const double pio4 = 0x1.921FB54442D18p-1;
+
+/* The constants and polynomials for sine and cosine. */
+typedef struct
+{
+ double sign[4]; /* Sign of sine in quadrants 0..3. */
+ double hpi_inv; /* 2 / PI ( * 2^24 if !TOINT_INTRINSICS). */
+ double hpi; /* PI / 2. */
+ double c0, c1, c2, c3, c4; /* Cosine polynomial. */
+ double s1, s2, s3; /* Sine polynomial. */
+} sincos_t;
+
+/* Polynomial data (the cosine polynomial is negated in the 2nd entry). */
+extern const sincos_t __sincosf_table[2] attribute_hidden;
+
+/* Table with 4/PI to 192 bit precision. */
+extern const uint32_t __inv_pio4[] attribute_hidden;
+
+/* Top 12 bits of the float representation with the sign bit cleared. */
+static inline uint32_t
+abstop12 (float x)
+{
+ return (asuint (x) >> 20) & 0x7ff;
+}
+
+/* Compute the sine and cosine of inputs X and X2 (X squared), using the
+ polynomial P and store the results in SINP and COSP. N is the quadrant,
+ if odd the cosine and sine polynomials are swapped. */
+static inline void
+sincosf_poly (double x, double x2, const sincos_t *p, int n, float *sinp,
+ float *cosp)
+{
+ double x3, x4, x5, x6, s, c, c1, c2, s1;
+
+ x4 = x2 * x2;
+ x3 = x2 * x;
+ c2 = p->c3 + x2 * p->c4;
+ s1 = p->s2 + x2 * p->s3;
+
+ /* Swap sin/cos result based on quadrant. */
+ float *tmp = (n & 1 ? cosp : sinp);
+ cosp = (n & 1 ? sinp : cosp);
+ sinp = tmp;
+
+ c1 = p->c0 + x2 * p->c1;
+ x5 = x3 * x2;
+ x6 = x4 * x2;
+
+ s = x + x3 * p->s1;
+ c = c1 + x4 * p->c2;
+
+ *sinp = s + x5 * s1;
+ *cosp = c + x6 * c2;
+}
+
+/* Fast range reduction using single multiply-subtract. Return the modulo of
+ X as a value between -PI/4 and PI/4 and store the quadrant in NP.
+ The values for PI/2 and 2/PI are accessed via P. Since PI/2 as a double
+ is accurate to 55 bits and the worst-case cancellation happens at 6 * PI/4,
+ the result is accurate for |X| <= 120.0. */
+static inline double
+reduce_fast (double x, const sincos_t *p, int *np)
+{
+ double r;
+#if TOINT_INTRINSICS
+ /* Use fast round and lround instructions when available. */
+ r = x * p->hpi_inv;
+ *np = converttoint (r);
+ return x - roundtoint (r) * p->hpi;
+#else
+ /* Use scaled float to int conversion with explicit rounding.
+ hpi_inv is prescaled by 2^24 so the quadrant ends up in bits 24..31.
+ This avoids inaccuracies introduced by truncating negative values. */
+ r = x * p->hpi_inv;
+ int n = ((int32_t)r + 0x800000) >> 24;
+ *np = n;
+ return x - n * p->hpi;
+#endif
+}
+
+/* Reduce the range of XI to a multiple of PI/2 using fast integer arithmetic.
+ XI is a reinterpreted float and must be >= 2.0f (the sign bit is ignored).
+ Return the modulo between -PI/4 and PI/4 and store the quadrant in NP.
+ Reduction uses a table of 4/PI with 192 bits of precision. A 32x96->128 bit
+ multiply computes the exact 2.62-bit fixed-point modulo. Since the result
+ can have at most 29 leading zeros after the binary point, the double
+ precision result is accurate to 33 bits. */
+static inline double
+reduce_large (uint32_t xi, int *np)
+{
+ const uint32_t *arr = &__inv_pio4[(xi >> 26) & 15];
+ int shift = (xi >> 23) & 7;
+ uint64_t n, res0, res1, res2;
+
+ xi = (xi & 0xffffff) | 0x800000;
+ xi <<= shift;
+
+ res0 = xi * arr[0];
+ res1 = (uint64_t)xi * arr[4];
+ res2 = (uint64_t)xi * arr[8];
+ res0 = (res2 >> 32) | (res0 << 32);
+ res0 += res1;
+
+ n = (res0 + (1ULL << 61)) >> 62;
+ res0 -= n << 62;
+ double x = (int64_t)res0;
+ *np = n;
+ return x * pi63;
+}
diff --git a/sysdeps/ieee754/flt-32/s_sincosf.c b/sysdeps/ieee754/flt-32/s_sincosf.c
index d4a5a1b22c2f9a5cf607cd2d31157dd1dbd14e9a..f7e32450971799340940c2d78380909a9306b434 100644
--- a/sysdeps/ieee754/flt-32/s_sincosf.c
+++ b/sysdeps/ieee754/flt-32/s_sincosf.c
@@ -1,5 +1,5 @@
/* Compute sine and cosine of argument.
- Copyright (C) 2017-2018 Free Software Foundation, Inc.
+ Copyright (C) 2018 Free Software Foundation, Inc.
This file is part of the GNU C Library.
The GNU C Library is free software; you can redistribute it and/or
@@ -17,9 +17,11 @@
<http://www.gnu.org/licenses/>. */
#include <errno.h>
+#include <stdint.h>
#include <math.h>
-#include <math_private.h>
+#include <math-barriers.h>
#include <libm-alias-float.h>
+#include "math_config.h"
#include "s_sincosf.h"
#ifndef SINCOSF
@@ -28,141 +30,71 @@
# define SINCOSF_FUNC SINCOSF
#endif
+/* Fast sincosf implementation. Worst-case ULP is 0.5607, maximum relative
+ error is 0.5303 * 2^-23. A single-step range reduction is used for
+ small values. Large inputs have their range reduced using fast integer
+ arithmetic. */
void
-SINCOSF_FUNC (float x, float *sinx, float *cosx)
+SINCOSF_FUNC (float y, float *sinp, float *cosp)
{
- double cx;
- double theta = x;
- double abstheta = fabs (theta);
- /* If |x|< Pi/4. */
- if (isless (abstheta, M_PI_4))
+ double x = y;
+ double s;
+ int n;
+ const sincos_t *p = &__sincosf_table[0];
+
+ if (abstop12 (y) < abstop12 (pio4))
+ {
+ double x2 = x * x;
+
+ if (__glibc_unlikely (abstop12 (y) < abstop12 (0x1p-12f)))
+ {
+ /* Force underflow for tiny y. */
+ if (__glibc_unlikely (abstop12 (y) < abstop12 (0x1p-126f)))
+ math_force_eval ((float)x2);
+ *sinp = y;
+ *cosp = 1.0f;
+ return;
+ }
+
+ sincosf_poly (x, x2, p, 0, sinp, cosp);
+ }
+ else if (abstop12 (y) < abstop12 (120.0f))
{
- if (abstheta >= 0x1p-5) /* |x| >= 2^-5. */
- {
- const double theta2 = theta * theta;
- /* Chebyshev polynomial of the form for sin and cos. */
- cx = C3 + theta2 * C4;
- cx = C2 + theta2 * cx;
- cx = C1 + theta2 * cx;
- cx = C0 + theta2 * cx;
- cx = 1.0 + theta2 * cx;
- *cosx = cx;
- cx = S3 + theta2 * S4;
- cx = S2 + theta2 * cx;
- cx = S1 + theta2 * cx;
- cx = S0 + theta2 * cx;
- cx = theta + theta * theta2 * cx;
- *sinx = cx;
- }
- else if (abstheta >= 0x1p-27) /* |x| >= 2^-27. */
- {
- /* A simpler Chebyshev approximation is close enough for this range:
- for sin: x+x^3*(SS0+x^2*SS1)
- for cos: 1.0+x^2*(CC0+x^3*CC1). */
- const double theta2 = theta * theta;
- cx = CC0 + theta * theta2 * CC1;
- cx = 1.0 + theta2 * cx;
- *cosx = cx;
- cx = SS0 + theta2 * SS1;
- cx = theta + theta * theta2 * cx;
- *sinx = cx;
- }
- else
- {
- /* Handle some special cases. */
- if (theta)
- *sinx = theta - (theta * SMALL);
- else
- *sinx = theta;
- *cosx = 1.0 - abstheta;
- }
+ x = reduce_fast (x, p, &n);
+
+ /* Setup the signs for sin and cos. */
+ s = p->sign[n & 3];
+
+ if (n & 2)
+ p = &__sincosf_table[1];
+
+ sincosf_poly (x * s, x * x, p, n, sinp, cosp);
}
- else /* |x| >= Pi/4. */
+ else if (__glibc_likely (abstop12 (y) < abstop12 (INFINITY)))
{
- unsigned int signbit = isless (x, 0);
- if (isless (abstheta, 9 * M_PI_4)) /* |x| < 9*Pi/4. */
- {
- /* There are cases where FE_UPWARD rounding mode can
- produce a result of abstheta * inv_PI_4 == 9,
- where abstheta < 9pi/4, so the domain for
- pio2_table must go to 5 (9 / 2 + 1). */
- unsigned int n = (abstheta * inv_PI_4) + 1;
- theta = abstheta - pio2_table[n / 2];
- *sinx = reduced_sin (theta, n, signbit);
- *cosx = reduced_cos (theta, n);
- }
- else if (isless (abstheta, INFINITY))
- {
- if (abstheta < 0x1p+23) /* |x| < 2^23. */
- {
- unsigned int n = ((unsigned int) (abstheta * inv_PI_4)) + 1;
- double x = n / 2;
- theta = (abstheta - x * PI_2_hi) - x * PI_2_lo;
- /* Argument reduction needed. */
- *sinx = reduced_sin (theta, n, signbit);
- *cosx = reduced_cos (theta, n);
- }
- else /* |x| >= 2^23. */
- {
- x = fabsf (x);
- int exponent;
- GET_FLOAT_WORD (exponent, x);
- exponent
- = (exponent >> FLOAT_EXPONENT_SHIFT) - FLOAT_EXPONENT_BIAS;
- exponent += 3;
- exponent /= 28;
- double a = invpio4_table[exponent] * x;
- double b = invpio4_table[exponent + 1] * x;
- double c = invpio4_table[exponent + 2] * x;
- double d = invpio4_table[exponent + 3] * x;
- uint64_t l = a;
- l &= ~0x7;
- a -= l;
- double e = a + b;
- l = e;
- e = a - l;
- if (l & 1)
- {
- e -= 1.0;
- e += b;
- e += c;
- e += d;
- e *= M_PI_4;
- *sinx = reduced_sin (e, l + 1, signbit);
- *cosx = reduced_cos (e, l + 1);
- }
- else
- {
- e += b;
- e += c;
- e += d;
- if (e <= 1.0)
- {
- e *= M_PI_4;
- *sinx = reduced_sin (e, l + 1, signbit);
- *cosx = reduced_cos (e, l + 1);
- }
- else
- {
- l++;
- e -= 2.0;
- e *= M_PI_4;
- *sinx = reduced_sin (e, l + 1, signbit);
- *cosx = reduced_cos (e, l + 1);
- }
- }
- }
- }
- else
- {
- int32_t ix;
- /* High word of x. */
- GET_FLOAT_WORD (ix, abstheta);
- /* sin/cos(Inf or NaN) is NaN. */
- *sinx = *cosx = x - x;
- if (ix == 0x7f800000)
- __set_errno (EDOM);
- }
+ uint32_t xi = asuint (y);
+ int sign = xi >> 31;
+
+ x = reduce_large (xi, &n);
+
+ /* Setup signs for sin and cos - include original sign. */
+ s = p->sign[(n + sign) & 3];
+
+ if ((n + sign) & 2)
+ p = &__sincosf_table[1];
+
+ sincosf_poly (x * s, x * x, p, n, sinp, cosp);
+ }
+ else
+ {
+ /* Return NaN if Inf or NaN for both sin and cos. */
+ *sinp = *cosp = y - y;
+#if WANT_ERRNO
+ /* Needed to set errno for +-Inf, the add is a hack to work
+ around a gcc register allocation issue: just passing y
+ affects code generation in the fast path (PR86901). */
+ __math_invalidf (y + y);
+#endif
}
}
diff --git a/sysdeps/ieee754/flt-32/s_sincosf_data.c b/sysdeps/ieee754/flt-32/s_sincosf_data.c
new file mode 100644
index 0000000000000000000000000000000000000000..21fc2b60f9ead7714deedb78c05529a8c58fe096
--- /dev/null
+++ b/sysdeps/ieee754/flt-32/s_sincosf_data.c
@@ -0,0 +1,74 @@
+/* Compute sine and cosine of argument.
+ Copyright (C) 2018 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+ The GNU C Library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+
+ The GNU C Library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with the GNU C Library; if not, see
+ <http://www.gnu.org/licenses/>. */
+
+#include <stdint.h>
+#include <math.h>
+#include "math_config.h"
+#include "s_sincosf.h"
+
+/* The constants and polynomials for sine and cosine. The 2nd entry
+ computes -cos (x) rather than cos (x) to get negation for free. */
+const sincos_t __sincosf_table[2] =
+{
+ {
+ { 1.0, -1.0, -1.0, 1.0 },
+#if TOINT_INTRINSICS
+ 0x1.45F306DC9C883p-1,
+#else
+ 0x1.45F306DC9C883p+23,
+#endif
+ 0x1.921FB54442D18p0,
+ 0x1p0,
+ -0x1.ffffffd0c621cp-2,
+ 0x1.55553e1068f19p-5,
+ -0x1.6c087e89a359dp-10,
+ 0x1.99343027bf8c3p-16,
+ -0x1.555545995a603p-3,
+ 0x1.1107605230bc4p-7,
+ -0x1.994eb3774cf24p-13
+ },
+ {
+ { 1.0, -1.0, -1.0, 1.0 },
+#if TOINT_INTRINSICS
+ 0x1.45F306DC9C883p-1,
+#else
+ 0x1.45F306DC9C883p+23,
+#endif
+ 0x1.921FB54442D18p0,
+ -0x1p0,
+ 0x1.ffffffd0c621cp-2,
+ -0x1.55553e1068f19p-5,
+ 0x1.6c087e89a359dp-10,
+ -0x1.99343027bf8c3p-16,
+ -0x1.555545995a603p-3,
+ 0x1.1107605230bc4p-7,
+ -0x1.994eb3774cf24p-13
+ }
+};
+
+/* Table with 4/PI to 192 bit precision. To avoid unaligned accesses
+ only 8 new bits are added per entry, making the table 4 times larger. */
+const uint32_t __inv_pio4[24] =
+{
+ 0xa2, 0xa2f9, 0xa2f983, 0xa2f9836e,
+ 0xf9836e4e, 0x836e4e44, 0x6e4e4415, 0x4e441529,
+ 0x441529fc, 0x1529fc27, 0x29fc2757, 0xfc2757d1,
+ 0x2757d1f5, 0x57d1f534, 0xd1f534dd, 0xf534ddc0,
+ 0x34ddc0db, 0xddc0db62, 0xc0db6295, 0xdb629599,
+ 0x6295993c, 0x95993c43, 0x993c4390, 0x3c439041
+};
diff --git a/sysdeps/m68k/m680x0/fpu/s_sincosf_data.c b/sysdeps/m68k/m680x0/fpu/s_sincosf_data.c
new file mode 100644
index 0000000000000000000000000000000000000000..1cc8931700702e65d29a6e2af287175d23c6b182
--- /dev/null
+++ b/sysdeps/m68k/m680x0/fpu/s_sincosf_data.c
@@ -0,0 +1 @@
+/* Not needed. */
diff --git a/sysdeps/x86_64/fpu/s_sincosf_data.c b/sysdeps/x86_64/fpu/s_sincosf_data.c
new file mode 100644
index 0000000000000000000000000000000000000000..1cc8931700702e65d29a6e2af287175d23c6b182
--- /dev/null
+++ b/sysdeps/x86_64/fpu/s_sincosf_data.c
@@ -0,0 +1 @@
+/* Not needed. */