Re: [pooma-dev] Evaluator/ReductionEvaluator.h question

[Richard Guenther]

On Tue, 18 Feb 2003, Richard Guenther wrote:

> Why is the result of ReductionEvaluator<>::evaluate() initialized
> to Expr.read(0) and op never applied to it? This seems to be wrong,
> f.i. if the operation is
>
>  void op(double &res, double val)
>  {
>    double tmp = std::sqrt(val);
>    if (tmp > res)
>       res = tmp;
>  }

I see now that the current implementation does make sense for all
reduction operators I can think of, but looking at the evaluation
loops they seem to be hard to optimize for the compiler, so may I
propose the following patch?

Richard.


===== src/Array/Reductions.h 1.1 vs edited =====
--- 1.1/r2/src/Array/Reductions.h       Mon May 13 17:47:27 2002
+++ edited/src/Array/Reductions.h       Tue Feb 18 12:59:28 2003
@@ -64,7 +64,7 @@
 template<int Dim, class T, class EngineTag>
 T sum(const Array<Dim, T, EngineTag> &a)
 {
-  T ret;
+  T ret = T(0);
   Reduction<MainEvaluatorTag>().evaluate(ret, OpAddAssign(), a);
   return ret;
 }
@@ -74,7 +74,7 @@
 template<int Dim, class T, class EngineTag>
 T prod(const Array<Dim, T, EngineTag> &a)
 {
-  T ret;
+  T ret = T(1);
   Reduction<MainEvaluatorTag>().evaluate(ret, OpMultiplyAssign(), a);
   return ret;
 }
@@ -84,7 +84,7 @@
 template<int Dim, class T, class EngineTag>
 T min(const Array<Dim, T, EngineTag> &a)
 {
-  T ret;
+  T ret = std::numeric_limits<T>::max();
   Reduction<MainEvaluatorTag>().evaluate(ret, FnMinAssign(), a);
   return ret;
 }
@@ -94,7 +94,7 @@
 template<int Dim, class T, class EngineTag>
 T max(const Array<Dim, T, EngineTag> &a)
 {
-  T ret;
+  T ret = std::numeric_limits<T>::min();
   Reduction<MainEvaluatorTag>().evaluate(ret, FnMaxAssign(), a);
   return ret;
 }
@@ -104,7 +104,7 @@
 template<int Dim, class T, class EngineTag>
 bool all(const Array<Dim, T, EngineTag> &a)
 {
-  bool ret;
+  bool ret = true;
   Reduction<MainEvaluatorTag>().evaluate(ret, FnAndAssign(), a);
   return ret;
 }
@@ -114,7 +114,7 @@
 template<int Dim, class T, class EngineTag>
 bool any(const Array<Dim, T, EngineTag> &a)
 {
-  bool ret;
+  bool ret = false;
   Reduction<MainEvaluatorTag>().evaluate(ret, FnOrAssign(), a);
   return ret;
 }
@@ -124,7 +124,7 @@
 template<int Dim, class T, class EngineTag>
 T bitOr(const Array<Dim, T, EngineTag> &a)
 {
-  T ret;
+  T ret = static_cast<T>(0ULL);
   Reduction<MainEvaluatorTag>().evaluate(ret, OpBitwiseOrAssign(), a);
   return ret;
 }
@@ -134,7 +134,7 @@
 template<int Dim, class T, class EngineTag>
 T bitAnd(const Array<Dim, T, EngineTag> &a)
 {
-  T ret;
+  T ret = static_cast<T>(~0ULL);
   Reduction<MainEvaluatorTag>().evaluate(ret, OpBitwiseAndAssign(), a);
   return ret;
 }
