diff --git a/gdb/completer.c b/gdb/completer.c
index 6658da6d7fb..93df1018f66 100644
--- a/gdb/completer.c
+++ b/gdb/completer.c
@@ -407,9 +407,10 @@ advance_to_filename_complete_word_point (completion_tracker &tracker,
 bool
 completion_tracker::completes_to_completion_word (const char *word)
 {
+  recompute_lowest_common_denominator ();
   if (m_lowest_common_denominator_unique)
     {
-      const char *lcd = m_lowest_common_denominator;
+      const char *lcd = m_lowest_common_denominator.get ();
 
       if (strncmp_iw (word, lcd, strlen (lcd)) == 0)
 	{
@@ -1512,9 +1513,7 @@ int max_completions = 200;
 
 completion_tracker::completion_tracker ()
 {
-  m_entries_hash = htab_create_alloc (INITIAL_COMPLETION_HTAB_SIZE,
-				      htab_hash_string, streq_hash,
-				      NULL, xcalloc, xfree);
+  /* Nothing.  */
 }
 
 /* See completer.h.  */
@@ -1522,25 +1521,23 @@ completion_tracker::completion_tracker ()
 void
 completion_tracker::discard_completions ()
 {
-  xfree (m_lowest_common_denominator);
   m_lowest_common_denominator = NULL;
-
   m_lowest_common_denominator_unique = false;
+  m_lowest_common_denominator_valid = false;
 
-  m_entries_vec.clear ();
-
-  htab_delete (m_entries_hash);
-  m_entries_hash = htab_create_alloc (INITIAL_COMPLETION_HTAB_SIZE,
-				      htab_hash_string, streq_hash,
-				      NULL, xcalloc, xfree);
+  for (const auto &p : m_entries_hash)
+    {
+      xfree ((char *) p.first);
+      xfree ((char *) p.second);
+    }
+  m_entries_hash.clear ();
 }
 
 /* See completer.h.  */
 
 completion_tracker::~completion_tracker ()
 {
-  xfree (m_lowest_common_denominator);
-  htab_delete (m_entries_hash);
+  discard_completions ();
 }
 
 /* See completer.h.  */
@@ -1551,17 +1548,15 @@ completion_tracker::maybe_add_completion
    completion_match_for_lcd *match_for_lcd,
    const char *text, const char *word)
 {
-  void **slot;
-
   if (max_completions == 0)
     return false;
 
-  if (htab_elements (m_entries_hash) >= max_completions)
+  if (m_entries_hash.size () >= max_completions)
     return false;
 
-  slot = htab_find_slot (m_entries_hash, name.get (), INSERT);
-  if (*slot == HTAB_EMPTY_ENTRY)
+  if (m_entries_hash.find (name.get ()) == m_entries_hash.end ())
     {
+      /* Not already in the hash.  Add it.  */
       const char *match_for_lcd_str = NULL;
 
       if (match_for_lcd != NULL)
@@ -1573,10 +1568,13 @@ completion_tracker::maybe_add_completion
       gdb::unique_xmalloc_ptr<char> lcd
 	= make_completion_match_str (match_for_lcd_str, text, word);
 
-      recompute_lowest_common_denominator (std::move (lcd));
+      size_t lcd_len = strlen (lcd.get ());
+      auto p = std::make_pair (name.release (), lcd.release ());
+      m_entries_hash.insert (std::move (p));
 
-      *slot = name.get ();
-      m_entries_vec.push_back (std::move (name));
+      m_lowest_common_denominator_valid = false;
+      m_lowest_common_denominator_max_length
+	= std::max (m_lowest_common_denominator_max_length, lcd_len);
     }
 
   return true;
@@ -1982,35 +1980,47 @@ completion_find_completion_word (completion_tracker &tracker, const char *text,
 /* See completer.h.  */
 
 void
-completion_tracker::recompute_lowest_common_denominator
-  (gdb::unique_xmalloc_ptr<char> &&new_match_up)
+completion_tracker::recompute_lowest_common_denominator ()
 {
-  if (m_lowest_common_denominator == NULL)
-    {
-      /* We don't have a lowest common denominator yet, so simply take
-	 the whole NEW_MATCH_UP as being it.  */
-      m_lowest_common_denominator = new_match_up.release ();
-      m_lowest_common_denominator_unique = true;
-    }
-  else
-    {
-      /* Find the common denominator between the currently-known
-	 lowest common denominator and NEW_MATCH_UP.  That becomes the
-	 new lowest common denominator.  */
-      size_t i;
-      const char *new_match = new_match_up.get ();
+  /* We've already done this.  */
+  if (m_lowest_common_denominator_valid)
+    return;
 
-      for (i = 0;
-	   (new_match[i] != '\0'
-	    && new_match[i] == m_lowest_common_denominator[i]);
-	   i++)
-	;
-      if (m_lowest_common_denominator[i] != new_match[i])
+  /* Resize the storage to ensure we have enough space, the plus one gives
+     us space for the trailing null terminator we will include.  */
+  char *tmp = (char *) xrealloc (m_lowest_common_denominator.release (),
+				 m_lowest_common_denominator_max_length + 1);
+  m_lowest_common_denominator.reset (tmp);
+
+  for (const auto &p : m_entries_hash)
+    {
+      if (!m_lowest_common_denominator_valid)
+	{
+	  strcpy (m_lowest_common_denominator.get (), p.second);
+	  m_lowest_common_denominator_unique = true;
+	  m_lowest_common_denominator_valid = true;
+	}
+      else
 	{
-	  m_lowest_common_denominator[i] = '\0';
-	  m_lowest_common_denominator_unique = false;
+	  /* Find the common denominator between the currently-known
+	     lowest common denominator and NEW_MATCH_UP.  That becomes the
+	     new lowest common denominator.  */
+	  size_t i;
+	  const char *new_match = p.second;
+
+	  for (i = 0;
+	       (new_match[i] != '\0'
+		&& new_match[i] == m_lowest_common_denominator.get ()[i]);
+	       i++)
+	    ;
+	  if (m_lowest_common_denominator.get ()[i] != new_match[i])
+	    {
+	      m_lowest_common_denominator.get ()[i] = '\0';
+	      m_lowest_common_denominator_unique = false;
+	    }
 	}
     }
+  m_lowest_common_denominator_valid = true;
 }
 
 /* See completer.h.  */
@@ -2092,19 +2102,17 @@ completion_result
 completion_tracker::build_completion_result (const char *text,
 					     int start, int end)
 {
-  completion_list &list = m_entries_vec;	/* The completions.  */
-
-  if (list.empty ())
+  if (m_entries_hash.empty ())
     return {};
 
   /* +1 for the LCD, and +1 for NULL termination.  */
-  char **match_list = XNEWVEC (char *, 1 + list.size () + 1);
+  char **match_list = XNEWVEC (char *, 1 + m_entries_hash.size () + 1);
 
   /* Build replacement word, based on the LCD.  */
-
+  recompute_lowest_common_denominator ();
   match_list[0]
     = expand_preserving_ws (text, end - start,
-			    m_lowest_common_denominator);
+			    m_lowest_common_denominator.get ());
 
   if (m_lowest_common_denominator_unique)
     {
@@ -2128,13 +2136,22 @@ completion_tracker::build_completion_result (const char *text,
     }
   else
     {
-      int ix;
+      int ix = 0;
 
-      for (ix = 0; ix < list.size (); ++ix)
-	match_list[ix + 1] = list[ix].release ();
+      for (const auto &ptr : m_entries_hash)
+	{
+	  match_list[ix + 1] = (char *) ptr.first;
+	  xfree ((char *) ptr.second);
+	  ix++;
+	}
       match_list[ix + 1] = NULL;
 
-      return completion_result (match_list, list.size (), false);
+      /* We must clear the hash here as ownership of all the entries is
+	 being passed over to readline, and we don't want to try and free
+	 these pointers when we ourselves are destroyed.  */
+      size_t hash_size = m_entries_hash.size ();
+      m_entries_hash.clear ();
+      return completion_result (match_list, hash_size, false);
     }
 }
 
diff --git a/gdb/completer.h b/gdb/completer.h
index 313010fce22..fd4aba79746 100644
--- a/gdb/completer.h
+++ b/gdb/completer.h
@@ -20,6 +20,8 @@
 #include "gdbsupport/gdb_vecs.h"
 #include "command.h"
 
+#include <unordered_map>
+
 /* Types of functions in struct match_list_displayer.  */
 
 struct match_list_displayer;
@@ -389,7 +391,7 @@ public:
 
   /* True if we have any completion match recorded.  */
   bool have_completions () const
-  { return !m_entries_vec.empty (); }
+  { return !m_entries_hash.empty (); }
 
   /* Discard the current completion match list and the current
      LCD.  */
@@ -403,6 +405,15 @@ public:
 
 private:
 
+  /* A map of completions.  The key is the completion, and the value is the
+     string to be used to compute the lowest common denominator.  Both the
+     key and the value are owned by the completion_tracker class while
+     being held in this map, as such completion_tracker must free these
+     strings when finished with them, or pass ownership to someone else who
+     will free them.  */
+  typedef std::unordered_map<const char *, const char *, std::hash<std::string>,
+			     std::equal_to<std::string>> completion_set;
+
   /* Add the completion NAME to the list of generated completions if
      it is not there already.  If false is returned, too many
      completions were found.  */
@@ -410,18 +421,11 @@ private:
 			     completion_match_for_lcd *match_for_lcd,
 			     const char *text, const char *word);
 
-  /* Given a new match, recompute the lowest common denominator (LCD)
-     to hand over to readline.  Normally readline computes this itself
-     based on the whole set of completion matches.  However, some
-     completers want to override readline, in order to be able to
-     provide a LCD that is not really a prefix of the matches, but the
-     lowest common denominator of some relevant substring of each
-     match.  E.g., "b push_ba" completes to
-     "std::vector<..>::push_back", "std::string::push_back", etc., and
-     in this case we want the lowest common denominator to be
-     "push_back" instead of "std::".  */
-  void recompute_lowest_common_denominator
-    (gdb::unique_xmalloc_ptr<char> &&new_match);
+  /* Ensure that the lowest common denominator held in the member variable
+     M_LOWEST_COMMON_DENOMINATOR is valid.  This method must be called if
+     there is any chance that new completions have been added to the
+     tracker before the lowest common denominator is read.  */
+  void recompute_lowest_common_denominator ();
 
   /* Completion match outputs returned by the symbol name matching
      routines (see symbol_name_matcher_ftype).  These results are only
@@ -430,16 +434,13 @@ private:
      symbol name matching routines.  */
   completion_match_result m_completion_match_result;
 
-  /* The completion matches found so far, in a vector.  */
-  completion_list m_entries_vec;
-
   /* The completion matches found so far, in a hash table, for
      duplicate elimination as entries are added.  Otherwise the user
      is left scratching his/her head: readline and complete_command
      will remove duplicates, and if removal of duplicates there brings
      the total under max_completions the user may think gdb quit
      searching too early.  */
-  htab_t m_entries_hash;
+  completion_set m_entries_hash;
 
   /* If non-zero, then this is the quote char that needs to be
      appended after completion (iff we have a unique completion).  We
@@ -472,8 +473,16 @@ private:
   bool m_suppress_append_ws = false;
 
   /* Our idea of lowest common denominator to hand over to readline.
-     See intro.  */
-  char *m_lowest_common_denominator = NULL;
+     Normally readline computes this itself based on the whole set of
+     completion matches.  However, some completers want to override
+     readline, in order to be able to provide a LCD that is not really a
+     prefix of the matches, but the lowest common denominator of some
+     relevant substring of each match.
+
+     E.g., "b push_ba" completes to "std::vector<..>::push_back",
+     "std::string::push_back", etc., and in this case we want the lowest
+     common denominator to be "push_back" instead of "std::".  */
+  gdb::unique_xmalloc_ptr<char> m_lowest_common_denominator = nullptr;
 
   /* If true, the LCD is unique.  I.e., all completions had the same
      MATCH_FOR_LCD substring, even if the completions were different.
@@ -483,6 +492,17 @@ private:
      "function()", instead of showing all the possible
      completions.  */
   bool m_lowest_common_denominator_unique = false;
+
+  /* True if the value in M_LOWEST_COMMON_DENOMINATOR is correct.  This is
+     set to true each time RECOMPUTE_LOWEST_COMMON_DENOMINATOR is called,
+     and reset to false whenever a new completion is added.  */
+  bool m_lowest_common_denominator_valid = false;
+
+  /* We can avoid multiple calls to xrealloc in
+     RECOMPUTE_LOWEST_COMMON_DENOMINATOR, we track the maximum possible
+     size of lowest common denominator, which we know as each completion is
+     added.  */
+  size_t m_lowest_common_denominator_max_length = 0;
 };
 
 /* Return a string to hand off to readline as a completion match
