removed group in reduce method

Tsung-Wei Huang · Tsung-Wei Huang · commit 02ad8013325d · 2018-07-01T22:22:21.000-05:00
diff --git a/README.md b/README.md
@@ -213,8 +213,8 @@ The table below summarizes its commonly used methods.
 | placeholder     | none        | task         | insert a node without any work; work can be assigned later |
 | linearize       | task list   | none         | create a linear dependency in the given task list |
 | parallel_for    | beg, end, callable, group | task pair | apply the callable in parallel and group-by-group to the result of dereferencing every iterator in the range | 
-| reduce | beg, end, res, bop, group | task pair | apply a binary operator group-by-group to reduce a range of elements to a single result | 
-| transform_reduce | beg, end, res, bop, uop, group | task pair | apply a unary operator to each element in the range and reduce them to a single result group-by-group through a binary operator | 
+| reduce | beg, end, res, bop | task pair | reduce a range of elements to a single result through a binary operator | 
+| transform_reduce | beg, end, res, bop, uop | task pair | apply a unary operator to each element in the range and reduce them to a single result through a binary operator | 
 | dispatch        | none        | future | dispatch the current graph and return a shared future to block on completeness |
 | silent_dispatch | none        | none | dispatch the current graph | 
 | wait_for_all    | none        | none | dispatch the current graph and block until all graphs including previously dispatched ones finish |