===== src/Engine/RemoteEngine.h 1.1 vs edited =====
--- 1.1/r2/src/Engine/RemoteEngine.h    Mon May 13 17:47:32 2002
+++ edited/src/Engine/RemoteEngine.h    Tue Feb 18 13:06:14 2003
@@ -2090,6 +2090,7 @@
          {
            if (computationalContext[j] == Pooma::context())
              {
+               vals[k] = ret;
                EngineView<RemoteView> view;
                Reduction<SinglePatchEvaluatorTag>().
                  evaluate(vals[k++], op,
===== src/Evaluator/Reduction.h 1.1 vs edited =====
--- 1.1/r2/src/Evaluator/Reduction.h    Mon May 13 17:47:34 2002
+++ edited/src/Evaluator/Reduction.h    Tue Feb 18 13:04:26 2003
@@ -226,6 +226,7 @@
     int j = 0;
     while (j < n)
       {
+       vals[j] = ret;
         Reduction<SinglePatchEvaluatorTag>().
           evaluate(vals[j], op, e(*i), csem);
         ++i; ++j;
===== src/Evaluator/ReductionEvaluator.h 1.1 vs edited =====
--- 1.1/r2/src/Evaluator/ReductionEvaluator.h   Mon May 13 17:47:34 2002
+++ edited/src/Evaluator/ReductionEvaluator.h   Tue Feb 18 11:56:09 2003
@@ -127,8 +127,8 @@
     Expr localExpr(e);
     int e0 = domain[0].length();

-    T answer(localExpr.read(0));
-    for (int i0 = 1; i0 < e0; ++i0)
+    T answer(ret);
+    for (int i0 = 0; i0 < e0; ++i0)
       op(answer, localExpr.read(i0));

     ret = answer;
@@ -145,22 +145,10 @@
     int e0 = domain[0].length();
     int e1 = domain[1].length();

-    int i00;
-    bool firstLoop = true;
-
-    T answer(localExpr.read(0, 0));
+    T answer(ret);
     for (int i1 = 0; i1 < e1; ++i1)
-      {
-        if (firstLoop)
-          {
-            firstLoop = false;
-            i00 = 1;
-          }
-        else
-          i00 = 0;
-        for (int i0 = i00; i0 < e0; ++i0)
-          op(answer, localExpr.read(i0, i1));
-      }
+      for (int i0 = 0; i0 < e0; ++i0)
+       op(answer, localExpr.read(i0, i1));

     ret = answer;
   }
@@ -177,24 +165,12 @@
     int e0 = domain[0].length();
     int e1 = domain[1].length();
     int e2 = domain[2].length();
-
-    int i00;
-    bool firstLoop = true;

-    T answer(localExpr.read(0, 0, 0));
+    T answer(ret);
     for (int i2 = 0; i2 < e2; ++i2)
       for (int i1 = 0; i1 < e1; ++i1)
-        {
-          if (firstLoop)
-            {
-              firstLoop = false;
-              i00 = 1;
-            }
-          else
-            i00 = 0;
-          for (int i0 = i00; i0 < e0; ++i0)
-            op(answer, localExpr.read(i0, i1, i2));
-        }
+       for (int i0 = 0; i0 < e0; ++i0)
+         op(answer, localExpr.read(i0, i1, i2));

     ret = answer;
   }
@@ -213,25 +189,13 @@
     int e1 = domain[1].length();
     int e2 = domain[2].length();
     int e3 = domain[3].length();
-
-    int i00;
-    bool firstLoop = true;

-    T answer(localExpr.read(0, 0, 0, 0));
+    T answer(ret);
     for (int i3 = 0; i3 < e3; ++i3)
       for (int i2 = 0; i2 < e2; ++i2)
         for (int i1 = 0; i1 < e1; ++i1)
-          {
-            if (firstLoop)
-              {
-                firstLoop = false;
-                i00 = 1;
-              }
-            else
-              i00 = 0;
-            for (int i0 = i00; i0 < e0; ++i0)
-              op(answer, localExpr.read(i0, i1, i2, i3));
-          }
+         for (int i0 = 0; i0 < e0; ++i0)
+           op(answer, localExpr.read(i0, i1, i2, i3));

     ret = answer;
   }
@@ -252,26 +216,14 @@
     int e2 = domain[2].length();
     int e3 = domain[3].length();
     int e4 = domain[4].length();
-
-    int i00;
-    bool firstLoop = true;

-    T answer(localExpr.read(0, 0, 0, 0, 0));
+    T answer(ret);
     for (int i4 = 0; i4 < e4; ++i4)
       for (int i3 = 0; i3 < e3; ++i3)
         for (int i2 = 0; i2 < e2; ++i2)
           for (int i1 = 0; i1 < e1; ++i1)
-            {
-              if (firstLoop)
-                {
-                  firstLoop = false;
-                  i00 = 1;
-                }
-              else
-                i00 = 0;
-              for (int i0 = i00; i0 < e0; ++i0)
-                op(answer, localExpr.read(i0, i1, i2, i3, i4));
-            }
+           for (int i0 = 0; i0 < e0; ++i0)
+             op(answer, localExpr.read(i0, i1, i2, i3, i4));

     ret = answer;
   }
