[11/11] gdb: optimize all_matching_threads_iterator

Message ID 20210622165704.2404007-12-simon.marchi@polymtl.ca
State New
Headers show
Series
  • Various thread lists optimizations
Related show

Commit Message

Eli Zaretskii via Gdb-patches June 22, 2021, 4:57 p.m.
all_matching_threads_iterator is used extensively in some pretty fast
paths, often under the all_non_exited_threads function.

If a filter target and thread-specific ptid are given, it iterates on
all threads of all inferiors of that target, to ultimately yield exactly
on thread.  And this happens quite often, which means we unnecessarily
spend time iterating on threads to find the one we are looking for.  The
same thing happens if an inferior-specific ptid is given, although there
the iterator yields all the threads of that inferior.

In those cases, the callers of all_non_exited_threads could have
different behaviors depending on the kind of ptid, to avoid this
inefficiency, but that would be very tedious.  Using
all_non_exited_threads has the advantage that one simple implementation
can work seamlessly on multiple threads or on one specific thread, just
by playing with the ptid.

Instead, optimize all_matching_threads_iterator directly to detect these
different cases and limiting what we iterate on to just what we need.

 - if filter_ptid is minus_one_ptid, do as we do now: filter inferiors
   based on filter_target, iterate on all of the matching inferiors'
   threads
 - if filter_ptid is a pid-only ptid (then a filter_target must
   necessarily be given), look up that inferior and iterate on all its
   threads
 - otherwise, filter_ptid is a thread-specific ptid, so look up that
   specific thread and "iterate" only on it

For the last case, what was an iteration on all threads of the filter
target now becomes a call to find_thread_ptid, which is quite efficient
now thanks to inferior::ptid_thread_map.

gdb/ChangeLog:

	* thread-iter.h (class all_matching_threads_iterator)
	<all_matching_threads_iterator>: Use default.
	<enum class mode>: New.
	<m_inf, m_thr>: Initialize.
	<m_filter_ptid>: Remove.
	* thread-iter.c (all_matching_threads_iterator::m_inf_matches):
	Don't filter on m_filter_ptid.
	(all_matching_threads_iterator::all_matching_threads_iterator):
	Choose path based on filter_ptid (all threads, all threads of
	inferior, single thread).
	(all_matching_threads_iterator::advance): Likewise.

Change-Id: Ic6a19845f5f760fa1b8eac8145793c0ff431bbc9
---
 gdb/thread-iter.c | 138 ++++++++++++++++++++++++++++++----------------
 gdb/thread-iter.h |  29 ++++++----
 2 files changed, 107 insertions(+), 60 deletions(-)

-- 
2.32.0

Comments

Pedro Alves July 5, 2021, 3:52 p.m. | #1
On 2021-06-22 5:57 p.m., Simon Marchi via Gdb-patches wrote:
> all_matching_threads_iterator is used extensively in some pretty fast

> paths, often under the all_non_exited_threads function.

> 

> If a filter target and thread-specific ptid are given, it iterates on

> all threads of all inferiors of that target, to ultimately yield exactly

> on thread.  And this happens quite often, which means we unnecessarily

> spend time iterating on threads to find the one we are looking for.  The

> same thing happens if an inferior-specific ptid is given, although there

> the iterator yields all the threads of that inferior.

> 

> In those cases, the callers of all_non_exited_threads could have

> different behaviors depending on the kind of ptid, to avoid this

> inefficiency, but that would be very tedious.  Using

> all_non_exited_threads has the advantage that one simple implementation

> can work seamlessly on multiple threads or on one specific thread, just

> by playing with the ptid.

> 

> Instead, optimize all_matching_threads_iterator directly to detect these

> different cases and limiting what we iterate on to just what we need.

> 

>  - if filter_ptid is minus_one_ptid, do as we do now: filter inferiors

>    based on filter_target, iterate on all of the matching inferiors'

>    threads

>  - if filter_ptid is a pid-only ptid (then a filter_target must

>    necessarily be given), look up that inferior and iterate on all its

>    threads

>  - otherwise, filter_ptid is a thread-specific ptid, so look up that

>    specific thread and "iterate" only on it

> 

> For the last case, what was an iteration on all threads of the filter

> target now becomes a call to find_thread_ptid, which is quite efficient

> now thanks to inferior::ptid_thread_map.

> 

> gdb/ChangeLog:

> 

> 	* thread-iter.h (class all_matching_threads_iterator)

> 	<all_matching_threads_iterator>: Use default.

> 	<enum class mode>: New.

> 	<m_inf, m_thr>: Initialize.

> 	<m_filter_ptid>: Remove.

> 	* thread-iter.c (all_matching_threads_iterator::m_inf_matches):

> 	Don't filter on m_filter_ptid.

> 	(all_matching_threads_iterator::all_matching_threads_iterator):

> 	Choose path based on filter_ptid (all threads, all threads of

> 	inferior, single thread).

> 	(all_matching_threads_iterator::advance): Likewise.


