From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 2205) id 195C03857364; Fri, 5 Aug 2022 14:13:07 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 195C03857364 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable From: Tom de Vries To: gdb-cvs@sourceware.org Subject: [binutils-gdb] [gdbsupport] Add task size parameter in parallel_for_each X-Act-Checkin: binutils-gdb X-Git-Author: Tom de Vries X-Git-Refname: refs/heads/master X-Git-Oldrev: 377c3a9c91785d5df5c0d96121160e6210204cc0 X-Git-Newrev: b859a3ef488cd1a3bf072f71002dced36353875b Message-Id: <20220805141307.195C03857364@sourceware.org> Date: Fri, 5 Aug 2022 14:13:07 +0000 (GMT) X-BeenThere: gdb-cvs@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gdb-cvs mailing list List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 05 Aug 2022 14:13:07 -0000 https://sourceware.org/git/gitweb.cgi?p=3Dbinutils-gdb.git;h=3Db859a3ef488c= d1a3bf072f71002dced36353875b commit b859a3ef488cd1a3bf072f71002dced36353875b Author: Tom de Vries Date: Fri Aug 5 16:12:56 2022 +0200 [gdbsupport] Add task size parameter in parallel_for_each =20 Add a task_size parameter to parallel_for_each, defaulting to nullptr, = and use the task size to distribute similarly-sized chunks to the threads. =20 Tested on x86_64-linux. Diff: --- gdb/unittests/parallel-for-selftests.c | 28 ++++++++ gdbsupport/parallel-for.h | 113 ++++++++++++++++++++++++++---= ---- 2 files changed, 119 insertions(+), 22 deletions(-) diff --git a/gdb/unittests/parallel-for-selftests.c b/gdb/unittests/paralle= l-for-selftests.c index 8a86b435fd3..6e341f64037 100644 --- a/gdb/unittests/parallel-for-selftests.c +++ b/gdb/unittests/parallel-for-selftests.c @@ -68,6 +68,34 @@ test (int n_threads) }); SELF_CHECK (counter =3D=3D 0); =20 + auto task_size_max_ =3D [] (int iter) + { + return (size_t)SIZE_MAX; + }; + auto task_size_max =3D gdb::make_function_view (task_size_max_); + + counter =3D 0; + gdb::parallel_for_each (1, 0, NUMBER, + [&] (int start, int end) + { + counter +=3D end - start; + }, task_size_max); + SELF_CHECK (counter =3D=3D NUMBER); + + auto task_size_one_ =3D [] (int iter) + { + return (size_t)1; + }; + auto task_size_one =3D gdb::make_function_view (task_size_one_); + + counter =3D 0; + gdb::parallel_for_each (1, 0, NUMBER, + [&] (int start, int end) + { + counter +=3D end - start; + }, task_size_one); + SELF_CHECK (counter =3D=3D NUMBER); + #undef NUMBER } =20 diff --git a/gdbsupport/parallel-for.h b/gdbsupport/parallel-for.h index 0037ee23ff3..4cd1dbf847e 100644 --- a/gdbsupport/parallel-for.h +++ b/gdbsupport/parallel-for.h @@ -23,6 +23,7 @@ #include #include #include "gdbsupport/thread-pool.h" +#include "gdbsupport/function-view.h" =20 namespace gdb { @@ -134,7 +135,8 @@ typename gdb::detail::par_for_accumulator< typename std::result_of::type >::result_type parallel_for_each (unsigned n, RandomIt first, RandomIt last, - RangeFunction callback) + RangeFunction callback, + gdb::function_view task_size =3D nullptr) { using result_type =3D typename std::result_of::type; @@ -148,17 +150,41 @@ parallel_for_each (unsigned n, RandomIt first, Random= It last, size_t n_elements =3D last - first; size_t elts_per_thread =3D 0; size_t elts_left_over =3D 0; + size_t total_size =3D 0; + size_t size_per_thread =3D 0; + size_t max_element_size =3D n_elements =3D=3D 0 ? 1 : SIZE_MAX / n_eleme= nts; =20 if (n_threads > 1) { - /* Require that there should be at least N elements in a - thread. */ - gdb_assert (n > 0); - if (n_elements / n_threads < n) - n_threads =3D std::max (n_elements / n, (size_t) 1); - elts_per_thread =3D n_elements / n_threads; - elts_left_over =3D n_elements % n_threads; - /* n_elements =3D=3D n_threads * elts_per_thread + elts_left_over. */ + if (task_size !=3D nullptr) + { + gdb_assert (n =3D=3D 1); + for (RandomIt i =3D first; i !=3D last; ++i) + { + size_t element_size =3D task_size (i); + gdb_assert (element_size > 0); + if (element_size > max_element_size) + /* We could start scaling here, but that doesn't seem to be + worth the effort. */ + element_size =3D max_element_size; + size_t prev_total_size =3D total_size; + total_size +=3D element_size; + /* Check for overflow. */ + gdb_assert (prev_total_size < total_size); + } + size_per_thread =3D total_size / n_threads; + } + else + { + /* Require that there should be at least N elements in a + thread. */ + gdb_assert (n > 0); + if (n_elements / n_threads < n) + n_threads =3D std::max (n_elements / n, (size_t) 1); + elts_per_thread =3D n_elements / n_threads; + elts_left_over =3D n_elements % n_threads; + /* n_elements =3D=3D n_threads * elts_per_thread + elts_left_over. */ + } } =20 size_t count =3D n_threads =3D=3D 0 ? 0 : n_threads - 1; @@ -167,20 +193,52 @@ parallel_for_each (unsigned n, RandomIt first, Random= It last, if (parallel_for_each_debug) { debug_printf (_("Parallel for: n_elements: %zu\n"), n_elements); - debug_printf (_("Parallel for: minimum elements per thread: %u\n"), = n); - debug_printf (_("Parallel for: elts_per_thread: %zu\n"), elts_per_th= read); + if (task_size !=3D nullptr) + { + debug_printf (_("Parallel for: total_size: %zu\n"), total_size); + debug_printf (_("Parallel for: size_per_thread: %zu\n"), size_per_threa= d); + } + else + { + debug_printf (_("Parallel for: minimum elements per thread: %u\n"), n); + debug_printf (_("Parallel for: elts_per_thread: %zu\n"), elts_per_threa= d); + } } =20 + size_t remaining_size =3D total_size; for (int i =3D 0; i < count; ++i) { - RandomIt end =3D first + elts_per_thread; - if (i < elts_left_over) - /* Distribute the leftovers over the worker threads, to avoid having - to handle all of them in a single thread. */ - end++; + RandomIt end; + size_t chunk_size =3D 0; + if (task_size =3D=3D nullptr) + { + end =3D first + elts_per_thread; + if (i < elts_left_over) + /* Distribute the leftovers over the worker threads, to avoid having + to handle all of them in a single thread. */ + end++; + } + else + { + RandomIt j; + for (j =3D first; j < last && chunk_size < size_per_thread; ++j) + { + size_t element_size =3D task_size (j); + if (element_size > max_element_size) + element_size =3D max_element_size; + chunk_size +=3D element_size; + } + end =3D j; + remaining_size -=3D chunk_size; + } if (parallel_for_each_debug) - debug_printf (_("Parallel for: elements on worker thread %i\t: %zu\n"), - i, (size_t)(end - first)); + { + debug_printf (_("Parallel for: elements on worker thread %i\t: %zu"), + i, (size_t)(end - first)); + if (task_size !=3D nullptr) + debug_printf (_("\t(size: %zu)"), chunk_size); + debug_printf (_("\n")); + } results.post (i, [=3D] () { return callback (first, end); @@ -190,12 +248,22 @@ parallel_for_each (unsigned n, RandomIt first, Random= It last, =20 for (int i =3D count; i < n_worker_threads; ++i) if (parallel_for_each_debug) - debug_printf (_("Parallel for: elements on worker thread %i\t: 0\n")= , i); + { + debug_printf (_("Parallel for: elements on worker thread %i\t: 0"), i); + if (task_size !=3D nullptr) + debug_printf (_("\t(size: 0)")); + debug_printf (_("\n")); + } =20 /* Process all the remaining elements in the main thread. */ if (parallel_for_each_debug) - debug_printf (_("Parallel for: elements on main thread\t\t: %zu\n"), - (size_t)(last - first)); + { + debug_printf (_("Parallel for: elements on main thread\t\t: %zu"), + (size_t)(last - first)); + if (task_size !=3D nullptr) + debug_printf (_("\t(size: %zu)"), remaining_size); + debug_printf (_("\n")); + } return results.finish ([=3D] () { return callback (first, last); @@ -211,7 +279,8 @@ typename gdb::detail::par_for_accumulator< typename std::result_of::type >::result_type sequential_for_each (unsigned n, RandomIt first, RandomIt last, - RangeFunction callback) + RangeFunction callback, + gdb::function_view task_size =3D nullptr) { using result_type =3D typename std::result_of::type;