@@ -294,27 +246,15 @@
     int e3 = domain[3].length();
     int e4 = domain[4].length();
     int e5 = domain[5].length();
-
-    int i00;
-    bool firstLoop = true;

-    T answer(localExpr.read(0, 0, 0, 0, 0, 0));
+    T answer(ret);
     for (int i5 = 0; i5 < e5; ++i5)
       for (int i4 = 0; i4 < e4; ++i4)
         for (int i3 = 0; i3 < e3; ++i3)
           for (int i2 = 0; i2 < e2; ++i2)
             for (int i1 = 0; i1 < e1; ++i1)
-              {
-                if (firstLoop)
-                  {
-                    firstLoop = false;
-                    i00 = 1;
-                  }
-                else
-                  i00 = 0;
-                for (int i0 = i00; i0 < e0; ++i0)
-                  op(answer, localExpr.read(i0, i1, i2, i3, i4, i5));
-              }
+             for (int i0 = 0; i0 < e0; ++i0)
+               op(answer, localExpr.read(i0, i1, i2, i3, i4, i5));

     ret = answer;
   }
@@ -340,27 +280,15 @@
     int e5 = domain[5].length();
     int e6 = domain[6].length();

-    int i00;
-    bool firstLoop = true;
-
-    T answer(localExpr.read(0, 0, 0, 0, 0, 0, 0));
+    T answer(ret);
     for (int i6 = 0; i6 < e6; ++i6)
       for (int i5 = 0; i5 < e5; ++i5)
         for (int i4 = 0; i4 < e4; ++i4)
           for (int i3 = 0; i3 < e3; ++i3)
             for (int i2 = 0; i2 < e2; ++i2)
               for (int i1 = 0; i1 < e1; ++i1)
-                {
-                  if (firstLoop)
-                    {
-                      firstLoop = false;
-                      i00 = 1;
-                    }
-                  else
-                    i00 = 0;
-                  for (int i0 = i00; i0 < e0; ++i0)
-                    op(answer, localExpr.read(i0, i1, i2, i3, i4, i5, i6));
-                }
+               for (int i0 = 0; i0 < e0; ++i0)
+                 op(answer, localExpr.read(i0, i1, i2, i3, i4, i5, i6));

     ret = answer;
   }
@@ -384,9 +312,10 @@
 struct CompressibleReduce
 {
   template<class T1>
-  inline static void evaluate(T &ret, const Op &, const T1 &val, int)
+  inline static void evaluate(T &ret, const Op &op, const T1 &val, int)
   {
-    ret = static_cast<T>(val);
+    // Works for op that is constrained to op(op(ret, val), val) == op(ret, 
val).
+    op(ret, static_cast<T>(val));
   }
 };

===== src/Evaluator/tests/ReductionTest1.cpp 1.1 vs edited =====
--- 1.1/r2/src/Evaluator/tests/ReductionTest1.cpp       Mon May 13 17:47:34 2002
+++ edited/src/Evaluator/tests/ReductionTest1.cpp       Tue Feb 18 12:12:52 2003
@@ -48,22 +48,27 @@
   int ret;
   bool bret;

+  ret = 0;
   Reduction<MainEvaluatorTag>().evaluate(ret, OpAddAssign(), a);
   tester.check("sum", ret, 55);
   tester.out() << ret << std::endl;

+  ret = 1;
   Reduction<MainEvaluatorTag>().evaluate(ret, OpMultiplyAssign(), 
a(Interval<1>(9)));
   tester.check("prod", ret, 362880);
   tester.out() << ret << std::endl;

+  ret = std::numeric_limits<int>::max();
   Reduction<MainEvaluatorTag>().evaluate(ret, FnMinAssign(), a - 2);
   tester.check("min", ret, -1);
   tester.out() << ret << std::endl;

+  bret = true;
   Reduction<MainEvaluatorTag>().evaluate(bret, FnAndAssign(), a - 1);
   tester.check("all", bret, false);
   tester.out() << bret << std::endl;