OK.
Tom de Vries July 14, 2021, 9:40 a.m. | #2
On 7/5/21 5:52 PM, Pedro Alves wrote:
> On 2021-06-22 5:57 p.m., Simon Marchi via Gdb-patches wrote:

>> all_matching_threads_iterator is used extensively in some pretty fast

>> paths, often under the all_non_exited_threads function.

>>

>> If a filter target and thread-specific ptid are given, it iterates on

>> all threads of all inferiors of that target, to ultimately yield exactly

>> on thread.  And this happens quite often, which means we unnecessarily

>> spend time iterating on threads to find the one we are looking for.  The

>> same thing happens if an inferior-specific ptid is given, although there

>> the iterator yields all the threads of that inferior.

>>

>> In those cases, the callers of all_non_exited_threads could have

>> different behaviors depending on the kind of ptid, to avoid this

>> inefficiency, but that would be very tedious.  Using

>> all_non_exited_threads has the advantage that one simple implementation

>> can work seamlessly on multiple threads or on one specific thread, just

>> by playing with the ptid.

>>

>> Instead, optimize all_matching_threads_iterator directly to detect these

>> different cases and limiting what we iterate on to just what we need.

>>

>>  - if filter_ptid is minus_one_ptid, do as we do now: filter inferiors

>>    based on filter_target, iterate on all of the matching inferiors'

>>    threads

>>  - if filter_ptid is a pid-only ptid (then a filter_target must

>>    necessarily be given), look up that inferior and iterate on all its

>>    threads

>>  - otherwise, filter_ptid is a thread-specific ptid, so look up that

>>    specific thread and "iterate" only on it

>>

>> For the last case, what was an iteration on all threads of the filter

>> target now becomes a call to find_thread_ptid, which is quite efficient

>> now thanks to inferior::ptid_thread_map.

>>

>> gdb/ChangeLog:

>>

>> 	* thread-iter.h (class all_matching_threads_iterator)

>> 	<all_matching_threads_iterator>: Use default.

>> 	<enum class mode>: New.

>> 	<m_inf, m_thr>: Initialize.

>> 	<m_filter_ptid>: Remove.

>> 	* thread-iter.c (all_matching_threads_iterator::m_inf_matches):

>> 	Don't filter on m_filter_ptid.

>> 	(all_matching_threads_iterator::all_matching_threads_iterator):

>> 	Choose path based on filter_ptid (all threads, all threads of

>> 	inferior, single thread).

>> 	(all_matching_threads_iterator::advance): Likewise.

> 

> OK.

> 


FTR, this caused an internal-error, filed at
https://sourceware.org/bugzilla/show_bug.cgi?id=28086 .

Thanks,
- Tom

Patch

diff --git a/gdb/thread-iter.c b/gdb/thread-iter.c
index 31b7a36eaada..e56ccd857b0a 100644
--- a/gdb/thread-iter.c
+++ b/gdb/thread-iter.c
@@ -75,39 +75,56 @@  all_threads_iterator::advance ()
 bool
 all_matching_threads_iterator::m_inf_matches ()
 {
-  return ((m_filter_target == nullptr
-	   || m_filter_target == m_inf->process_target ())
-	  && (m_filter_ptid == minus_one_ptid
-	      || m_filter_ptid.pid () == m_inf->pid));
+  return (m_filter_target == nullptr
+	  || m_filter_target == m_inf->process_target ());
 }
 
 /* See thread-iter.h.  */
 
 all_matching_threads_iterator::all_matching_threads_iterator
   (process_stratum_target *filter_target, ptid_t filter_ptid)
-    : m_filter_target (filter_target),
-      m_filter_ptid (filter_ptid)
+  : m_filter_target (filter_target)
 {
-  gdb_assert ((filter_target == nullptr && filter_ptid == minus_one_ptid)
-	      || filter_target->stratum () == process_stratum);
-
-  for (inferior &inf : inferior_list)
+  if (filter_ptid == minus_one_ptid)
     {
-      m_inf = &inf;
-      if (m_inf_matches ())
-	for (auto thr_iter = m_inf->thread_list.begin ();
-	     thr_iter != m_inf->thread_list.end ();
-	     ++thr_iter)
-	  {
-	    if (thr_iter->ptid.matches (m_filter_ptid))
-	      {
-		m_thr = &*thr_iter;
-		return;
-	      }
-	  }
+      /* Iterate on all threads of all inferiors, possibly filtering on
+         FILTER_TARGET.  */
+      m_mode = mode::ALL_THREADS;
+
+      /* Seek the first thread of the first matching inferior.  */
+      for (inferior &inf : inferior_list)
+	{
+	  m_inf = &inf;
+
+	  if (!m_inf_matches ()
+	      || inf.thread_list.empty ())
+	    continue;
+
+	  m_thr = &inf.thread_list.front ();
+	  return;
+	}
     }
+  else
+    {
+      gdb_assert (filter_target != nullptr);
 
-  m_thr = nullptr;
+      if (filter_ptid.is_pid ())
+	{
+	  /* Iterate on all threads of the given inferior.  */
+	  m_mode = mode::ALL_THREADS_OF_INFERIOR;
+
+	  m_inf = find_inferior_pid (filter_target, filter_ptid.pid ());
+	  if (m_inf != nullptr)
+	    m_thr = &m_inf->thread_list.front ();
+	}
+      else
+	{
+	  /* Iterate on a single thread.  */
+	  m_mode = mode::SINGLE_THREAD;
+
+	  m_thr = find_thread_ptid (filter_target, filter_ptid);
+	}
+    }
 }
 
 /* See thread-iter.h.  */
