* Patch to improve assemble time for files with large number of sections and section groups.
@ 2009-09-10 1:07 Martin Thuresson
2009-09-10 15:48 ` Fwd: " Martin Thuresson
0 siblings, 1 reply; 3+ messages in thread
From: Martin Thuresson @ 2009-09-10 1:07 UTC (permalink / raw)
To: binutils
[-- Attachment #1: Type: text/plain, Size: 532 bytes --]
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
[-- Attachment #2: hash.patch --]
[-- Type: text/x-patch, Size: 5493 bytes --]
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 #3: hash.changelog --]
[-- Type: application/octet-stream, Size: 420 bytes --]
2009-09-09 Martin Thuresson <martint@google.com>
* gas/as.c (main): Call dwarf2_init.
* gas/config/obj-elf.c (struct group_list): New field.
(build_group_lists): Use hash lookup.
(free_section_idx): New function.
(elf_frob_file): Adjust.
* gas/dwarf2dbg.c (all_segs_hash, last_seg_ptr): New variables.
(get_line_subseg): Adjust.
(dwarf2_init): New function.
* gas/dwarf2dbg.h (dwarf2_init): New declaration.
^ permalink raw reply [flat|nested] 3+ messages in thread
* Fwd: Patch to improve assemble time for files with large number of sections and section groups.
2009-09-10 1:07 Patch to improve assemble time for files with large number of sections and section groups Martin Thuresson
@ 2009-09-10 15:48 ` Martin Thuresson
2009-09-11 15:29 ` Nick Clifton
0 siblings, 1 reply; 3+ messages in thread
From: Martin Thuresson @ 2009-09-10 15:48 UTC (permalink / raw)
To: binutils
[-- Attachment #1: Type: text/plain, Size: 912 bytes --]
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
[-- Attachment #2: hash.patch --]
[-- Type: text/x-patch, Size: 5493 bytes --]
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 #3: hash.changelog --]
[-- Type: application/octet-stream, Size: 420 bytes --]
2009-09-09 Martin Thuresson <martint@google.com>
* gas/as.c (main): Call dwarf2_init.
* gas/config/obj-elf.c (struct group_list): New field.
(build_group_lists): Use hash lookup.
(free_section_idx): New function.
(elf_frob_file): Adjust.
* gas/dwarf2dbg.c (all_segs_hash, last_seg_ptr): New variables.
(get_line_subseg): Adjust.
(dwarf2_init): New function.
* gas/dwarf2dbg.h (dwarf2_init): New declaration.
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: Fwd: Patch to improve assemble time for files with large number of sections and section groups.
2009-09-10 15:48 ` Fwd: " Martin Thuresson
@ 2009-09-11 15:29 ` Nick Clifton
0 siblings, 0 replies; 3+ messages in thread
From: Nick Clifton @ 2009-09-11 15:29 UTC (permalink / raw)
To: Martin Thuresson; +Cc: binutils
Hi Martin,
> Resending after subscribing, as I never saw the email appear on the list.
Approved and applied (mainline only).
Cheers
Nick
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2009-09-11 15:29 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2009-09-10 1:07 Patch to improve assemble time for files with large number of sections and section groups Martin Thuresson
2009-09-10 15:48 ` Fwd: " Martin Thuresson
2009-09-11 15:29 ` Nick Clifton
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).