+  ret = static_cast<int>(0ULL);
   Reduction<MainEvaluatorTag>().evaluate(ret, OpBitwiseOrAssign(), a);
   tester.check("bitOr", ret, 15);
   tester.out() << ret << std::endl;
===== src/Evaluator/tests/ReductionTest2.cpp 1.1 vs edited =====
--- 1.1/r2/src/Evaluator/tests/ReductionTest2.cpp       Mon May 13 17:47:34 2002
+++ edited/src/Evaluator/tests/ReductionTest2.cpp       Tue Feb 18 12:13:48 2003
@@ -52,22 +52,27 @@
   int ret;
   bool bret;

+  ret = 0;
   Reduction<MainEvaluatorTag>().evaluate(ret, OpAddAssign(), a);
   tester.check("sum", ret, 55);
   tester.out() << ret << std::endl;

+  ret = 1;
   Reduction<MainEvaluatorTag>().evaluate(ret, OpMultiplyAssign(), 
a(Interval<1>(9)));
   tester.check("prod", ret, 362880);
   tester.out() << ret << std::endl;

+  ret = std::numeric_limits<int>::max();
   Reduction<MainEvaluatorTag>().evaluate(ret, FnMinAssign(), a - 2);
   tester.check("min", ret, -1);
   tester.out() << ret << std::endl;

+  bret = true;
   Reduction<MainEvaluatorTag>().evaluate(bret, FnAndAssign(), a - 1);
   tester.check("all", bret, false);
   tester.out() << bret << std::endl;

+  ret = static_cast<int>(0ULL);
   Reduction<MainEvaluatorTag>().evaluate(ret, OpBitwiseOrAssign(), a);
   tester.check("bitOr", ret, 15);
   tester.out() << ret << std::endl;
===== src/Evaluator/tests/ReductionTest3.cpp 1.1 vs edited =====
--- 1.1/r2/src/Evaluator/tests/ReductionTest3.cpp       Mon May 13 17:47:34 2002
+++ edited/src/Evaluator/tests/ReductionTest3.cpp       Tue Feb 18 12:13:39 2003
@@ -47,22 +47,27 @@
   int ret;
   bool bret;

+  ret = 0;
   Reduction<MainEvaluatorTag>().evaluate(ret, OpAddAssign(), a);
   tester.check("sum", ret, int(2 * a.domain().size()));
   tester.out() << ret << std::endl;

+  ret = 1;
   Reduction<MainEvaluatorTag>().evaluate(ret, OpMultiplyAssign(), a);
   tester.check("prod", ret, 65536);
   tester.out() << ret << std::endl;

+  ret = std::numeric_limits<int>::max();
   Reduction<MainEvaluatorTag>().evaluate(ret, FnMinAssign(), a);
   tester.check("min", ret, 2);
   tester.out() << ret << std::endl;

+  bret = true;
   Reduction<MainEvaluatorTag>().evaluate(bret, FnAndAssign(), a);
   tester.check("all", bret, true);
   tester.out() << bret << std::endl;

+  ret = static_cast<int>(0ULL);
   Reduction<MainEvaluatorTag>().evaluate(ret, OpBitwiseOrAssign(), a);
   tester.check("bitOr", ret, 2);
   tester.out() << ret << std::endl;
===== src/Evaluator/tests/ReductionTest4.cpp 1.3 vs edited =====
--- 1.3/r2/src/Evaluator/tests/ReductionTest4.cpp       Thu Dec 19 10:38:23 2002
+++ edited/src/Evaluator/tests/ReductionTest4.cpp       Tue Feb 18 12:15:06 2003
@@ -65,47 +65,56 @@

   // Test various sorts of reductions with a single array.

+  ret = 0;
   Reduction<MainEvaluatorTag>().evaluate(ret, OpAddAssign(), a);
   tester.check("sum", ret, 55);
   tester.out() << ret << std::endl;

+  ret = 1;
   Reduction<MainEvaluatorTag>().evaluate(ret, OpMultiplyAssign(),
     a(Interval<1>(9)));
   tester.check("prod", ret, 362880);
   tester.out() << ret << std::endl;

