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]

Fwd: Patch to improve assemble time for files with large number of sections and section groups.


Resending after subscribing, as I never saw the email appear on the list.

Thanks,
Martin


---------- Forwarded message ----------
From: Martin Thuresson <martint@google.com>
Date: Wed, Sep 9, 2009 at 6:06 PM
Subject: Patch to improve assemble time for files with large number of
sections and section groups.
To: binutils <binutils@sourceware.org>


This patch adds two hashmaps to avoid the N^2 complexity of
scanning lists to find object. In obj-elf.c, group names are
mapped to indexes into an array, and in dwarf2dbg.c segment
names are mapped to segments.

For inputs with ~40k sections, this patch reduces the assembly
time from 3min to 15s on builds with debug information. It does
this at the expense of increase memory usage. ?In my example, it
increased from 405MB to 640MB.

Tested with x86_64-linux arm-eabi with no regressions seen on
check, check-gas.

Thanks,
Martin
Only in src.head/CVS: Entries.Log
diff -urp src.head/gas/as.c src.hash/gas/as.c
--- src.head/gas/as.c	2009-09-07 13:21:22.509595000 -0700
+++ src.hash/gas/as.c	2009-09-09 16:45:28.248544000 -0700
@@ -1158,6 +1158,8 @@ main (int argc, char ** argv)
 
   itbl_init ();
 
+  dwarf2_init ();
+
   /* Now that we have fully initialized, and have created the output
      file, define any symbols requested by --defsym command line
      arguments.  */
Only in src.hash/gas: as.c.orig
diff -urp src.head/gas/config/obj-elf.c src.hash/gas/config/obj-elf.c
--- src.head/gas/config/obj-elf.c	2009-09-07 13:21:23.923315000 -0700
+++ src.hash/gas/config/obj-elf.c	2009-09-09 16:45:28.661557000 -0700
@@ -2006,6 +2006,7 @@ struct group_list
   asection **head;		/* Section lists.  */
   unsigned int *elt_count;	/* Number of sections in each list.  */
   unsigned int num_group;	/* Number of lists.  */
+  struct hash_control *indexes; /* Maps group name to index in head array.  */
 };
 
 /* Called via bfd_map_over_sections.  If SEC is a member of a group,
@@ -2019,21 +2020,21 @@ build_group_lists (bfd *abfd ATTRIBUTE_U
   struct group_list *list = inf;
   const char *group_name = elf_group_name (sec);
   unsigned int i;
+  unsigned int *elem_idx;
+  unsigned int *idx_ptr;
 
   if (group_name == NULL)
     return;
 
   /* If this group already has a list, add the section to the head of
      the list.  */
-  for (i = 0; i < list->num_group; i++)
+  elem_idx = (unsigned int *) hash_find (list->indexes, group_name);
+  if (elem_idx != NULL)
     {
-      if (strcmp (group_name, elf_group_name (list->head[i])) == 0)
-	{
-	  elf_next_in_group (sec) = list->head[i];
-	  list->head[i] = sec;
-	  list->elt_count[i] += 1;
-	  return;
-	}
+      elf_next_in_group (sec) = list->head[*elem_idx];
+      list->head[*elem_idx] = sec;
+      list->elt_count[*elem_idx] += 1;
+      return;
     }
 
   /* New group.  Make the arrays bigger in chunks to minimize calls to
@@ -2049,6 +2050,16 @@ build_group_lists (bfd *abfd ATTRIBUTE_U
   list->head[i] = sec;
   list->elt_count[i] = 1;
   list->num_group += 1;
+
+  /* Add index to hash.  */
+  idx_ptr = xmalloc (sizeof (unsigned int));
+  *idx_ptr = i;
+  hash_insert (list->indexes, group_name, idx_ptr);
+}
+
+static void free_section_idx (const char *key ATTRIBUTE_UNUSED, void *val)
+{
+  free ((unsigned int *) val);
 }
 
 void
@@ -2063,6 +2074,7 @@ elf_frob_file (void)
   list.num_group = 0;
   list.head = NULL;
   list.elt_count = NULL;
