From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp-out1.suse.de (smtp-out1.suse.de [195.135.220.28]) by sourceware.org (Postfix) with ESMTPS id 5AED23835407 for ; Fri, 22 Jul 2022 17:03:47 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 5AED23835407 Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by smtp-out1.suse.de (Postfix) with ESMTPS id 217C83832D for ; Fri, 22 Jul 2022 17:03:46 +0000 (UTC) Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by imap2.suse-dmz.suse.de (Postfix) with ESMTPS id 0EEEE13AB3 for ; Fri, 22 Jul 2022 17:03:46 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id KNSSAnLY2mKvMAAAMHmgww (envelope-from ) for ; Fri, 22 Jul 2022 17:03:46 +0000 From: Tom de Vries To: gdb-patches@sourceware.org Subject: [PATCH 2/4] [gdbsupport] Add task size parameter in parallel_for_each Date: Fri, 22 Jul 2022 19:03:43 +0200 Message-Id: <20220722170345.24713-2-tdevries@suse.de> X-Mailer: git-send-email 2.35.3 In-Reply-To: <20220722170345.24713-1-tdevries@suse.de> References: <20220722170345.24713-1-tdevries@suse.de> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-12.7 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gdb-patches@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gdb-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 22 Jul 2022 17:03:49 -0000 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. Tested on x86_64-linux. --- 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/parallel-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 == 0); + auto task_size_max_ = [] (int iter) + { + return (size_t)SIZE_MAX; + }; + auto task_size_max = gdb::make_function_view (task_size_max_); + + counter = 0; + gdb::parallel_for_each (1, 0, NUMBER, + [&] (int start, int end) + { + counter += end - start; + }, task_size_max); + SELF_CHECK (counter == NUMBER); + + auto task_size_one_ = [] (int iter) + { + return (size_t)1; + }; + auto task_size_one = gdb::make_function_view (task_size_one_); + + counter = 0; + gdb::parallel_for_each (1, 0, NUMBER, + [&] (int start, int end) + { + counter += end - start; + }, task_size_one); + SELF_CHECK (counter == NUMBER); + #undef NUMBER } 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" 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 = nullptr) { using result_type = typename std::result_of::type; @@ -148,17 +150,41 @@ parallel_for_each (unsigned n, RandomIt first, RandomIt last, size_t n_elements = last - first; size_t elts_per_thread = 0; size_t elts_left_over = 0; + size_t total_size = 0; + size_t size_per_thread = 0; + size_t max_element_size = n_elements == 0 ? 1 : SIZE_MAX / n_elements; 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 = std::max (n_elements / n, (size_t) 1); - elts_per_thread = n_elements / n_threads; - elts_left_over = n_elements % n_threads; - /* n_elements == n_threads * elts_per_thread + elts_left_over. */ + if (task_size != nullptr) + { + gdb_assert (n == 1); + for (RandomIt i = first; i != last; ++i) + { + size_t element_size = 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 = max_element_size; + size_t prev_total_size = total_size; + total_size += element_size; + /* Check for overflow. */ + gdb_assert (prev_total_size < total_size); + } + size_per_thread = 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 = std::max (n_elements / n, (size_t) 1); + elts_per_thread = n_elements / n_threads; + elts_left_over = n_elements % n_threads; + /* n_elements == n_threads * elts_per_thread + elts_left_over. */ + } } size_t count = n_threads == 0 ? 0 : n_threads - 1; @@ -167,20 +193,52 @@ parallel_for_each (unsigned n, RandomIt first, RandomIt 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_thread); + if (task_size != nullptr) + { + debug_printf (_("Parallel for: total_size: %zu\n"), total_size); + debug_printf (_("Parallel for: size_per_thread: %zu\n"), size_per_thread); + } + else + { + debug_printf (_("Parallel for: minimum elements per thread: %u\n"), n); + debug_printf (_("Parallel for: elts_per_thread: %zu\n"), elts_per_thread); + } } + size_t remaining_size = total_size; for (int i = 0; i < count; ++i) { - RandomIt end = 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 = 0; + if (task_size == nullptr) + { + end = 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 = first; j < last && chunk_size < size_per_thread; ++j) + { + size_t element_size = task_size (j); + if (element_size > max_element_size) + element_size = max_element_size; + chunk_size += element_size; + } + end = j; + remaining_size -= 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 != nullptr) + debug_printf (_("\t(size: %zu)"), chunk_size); + debug_printf (_("\n")); + } results.post (i, [=] () { return callback (first, end); @@ -190,12 +248,22 @@ parallel_for_each (unsigned n, RandomIt first, RandomIt last, for (int i = 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 != nullptr) + debug_printf (_("\t(size: 0)")); + debug_printf (_("\n")); + } /* 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 != nullptr) + debug_printf (_("\t(size: %zu)"), remaining_size); + debug_printf (_("\n")); + } return results.finish ([=] () { 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 = nullptr) { using result_type = typename std::result_of::type; -- 2.35.3