Demangle minsyms in parallel

This patch introduces a simple parallel for_each and changes the
minimal symbol reader to use it when computing the demangled name for
a minimal symbol.  This yields a speedup when reading minimal symbols.

2019-11-26  Christian Biesinger  <cbiesinger@google.com>
	    Tom Tromey  <tom@tromey.com>

	* minsyms.c (minimal_symbol_reader::install): Use
	parallel_for_each.
	* gdbsupport/parallel-for.h: New file.
	* Makefile.in (HFILES_NO_SRCDIR): Add gdbsupport/parallel-for.h.

Change-Id: I220341f70e94dd02df5dd424272c50a5afb64978

6 files changed, 158 insertions, 18 deletions

diff --git a/gdb/ChangeLog b/gdb/ChangeLog
index 7c4e2b8..b73ae8d 100644
--- a/gdb/ChangeLog
+++ b/gdb/ChangeLog
@@ -1,6 +1,14 @@
 2019-11-26  Christian Biesinger  <cbiesinger@google.com>
 	    Tom Tromey  <tom@tromey.com>
 
+	* minsyms.c (minimal_symbol_reader::install): Use
+	parallel_for_each.
+	* gdbsupport/parallel-for.h: New file.
+	* Makefile.in (HFILES_NO_SRCDIR): Add gdbsupport/parallel-for.h.
+
+2019-11-26  Christian Biesinger  <cbiesinger@google.com>
+	    Tom Tromey  <tom@tromey.com>
+
 	* gdbsupport/thread-pool.h: New file.
 	* gdbsupport/thread-pool.c: New file.
 	* Makefile.in (COMMON_SFILES): Add thread-pool.c.
diff --git a/gdb/Makefile.in b/gdb/Makefile.in
index b07b11e..58f5f93 100644
--- a/gdb/Makefile.in
+++ b/gdb/Makefile.in
@@ -1491,6 +1491,7 @@ HFILES_NO_SRCDIR = \
 	gdbsupport/common-inferior.h \
 	gdbsupport/netstuff.h \
 	gdbsupport/host-defs.h \
+	gdbsupport/parallel-for.h \
 	gdbsupport/pathstuff.h \
 	gdbsupport/print-utils.h \
 	gdbsupport/ptid.h \
diff --git a/gdb/gdbsupport/parallel-for.h b/gdb/gdbsupport/parallel-for.h
new file mode 100644
index 0000000..70fdacd
--- /dev/null
+++ b/gdb/gdbsupport/parallel-for.h
@@ -0,0 +1,86 @@
+/* Parallel for loops
+
+   Copyright (C) 2019 Free Software Foundation, Inc.
+
+   This file is part of GDB.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 3 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
+
+#ifndef GDBSUPPORT_PARALLEL_FOR_H
+#define GDBSUPPORT_PARALLEL_FOR_H
+
+#include <algorithm>
+#if CXX_STD_THREAD
+#include <thread>
+#include "gdbsupport/thread-pool.h"
+#endif
+
+namespace gdb
+{
+
+/* A very simple "parallel for".  This splits the range of iterators
+   into subranges, and then passes each subrange to the callback.  The
+   work may or may not be done in separate threads.
+
+   This approach was chosen over having the callback work on single
+   items because it makes it simple for the caller to do
+   once-per-subrange initialization and destruction.  */
+
+template<class RandomIt, class RangeFunction>
+void
+parallel_for_each (RandomIt first, RandomIt last, RangeFunction callback)
+{
+#if CXX_STD_THREAD
+  /* So we can use a local array below.  */
+  const size_t local_max = 16;
+  size_t n_threads = std::min (thread_pool::g_thread_pool->thread_count (),
+			       local_max);
+  size_t n_actual_threads = 0;
+  std::future<void> futures[local_max];
+
+  size_t n_elements = last - first;
+  if (n_threads > 1)
+    {
+      /* Arbitrarily require that there should be at least 10 elements
+	 in a thread.  */
+      if (n_elements / n_threads < 10)
+	n_threads = std::max (n_elements / 10, (size_t) 1);
+      size_t elts_per_thread = n_elements / n_threads;
+      n_actual_threads = n_threads - 1;
+      for (int i = 0; i < n_actual_threads; ++i)
+	{
+	  RandomIt end = first + elts_per_thread;
+	  auto task = [=] ()
+		      {
+			callback (first, end);
+		      };
+
+	  futures[i] = gdb::thread_pool::g_thread_pool->post_task (task);
+	  first = end;
+	}
+    }
+#endif /* CXX_STD_THREAD */
+
+  /* Process all the remaining elements in the main thread.  */
+  callback (first, last);
+
+#if CXX_STD_THREAD
+  for (int i = 0; i < n_actual_threads; ++i)
+    futures[i].wait ();
+#endif /* CXX_STD_THREAD */
+}
+
+}
+
+#endif /* GDBSUPPORT_PARALLEL_FOR_H */
diff --git a/gdb/minsyms.c b/gdb/minsyms.c
index 6e7021a..03a1932 100644
--- a/gdb/minsyms.c
+++ b/gdb/minsyms.c
@@ -53,6 +53,11 @@
 #include "gdbsupport/symbol.h"
 #include <algorithm>
 #include "safe-ctype.h"
