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]

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


Mikolaj Zalewski <mikolajz@google.com> writes:

>   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.

Thanks for the patch.  I'm not quite happy with this approach, since a
typical C program will have hardly any linkonce sections, so there is no
reason to allocate a big hash table.  Also, I think your size is a bit
too big--typically the same signature will appear in many input files,
and take up only one slot in the hash table.  Also, the rehash call
doesn't work if we are using __gnu_cxx::hash_map.  I implemented a
similar but slightly different approach as follows.  I also removed the
options_ field from Layout, as it is accessible via parameters.

Ian


2009-04-01  Ian Lance Taylor  <iant@google.com>
	    Mikolaj Zalewski  <mikolajz@google.com>

	* gold.h (reserve_unordered_map): Define, three versions, one for
	each version of Unordered_map.
	* layout.cc (Layout::Layout): Remove options parameter.  Add
	number_of_input_files parameter.  Don't initialize options_.
	Initialize number_of_input_files_ and resized_signatures_.  Move
	sections_are_attached_.
	(Layout::layout_group): Reserve space for group_signatures_.
	(Layout::find_or_add_kept_section): Change name parameter to be a
	reference.  Resize signatures_ map when it gets large enough.
	(Layout::layout_eh_frame): Use parameters->options() instead of
	this->options_.
	(Layout::make_output_section): Likewise.
	(Layout::attach_allocated_section_to_segment): Likewise.
	(Layout::finalize, Layout::create_executable_stack): Likewise.
	(Layout::set_segment_offsets, Layout::create_interp): Likewise.
	(Layout::finish_dynamic_section, Layout::write_binary): Likewise.
	* layout.h (class Layout): Update declarations.  Remove options_
	field.  Add number_of_input_files_ and resized_signatures_
	fields.  Move sections_are_attached_ field.
	* main.cc (main): Pass number of input files to Layout
	constructor.  Don't pass options.


Index: gold.h
===================================================================
RCS file: /cvs/src/src/gold/gold.h,v
retrieving revision 1.34
diff -u -p -r1.34 gold.h
--- gold.h	28 Mar 2009 05:22:30 -0000	1.34
+++ gold.h	2 Apr 2009 00:46:45 -0000
@@ -75,6 +75,8 @@
 #define Unordered_set std::tr1::unordered_set
 #define Unordered_map std::tr1::unordered_map
 
+#define reserve_unordered_map(map, n) ((map)->rehash(n))
+
 #elif defined(HAVE_EXT_HASH_MAP) && defined(HAVE_EXT_HASH_SET)
 
 #include <ext/hash_map>
@@ -105,6 +107,8 @@ struct hash<T*>
 
 }
 
+#define reserve_unordered_map(map, n) ((map)->resize(n))
+
 #else
 
 // The fallback is to just use set and map.
@@ -115,6 +119,8 @@ struct hash<T*>
 #define Unordered_set std::set
 #define Unordered_map std::map
 
+#define reserve_unordered_map(map, n)
+
 #endif
 
 #ifndef HAVE_PREAD
