Performance issues with -ffunction-sections and dwarf2 debug line info

Performance issues with -ffunction-sections and dwarf2 debug line info

[Nicolas Roche]

I am using GCC 3.4 and the -ffunction-sections -fdata-sections options 
along with binutils 2.16.1 (for dead code elimination)

When using this functions the debug line info is no more sorted 
(increasing line and increasing vma) and so on big files with lots of 
functions you can observe a quadratic behavior for the time needed to 
read this info (addr2line, ...). The reason is that we are almost always 
triggering the worst case in add_line_info function in bfd/dwarf2.c.

The problem is in gas. Indeed in dwarf2dbg.c a list of sections is 
maintained (all_segs), but each time a new section is created, it is 
appended to the beginning of the list....

so if  you have the following source:

1 begin function1
2
3 end function1
4 begin function2
5
6 end function2

the line information will be sorted in the following order:
4,5,6,1,2,3

In order to solve this issue we just have to append to the tail of all_segs.

Here is the patch I would like to submit to the head and if it is still 
possible to the binutils 2.17 branch.

Thanks in advance for your comments

Nicolas

Index: dwarf2dbg.c
===================================================================
RCS file: /cvs/src/src/gas/dwarf2dbg.c,v
retrieving revision 1.81
diff -r1.81 dwarf2dbg.c
128c128,131
< static struct line_seg *all_segs;
---
 > static struct line_seg *all_segs = NULL;
 >
 > /* Pointer to the last item in all_segs. NULL if all_segs is empty */
 > static struct line_seg *all_segs_last = NULL;
223c226
<   s->next = all_segs;
---
 >   s->next = NULL;
226c229,245
<   all_segs = s;
---
 >
 >   /* Append s at the end of the all_segs list. Appending it to the 
head is
 >      not recommended as this will break the line debug info order (when
 >      compiling using -ffunction-sections). Ensuring that line appears 
in order
 >      with increasing VMAs helps reading that info afterward from a
 >      performance point of view (see comments in add_line_info 
(bfd/dwarf2.c).
 >   */
 >   if (all_segs_last)
 >     {
 >       all_segs_last->next = s;
 >       all_segs_last = s;
 >     }
 >   else
 >     {
 >       all_segs = s;
 >       all_segs_last = s;
 >     }

Re: Performance issues with -ffunction-sections and dwarf2 debug line info

[Alan Modra]

On Wed, Apr 26, 2006 at 12:29:18PM +0200, Nicolas Roche wrote:
> I am using GCC 3.4 and the -ffunction-sections -fdata-sections options 
> along with binutils 2.16.1 (for dead code elimination)
> 
> When using this functions the debug line info is no more sorted 
> (increasing line and increasing vma) and so on big files with lots of 
> functions you can observe a quadratic behavior for the time needed to 
> read this info (addr2line, ...). The reason is that we are almost always 
> triggering the worst case in add_line_info function in bfd/dwarf2.c.
> 
> The problem is in gas. Indeed in dwarf2dbg.c a list of sections is 
> maintained (all_segs), but each time a new section is created, it is 
> appended to the beginning of the list....
> 
> so if  you have the following source:
> 
> 1 begin function1
> 2
> 3 end function1
> 4 begin function2
> 5
> 6 end function2
> 
> the line information will be sorted in the following order:
> 4,5,6,1,2,3
> 
> In order to solve this issue we just have to append to the tail of all_segs.

Thanks for the analysis and patch.  It looks OK to me as all places that
traverse the list don't care too much about the order.  I'm going to
apply the following slightly different patch instead, so we don't need
another static var and to make line_seg and line_subseg list addition
look similar.

	* dwarf2dbg.c (get_line_subseg): Attach new struct line_seg to end
	of list rather than beginning.

Index: gas/dwarf2dbg.c
===================================================================
RCS file: /cvs/src/src/gas/dwarf2dbg.c,v
retrieving revision 1.81
diff -u -p -r1.81 dwarf2dbg.c
--- gas/dwarf2dbg.c	28 Feb 2006 00:38:19 -0000	1.81
+++ gas/dwarf2dbg.c	27 Apr 2006 03:18:54 -0000
@@ -209,21 +209,21 @@ get_line_subseg (segT seg, subsegT subse
   static subsegT last_subseg;
   static struct line_subseg *last_line_subseg;
 
-  struct line_seg *s;
+  struct line_seg **ps, *s;
   struct line_subseg **pss, *ss;
 
   if (seg == last_seg && subseg == last_subseg)
     return last_line_subseg;
 
-  for (s = all_segs; s; s = s->next)
+  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 = all_segs;
+  s->next = NULL;
   s->seg = seg;
   s->head = NULL;
-  all_segs = s;
+  *ps = s;
 
  found_seg:
   for (pss = &s->head; (ss = *pss) != NULL ; pss = &ss->next)

-- 
Alan Modra
IBM OzLabs - Linux Technology Centre

Re: Performance issues with -ffunction-sections and dwarf2 debug line info

[Nicolas Roche]

Alan Modra wrote:
>
> Thanks for the analysis and patch.  It looks OK to me as all places that
> traverse the list don't care too much about the order.  I'm going to
> apply the following slightly different patch instead, so we don't need
> another static var and to make line_seg and line_subseg list addition
> look similar.

Thanks for your review (I just see that I forgot to provide a Changelog 
entry ... will do next time).

Just a little question. Will you apply that patch on the 2.17 branch as 
well so that this fix is included in the upcoming 2.17 release ?

Nicolas Roche

Re: Performance issues with -ffunction-sections and dwarf2 debug line info

[Alan Modra]

On Fri, Apr 28, 2006 at 12:37:27PM +0200, Nicolas Roche wrote:
> Will you apply that patch on the 2.17 branch as 
> well so that this fix is included in the upcoming 2.17 release ?

If no problems show up in the next week, yes.

-- 
Alan Modra
IBM OzLabs - Linux Technology Centre

Re: Performance issues with -ffunction-sections and dwarf2 debug line info

[Nicolas Roche]

Alan Modra wrote:
> On Fri, Apr 28, 2006 at 12:37:27PM +0200, Nicolas Roche wrote:
>   
>> Will you apply that patch on the 2.17 branch as 
>> well so that this fix is included in the upcoming 2.17 release ?
>>     
>
> If no problems show up in the next week, yes.
>   

Thanks a lot.

Nicolas