From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from simark.ca by simark.ca with LMTP id 9EMgCPPhZmiFgioAWB0awg (envelope-from ) for ; Thu, 03 Jul 2025 16:02:59 -0400 Authentication-Results: simark.ca; dkim=pass (1024-bit key; unprotected) header.d=polymtl.ca header.i=@polymtl.ca header.a=rsa-sha256 header.s=default header.b=KWuliAqR; dkim-atps=neutral Received: by simark.ca (Postfix, from userid 112) id 0BD741E126; Thu, 3 Jul 2025 16:02:59 -0400 (EDT) X-Spam-Checker-Version: SpamAssassin 4.0.1 (2024-03-25) on simark.ca X-Spam-Level: X-Spam-Status: No, score=-9.1 required=5.0 tests=ARC_SIGNED,ARC_VALID,BAYES_00, DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,MAILING_LIST_MULTI, RCVD_IN_DNSWL_MED,RCVD_IN_VALIDITY_CERTIFIED,RCVD_IN_VALIDITY_RPBL, RCVD_IN_VALIDITY_SAFE autolearn=unavailable autolearn_force=no version=4.0.1 Received: from server2.sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (prime256v1) server-digest SHA256) (No client certificate requested) by simark.ca (Postfix) with ESMTPS id 566EC1E0C2 for ; Thu, 3 Jul 2025 16:02:58 -0400 (EDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id D7DAA3860015 for ; Thu, 3 Jul 2025 20:02:57 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org D7DAA3860015 Authentication-Results: sourceware.org; dkim=pass (1024-bit key, unprotected) header.d=polymtl.ca header.i=@polymtl.ca header.a=rsa-sha256 header.s=default header.b=KWuliAqR Received: from smtp.polymtl.ca (smtp.polymtl.ca [132.207.4.11]) by sourceware.org (Postfix) with ESMTPS id 94FCF3852108 for ; Thu, 3 Jul 2025 20:01:43 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 94FCF3852108 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=polymtl.ca Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=polymtl.ca ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 94FCF3852108 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=132.207.4.11 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1751572903; cv=none; b=FuP/MQdRmgTA2ITSzCdNEQczbMP3a9cBN81nh/Nn8f1O8u9Ow4JFGxn87Bx9i1yrQLBYBqRLhfF9hm5ozjlCDwNzpY0avuVKLxTG/nB2JpixwUguEI87SERvockUu7kUpGwvDme/T9U5o5xbnwOkhob5aEL5Ofpn7WqYeElXzE4= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1751572903; c=relaxed/simple; bh=XSub1vyNiDK048v1qbyaDf1NSX0XipKghC7JAOHqeBw=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=Cq93eT1jzSmXU719URtB9JaHyFM8ZvzgxeEE0UUqmc2gVcNTOCOE2CyM6JfI9hBuIzxJrioRKC3eZmwwwFDGYPPm/FQsin2HM8R+T1jmw3uLQ8HhezUwAPli3BdGwaV3wqbzTole33+Gz4v95rvPMRjyi8f0KQgo4r1Vefx9Ocg= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 94FCF3852108 Received: from simark.ca (simark.ca [158.69.221.121]) (authenticated bits=0) by smtp.polymtl.ca (8.14.7/8.14.7) with ESMTP id 563K1cmM007529 (version=TLSv1/SSLv3 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT) for ; Thu, 3 Jul 2025 16:01:43 -0400 DKIM-Filter: OpenDKIM Filter v2.11.0 smtp.polymtl.ca 563K1cmM007529 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=polymtl.ca; s=default; t=1751572903; bh=NVdhAWxwjMcPZcALiGNPWFIxXvG/LOpMplCe9dpgFLE=; h=From:To:Cc:Subject:Date:In-Reply-To:From; b=KWuliAqRBxVPQqbGTXIz+x1nlbNGVFUIp3TovlWrSOMreQS4pjt2LQDV5OwyEMZka EByX5ebRPaAdRWCqySzxkcmaZBMCJPX7kxxGNcHPJFPzkeuL8J7h0uYPmusZjn3iR5 EuXcjINIsK45h0NULwlTdJJP7HgdJtj7dhJev9OI= Received: by simark.ca (Postfix, from userid 112) id 6542C1E12E; Thu, 3 Jul 2025 16:01:38 -0400 (EDT) Received: from simark.localdomain (modemcable238.237-201-24.mc.videotron.ca [24.201.237.238]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (prime256v1) server-digest SHA256) (No client certificate requested) by simark.ca (Postfix) with ESMTPSA id F2F511E11C; Thu, 3 Jul 2025 16:01:31 -0400 (EDT) From: simon.marchi@polymtl.ca To: gdb-patches@sourceware.org Cc: Simon Marchi Subject: [PATCH v2 2/4] gdbsupport: factor out work queue from parallel-for.h Date: Thu, 3 Jul 2025 16:01:17 -0400 Message-ID: <20250703200130.4095761-2-simon.marchi@polymtl.ca> X-Mailer: git-send-email 2.50.0 In-Reply-To: <20250703200130.4095761-1-simon.marchi@polymtl.ca> References: <20250703200130.4095761-1-simon.marchi@polymtl.ca> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Poly-FromMTA: (simark.ca [158.69.221.121]) at Thu, 3 Jul 2025 20:01:38 +0000 X-BeenThere: gdb-patches@sourceware.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gdb-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gdb-patches-bounces~public-inbox=simark.ca@sourceware.org From: Simon Marchi New in v2: add some consts In preparation for a following patch that will re-use the shared work queue algorithm, move it to a separate class. Change-Id: Id05cf8898a5d162048fa8fa056fbf7e0441bfb78 --- gdbsupport/parallel-for.h | 45 +++++-------------- gdbsupport/work-queue.h | 95 +++++++++++++++++++++++++++++++++++++++ 2 files changed, 107 insertions(+), 33 deletions(-) create mode 100644 gdbsupport/work-queue.h diff --git a/gdbsupport/parallel-for.h b/gdbsupport/parallel-for.h index bb41eb8700f0..c5a15d3235a7 100644 --- a/gdbsupport/parallel-for.h +++ b/gdbsupport/parallel-for.h @@ -23,6 +23,7 @@ #include #include #include "gdbsupport/thread-pool.h" +#include "gdbsupport/work-queue.h" namespace gdb { @@ -57,12 +58,8 @@ parallel_for_each (const RandomIt first, const RandomIt last, debug_printf ("Parallel for: batch size: %zu\n", batch_size); } - const size_t n_worker_threads - = std::max (thread_pool::g_thread_pool->thread_count (), 1); std::vector> results; - - /* The next item to hand out. */ - std::atomic next = first; + work_queue queue (first, last); /* The worker thread task. @@ -75,49 +72,31 @@ parallel_for_each (const RandomIt first, const RandomIt last, and `args` can be used as-is in the lambda. */ auto args_tuple = std::forward_as_tuple (std::forward (worker_args)...); - auto task = - [&next, first, last, n_worker_threads, &args_tuple] () { + auto task = [&queue, first, &args_tuple] () { /* Instantiate the user-defined worker. */ auto worker = std::make_from_tuple (args_tuple); for (;;) { - /* Grab a snapshot of NEXT. */ - auto local_next = next.load (); - gdb_assert (local_next <= last); + const auto [batch_first, batch_last] = queue.pop_batch (); - /* Number of remaining items. */ - auto n_remaining = last - local_next; - gdb_assert (n_remaining >= 0); - - /* Are we done? */ - if (n_remaining == 0) + if (batch_first == batch_last) break; - const auto this_batch_size - = std::min (batch_size, n_remaining); - - /* The range to process in this iteration. */ - const auto this_batch_first = local_next; - const auto this_batch_last = local_next + this_batch_size; - - /* Update NEXT. If the current value of NEXT doesn't match - LOCAL_NEXT, it means another thread updated it concurrently, - restart. */ - if (!next.compare_exchange_weak (local_next, this_batch_last)) - continue; - if (parallel_for_each_debug) debug_printf ("Processing %zu items, range [%zu, %zu[\n", - this_batch_size, - static_cast (this_batch_first - first), - static_cast (this_batch_last - first)); + static_cast (batch_last - batch_first), + static_cast (batch_first - first), + static_cast (batch_last - first)); - worker (this_batch_first, this_batch_last); + worker (batch_first, batch_last); } }; /* Start N_WORKER_THREADS tasks. */ + const size_t n_worker_threads + = std::max (thread_pool::g_thread_pool->thread_count (), 1); + for (int i = 0; i < n_worker_threads; ++i) results.push_back (gdb::thread_pool::g_thread_pool->post_task (task)); diff --git a/gdbsupport/work-queue.h b/gdbsupport/work-queue.h new file mode 100644 index 000000000000..f84b29a4f523 --- /dev/null +++ b/gdbsupport/work-queue.h @@ -0,0 +1,95 @@ +/* Synchronized work queue. + + Copyright (C) 2025 Free Software Foundation, Inc. + + This file is part of GDB. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see . */ + +#ifndef GDBSUPPORT_WORK_QUEUE_H +#define GDBSUPPORT_WORK_QUEUE_H + +namespace gdb +{ + +/* Implementation of a thread-safe work queue. + + The work items are specified by two iterators of type RandomIt. + + BATCH_SIZE is the number of work items to pop in a batch. */ + +template +class work_queue +{ +public: + /* The work items are specified by the range `[first, last[`. */ + work_queue (RandomIt first, RandomIt last) noexcept + : m_next (first), + m_last (last) + { + gdb_assert (first <= last); + } + + DISABLE_COPY_AND_ASSIGN (work_queue); + + /* Pop a batch of work items. + + The return value is a pair containing iterators to the first and last + (exclusive) work items. */ + std::pair pop_batch () noexcept + { + for (;;) + { + /* Grab a snapshot of M_NEXT. */ + auto next = m_next.load (); + gdb_assert (next <= m_last); + + /* The number of items remaining in the queue. */ + const auto n_remaining = static_cast (m_last - next); + + /* Are we done? */ + if (n_remaining == 0) + return std::make_pair (m_last, m_last); + + /* The batch size is proportional to the number of items remaining in + the queue. We do this to try to stike a balance, avoiding + synchronization overhead when there are many items to process at the + start, and avoiding workload imbalance when there are few items to + process at the end. */ + const auto this_batch_size = std::min (batch_size, n_remaining); + + /* The range of items in this batch. */ + const auto this_batch_first = next; + const auto this_batch_last = next + this_batch_size; + + /* Update M_NEXT. If the current value of M_NEXT doesn't match NEXT, it + means another thread updated it concurrently, restart. */ + if (!m_next.compare_exchange_weak (next, this_batch_last)) + continue; + + return std::make_pair (this_batch_first, this_batch_last); + } + } + +private: + /* The next work item to hand out. */ + std::atomic m_next; + + /* The end of the work item range. */ + RandomIt m_last; +}; + +} /* namespace gdb */ + +#endif /* GDBSUPPORT_WORK_QUEUE_H */ -- 2.50.0