@@ -115,32 +132,57 @@  all_matching_threads_iterator::all_matching_threads_iterator
 void
 all_matching_threads_iterator::advance ()
 {
-  intrusive_list<inferior>::iterator inf_iter (m_inf);
-  intrusive_list<thread_info>::iterator thr_iter (m_thr);
+  switch (m_mode)
+    {
+    case mode::ALL_THREADS:
+      {
+	intrusive_list<inferior>::iterator inf_iter (m_inf);
+	intrusive_list<thread_info>::iterator thr_iter
+	  = m_inf->thread_list.iterator_to (*m_thr);
+
+	/* The loop below is written in the natural way as-if we'd always
+	   start at the beginning of the inferior list.  This fast forwards
+	   the algorithm to the actual current position.  */
+	goto start;
+
+	for (; inf_iter != inferior_list.end (); ++inf_iter)
+	  {
+	    m_inf = &*inf_iter;
 
-  /* The loop below is written in the natural way as-if we'd always
-     start at the beginning of the inferior list.  This fast forwards
-     the algorithm to the actual current position.  */
-  goto start;
+	    if (!m_inf_matches ())
+	      continue;
 
-  for (; inf_iter != inferior_list.end (); ++inf_iter)
-    {
-      m_inf = &*inf_iter;
-      if (m_inf_matches ())
-	{
-	  thr_iter = m_inf->thread_list.begin ();
-	  while (thr_iter != m_inf->thread_list.end ())
-	    {
-	      if (thr_iter->ptid.matches (m_filter_ptid))
-		{
-		  m_thr = &*thr_iter;
-		  return;
-		}
-	    start:
-	      ++thr_iter;
-	    }
-	}
-    }
+	    thr_iter = m_inf->thread_list.begin ();
+	    while (thr_iter != m_inf->thread_list.end ())
+	      {
+		m_thr = &*thr_iter;
+		return;
 
-  m_thr = nullptr;
+	      start:
+		++thr_iter;
+	      }
+	  }
+      }
+      m_thr = nullptr;
+      break;
+
+    case mode::ALL_THREADS_OF_INFERIOR:
+      {
+	intrusive_list<thread_info>::iterator thr_iter
+	  = m_inf->thread_list.iterator_to (*m_thr);
+	++thr_iter;
+	if (thr_iter != m_inf->thread_list.end ())
+	  m_thr = &*thr_iter;
+	else
+	  m_thr = nullptr;
+	break;
+      }
+
+    case mode::SINGLE_THREAD:
+      m_thr = nullptr;
+      break;
+
+    default:
+      gdb_assert_not_reached ("invalid mode value");
+    }
 }
diff --git a/gdb/thread-iter.h b/gdb/thread-iter.h
index 2e43034550e8..6700f5593b91 100644
--- a/gdb/thread-iter.h
+++ b/gdb/thread-iter.h
@@ -99,12 +99,7 @@  class all_matching_threads_iterator
 				 ptid_t filter_ptid);
 
   /* Create a one-past-end iterator.  */
-  all_matching_threads_iterator ()
-    : m_inf (nullptr),
-      m_thr (nullptr),
-      m_filter_target (nullptr),
-      m_filter_ptid (minus_one_ptid)
-  {}
+  all_matching_threads_iterator () = default;
 
   thread_info *operator* () const { return m_thr; }
 
@@ -124,20 +119,30 @@  class all_matching_threads_iterator
   /* Advance to next thread, skipping filtered threads.  */
   void advance ();
 
-  /* True if M_INF matches the process identified by
-     M_FILTER_PTID.  */
+  /* True if M_INF has the process target M_FILTER_TARGET.  */
   bool m_inf_matches ();
 
 private:
+  enum class mode
+  {
+    /* All threads, possibly filtered down to a single target.  */
+    ALL_THREADS,
+
+    /* All threads of the given inferior.  */
+    ALL_THREADS_OF_INFERIOR,
+
+    /* A specific thread.  */
+    SINGLE_THREAD,
+  } m_mode;
+
   /* The current inferior.  */
-  inferior *m_inf;
+  inferior *m_inf = nullptr;
 
   /* The current thread.  */
-  thread_info *m_thr;
+  thread_info *m_thr = nullptr;
 
-  /* The filter.  */
+  /* The target we filter on (may be nullptr).  */
   process_stratum_target *m_filter_target;
-  ptid_t m_filter_ptid;
 };
 
 /* Filter for filtered_iterator.  Filters out exited threads.  */