From 71a2349005e74e0d64554f5c88e3632f3ace167a Mon Sep 17 00:00:00 2001 From: Simon Marchi Date: Tue, 15 Jun 2021 22:14:38 -0400 Subject: gdb: optimize selection of resumed thread with pending event 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. Change-Id: I1b71d01beaa500a148b5b9797745103e13917325 --- gdb/process-stratum-target.c | 43 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 43 insertions(+) (limited to 'gdb/process-stratum-target.c') diff --git a/gdb/process-stratum-target.c b/gdb/process-stratum-target.c index 2cb6dfc..7aeda79 100644 --- a/gdb/process-stratum-target.c +++ b/gdb/process-stratum-target.c @@ -20,6 +20,7 @@ #include "defs.h" #include "process-stratum-target.h" #include "inferior.h" +#include process_stratum_target::~process_stratum_target () { @@ -140,6 +141,48 @@ process_stratum_target::maybe_remove_resumed_with_pending_wait_status /* See process-stratum-target.h. */ +thread_info * +process_stratum_target::random_resumed_with_pending_wait_status + (inferior *inf, ptid_t filter_ptid) +{ + auto matches = [inf, filter_ptid] (const thread_info &thread) + { + return thread.inf == inf && thread.ptid.matches (filter_ptid); + }; + + /* First see how many matching events we have. */ + const auto &l = m_resumed_with_pending_wait_status; + unsigned int count = std::count_if (l.begin (), l.end (), matches); + + if (count == 0) + return nullptr; + + /* Now randomly pick a thread out of those that match the criteria. */ + int random_selector + = (int) ((count * (double) rand ()) / (RAND_MAX + 1.0)); + + if (count > 1) + infrun_debug_printf ("Found %u events, selecting #%d", + count, random_selector); + + /* Select the Nth thread that matches. */ + auto it = std::find_if (l.begin (), l.end (), + [&random_selector, &matches] + (const thread_info &thread) + { + if (!matches (thread)) + return false; + + return random_selector-- == 0; + }); + + gdb_assert (it != l.end ()); + + return &*it; +} + +/* See process-stratum-target.h. */ + std::set all_non_exited_process_targets () { -- cgit v1.1