@@ -307,36 +307,17 @@ auto [S, T] = tf.parallel_for(
 
 ### *reduce/transform_reduce*
 
-The method `reduce` creates a subgraph that applies a binary operator to a range of items in a container.
+The method `reduce` creates a subgraph that applies a binary operator to a range of items.
 The result will be stored in the referenced `res` object passed to the method. 
 It is your responsibility to assign it a correct initial value to reduce.
 
-<img align="right" width="45%" src="image/reduce.png">
-
-```cpp
-auto v = {1, 2, 3, 4};
-int sum {0};    // initial value
-auto [S, T] = tf.reduce(
-  v.begin(),    // beg of range
-  v.end(),      // end of range
-  sum,          // pass by reference
-  std::plus<int>(),
-  1             // execute one task at a time
-);
-// add dependencies via S and T.
-```
-
-Changing the group size can force intra-group tasks to run sequentially
-and inter-group tasks to run in parallel.
-Depending on applications, different group sizes can result in significant performance hit.
-
 <img align="right" width="45%" src="image/reduce_2.png">
 
 ```cpp
 auto v = {1, 2, 3, 4}; 
 int sum {0};
-auto [S, T] = tf.reduce(
-  v.begin(), v.end(), sum, std::plus<int>(), 2
+auto [S, T] = tf.reduce(    // for example, 2 threads
+  v.begin(), v.end(), sum, std::plus<int>()
 );  
 ```
 
@@ -352,8 +333,7 @@ auto [S, T] = tf.transform_reduce(v.begin(), v.end(), min,
 );
 ```
 
-All reduce methods have overloads with no group size, 
-in which the workload is evenly partitioned across threads.
+By default, all reduce methods distribute the workload evenly across threads.
 
 ### *dispatch/silent_dispatch/wait_for_all*
 Dispatching a taskflow graph will schedule threads to execute the current graph and return immediately.
@@ -370,6 +350,7 @@ std::cout << "all tasks complete" << '\n';
 ```
 
 If you need to block your program flow until all tasks finish, use `wait_for_all` instead.
+
 ```cpp
 tf.wait_for_all();
 std::cout << "all tasks complete" << '\n';
diff --git a/image/pdf2eps b/image/pdf2eps
@@ -0,0 +1,4 @@
+rm -rf $1.eps $1.ps
+pdfcrop $1.pdf $1.pdf
+pdftops $1.pdf
+ps2eps $1.ps
diff --git a/image/reduce.png b/image/reduce.png
diff --git a/image/reduce_2.png b/image/reduce_2.png
diff --git a/taskflow.hpp b/taskflow.hpp
@@ -448,9 +448,6 @@ class BasicTaskflow {
     template <typename T, typename C, std::enable_if_t<is_iterable_v<T>, void>* = nullptr>
     auto parallel_for(T&, C&&, size_t = 1);
 
-    template <typename I, typename T, typename B>
-    auto reduce(I, I, T&, B&&, size_t);
-    
     template <typename I, typename T, typename B>
     auto reduce(I, I, T&, B&&);
 
@@ -460,9 +457,6 @@ class BasicTaskflow {
     template <typename I, typename T>
     auto reduce_max(I, I, T&);
 
-    template <typename I, typename T, typename B, typename U>
-    auto transform_reduce(I, I, T&, B&&, U&&, size_t);
-
     template <typename I, typename T, typename B, typename U>
     auto transform_reduce(I, I, T&, B&&, U&&);
     
@@ -987,16 +981,16 @@ auto BasicTaskflow<F>::_reduce(I beg, size_t n, O op, size_t g, Task& S) {
 // Function: reduce 
 template <typename F>
 template <typename I, typename T, typename B>
-auto BasicTaskflow<F>::reduce(I beg, I end, T& result, B&& op, size_t g) {
+auto BasicTaskflow<F>::reduce(I beg, I end, T& result, B&& op/*, size_t g*/) {
   
   using category = typename std::iterator_traits<I>::iterator_category;
   
   // Evenly partition
-  if(g == 0) {
-    auto d = std::distance(beg, end);
-    auto w = std::max(size_t{1}, num_workers());
-    g = (d + w - 1) / w;
-  }
+  //if(g == 0) {
+  size_t d = std::distance(beg, end);
+  size_t w = std::max(size_t{1}, num_workers());
+  size_t g = std::max((d + w - 1) / w, size_t{2});
+  //}
 
   auto source = placeholder();
   auto target = placeholder();
@@ -1060,21 +1054,14 @@ auto BasicTaskflow<F>::reduce(I beg, I end, T& result, B&& op, size_t g) {
   }*/
 }
 
-// Function: reduce 
-template <typename F>
-template <typename I, typename T, typename B>
-auto BasicTaskflow<F>::reduce(I beg, I end, T& result, B&& op) {
-  return reduce(beg, end, result, std::forward<B>(op), 0);
-}
-
 // Function: reduce_min
 // Find the minimum element over a range of items.
 template <typename F>
 template <typename I, typename T>
 auto BasicTaskflow<F>::reduce_min(I beg, I end, T& result) {
   return reduce(beg, end, result, [] (const auto& l, const auto& r) {
     return std::min(l, r);
-  }, 0);
+  });
 }
 
 // Function: reduce_max
@@ -1084,22 +1071,20 @@ template <typename I, typename T>
 auto BasicTaskflow<F>::reduce_max(I beg, I end, T& result) {
   return reduce(beg, end, result, [] (const auto& l, const auto& r) {
     return std::max(l, r);
-  }, 0);
+  });
 }
 
 // Function: transform_reduce    
 template <typename F>
 template <typename I, typename T, typename B, typename U>
-auto BasicTaskflow<F>::transform_reduce(I beg, I end, T& result, B&& bop, U&& uop, size_t g) {
+auto BasicTaskflow<F>::transform_reduce(I beg, I end, T& result, B&& bop, U&& uop) {
 
   using category = typename std::iterator_traits<I>::iterator_category;
   
   // Even partition
-  if(g == 0) {
-    auto d = std::distance(beg, end);
-    auto w = std::max(size_t{1}, num_workers());
-    g = (d + w - 1) / w;
-  }
+  size_t d = std::distance(beg, end);
+  size_t w = std::max(size_t{1}, num_workers());
+  size_t g = std::max((d + w - 1) / w, size_t{2});
 
   auto source = placeholder();
   auto target = placeholder();
@@ -1146,14 +1131,6 @@ auto BasicTaskflow<F>::transform_reduce(I beg, I end, T& result, B&& bop, U&& uo
   return std::make_pair(source, target); 
 }
 
-// Function: transform_reduce    
-template <typename F>
-template <typename I, typename T, typename B, typename U>
-auto BasicTaskflow<F>::transform_reduce(I beg, I end, T& result, B&& bop, U&& uop) {
-  return transform_reduce(beg, end, result, std::forward<B>(bop), std::forward<U>(uop), 0);
-}
-
-
 /*// Function: parallel_range    
 template <typename F>
 template <typename I, typename C>
diff --git a/unittest/taskflow.cpp b/unittest/taskflow.cpp
@@ -256,40 +256,40 @@ TEST_CASE("Taskflow.ParallelFor") {
 // --------------------------------------------------------
 TEST_CASE("Taskflow.Reduce") {
 
-  const auto plus_test = [](const size_t num_workers, auto &&data, size_t group){
+  const auto plus_test = [](const size_t num_workers, auto &&data){
     tf::Taskflow tf(num_workers);
     int result {0};
     std::iota(data.begin(), data.end(), 1);
-    tf.reduce(data.begin(), data.end(), result, std::plus<int>(), group);
+    tf.reduce(data.begin(), data.end(), result, std::plus<int>());
     tf.wait_for_all();
     REQUIRE(result == std::accumulate(data.begin(), data.end(), 0, std::plus<int>()));
   };
 
-  const auto multiply_test = [](const size_t num_workers, auto &&data, size_t group){
+  const auto multiply_test = [](const size_t num_workers, auto &&data){
     tf::Taskflow tf(num_workers);
     std::fill(data.begin(), data.end(), 1.0);
     double result {2.0};
-    tf.reduce(data.begin(), data.end(), result, std::multiplies<double>(), group);
+    tf.reduce(data.begin(), data.end(), result, std::multiplies<double>());
     tf.wait_for_all();
     REQUIRE(result == std::accumulate(data.begin(), data.end(), 2.0, std::multiplies<double>()));
   };
 
-  const auto max_test = [](const size_t num_workers, auto &&data, size_t group){
+  const auto max_test = [](const size_t num_workers, auto &&data){
     tf::Taskflow tf(num_workers);
     std::iota(data.begin(), data.end(), 1);
     int result {0};
     auto lambda = [](const auto& l, const auto& r){return std::max(l, r);};
-    tf.reduce(data.begin(), data.end(), result, lambda, group);
+    tf.reduce(data.begin(), data.end(), result, lambda);
     tf.wait_for_all();
     REQUIRE(result == std::accumulate(data.begin(), data.end(), 0, lambda));
   };
 
-  const auto min_test = [](const size_t num_workers, auto &&data, size_t group){
+  const auto min_test = [](const size_t num_workers, auto &&data){
     tf::Taskflow tf(num_workers);
     std::iota(data.begin(), data.end(), 1);
     int result {std::numeric_limits<int>::max()};
     auto lambda = [](const auto& l, const auto& r){return std::min(l, r);};
-    tf.reduce(data.begin(), data.end(), result, lambda, group);
+    tf.reduce(data.begin(), data.end(), result, lambda);
     tf.wait_for_all();
     REQUIRE(result == std::accumulate(
       data.begin(), data.end(), std::numeric_limits<int>::max(), lambda)
@@ -298,19 +298,17 @@ TEST_CASE("Taskflow.Reduce") {
 
   for(size_t i=0; i<=4; ++i){
     for(size_t j=0; j<=256; j=j*2+1){
-      for(size_t k=0; k<=256; k++){
-        plus_test(i, std::vector<int>(j), k);
-        plus_test(i, std::list<int>(j)  , k);
+      plus_test(i, std::vector<int>(j));
+      plus_test(i, std::list<int>(j));
 
-        multiply_test(i, std::vector<double>(j), k);
-        multiply_test(i, std::list<double>(j),   k);
+      multiply_test(i, std::vector<double>(j));
+      multiply_test(i, std::list<double>(j));
 
-        max_test(i, std::vector<int>(j), k);
-        max_test(i, std::list<int>(j),   k);
+      max_test(i, std::vector<int>(j));
+      max_test(i, std::list<int>(j));
 
-        min_test(i, std::vector<int>(j), k);
-        min_test(i, std::list<int>(j),   k);
-      }
+      min_test(i, std::vector<int>(j));
+      min_test(i, std::list<int>(j));
     }
   }
 }
