[PATCH 11/30] Return vector of results from parallel_for_each

[Tom Tromey <tom@tromey.com>]

This changes gdb::parallel_for_each to return a vector of the results.
However, if the passed-in function returns void, the return type
remains 'void'.  This functionality is used later, to parallelize the
new indexer.
---
 gdbsupport/parallel-for.h | 142 +++++++++++++++++++++++++++++++-------
 gdbsupport/thread-pool.cc |   6 +-
 gdbsupport/thread-pool.h  |  23 +++++-
 3 files changed, 140 insertions(+), 31 deletions(-)

diff --git a/gdbsupport/parallel-for.h b/gdbsupport/parallel-for.h
index 54027e69402..e9098f94fb3 100644
--- a/gdbsupport/parallel-for.h
+++ b/gdbsupport/parallel-for.h
@@ -21,6 +21,7 @@
 #define GDBSUPPORT_PARALLEL_FOR_H
 
 #include <algorithm>
+#include <type_traits>
 #if CXX_STD_THREAD
 #include <thread>
 #include "gdbsupport/thread-pool.h"
@@ -29,6 +30,89 @@
 namespace gdb
 {
 
+namespace detail
+{
+
+/* This is a helper class that is used to accumulate results for
+   parallel_for.  There is a specialization for 'void', below.  */
+template<typename T>
+struct par_for_accumulator
+{
+public:
+
+  explicit par_for_accumulator (size_t n_threads)
+    : m_futures (n_threads)
+  {
+  }
+
+  /* The result type that is accumulated.  */
+  typedef std::vector<T> result_type;
+
+  /* Post the Ith task to a background thread, and store a future for
+     later.  */
+  void post (size_t i, std::function<T ()> task)
+  {
+    m_futures[i]
+      = gdb::thread_pool::g_thread_pool->post_task (std::move (task));
+  }
+
+  /* Invoke TASK in the current thread, then compute all the results
+     from all background tasks and put them into a result vector,
+     which is returned.  */
+  result_type finish (std::function<T ()> task)
+  {
+    result_type result (m_futures.size () + 1);
+
+    result.back () = task ();
+
+    for (size_t i = 0; i < m_futures.size (); ++i)
+      result[i] = m_futures[i].get ();
+
+    return result;
+  }
+
+private:
+  
+  /* A vector of futures coming from the tasks run in the
+     background.  */
+  std::vector<std::future<T>> m_futures;
+};
+
+/* See the generic template.  */
+template<>
+struct par_for_accumulator<void>
+{
+public:
+
+  explicit par_for_accumulator (size_t n_threads)
+    : m_futures (n_threads)
+  {
+  }
+
+  /* This specialization does not compute results.  */
+  typedef void result_type;
+
+  void post (size_t i, std::function<void ()> task)
+  {
+    m_futures[i]
+      = gdb::thread_pool::g_thread_pool->post_task (std::move (task));
+  }
+
+  result_type finish (std::function<void ()> task)
+  {
+    task ();
+
+    for (auto &future : m_futures)
+      future.wait ();
+  }
+
+private:
+
+  std::vector<std::future<void>> m_futures;
+};
+
+}
+
 /* A very simple "parallel for".  This splits the range of iterators
    into subranges, and then passes each subrange to the callback.  The
    work may or may not be done in separate threads.
@@ -39,22 +123,28 @@ namespace gdb
 
    The parameter N says how batching ought to be done -- there will be
    at least N elements processed per thread.  Setting N to 0 is not
-   allowed.  */
+   allowed.
+
+   If the function returns a non-void type, then a vector of the
+   results is returned.  The size of the resulting vector depends on
+   the number of threads that were used.  */
 
 template<class RandomIt, class RangeFunction>
-void
+typename gdb::detail::par_for_accumulator<
+    std::result_of_t<RangeFunction (RandomIt, RandomIt)>
+  >::result_type
 parallel_for_each (unsigned n, RandomIt first, RandomIt last,
 		   RangeFunction callback)
 {
-#if CXX_STD_THREAD
-  /* So we can use a local array below.  */
-  const size_t local_max = 16;
-  size_t n_threads = std::min (thread_pool::g_thread_pool->thread_count (),
-			       local_max);
-  size_t n_actual_threads = 0;
-  std::future<void> futures[local_max];
+  typedef typename std::result_of_t<RangeFunction (RandomIt, RandomIt)>
+    result_type;
+
+  size_t n_threads = 1;
 
+#if CXX_STD_THREAD
+  n_threads = thread_pool::g_thread_pool->thread_count ();
   size_t n_elements = last - first;
+  size_t elts_per_thread = 0;
   if (n_threads > 1)
     {
       /* Require that there should be at least N elements in a
@@ -62,29 +152,29 @@ parallel_for_each (unsigned n, RandomIt first, RandomIt last,
       gdb_assert (n > 0);
       if (n_elements / n_threads < n)
 	n_threads = std::max (n_elements / n, (size_t) 1);
-      size_t elts_per_thread = n_elements / n_threads;
-      n_actual_threads = n_threads - 1;
-      for (int i = 0; i < n_actual_threads; ++i)
-	{
-	  RandomIt end = first + elts_per_thread;
-	  auto task = [=] ()
-		      {
-			callback (first, end);
-		      };
-
-	  futures[i] = gdb::thread_pool::g_thread_pool->post_task (task);
-	  first = end;
-	}
+      elts_per_thread = n_elements / n_threads;
     }
 #endif /* CXX_STD_THREAD */
 
-  /* Process all the remaining elements in the main thread.  */
-  callback (first, last);
+  gdb::detail::par_for_accumulator<result_type> results (n_threads - 1);
 
 #if CXX_STD_THREAD
-  for (int i = 0; i < n_actual_threads; ++i)
-    futures[i].wait ();
+  for (int i = 0; i < n_threads - 1; ++i)
+    {
+      RandomIt end = first + elts_per_thread;
+      results.post (i, [=] ()
+        {
+	  return callback (first, end);
+	});
+      first = end;
+    }
 #endif /* CXX_STD_THREAD */
+
+  /* Process all the remaining elements in the main thread.  */
+  return results.finish ([=] ()
+    {
+      return callback (first, last);
+    });
 }
 
 }
diff --git a/gdbsupport/thread-pool.cc b/gdbsupport/thread-pool.cc
index 2bb75cc9cef..f2252ffc9fd 100644
--- a/gdbsupport/thread-pool.cc
+++ b/gdbsupport/thread-pool.cc
@@ -129,11 +129,10 @@ thread_pool::set_thread_count (size_t num_threads)
   m_thread_count = num_threads;
 }
 
