From Craig Silverstein: size hash tables to avoid resizing.

7 files changed, 81 insertions, 11 deletions

diff --git a/gold/layout.cc b/gold/layout.cc
index 26585fa..1cea1a6 100644
--- a/gold/layout.cc
+++ b/gold/layout.cc
@@ -1154,6 +1154,25 @@ Layout::set_section_indexes(unsigned int shndx)
 void
 Layout::count_local_symbols(const Input_objects* input_objects)
 {
+  // First, figure out an upper bound on the number of symbols we'll
+  // be inserting into each pool.  This helps us create the pools with
+  // the right size, to avoid unnecessary hashtable resizing.
+  unsigned int symbol_count = 0;
+  for (Input_objects::Relobj_iterator p = input_objects->relobj_begin();
+       p != input_objects->relobj_end();
+       ++p)
+    symbol_count += (*p)->local_symbol_count();
+
+  // Go from "upper bound" to "estimate."  We overcount for two
+  // reasons: we double-count symbols that occur in more than one
+  // object file, and we count symbols that are dropped from the
+  // output.  Add it all together and assume we overcount by 100%.
+  symbol_count /= 2;
+
+  // We assume all symbols will go into both the sympool and dynpool.
+  this->sympool_.reserve(symbol_count);
+  this->dynpool_.reserve(symbol_count);
+
   for (Input_objects::Relobj_iterator p = input_objects->relobj_begin();
        p != input_objects->relobj_end();
        ++p)
diff --git a/gold/main.cc b/gold/main.cc
index 921d148..c7c2d95 100644
--- a/gold/main.cc
+++ b/gold/main.cc
@@ -75,8 +75,11 @@ main(int argc, char** argv)
   // The list of input objects.
   Input_objects input_objects;
 
-  // The symbol table.
-  Symbol_table symtab;
+  // The symbol table.  We're going to guess here how many symbols
+  // we're going to see based on the number of input files.  Even when
+  // this is off, it means at worse we don't quite optimize hashtable
+  // resizing as well as we could have (perhap using more memory).
+  Symbol_table symtab(command_line.number_of_input_files() * 1024);
 
   // The layout object.
   Layout layout(command_line.options());
diff --git a/gold/object.h b/gold/object.h
index 5faa911..a98e756 100644
--- a/gold/object.h
+++ b/gold/object.h
@@ -429,6 +429,11 @@ class Relobj : public Object
 	      Layout* layout, Read_relocs_data* rd)
   { return this->do_scan_relocs(options, symtab, layout, rd); }
 
+  // The number of local symbols in the input symbol table.
+  virtual unsigned int
+  local_symbol_count() const
+  { return this->do_local_symbol_count(); }
+
   // Initial local symbol processing: count the number of local symbols
   // in the output symbol table and dynamic symbol table; add local symbol
   // names to *POOL and *DYNPOOL.
@@ -538,6 +543,10 @@ class Relobj : public Object
   do_scan_relocs(const General_options&, Symbol_table*, Layout*,
 		 Read_relocs_data*) = 0;
 
+  // Return the number of local symbols--implemented by child class.
+  virtual unsigned int
+  do_local_symbol_count() const = 0;
+
   // Count local symbols--implemented by child class.
   virtual void
   do_count_local_symbols(Stringpool_template<char>*,
@@ -791,11 +800,6 @@ class Sized_relobj : public Relobj
   void
   setup(const typename elfcpp::Ehdr<size, big_endian>&);
 
-  // Return the number of local symbols.
-  unsigned int
-  local_symbol_count() const
-  { return this->local_symbol_count_; }
-
   // If SYM is the index of a global symbol in the object file's
   // symbol table, return the Symbol object.  Otherwise, return NULL.
   Symbol*
@@ -964,10 +968,16 @@ class Sized_relobj : public Relobj
   get_symbol_location_info(unsigned int shndx, off_t offset,
 			   Symbol_location_info* info);
 
+ protected:
   // Read the symbols.
   void
   do_read_symbols(Read_symbols_data*);
 
+  // Return the number of local symbols.
+  unsigned int
+  do_local_symbol_count() const
+  { return this->local_symbol_count_; }
+
   // Lay out the input sections.
   void
   do_layout(Symbol_table*, Layout*, Read_symbols_data*);
diff --git a/gold/stringpool.cc b/gold/stringpool.cc
index 0ac1dcb..7bf8365 100644
--- a/gold/stringpool.cc
+++ b/gold/stringpool.cc
@@ -58,6 +58,30 @@ Stringpool_template<Stringpool_char>::~Stringpool_template()
   this->clear();
 }
 
