aboutsummaryrefslogtreecommitdiff
path: root/gold
diff options
context:
space:
mode:
authorIan Lance Taylor <iant@google.com>2007-12-14 05:24:17 +0000
committerIan Lance Taylor <iant@google.com>2007-12-14 05:24:17 +0000
commit6d01333390a0047a4e8ec0d69f4d1c8f43c3fc55 (patch)
treeaa539a8dc67b986680175065607f9f51c471b831 /gold
parent460c00b558bc0cf4501c514b0ff13c7d48750165 (diff)
downloadgdb-6d01333390a0047a4e8ec0d69f4d1c8f43c3fc55.zip
gdb-6d01333390a0047a4e8ec0d69f4d1c8f43c3fc55.tar.gz
gdb-6d01333390a0047a4e8ec0d69f4d1c8f43c3fc55.tar.bz2
From Craig Silverstein: size hash tables to avoid resizing.
Diffstat (limited to 'gold')
-rw-r--r--gold/layout.cc19
-rw-r--r--gold/main.cc7
-rw-r--r--gold/object.h20
-rw-r--r--gold/stringpool.cc30
-rw-r--r--gold/stringpool.h6
-rw-r--r--gold/symtab.cc5
-rw-r--r--gold/symtab.h5
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();