gdb: change regcache list to be a map

One regcache object is created for each stopped thread and is stored in
the regcache::regcaches linked list.  Looking up a regcache for a given
thread is therefore in O(number of threads).  Stopping all threads then
becomes O((number of threads) ^ 2).  Same goes for resuming a thread
(need to delete the regcache of a given ptid) and resuming all threads.
It becomes noticeable when debugging thousands of threads, which is
typical with GPU targets.  This patch replaces the linked list with some
maps to reduce that complexity.

The first design was using an std::unordered_map with (target, ptid,
arch) as the key, because that's how lookups are done (in
get_thread_arch_aspace_regcache).  However, the registers_changed_ptid
function, also somewhat on the hot path (it is used when resuming
threads), needs to delete all regcaches associated to a given (target,
ptid) tuple.  If the key of the map is (target, ptid, arch), we have to
walk all items of the map, not good.

The second design was therefore using an std::unordered_multimap with
(target, ptid) as the key.  One key could be associated to multiple
regcaches, all with different gdbarches.  When looking up, we would have
to walk all these regcaches.  This would be ok, because there will
usually be actually one matching regcache.  In the exceptional
multi-arch thread cases, there will be maybe two.  However, in
registers_changed_ptid, we sometimes need to remove all regcaches
matching a given target.  We would then have to talk all items of the
map again, not good.

The design as implemented in this patch therefore uses two levels of
map.  One std::unordered_map uses the target as the key.  The value type
is an std::unordered_multimap that itself uses the ptid as the key.  The
values of the multimap are the regcaches themselves.  Again, we expect
to have one or very few regcaches per (target, ptid).

So, in summary:

* The lookups (in get_thread_arch_aspace_regcache), become faster when
  the number of threads grows, compared to the linked list.  With a
  small number of threads, it will probably be a bit slower to do map
  lookups than to walk a few linked list nodes, but I don't think it
  will be noticeable in practice.

* The function registers_changed_ptid deletes all regcaches related to a
  given (target, ptid).  It must now handle the different cases separately:

    - NULL target and minus_one_ptid: we delete all the entries
    - NULL target and non-minus_one_ptid: invalid (checked by assert)
    - non-NULL target and non-minus_one_ptid: we delete all the entries
      associated to that tuple
    - a non-NULL target and minus_one_ptid: we delete all the entries
      associated to that target

* The function regcache_thread_ptid_changed is called when a thread
  changes ptid.  It is implemented efficiently using the map, although
  that's not very important: it is not called often, mostly when
  creating an inferior, on some specific platforms.

This patch is a tiny bit from ROCm GDB [1] we would like to merge
upstream.  Laurent Morichetti gave be these performance numbers:

The benchmark used is:

  time ./gdb --data-directory=data-directory /extra/lmoriche/hip/samples/0_Intro/bit_extract/bit_extract -ex "set pagination off" -ex "set breakpoint pending on" -ex "b bit_extract_kernel if \$_thread == 5" -ex run -ex c -batch

It measures the time it takes to continue from a conditional breakpoint with
2048 threads at that breakpoint, one of them reporting the breakpoint.

baseline:
real    0m10.227s
real    0m10.177s
real    0m10.362s

with patch:
real    0m8.356s
real    0m8.424s
real    0m8.494s

[1] https://github.com/ROCm-Developer-Tools/ROCgdb

gdb/ChangeLog:

	* regcache.c (ptid_regcache_map): New type.
	(target_ptid_regcache_map): New type.
	(regcaches): Change type to target_ptid_regcache_map.
	(get_thread_arch_aspace_regcache): Update to regcaches' new
	type.
	(regcache_thread_ptid_changed): Likewise.
	(registers_changed_ptid): Likewise.
	(regcaches_size): Likewise.
	(regcaches_test): Update.
	(regcache_thread_ptid_changed): Update.
	* regcache.h (regcache_up): New type.
	* gdbsupport/ptid.h (hash_ptid): New struct.

Change-Id: Iabb0a1111707936ca111ddb13f3b09efa83d3402

1 files changed, 16 insertions, 0 deletions

diff --git a/gdbsupport/ptid.h b/gdbsupport/ptid.h
index ef52d55..a528312 100644
--- a/gdbsupport/ptid.h
+++ b/gdbsupport/ptid.h
@@ -32,6 +32,8 @@
    thread_stratum target that might want to sit on top.
 */
 
+#include <functional>
+
 class ptid_t
 {
 public:
@@ -143,6 +145,20 @@ private:
   long m_tid;
 };
 
+/* Functor to hash a ptid.  */
+
+struct hash_ptid
+{
+  size_t operator() (const ptid_t &ptid) const
+  {
+    std::hash<long> long_hash;
+
+    return (long_hash (ptid.pid ())
+	    + long_hash (ptid.lwp ())
+	    + long_hash (ptid.tid ()));
+  }
+};
+
 /* The null or zero ptid, often used to indicate no process. */
 
 extern const ptid_t null_ptid;