+// Resize the internal hashtable with the expectation we'll get n new
+// elements.  Note that the hashtable constructor takes a "number of
+// buckets you'd like," rather than "number of elements you'd like,"
+// but that's the best we can do.
+
+template<typename Stringpool_char>
+void
+Stringpool_template<Stringpool_char>::reserve(unsigned int n)
+{
+#if defined(HAVE_TR1_UNORDERED_MAP)
+  // rehash() implementation is broken in gcc 4.0.3's stl
+  //this->string_set_.rehash(this->string_set_.size() + n);
+  //return;
+#elif defined(HAVE_EXT_HASH_MAP)
+  this->string_set_.resize(this->string_set_.size() + n);
+  return;
+#endif
+
+  // This is the generic "reserve" code, if no #ifdef above triggers.
+  String_set_type new_string_set(this->string_set_.size() + n);
+  new_string_set.insert(this->string_set_.begin(), this->string_set_.end());
+  this->string_set_.swap(new_string_set);
+}
+
 // Return the length of a string of arbitrary character type.
 
 template<typename Stringpool_char>
@@ -212,7 +236,11 @@ Stringpool_template<Stringpool_char>::add_string(const Stringpool_char* s,
   ++this->next_index_;
 
   if (pkey != NULL)
-    *pkey = psd->index * key_mult;
+    {
+      *pkey = psd->index * key_mult;
+      // Ensure there was no overflow.
+      gold_assert(*pkey / key_mult == psd->index);
+    }
 
   if (front)
     this->strings_.push_front(psd);
diff --git a/gold/stringpool.h b/gold/stringpool.h
index 929b4d1..93e1ec8 100644
--- a/gold/stringpool.h
+++ b/gold/stringpool.h
@@ -88,6 +88,12 @@ class Stringpool_template
   void
   clear();
 
+  // Hint to the stringpool class that you intend to insert n additional
+  // elements.  The stringpool class can use this info however it likes;
+  // in practice it will resize its internal hashtables to make room.
+  void
+  reserve(unsigned int n);
+
   // Indicate that we should not reserve offset 0 to hold the empty
   // string when converting the stringpool to a string table.  This
   // should not be called for a proper ELF SHT_STRTAB section.
diff --git a/gold/symtab.cc b/gold/symtab.cc
index 9187f32..770628c 100644
--- a/gold/symtab.cc
+++ b/gold/symtab.cc
@@ -295,10 +295,11 @@ Symbol::final_value_is_known() const
 
 // Class Symbol_table.
 
-Symbol_table::Symbol_table()
-  : saw_undefined_(0), offset_(0), table_(), namepool_(),
+Symbol_table::Symbol_table(unsigned int count)
+  : saw_undefined_(0), offset_(0), table_(count), namepool_(),
     forwarders_(), commons_(), warnings_()
 {
+  namepool_.reserve(count);
 }
 
 Symbol_table::~Symbol_table()
diff --git a/gold/symtab.h b/gold/symtab.h
index a4f1106..cb3be9b 100644
--- a/gold/symtab.h
+++ b/gold/symtab.h
@@ -955,7 +955,10 @@ class Warnings
 class Symbol_table
 {
  public:
-  Symbol_table();
+  // COUNT is an estimate of how many symbosl will be inserted in the
+  // symbol table.  It's ok to put 0 if you don't know; a correct
+  // guess will just save some CPU by reducing hashtable resizes.
+  Symbol_table(unsigned int count);
 
   ~Symbol_table();