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 */ 153