-std::future<void>
-thread_pool::post_task (std::function<void ()> &&func)
+void
+thread_pool::do_post_task (std::packaged_task<void ()> &&func)
 {
   std::packaged_task<void ()> t (std::move (func));
-  std::future<void> f = t.get_future ();
 
   if (m_thread_count == 0)
     {
@@ -146,7 +145,6 @@ thread_pool::post_task (std::function<void ()> &&func)
       m_tasks.emplace (std::move (t));
       m_tasks_cv.notify_one ();
     }
-  return f;
 }
 
 void
diff --git a/gdbsupport/thread-pool.h b/gdbsupport/thread-pool.h
index 9bddaa9eaae..bf0e03f005a 100644
--- a/gdbsupport/thread-pool.h
+++ b/gdbsupport/thread-pool.h
@@ -58,7 +58,24 @@ class thread_pool
 
   /* Post a task to the thread pool.  A future is returned, which can
      be used to wait for the result.  */
-  std::future<void> post_task (std::function<void ()> &&func);
+  std::future<void> post_task (std::function<void ()> &&func)
+  {
+    std::packaged_task<void ()> task (std::move (func));
+    std::future<void> result = task.get_future ();
+    do_post_task (std::packaged_task<void ()> (std::move (task)));
+    return result;
+  }
+
+  /* Post a task to the thread pool.  A future is returned, which can
+     be used to wait for the result.  */
+  template<typename T>
+  std::future<T> post_task (std::function<T ()> &&func)
+  {
+    std::packaged_task<T ()> task (std::move (func));
+    std::future<T> result = task.get_future ();
+    do_post_task (std::packaged_task<void ()> (std::move (task)));
+    return result;
+  }
 
 private:
 
@@ -67,6 +84,10 @@ class thread_pool
   /* The callback for each worker thread.  */
   void thread_function ();
 
+  /* Post a task to the thread pool.  A future is returned, which can
+     be used to wait for the result.  */
+  void do_post_task (std::packaged_task<void ()> &&func);
+
   /* The current thread count.  */
   size_t m_thread_count = 0;
 
-- 
2.31.1