This is the mail archive of the binutils@sourceware.org mailing list for the binutils project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH] gold: reserve up front buckets in comdat/linkonce signatures hash table


  I haven't yet finished the updated incremental linking patch, but I
have made a simple patch that may be also interesting as it speeds up
the normal case. It gives some 2-3% improvement on my test by
reserving upfront more buckets in the comdat signatures hash
(previously, the linker was spending something like  3% time of time
rehashing it - the final number of signatures was 2/3 of the number of
symbols). The heuristic is similar to the initial symbol table size
heuristic, but with the result 8 times smaller. In my test this has
given an average of 2.5 items per bucket and it seems there was no
need to rehash. Should I test if the numbers are similar in other
programs?
  The patch also fixes the parameter of find_or_add_kept_comdat to
pass string be reference, but I don't know if this makes a big
difference. I have also kept the code printing statistics about the
number of signatures, as I thought this may be interesting for others.

2009-04-01  Mikolaj Zalewski  <mikolajz@google.com>
       * layout.cc (Layout::Layout): reserve buckets up front for
signatures hash.
       (Layout::find_or_add_kept_section): pass string by reference
       (Layout::print stats): print information about the number of
comdat signatures.
       * layout.h (Layout::Layout): pass Command_line.
       (Layout::find_or_add_kept_section): pass string by reference
       * main.cc (main): pass Command_line to Layout::Layout.
From 8e4d3202c8666f457163e763073abee6c4a2588e Mon Sep 17 00:00:00 2001
From: Mikolaj Zalewski <mikolajz@google.com>
Date: Wed, 1 Apr 2009 17:58:24 +0200
Subject: [PATCH] gold: reserve up front more buckets in comdat signatures hash table

---
 gold/layout.cc |   14 +++++++++++---
 gold/layout.h  |    5 +++--
 gold/main.cc   |    2 +-
 3 files changed, 15 insertions(+), 6 deletions(-)

diff --git a/gold/layout.cc b/gold/layout.cc
index 108111a..2fc8733 100644
--- a/gold/layout.cc
+++ b/gold/layout.cc
@@ -86,8 +86,8 @@ Layout_task_runner::run(Workqueue* workqueue, const Task* task)
 
 // Layout methods.
 
-Layout::Layout(const General_options& options, Script_options* script_options)
-  : options_(options),
+Layout::Layout(const Command_line& cmd_line, Script_options* script_options)
+  : options_(cmd_line.options()),
     script_options_(script_options),
     namepool_(),
     sympool_(),
@@ -130,6 +130,11 @@ Layout::Layout(const General_options& options, Script_options* script_options)
   // We expect two unattached Output_data objects: the file header and
   // the segment headers.
   this->special_output_list_.reserve(2);
+
+  // Moke some buckets for comdat/linkonce data up front to avoid too many
+  // rehashes. This is 1/8 of the number of symbols we reserve up front
+  // in Symbol_table.
+  this->signatures_.rehash(cmd_line.number_of_input_files() * 128);
 }
 
 // Hash a key we use to look up an output section mapping.
@@ -2948,7 +2953,7 @@ Layout::output_section_name(const char* name, size_t* plen)
 // CANDIDATE.
 
 bool
-Layout::find_or_add_kept_section(const std::string name,
+Layout::find_or_add_kept_section(const std::string& name,
                                  Kept_section* candidate,
                                  Kept_section** kept_section)
 {
@@ -3243,6 +3248,9 @@ Layout::print_to_mapfile(Mapfile* mapfile) const
 void
 Layout::print_stats() const
 {
+  fprintf(stderr, _("%s: comdat/linkonce signatures: %zu\n"),
+          program_name, this->signatures_.size());
+
   this->namepool_.print_stats("section name pool");
   this->sympool_.print_stats("output symbol name pool");
   this->dynpool_.print_stats("dynamic name pool");
diff --git a/gold/layout.h b/gold/layout.h
index 010ab2e..634786e 100644
--- a/gold/layout.h
+++ b/gold/layout.h
@@ -38,6 +38,7 @@
 namespace gold
 {
 
+class Command_line;
 class General_options;
 class Input_objects;
 class Mapfile;
@@ -125,7 +126,7 @@ struct Kept_section
 class Layout
 {
  public:
-  Layout(const General_options& options, Script_options*);
+  Layout(const Command_line& options, Script_options*);
 
   // Given an input section SHNDX, named NAME, with data in SHDR, from
   // the object file OBJECT, return the output section where this
@@ -271,7 +272,7 @@ class Layout
   // CANDIDATE->GROUP_ being false, KEPT_SECTION can point back to
   // CANDIDATE.
   bool
-  find_or_add_kept_section(const std::string name,
+  find_or_add_kept_section(const std::string& name,
                            Kept_section* candidate,
                            Kept_section** kept_section);
 
diff --git a/gold/main.cc b/gold/main.cc
index 0019863..f245da0 100644
--- a/gold/main.cc
+++ b/gold/main.cc
@@ -216,7 +216,7 @@ main(int argc, char** argv)
     symtab.set_gc(&gc);
 
   // The layout object.
-  Layout layout(command_line.options(), &command_line.script_options());
+  Layout layout(command_line, &command_line.script_options());
 
   // Get the search path from the -L options.
   Dirsearch search_path;
-- 
1.5.4.3


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]