+#include "gdbsupport/parallel-for.h"
+
+#if CXX_STD_THREAD
+#include <mutex>
+#endif
 
 /* See minsyms.h.  */
 
@@ -1359,16 +1364,43 @@ minimal_symbol_reader::install ()
       m_objfile->per_bfd->minimal_symbol_count = mcount;
       m_objfile->per_bfd->msymbols = std::move (msym_holder);
 
+#if CXX_STD_THREAD
+      /* Mutex that is used when modifying or accessing the demangled
+	 hash table.  */
+      std::mutex demangled_mutex;
+#endif
+
       msymbols = m_objfile->per_bfd->msymbols.get ();
-      for (int i = 0; i < mcount; ++i)
-	{
-	  if (!msymbols[i].name_set)
-	    {
-	      symbol_set_names (&msymbols[i], msymbols[i].name,
-				false, m_objfile->per_bfd);
-	      msymbols[i].name_set = 1;
-	    }
-	}
+      gdb::parallel_for_each
+	(&msymbols[0], &msymbols[mcount],
+	 [&] (minimal_symbol *start, minimal_symbol *end)
+	 {
+	   for (minimal_symbol *msym = start; msym < end; ++msym)
+	     {
+	       if (!msym->name_set)
+		 {
+		   /* This will be freed later, by symbol_set_names.  */
+		   char *demangled_name
+		     = symbol_find_demangled_name (msym, msym->name);
+		   symbol_set_demangled_name
+		     (msym, demangled_name,
+		      &m_objfile->per_bfd->storage_obstack);
+		   msym->name_set = 1;
+		 }
+	     }
+	   {
+	     /* To limit how long we hold the lock, we only acquire it here
+	        and not while we demangle the names above.  */
+#if CXX_STD_THREAD
+	     std::lock_guard<std::mutex> guard (demangled_mutex);
+#endif
+	     for (minimal_symbol *msym = start; msym < end; ++msym)
+	       {
+		 symbol_set_names (msym, msym->name, false,
+				   m_objfile->per_bfd);
+	       }
+	   }
+	 });
 
       build_minimal_symbol_hash_tables (m_objfile);
     }
diff --git a/gdb/symtab.c b/gdb/symtab.c
index 711f8ef..b5c8109 100644
--- a/gdb/symtab.c
+++ b/gdb/symtab.c
@@ -787,13 +787,9 @@ create_demangled_names_hash (struct objfile_per_bfd_storage *per_bfd)
      free_demangled_name_entry, xcalloc, xfree));
 }
 
-/* Try to determine the demangled name for a symbol, based on the
-   language of that symbol.  If the language is set to language_auto,
-   it will attempt to find any demangling algorithm that works and
-   then set the language appropriately.  The returned name is allocated
-   by the demangler and should be xfree'd.  */
+/* See symtab.h  */
 
-static char *
+char *
 symbol_find_demangled_name (struct general_symbol_info *gsymbol,
 			    const char *mangled)
 {
@@ -894,8 +890,15 @@ symbol_set_names (struct general_symbol_info *gsymbol,
       else
 	linkage_name_copy = linkage_name;
 
-      gdb::unique_xmalloc_ptr<char> demangled_name_ptr
-	(symbol_find_demangled_name (gsymbol, linkage_name_copy.data ()));
+      /* The const_cast is safe because the only reason it is already
+         initialized is if we purposefully set it from a background
+         thread to avoid doing the work here.  However, it is still
+         allocated from the heap and needs to be freed by us, just
+         like if we called symbol_find_demangled_name here.  */
+      gdb::unique_xmalloc_ptr<char> demangled_name
+	(gsymbol->language_specific.demangled_name
+	 ? const_cast<char *> (gsymbol->language_specific.demangled_name)
+	 : symbol_find_demangled_name (gsymbol, linkage_name_copy.data ()));
 
       /* Suppose we have demangled_name==NULL, copy_name==0, and
 	 linkage_name_copy==linkage_name.  In this case, we already have the
@@ -929,7 +932,7 @@ symbol_set_names (struct general_symbol_info *gsymbol,
 	  new (*slot) demangled_name_entry
 	    (gdb::string_view (mangled_ptr, linkage_name.length ()));
 	}
-      (*slot)->demangled = std::move (demangled_name_ptr);
+      (*slot)->demangled = std::move (demangled_name);
       (*slot)->language = gsymbol->language;
     }
   else if (gsymbol->language == language_unknown
diff --git a/gdb/symtab.h b/gdb/symtab.h
index bcbc9c8..9c2aea7 100644
--- a/gdb/symtab.h
+++ b/gdb/symtab.h
@@ -528,6 +528,16 @@ extern void symbol_set_language (struct general_symbol_info *symbol,
                                  enum language language,
 				 struct obstack *obstack);
 
+
+/* Try to determine the demangled name for a symbol, based on the
+   language of that symbol.  If the language is set to language_auto,
+   it will attempt to find any demangling algorithm that works and
+   then set the language appropriately.  The returned name is allocated
+   by the demangler and should be xfree'd.  */
+
+extern char *symbol_find_demangled_name (struct general_symbol_info *gsymbol,
+					 const char *mangled);
+
 /* Set just the linkage name of a symbol; do not try to demangle
    it.  Used for constructs which do not have a mangled name,
    e.g. struct tags.  Unlike SYMBOL_SET_NAMES, linkage_name must