From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from simark.ca by simark.ca with LMTP id po9ZKMb82mKBwRgAWB0awg (envelope-from ) for ; Fri, 22 Jul 2022 15:38:46 -0400 Received: by simark.ca (Postfix, from userid 112) id 963B81E5EA; Fri, 22 Jul 2022 15:38:46 -0400 (EDT) Authentication-Results: simark.ca; dkim=pass (1024-bit key; secure) header.d=sourceware.org header.i=@sourceware.org header.a=rsa-sha256 header.s=default header.b=oZXqAgjF; dkim-atps=neutral X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on simark.ca X-Spam-Level: X-Spam-Status: No, score=-3.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,MAILING_LIST_MULTI,NICE_REPLY_A,RDNS_DYNAMIC, URIBL_BLOCKED autolearn=ham autolearn_force=no version=3.4.6 Received: from sourceware.org (ip-8-43-85-97.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by simark.ca (Postfix) with ESMTPS id 2E8311E222 for ; Fri, 22 Jul 2022 15:38:46 -0400 (EDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id B9C463858015 for ; Fri, 22 Jul 2022 19:38:45 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org B9C463858015 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1658518725; bh=2kIOkpfPf5GcwDwpO6HIfEMLBEYr9o797mnsXrQgiqY=; h=Date:Subject:To:References:In-Reply-To:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To:Cc: From; b=oZXqAgjFSGW6+txdrx/T7TjHeUlGesubWx/zS2bosDhLMsWYlNbFFlNGIEu8tdCKH 2eYzKkh1pmEZRyZqO6NhS7ztTmXHmCb5ZYHQ6anAt1DD39HV4qCS/HuIF7sN1JoakK 3ASb65jzDZsKfYci/+IqGRDgIw0Ut7Y4QOwqG4Ds= Received: from simark.ca (simark.ca [158.69.221.121]) by sourceware.org (Postfix) with ESMTPS id 5643C3858405 for ; Fri, 22 Jul 2022 19:38:26 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 5643C3858405 Received: from [10.0.0.11] (192-222-157-6.qc.cable.ebox.net [192.222.157.6]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits)) (No client certificate requested) by simark.ca (Postfix) with ESMTPSA id F10931E222; Fri, 22 Jul 2022 15:38:25 -0400 (EDT) Message-ID: <0f84af97-ddf4-a9f7-b374-eeee46f94303@simark.ca> Date: Fri, 22 Jul 2022 15:38:25 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.11.0 Subject: Re: [PATCH][gdbsupport] Use task size in parallel_for_each Content-Language: en-US To: Tom Tromey , Tom de Vries via Gdb-patches References: <20220718194219.GA16823@delia.home> <4fc23fcd-c15d-7622-8b51-cc48cd3cba16@palves.net> <75931310-5dcd-059d-9221-6c94dbcd231f@suse.de> <87leslj786.fsf@tromey.com> In-Reply-To: <87leslj786.fsf@tromey.com> Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit 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: , From: Simon Marchi via Gdb-patches Reply-To: Simon Marchi Cc: Pedro Alves Errors-To: gdb-patches-bounces+public-inbox=simark.ca@sourceware.org Sender: "Gdb-patches" On 2022-07-22 15:08, Tom Tromey wrote: > Pedro> My passerby comment is that I wonder whether we should consider > Pedro> switching to a work stealing implementation, so that threads that > Pedro> are done with their chunk would grab another chunk from the work > Pedro> pool. I think this would spare us from having to worry about > Pedro> these distribution heuristics. > > Tom> I also though about a dynamic solution, but decided to try the > Tom> simplest solution first. > > Tom> Anyway, with a dynamic solution you still might want to decide how big > Tom> a chunck is, for which you could still need this type of heuristics. > > I think the idea of the work-stealing approach is that each worker grabs > work as it can, and so no sizing is needed at all. If one worker ends > up with a very large CU, it will simply end up working on fewer CUs. > > In this situation, work stealing might make the overall implementation > simpler. Perhaps the batching parameter patch (commit 82d734f7a) and > the vector of results patch (commit f4565e4c9) could be removed. > > Then, rather than using parallel_for, the DWARF reader could send N jobs > to the thread pool, and each job would simply take the next available CU > by incrementing an atomic counter. When the counter reached the number > of CUs, a job would stop. > > Tom Just a nit, if we are talking about a centralized work pool that threads pick from to get their next work item, that's not really work stealing. Work stealing is when threads all have their own work queue, and threads with empty queues go steal some work from other threads' queues. I suppose a downside to having one centralized work item queue / pool where threads pick one work item at a time is contention. If you have a ton of tiny work items, threads could spend a lot of time synchronizing on that work queue, since they need to synchronize between each item. With work stealing, there's no synchronization required until a thread is actually out of work. Given our work items are fairly large, I'm guessing that having one centralized queue is fine. Well, benchmarks will tell if that is faster than Tom de Vries' balancing approach. Simon