+  ret = std::numeric_limits<int>::max();
   Reduction<MainEvaluatorTag>().evaluate(ret, FnMinAssign(), a - 2);
   tester.check("min", ret, -1);
   tester.out() << ret << std::endl;

+  bret = true;
   Reduction<MainEvaluatorTag>().evaluate(bret, FnAndAssign(), a - 1);
   tester.check("all", bret, false);
   tester.out() << bret << std::endl;

+  ret = static_cast<int>(0ULL);
   Reduction<MainEvaluatorTag>().evaluate(ret, OpBitwiseOrAssign(), a);
   tester.check("bitOr", ret, 15);
   tester.out() << ret << std::endl;

   // Test something with an expression engine (remote2 + remote5).

+  ret = 0;
   Reduction<MainEvaluatorTag>().evaluate(ret, OpAddAssign(), a + b);
   tester.check("sum(a + b)", ret, 55 + 90);
   tester.out() << ret << std::endl;

   // Test something with an expression engine (remote5 + remote2).

+  ret = 0;
   Reduction<MainEvaluatorTag>().evaluate(ret, OpAddAssign(), b + a);
   tester.check("sum(b + a)", ret, 90 + 55);
   tester.out() << ret << std::endl;

   // Test something with a brick (remote2 + remote5 + brick).

+  ret = 0;
   Reduction<MainEvaluatorTag>().evaluate(ret, OpAddAssign(), a + b + c);
   tester.check("sum(a + b + c)", ret, 90 + 55 + 20);
   tester.out() << ret << std::endl;

   // Test something with a brick (brick + remote5 + remote2).

+  ret = 0;
   Reduction<MainEvaluatorTag>().evaluate(ret, OpAddAssign(), c + b + a);
   tester.check("sum(c + b + a)", ret,  20 + 55 + 90);
   tester.out() << ret << std::endl;
===== src/Field/FieldReductions.h 1.1 vs edited =====
--- 1.1/r2/src/Field/FieldReductions.h  Mon May 13 17:47:35 2002
+++ edited/src/Field/FieldReductions.h  Tue Feb 18 12:59:01 2003
@@ -73,7 +73,7 @@

   forEach(f, PerformUpdateTag(), NullCombine());

-  T ret;
+  T ret = T(0);
   Reduction<MainEvaluatorTag>().evaluate(ret, OpAddAssign(), f);
   return ret;
 }
@@ -92,7 +92,7 @@

   forEach(f, PerformUpdateTag(), NullCombine());

-  T ret;
+  T ret = T(1);
   Reduction<MainEvaluatorTag>().evaluate(ret, OpMultiplyAssign(), f);
   return ret;
 }
@@ -111,7 +111,7 @@

   forEach(f, PerformUpdateTag(), NullCombine());

-  T ret;
+  T ret = std::numeric_limits<T>::max();
   Reduction<MainEvaluatorTag>().evaluate(ret, FnMinAssign(), f);
   return ret;
 }
@@ -130,7 +130,7 @@

   forEach(f, PerformUpdateTag(), NullCombine());

-  T ret;
+  T ret = std::numeric_limits<T>::min();
   Reduction<MainEvaluatorTag>().evaluate(ret, FnMaxAssign(), f);
   return ret;
 }
@@ -149,7 +149,7 @@

   forEach(f, PerformUpdateTag(), NullCombine());

-  bool ret;
+  bool ret = true;
   Reduction<MainEvaluatorTag>().evaluate(ret, FnAndAssign(), f);
   return ret;
 }
@@ -168,7 +168,7 @@

   forEach(f, PerformUpdateTag(), NullCombine());

-  bool ret;
+  bool ret = false;
   Reduction<MainEvaluatorTag>().evaluate(ret, FnOrAssign(), f);
   return ret;
 }
@@ -187,7 +187,7 @@

   forEach(f, PerformUpdateTag(), NullCombine());

-  T ret;
+  T ret = static_cast<T>(0ULL);
   Reduction<MainEvaluatorTag>().evaluate(ret, OpBitwiseOrAssign(), f);
   return ret;
 }
@@ -206,7 +206,7 @@

   forEach(f, PerformUpdateTag(), NullCombine());

-  T ret;
+  T ret = static_cast<T>(~0ULL);
   Reduction<MainEvaluatorTag>().evaluate(ret, OpBitwiseAndAssign(), f);
   return ret;
 }