Index: layout.cc
===================================================================
RCS file: /cvs/src/src/gold/layout.cc,v
retrieving revision 1.121
diff -u -p -r1.121 layout.cc
--- layout.cc	19 Mar 2009 19:39:32 -0000	1.121
+++ layout.cc	2 Apr 2009 00:46:46 -0000
@@ -86,8 +86,8 @@ Layout_task_runner::run(Workqueue* workq
 
 // Layout methods.
 
-Layout::Layout(const General_options& options, Script_options* script_options)
-  : options_(options),
+Layout::Layout(int number_of_input_files, Script_options* script_options)
+  : number_of_input_files_(number_of_input_files),
     script_options_(script_options),
     namepool_(),
     sympool_(),
@@ -97,7 +97,6 @@ Layout::Layout(const General_options& op
     segment_list_(),
     section_list_(),
     unattached_section_list_(),
-    sections_are_attached_(false),
     special_output_list_(),
     section_headers_(NULL),
     tls_segment_(NULL),
@@ -117,11 +116,13 @@ Layout::Layout(const General_options& op
     debug_info_(NULL),
     group_signatures_(),
     output_file_size_(-1),
+    sections_are_attached_(false),
     input_requires_executable_stack_(false),
     input_with_gnu_stack_note_(false),
     input_without_gnu_stack_note_(false),
     has_static_tls_(false),
-    any_postprocessing_sections_(false)
+    any_postprocessing_sections_(false),
+    resized_signatures_(false)
 {
   // Make space for more than enough segments for a typical file.
   // This is just for efficiency--it's OK if we wind up needing more.
@@ -581,6 +582,10 @@ Layout::layout_group(Symbol_table* symta
     os->set_info_symndx(sym);
   else
     {
+      // Reserve some space to minimize reallocations.
+      if (this->group_signatures_.empty())
+	this->group_signatures_.reserve(this->number_of_input_files_ * 16);
+
       // We will wind up using a symbol whose name is the signature.
       // So just put the signature in the symbol name pool to save it.
       signature = symtab->canonicalize_name(signature);
@@ -631,7 +636,7 @@ Layout::layout_eh_frame(Sized_relobj<siz
       this->eh_frame_section_ = os;
       this->eh_frame_data_ = new Eh_frame();
 
-      if (this->options_.eh_frame_hdr())
+      if (parameters->options().eh_frame_hdr())
 	{
 	  Output_section* hdr_os =
 	    this->choose_output_section(NULL,
@@ -751,12 +756,13 @@ Layout::make_output_section(const char* 
 {
   Output_section* os;
   if ((flags & elfcpp::SHF_ALLOC) == 0
-      && strcmp(this->options_.compress_debug_sections(), "none") != 0
+      && strcmp(parameters->options().compress_debug_sections(), "none") != 0
       && is_compressible_debug_section(name))
-    os = new Output_compressed_section(&this->options_, name, type, flags);
+    os = new Output_compressed_section(&parameters->options(), name, type,
+				       flags);
 
   else if ((flags & elfcpp::SHF_ALLOC) == 0
-           && this->options_.strip_debug_non_line()
+           && parameters->options().strip_debug_non_line()
            && strcmp(".debug_abbrev", name) == 0)
     {
       os = this->debug_abbrev_ = new Output_reduced_debug_abbrev_section(
@@ -765,7 +771,7 @@ Layout::make_output_section(const char* 
         this->debug_info_->set_abbreviations(this->debug_abbrev_);
     }
   else if ((flags & elfcpp::SHF_ALLOC) == 0
-           && this->options_.strip_debug_non_line()
+           && parameters->options().strip_debug_non_line()
            && strcmp(".debug_info", name) == 0)
     {
       os = this->debug_info_ = new Output_reduced_debug_info_section(
@@ -877,7 +883,7 @@ Layout::attach_allocated_section_to_segm
         {
           // If -Tbss was specified, we need to separate the data
           // and BSS segments.
-          if (this->options_.user_set_Tbss())
+          if (parameters->options().user_set_Tbss())
             {
               if ((os->type() == elfcpp::SHT_NOBITS)
                   == (*p)->has_any_data_sections())
@@ -1220,7 +1226,8 @@ Layout::finalize(const Input_objects* in
   else
     load_seg = this->find_first_load_seg();
 
-  if (this->options_.oformat_enum() != General_options::OBJECT_FORMAT_ELF)
+  if (parameters->options().oformat_enum()
+      != General_options::OBJECT_FORMAT_ELF)
     load_seg = NULL;
 
   gold_assert(phdr_seg == NULL || load_seg != NULL);
@@ -1241,7 +1248,7 @@ Layout::finalize(const Input_objects* in
   // Lay out the file header.
   Output_file_header* file_header;
   file_header = new Output_file_header(target, symtab, segment_headers,
-				       this->options_.entry());
+				       parameters->options().entry());
   if (load_seg != NULL)
     load_seg->add_initial_output_data(file_header);
 
@@ -1454,8 +1461,8 @@ void
 Layout::create_executable_stack_info(const Target* target)
 {
   bool is_stack_executable;
-  if (this->options_.is_execstack_set())
-    is_stack_executable = this->options_.is_stack_executable();
+  if (parameters->options().is_execstack_set())
+    is_stack_executable = parameters->options().is_stack_executable();
   else if (!this->input_with_gnu_stack_note_)
     return;
   else
@@ -1717,8 +1724,8 @@ Layout::set_segment_offsets(const Target
   // Find the PT_LOAD segments, and set their addresses and offsets
   // and their section's addresses and offsets.
   uint64_t addr;
-  if (this->options_.user_set_Ttext())
-    addr = this->options_.Ttext();
+  if (parameters->options().user_set_Ttext())
+    addr = parameters->options().Ttext();
   else if (parameters->options().shared())
     addr = 0;
   else
@@ -1761,19 +1768,19 @@ Layout::set_segment_offsets(const Target
 	      // the physical address.
 	      addr = (*p)->paddr();
 	    }
-	  else if (this->options_.user_set_Tdata()
+	  else if (parameters->options().user_set_Tdata()
 		   && ((*p)->flags() & elfcpp::PF_W) != 0
-		   && (!this->options_.user_set_Tbss()
+		   && (!parameters->options().user_set_Tbss()
 		       || (*p)->has_any_data_sections()))
 	    {
-	      addr = this->options_.Tdata();
+	      addr = parameters->options().Tdata();
 	      are_addresses_set = true;
 	    }
-	  else if (this->options_.user_set_Tbss()
+	  else if (parameters->options().user_set_Tbss()
 		   && ((*p)->flags() & elfcpp::PF_W) != 0
 		   && !(*p)->has_any_data_sections())
 	    {
-	      addr = this->options_.Tbss();
+	      addr = parameters->options().Tbss();
 	      are_addresses_set = true;
 	    }
 
@@ -2616,7 +2623,7 @@ Layout::sized_create_version_sections(
 void
 Layout::create_interp(const Target* target)
 {
-  const char* interp = this->options_.dynamic_linker();
+  const char* interp = parameters->options().dynamic_linker();
   if (interp == NULL)
     {
       interp = target->dynamic_linker();
@@ -2668,7 +2675,7 @@ Layout::finish_dynamic_section(const Inp
 
   if (parameters->options().shared())
     {
-      const char* soname = this->options_.soname();
+      const char* soname = parameters->options().soname();
       if (soname != NULL)
 	odyn->add_string(elfcpp::DT_SONAME, soname);
     }
@@ -2685,7 +2692,7 @@ Layout::finish_dynamic_section(const Inp
   // FIXME: Support DT_INIT_ARRAY and DT_FINI_ARRAY.
 
   // Add a DT_RPATH entry if needed.
-  const General_options::Dir_list& rpath(this->options_.rpath());
+  const General_options::Dir_list& rpath(parameters->options().rpath());
   if (!rpath.empty())
     {
       std::string rpath_val;
@@ -2948,10 +2955,21 @@ Layout::output_section_name(const char* 
 // 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)
 {
+  // It's normal to see a couple of entries here, for the x86 thunk
+  // sections.  If we see more than a few, we're linking a C++
+  // program, and we resize to get more space to minimize rehashing.
+  if (this->signatures_.size() > 4
+      && !this->resized_signatures_)
+    {
+      reserve_unordered_map(&this->signatures_,
+			    this->number_of_input_files_ * 64);
+      this->resized_signatures_ = true;
+    }
+
   std::pair<Signatures::iterator, bool> ins(
     this->signatures_.insert(std::make_pair(name, *candidate)));
 
@@ -3188,7 +3206,7 @@ Layout::write_build_id(Output_file* of) 
 void
 Layout::write_binary(Output_file* in) const
 {
-  gold_assert(this->options_.oformat_enum()
+  gold_assert(parameters->options().oformat_enum()
 	      == General_options::OBJECT_FORMAT_BINARY);
 
   // Get the size of the binary file.
Index: layout.h
===================================================================
RCS file: /cvs/src/src/gold/layout.h,v
retrieving revision 1.62
diff -u -p -r1.62 layout.h
--- layout.h	17 Mar 2009 20:36:30 -0000	1.62
+++ layout.h	2 Apr 2009 00:46:46 -0000
@@ -125,7 +125,7 @@ struct Kept_section
 class Layout
 {
  public:
-  Layout(const General_options& options, Script_options*);
+  Layout(int number_of_input_files, 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 +271,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);
 
@@ -640,8 +640,8 @@ class Layout
     { return Layout::segment_precedes(seg1, seg2); }
   };
 
-  // A reference to the options on the command line.
-  const General_options& options_;
+  // The number of input files, for sizing tables.
+  int number_of_input_files_;
   // Information set by scripts or by command line options.
   Script_options* script_options_;
   // The output section names.
@@ -661,8 +661,6 @@ class Layout
   // The list of output sections which are not attached to any output
   // segment.
   Section_list unattached_section_list_;
-  // Whether we have attached the sections to the segments.
-  bool sections_are_attached_;
   // The list of unattached Output_data objects which require special
   // handling because they are not Output_sections.
   Data_list special_output_list_;
@@ -702,6 +700,8 @@ class Layout
   Group_signatures group_signatures_;
   // The size of the output file.
   off_t output_file_size_;
+  // Whether we have attached the sections to the segments.
+  bool sections_are_attached_;
   // Whether we have seen an object file marked to require an
   // executable stack.
   bool input_requires_executable_stack_;
@@ -715,6 +715,8 @@ class Layout
   bool has_static_tls_;
   // Whether any sections require postprocessing.
   bool any_postprocessing_sections_;
+  // Whether we have resized the signatures_ hash table.
+  bool resized_signatures_;
 };
 
 // This task handles writing out data in output sections which is not
Index: main.cc
===================================================================
RCS file: /cvs/src/src/gold/main.cc,v
retrieving revision 1.29
diff -u -p -r1.29 main.cc
--- main.cc	28 Jan 2009 02:25:33 -0000	1.29
+++ main.cc	2 Apr 2009 00:46:46 -0000
@@ -216,7 +216,8 @@ 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.number_of_input_files(),
+		&command_line.script_options());
 
   // Get the search path from the -L options.
   Dirsearch search_path;

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