From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from simark.ca by simark.ca with LMTP id CN6BM5Iq42BLYwAAWB0awg (envelope-from ) for ; Mon, 05 Jul 2021 11:51:46 -0400 Received: by simark.ca (Postfix, from userid 112) id D07D81F1F2; Mon, 5 Jul 2021 11:51:46 -0400 (EDT) X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on simark.ca X-Spam-Level: X-Spam-Status: No, score=-1.0 required=5.0 tests=MAILING_LIST_MULTI autolearn=ham autolearn_force=no version=3.4.2 Received: from 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 RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by simark.ca (Postfix) with ESMTPS id 279E71E940 for ; Mon, 5 Jul 2021 11:51:46 -0400 (EDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id E42C4386FC05 for ; Mon, 5 Jul 2021 15:51:45 +0000 (GMT) Received: from mail-wm1-x330.google.com (mail-wm1-x330.google.com [IPv6:2a00:1450:4864:20::330]) by sourceware.org (Postfix) with ESMTPS id 0898F386FC0E for ; Mon, 5 Jul 2021 15:51:29 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 0898F386FC0E Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=palves.net Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com Received: by mail-wm1-x330.google.com with SMTP id t14-20020a05600c198eb029020c8aac53d4so4299549wmq.1 for ; Mon, 05 Jul 2021 08:51:28 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:from:to:references:message-id:date :user-agent:mime-version:in-reply-to:content-language :content-transfer-encoding; bh=SM7z1Qmh5xdp7N3CLA6G94ESSSp2RWUbHQ7g0AOuZgA=; b=YrQvJ4YhmgccMgQUcgHTiSWW0oalGj9tlmwR7PnuSIeIHIOYC109itkREfHP2ByqFX nlFq59hQsaMo1jr0jmcZM4bN7+8/UVlLv9J5VUYzSXq7iu6n8WlhP+Hc4y59E/+uNPxd PVB3HDoMwcYpNNn2Nz4lTFJFfUMUPf0bj6JOgoE5PfA1WWD/j0rOqa72x3VaXdLj45fK wkyuu9YiQejlrjIbIePX8Ddy1cRXHnvcUw2eIHisnP9Q7x4sDSAdtxvJ3Oxs6W3hMo/o BkCTK4/Dg1n+WMzPoQJ7RavFJK03Z0FPViHJ49tkU7/C9KyvBENZ/OEcr9TUARY4WHpD BwkA== X-Gm-Message-State: AOAM5316ahsx1qBk49uSiDPNk5Hy4jhKqyw1oA6yWNLuCnAZvcT0Xq+I Wh/LShmVe+et6oI13h5cxHfmlvPlgLDkDA== X-Google-Smtp-Source: ABdhPJxgbSauJcEI68W8kHLcjqphCoTgX+bv2vShZWlaKsR8azutzIemYxQNZnjYveJBKabQ+UFnPA== X-Received: by 2002:a05:600c:49a4:: with SMTP id h36mr15352263wmp.122.1625500287358; Mon, 05 Jul 2021 08:51:27 -0700 (PDT) Received: from ?IPv6:2001:8a0:f932:6a00:46bc:d03b:7b3a:2227? ([2001:8a0:f932:6a00:46bc:d03b:7b3a:2227]) by smtp.gmail.com with ESMTPSA id k5sm13901626wmk.11.2021.07.05.08.51.26 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 05 Jul 2021 08:51:26 -0700 (PDT) Subject: Re: [PATCH 09/11] gdb: optimize selection of resumed thread with pending event From: Pedro Alves To: Simon Marchi , gdb-patches@sourceware.org References: <20210622165704.2404007-1-simon.marchi@polymtl.ca> <20210622165704.2404007-10-simon.marchi@polymtl.ca> Message-ID: <752478a3-ba8d-7f3b-e5d5-8b0a92eaa5b9@palves.net> Date: Mon, 5 Jul 2021 16:51:25 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.11.0 MIME-Version: 1.0 In-Reply-To: <20210622165704.2404007-10-simon.marchi@polymtl.ca> Content-Type: text/plain; charset=utf-8 Content-Language: en-US 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: , Errors-To: gdb-patches-bounces+public-inbox=simark.ca@sourceware.org Sender: "Gdb-patches" On 2021-06-22 5:57 p.m., Simon Marchi via Gdb-patches wrote: > Consider a case where many threads (thousands) keep hitting a breakpoint > whose condition evaluates to false. random_pending_event_thread is > responsible for selecting a thread from an inferior among all that are > resumed with a pending wait status. It is currently implemented by > walking the inferior's thread list twice: once to count the number of > candidates and once to select a random one. > > Since we now maintain a per target list of resumed threads with pending > event, we can implement this more efficiently by walking that list and > selecting the first thread that matches the criteria > (random_pending_event_thread looks for an thread from a specific > inferior, and possibly a filter ptid). It will be faster especially in > the common case where there isn't any resumed thread with pending > event. Currently, we have to iterate the thread list to figure this > out. With this patch, the list of resumed threads with pending event > will be empty, so it's quick to figure out. > > The random selection is kept, but is moved to > process_stratum_target::random_resumed_with_pending_wait_status. The > same technique is used: do a first pass to count the number of > candidates, and do a second pass to select a random one. But given that > the list of resumed threads with pending wait statuses will generally be > short, or at least shorter than the full thread list, it should be > quicker. > > Note that this isn't completely true, in case there are multiple > inferiors on the same target. Imagine that inferior A has 10k resumed > threads with pending wait statuses, and random_pending_event_thread is > called with inferior B. We'll need to go through the list that contains > inferior A's threads to realize that inferior B has no resumed threads > with pending wait status. But I think that this is a corner / > pathological case. And a possible fix for this situation would be to > make random_pending_event_thread work per-process-target, rather than > per-inferior. > > gdb/ChangeLog: > > * process-stratum-target.h (class process_stratum_target) > : New. > * process-stratum-target.c > (process_stratum_target::random_resumed_with_pending_wait_status): > New. > * infrun.c (random_pending_event_thread): Use > random_resumed_with_pending_wait_status. OK.