+  list.indexes  = hash_new ();
   bfd_map_over_sections (stdoutput, build_group_lists, &list);
 
   /* Make the SHT_GROUP sections that describe each section group.  We
@@ -2128,6 +2140,10 @@ elf_frob_file (void)
 #ifdef elf_tc_final_processing
   elf_tc_final_processing ();
 #endif
+
+  /* Cleanup hash.  */
+  hash_traverse (list.indexes, free_section_idx);
+  hash_die (list.indexes);
 }
 
 /* It removes any unneeded versioned symbols from the symbol table.  */
Only in src.hash/gas/config: obj-elf.c.orig
diff -urp src.head/gas/dwarf2dbg.c src.hash/gas/dwarf2dbg.c
--- src.head/gas/dwarf2dbg.c	2009-09-07 13:21:22.777508000 -0700
+++ src.hash/gas/dwarf2dbg.c	2009-09-09 16:45:28.787528000 -0700
@@ -168,6 +168,10 @@ struct line_seg {
 
 /* Collects data for all line table entries during assembly.  */
 static struct line_seg *all_segs;
+/* Hash used to quickly lookup a segment by name, avoiding the need to search
+   through the all_segs list.  */
+static struct hash_control *all_segs_hash;
+static struct line_seg **last_seg_ptr;
 
 struct file_entry {
   const char *filename;
@@ -230,23 +234,25 @@ get_line_subseg (segT seg, subsegT subse
   static subsegT last_subseg;
   static struct line_subseg *last_line_subseg;
 
-  struct line_seg **ps, *s;
+  struct line_seg *s;
   struct line_subseg **pss, *ss;
 
   if (seg == last_seg && subseg == last_subseg)
     return last_line_subseg;
 
-  for (ps = &all_segs; (s = *ps) != NULL; ps = &s->next)
-    if (s->seg == seg)
-      goto found_seg;
-
-  s = (struct line_seg *) xmalloc (sizeof (*s));
-  s->next = NULL;
-  s->seg = seg;
-  s->head = NULL;
-  *ps = s;
+  s = (struct line_seg *) hash_find (all_segs_hash, seg->name);
+  if (s == NULL)
+    {
+      s = (struct line_seg *) xmalloc (sizeof (*s));
+      s->next = NULL;
+      s->seg = seg;
+      s->head = NULL;
+      *last_seg_ptr = s;
+      last_seg_ptr = &s->next;
+      hash_insert (all_segs_hash, seg->name, s);
+    }
+  gas_assert (seg == s->seg);
 
- found_seg:
   for (pss = &s->head; (ss = *pss) != NULL ; pss = &ss->next)
     {
       if (ss->subseg == subseg)
@@ -1702,6 +1708,14 @@ out_debug_info (segT info_seg, segT abbr
   symbol_set_value_now (info_end);
 }
 
+void
+dwarf2_init (void)
+{
+  all_segs_hash = hash_new ();
+  last_seg_ptr = &all_segs;
+}
+
+
 /* Finish the dwarf2 debug sections.  We emit .debug.line if there
    were any .file/.loc directives, or --gdwarf2 was given, or if the
    file has a non-empty .debug_info section.  If we emit .debug_line,
Only in src.hash/gas: dwarf2dbg.c.orig
diff -urp src.head/gas/dwarf2dbg.h src.hash/gas/dwarf2dbg.h
--- src.head/gas/dwarf2dbg.h	2009-09-07 13:21:22.797478000 -0700
+++ src.hash/gas/dwarf2dbg.h	2009-09-09 16:45:28.883566000 -0700
@@ -90,6 +90,8 @@ bfd_boolean dwarf2_loc_directive_seen;
    dwarf2_emit_label.  */
 extern bfd_boolean dwarf2_loc_mark_labels;
 
+extern void dwarf2_init (void);
+
 extern void dwarf2_finish (void);
 
 extern int dwarf2dbg_estimate_size_before_relax (fragS *);

Attachment: hash.changelog
Description: Binary data


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