summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAkarsh Simha <akarsh@kde.org>2016-09-25 01:23:20 (GMT)
committerAkarsh Simha <akarsh@kde.org>2016-09-28 22:16:21 (GMT)
commit2d4f65a20b3da0bc7c8123a11da316c07d8b4b5c (patch)
treee92f941ff58131e52c03ea52f70b739673ab5299
parent5da196c1adefe88e697a72cd23f4af4e5a998d9c (diff)
Experiment 1: Can we cache trig values during first computation?
Is there an improvement if we cache trig values at the cost of one conditional branch to see if the cache is available or not? The answer seems to be no! Running this code and comparing the results printed to the console against the previous one do not seem to indicate any improvement: BEFORE: DeepStarComponent::draw (322) - Spent 0.254752 seconds doing 2233550 trigonometric function calls amounting to an average of 0.000114057 ms per call AFTER DeepStarComponent::draw (322) - Spent 0.229613 seconds doing 2233550 trigonometric function calls amounting to an average of 0.000102802 ms per call The difference seems very insignificant. Although there might be a consistent trend of improvement, it is not staggering. I rationalize the results as follows (on Intel x86_64): 1. If we assume that a branch mispredict takes about 10 CPU cycles (https://gist.github.com/jboner/2841832) and the float comparison takes another 10 CPU cycles, we add about 20 CPU cycles by introducing the branch. 2. sin() and cos() seem to take about 55 CPU cycles each, sincos() taking about 210. So let's suppose 52 CPU cycles on average. 3. Since about 50% of the trig function calls are redundant, and the redundant and non-redundant calls are interspersed, the branch predictor is very likely to mispredict. So this suggests that in the 50% cases where we are asked to do a fresh computation, we spend ~ 72 CPU cycles, whereas in the 50% cases where we don't need to do any computation, we spend ~ 20 CPU cycles. The resulting average is about 46 CPU cycles, which is not a significant improvement from 52 CPU cycles. This suggests that Experiment 2 should be as follows: Create an inherited class of dms called FastDms that caches trigonometric values every time the angle changes. So in this class, we basically assume that we _will_ call sin() and cos() eventually. Otherwise, we introduce overhead. The assumption can be verified by counting calls and profiling.
-rw-r--r--kstars/auxiliary/dms.cpp2
-rw-r--r--kstars/auxiliary/dms.h60
2 files changed, 41 insertions, 21 deletions
diff --git a/kstars/auxiliary/dms.cpp b/kstars/auxiliary/dms.cpp
index b457be1..33a1f70 100644
--- a/kstars/auxiliary/dms.cpp
+++ b/kstars/auxiliary/dms.cpp
@@ -34,6 +34,7 @@ double dms::seconds_in_trig = 0;
void dms::setD(const int &d, const int &m, const int &s, const int &ms) {
D = (double)abs(d) + ((double)m + ((double)s + (double)ms/1000.)/60.)/60.;
if (d<0) {D = -1.0*D;}
+ m_s = m_c = NaN::d;
#ifdef COUNT_DMS_SINCOS_CALLS
m_cosDirty = m_sinDirty = true;
#endif
@@ -49,6 +50,7 @@ void dms::setH( const double &x ) {
void dms::setH(const int &h, const int &m, const int &s, const int &ms) {
D = 15.0*((double)abs(h) + ((double)m + ((double)s + (double)ms/1000.)/60.)/60.);
if (h<0) {D = -1.0*D;}
+ m_s = m_c = NaN::d;
#ifdef COUNT_DMS_SINCOS_CALLS
m_cosDirty = m_sinDirty = true;
#endif
diff --git a/kstars/auxiliary/dms.h b/kstars/auxiliary/dms.h
index b07fbab..2945f3d 100644
--- a/kstars/auxiliary/dms.h
+++ b/kstars/auxiliary/dms.h
@@ -53,6 +53,7 @@ public:
#ifdef COUNT_DMS_SINCOS_CALLS
, m_sinCosCalled(false), m_sinDirty( true ), m_cosDirty( true )
#endif
+ , m_s( NaN::d ), m_c( NaN::d )
{
#ifdef COUNT_DMS_SINCOS_CALLS
++dms_constructor_calls;
@@ -65,15 +66,16 @@ public:
* @param s arcsecond portion of angle (int). Defaults to zero.
* @param ms arcsecond portion of angle (int). Defaults to zero.
*/
- explicit dms( const int &d, const int &m=0, const int &s=0, const int &ms=0 )
+ explicit dms( const int &d, const int &m=0, const int &s=0, const int &ms=0 ) :
#ifdef COUNT_DMS_SINCOS_CALLS
- : m_sinCosCalled(false), m_sinDirty( true ), m_cosDirty( true )
+ m_sinCosCalled(false), m_sinDirty( true ), m_cosDirty( true ),
#endif
+ m_s( NaN::d ), m_c( NaN::d )
{ setD( d, m, s, ms );
#ifdef COUNT_DMS_SINCOS_CALLS
++dms_constructor_calls;
#endif
-}
+ }
/** @short Construct an angle from a double value.
*
@@ -84,6 +86,7 @@ public:
#ifdef COUNT_DMS_SINCOS_CALLS
, m_sinCosCalled(false), m_sinDirty( true ), m_cosDirty( true )
#endif
+ , m_s( NaN::d ), m_c( NaN::d )
{
#ifdef COUNT_DMS_SINCOS_CALLS
++dms_constructor_calls;
@@ -103,10 +106,11 @@ public:
* @param isDeg if true, value is in degrees; if false, value is in hours.
* @sa setFromString()
*/
- explicit dms( const QString &s, bool isDeg=true )
+ explicit dms( const QString &s, bool isDeg=true ) :
#ifdef COUNT_DMS_SINCOS_CALLS
- : m_sinCosCalled(false), m_sinDirty( true ), m_cosDirty( true )
+ m_sinCosCalled(false), m_sinDirty( true ), m_cosDirty( true ),
#endif
+ m_s( NaN::d ), m_c( NaN::d )
{ setFromString( s, isDeg );
#ifdef COUNT_DMS_SINCOS_CALLS
++dms_constructor_calls;
@@ -170,7 +174,9 @@ public:
#ifdef COUNT_DMS_SINCOS_CALLS
m_sinDirty = m_cosDirty = true;
#endif
- D = x; }
+ m_s = m_c = NaN::d;
+ D = x;
+ }
/** @short Sets floating-point value of angle, in degrees.
*
@@ -248,15 +254,17 @@ public:
#endif
#ifdef PROFILE_SINCOS
std::clock_t start, stop;
- double s;
start = std::clock();
- s = ::sin(D*DegToRad);
+#endif
+ if( std::isnan( m_s ) )
+ m_s = ::sin(D*DegToRad);
+
+#ifdef PROFILE_SINCOS
stop = std::clock();
seconds_in_trig += double(stop - start)/double(CLOCKS_PER_SEC);
- return s;
-#else
- return ::sin(D*DegToRad);
#endif
+ Q_ASSERT( !std::isnan( m_s ) );
+ return m_s;
}
/** @short Compute the Angle's Cosine.
@@ -275,15 +283,17 @@ public:
#endif
#ifdef PROFILE_SINCOS
std::clock_t start, stop;
- double c;
start = std::clock();
- c = ::cos(D*DegToRad);
+#endif
+ if( std::isnan( m_c ) )
+ m_c = ::cos(D*DegToRad);
+
+#ifdef PROFILE_SINCOS
stop = std::clock();
seconds_in_trig += double(stop - start)/double(CLOCKS_PER_SEC);
- return c;
-#else
- return ::cos(D*DegToRad);
#endif
+ Q_ASSERT( !std::isnan( m_c ) );
+ return m_c;
}
/** @short Express the angle in radians.
@@ -352,6 +362,7 @@ public:
#endif
private:
double D;
+ mutable double m_s, m_c; // Trigonometric functions
#ifdef COUNT_DMS_SINCOS_CALLS
mutable bool m_sinDirty, m_cosDirty, m_sinCosCalled;
#endif
@@ -380,17 +391,24 @@ inline void dms::SinCos(double& s, double& c) const {
#ifdef __GLIBC__
#if ( __GLIBC__ >= 2 && __GLIBC_MINOR__ >=1 && !defined(__UCLIBC__))
//GNU version
- sincos( radians(), &s, &c );
+ if( std::isnan( m_s ) || std::isnan( m_c ) )
+ sincos( radians(), &m_s, &m_c );
#else
//For older GLIBC versions
- s = ::sin( radians() );
- c = ::cos( radians() );
+ if( std::isnan( m_s ) )
+ m_s = ::sin( radians() );
+ if( std::isnan( m_c ) )
+ m_c = ::cos( radians() );
#endif
#else
//ANSI-compliant version
- s = ::sin( radians() );
- c = ::cos( radians() );
+ if( std::isnan( m_s ) )
+ m_s = ::sin( radians() );
+ if( std::isnan( m_c ) )
+ m_c = ::cos( radians() );
#endif
+ s = m_s; c = m_c;
+ Q_ASSERT( !std::isnan( m_s ) && !std::isnan( m_c ) );
#ifdef PROFILE_SINCOS
stop = std::clock();