[dasher] Find next-lowest representable double below dParentCost without using an expensive for loop.

[Patrick Welche <pwelche src gnome org>]

commit 372dba9f827270d32acc5f0189305cb75aa3c29a
Author: Tom Lawton <tlawton gmx de>
Date:   Sat Mar 13 19:53:04 2010 +0000

    Find next-lowest representable double below dParentCost without using an
    expensive for loop.
    
    Dasher is using a /lot/ of CPU (10-15%) in the for loop in pushNode which
    as far as I can see only exists to find the next-lowest representable
    double below dParentCost.
    
    The method I've left in you might consider slightly hacky; it simply
    decreases the significand by one (or increases it by one if it's
    negative). It correctly overflows into the exponent if required.
    
    However, it assumes IEEE 754 storage (which is almost certainly true).
    Alternatively, there's a C99 function nextafter() which does what we
    want and isn't much slower than my method. Naturally MS don't fully
    support C99, although _nextafter() exists.
    
    (PW: use the old loop if big endian...)

 ChangeLog                          |    2 ++
 Src/DasherCore/ExpansionPolicy.cpp |   27 ++++++++++++++++++++++++---
 2 files changed, 26 insertions(+), 3 deletions(-)
---
diff --git a/ChangeLog b/ChangeLog
index 040be22..d14bab0 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -9,6 +9,8 @@
 	From Tom Lawton:
 	* Win32: ModuleControl.h - correct header location
 	* Win32: Fix stylus mode by allowing 'KeyUp' to be triggered.
+	* ExpansionPolicy: Find next-lowest representable double below
+	  dParentCost without using an expensive for loop.
 
 2010-03-11  Patrick Welche <prlw1 cam ac uk>
 
diff --git a/Src/DasherCore/ExpansionPolicy.cpp b/Src/DasherCore/ExpansionPolicy.cpp
index 15e8ffc..1f91861 100644
--- a/Src/DasherCore/ExpansionPolicy.cpp
+++ b/Src/DasherCore/ExpansionPolicy.cpp
@@ -21,13 +21,34 @@ BudgettingPolicy::BudgettingPolicy(unsigned int iNodeBudget) : m_iNodeBudget(iNo
 
 double BudgettingPolicy::pushNode(CDasherNode *pNode, int iMin, int iMax, bool bExpand, double dParentCost) {
   double dRes = getCost(pNode, iMin, iMax);
+
   if (dRes >= dParentCost) {
+
+#if defined(BYTE_ORDER) && (BYTE_ORDER == BIG_ENDIAN)
     double eps = max(abs(dParentCost),1.0) * std::numeric_limits<double>::epsilon();
     DASHER_ASSERT((dParentCost-eps) < dParentCost);
     for (double nRes; (nRes = dParentCost - eps) < dParentCost; eps/=2.0) {
-      //nRes<dParentCost guaranteed true by loop test - remember it!
-      dRes = nRes;
+        // nRes<dParentCost guaranteed true by loop test - remember it!
+        dRes = nRes;
+    }
+#else
+
+// TL - Dasher spends 10-15% of its time on my system in the 'for' loop
+// above. The code below has the same result, though might be considered
+// hacky and relies on endian-ness.
+
+    dRes = ((dParentCost==0.0)?-0.0:dParentCost);
+    if (dRes > 0.0) {
+        (*(int64*)&dRes)--;
+    } else {
+        (*(int64*)&dRes)++;
     }
+
+// This is probably more portable, uses fractionally more CPU than the above
+// (but still 50x less than the for loop).
+// nextafter() is called _nextafter() in Visual Studio.
+// dRes=_nextafter(dParentCost,-std::numeric_limits<double>::max());
+#endif
   }
   DASHER_ASSERT(dRes < dParentCost);
   vector<pair<double, CDasherNode*> > &target = (bExpand) ? sExpand : sCollapse;
@@ -179,4 +200,4 @@ void AmortizedPolicy::trim() {
     else if (it1->first == dFirstCost && it2->first==dFirstCost) continue;
     else cout << "trim not equal!\n";
 #endif
-}
\ No newline at end of file
+}