gdbsupport/parallel-for.h

   1 /* Parallel for loops
   2
   3    Copyright (C) 2019-2024 Free Software Foundation, Inc.
   4
   5    This file is part of GDB.
   6
   7    This program is free software; you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 3 of the License, or
  10    (at your option) any later version.
  11
  12    This program is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
  19
  20 #ifndef GDBSUPPORT_PARALLEL_FOR_H
  21 #define GDBSUPPORT_PARALLEL_FOR_H
  22
  23 #include <algorithm>
  24 #include <type_traits>
  25 #include "gdbsupport/thread-pool.h"
  26 #include "gdbsupport/function-view.h"
  27
  28 namespace gdb
  29 {
  30
  31 /* A very simple "parallel for".  This splits the range of iterators
  32    into subranges, and then passes each subrange to the callback.  The
  33    work may or may not be done in separate threads.
  34
  35    This approach was chosen over having the callback work on single
  36    items because it makes it simple for the caller to do
  37    once-per-subrange initialization and destruction.
  38
  39    The parameter N says how batching ought to be done -- there will be
  40    at least N elements processed per thread.  Setting N to 0 is not
  41    allowed.  */
  42
  43 template<class RandomIt, class RangeFunction>
  44 void
  45 parallel_for_each (unsigned n, RandomIt first, RandomIt last,
  46                    RangeFunction callback)
  47 {
  48   /* If enabled, print debug info about how the work is distributed across
  49      the threads.  */
  50   const bool parallel_for_each_debug = false;
  51
  52   size_t n_worker_threads = thread_pool::g_thread_pool->thread_count ();
  53   size_t n_threads = n_worker_threads;
  54   size_t n_elements = last - first;
  55   size_t elts_per_thread = 0;
  56   size_t elts_left_over = 0;
  57
  58   if (n_threads > 1)
  59     {
  60       /* Require that there should be at least N elements in a
  61          thread.  */
  62       gdb_assert (n > 0);
  63       if (n_elements / n_threads < n)
  64         n_threads = std::max (n_elements / n, (size_t) 1);
  65       elts_per_thread = n_elements / n_threads;
  66       elts_left_over = n_elements % n_threads;
  67       /* n_elements == n_threads * elts_per_thread + elts_left_over. */
  68     }
  69
  70   size_t count = n_threads == 0 ? 0 : n_threads - 1;
  71   std::vector<gdb::future<void>> results;
  72
  73   if (parallel_for_each_debug)
  74     {
  75       debug_printf (_("Parallel for: n_elements: %zu\n"), n_elements);
  76       debug_printf (_("Parallel for: minimum elements per thread: %u\n"), n);
  77       debug_printf (_("Parallel for: elts_per_thread: %zu\n"), elts_per_thread);
  78     }
  79
  80   for (int i = 0; i < count; ++i)
  81     {
  82       RandomIt end;
  83       end = first + elts_per_thread;
  84       if (i < elts_left_over)
  85         /* Distribute the leftovers over the worker threads, to avoid having
  86            to handle all of them in a single thread.  */
  87         end++;
  88
  89       /* This case means we don't have enough elements to really
  90          distribute them.  Rather than ever submit a task that does
  91          nothing, we short-circuit here.  */
  92       if (first == end)
  93         end = last;
  94
  95       if (end == last)
  96         {
  97           /* We're about to dispatch the last batch of elements, which
  98              we normally process in the main thread.  So just truncate
  99              the result list here.  This avoids submitting empty tasks
 100              to the thread pool.  */
 101           count = i;
 102           break;
 103         }
 104
 105       if (parallel_for_each_debug)
 106         {
 107           debug_printf (_("Parallel for: elements on worker thread %i\t: %zu"),
 108                         i, (size_t)(end - first));
 109           debug_printf (_("\n"));
 110         }
 111       results.push_back (gdb::thread_pool::g_thread_pool->post_task ([=] ()
 112         {
 113           return callback (first, end);
 114         }));
 115       first = end;
 116     }
 117
 118   for (int i = count; i < n_worker_threads; ++i)
 119     if (parallel_for_each_debug)
 120       {
 121         debug_printf (_("Parallel for: elements on worker thread %i\t: 0"), i);
 122         debug_printf (_("\n"));
 123       }
 124
 125   /* Process all the remaining elements in the main thread.  */
 126   if (parallel_for_each_debug)
 127     {
 128       debug_printf (_("Parallel for: elements on main thread\t\t: %zu"),
 129                     (size_t)(last - first));
 130       debug_printf (_("\n"));
 131     }
 132   callback (first, last);
 133
 134   for (auto &fut : results)
 135     fut.get ();
 136 }
 137
 138 /* A sequential drop-in replacement of parallel_for_each.  This can be useful
 139    when debugging multi-threading behaviour, and you want to limit
 140    multi-threading in a fine-grained way.  */
 141
 142 template<class RandomIt, class RangeFunction>
 143 void
 144 sequential_for_each (unsigned n, RandomIt first, RandomIt last,
 145                      RangeFunction callback)
 146 {
 147   callback (first, last);
 148 }
 149
 150 }
 151
 152 #endif /* GDBSUPPORT_PARALLEL_FOR_H */