[PATCH] This patch replaces the linear search in find_pc_sect_line with a binary search for faster performance.

[Yao Qi]

Stephen Roberts <stephen.roberts@arm.com> writes:

> This patch addresses slowness when setting breakpoints, especially in
> heavily templatized code. Profiling showed that find_pc_sect_line in
> symtab.c was the performance bottleneck.  The original logic performed a
> linear search over ordered data. This patch uses a binary search, as
> suggested by comments around the function.  There are no behavioural
> changes, but gdb is now faster at setting breakpoints in template code.
> Tested using on make check on an x86 target. The optimisation speeds up
> the included template-breakpoints.py performance test by a factor of 7
> on my machine.

Nice!  Can you run template-breakpoints.exp twice, with the fix and
without the fix, and post the contents of ./testsuite/perftest.sum here.

> @@ -3206,23 +3204,25 @@ find_pc_sect_line (CORE_ADDR pc, struct obj_section *section, int notcurrent)
>  	  continue;
>  	}
>  
> -      prev = NULL;
> -      item = l->item;		/* Get first line info.  */
> +	prev = NULL;
> +	item = l->item;		/* Get first line info.  */
>  
> -      /* Is this file's first line closer than the first lines of other files?
> -         If so, record this file, and its first line, as best alternate.  */
> -      if (item->pc > pc && (!alt || item->pc < alt->pc))
> -	alt = item;
> +	/* Is this file's first line closer than the first lines of other files?
> +	   If so, record this file, and its first line, as best alternate.  */
> +	if (item->pc > pc && (!alt || item->pc < alt->pc))
> +		alt = item;
>  

Unnecessary change.

> -      for (i = 0; i < len; i++, item++)
> +	auto PCCompare = [](const CORE_ADDR &pc,

Nit: the naming of PCCompare looks odd to me.  How about "pc_compare"?

> +			    const struct linetable_entry &lhs) -> bool
>  	{
> -	  /* Leave prev pointing to the linetable entry for the last line
> -	     that started at or before PC.  */
> -	  if (item->pc > pc)
> -	    break;
> +		return pc < lhs.pc;

Indentation looks wrong to me.

> +	};
>  
> -	  prev = item;
> -	}
> +	struct linetable_entry *first = item;
> +	struct linetable_entry *last = item + len;
> +	item = std::upper_bound (first, last, pc, PCCompare);
> +	if (item != first)
> +	prev = item - 1; /* Found a matching item.  */

Lack of indent.

>  
>        /* At this point, prev points at the line whose start addr is <= pc, and
>           item points at the next line.  If we ran off the end of the linetable
> @@ -3247,7 +3247,7 @@ find_pc_sect_line (CORE_ADDR pc, struct obj_section *section, int notcurrent)
>        /* If another line (denoted by ITEM) is in the linetable and its
>           PC is after BEST's PC, but before the current BEST_END, then
>  	 use ITEM's PC as the new best_end.  */
> -      if (best && i < len && item->pc > best->pc
> +      if (best && item < last && item->pc > best->pc
>            && (best_end == 0 || best_end > item->pc))
>  	best_end = item->pc;
>      }
> diff --git a/gdb/testsuite/gdb.perf/template-breakpoints.cc b/gdb/testsuite/gdb.perf/template-breakpoints.cc
> new file mode 100644
> index 0000000..164c31e
> --- /dev/null
> +++ b/gdb/testsuite/gdb.perf/template-breakpoints.cc
> @@ -0,0 +1,97 @@
> +/* This testcase is part of GDB, the GNU debugger.
> +
> +   Copyright (C) 2016-2018 Free Software Foundation, Inc.

2016-2018 -> 2018

> diff --git a/gdb/testsuite/gdb.perf/template-breakpoints.exp b/gdb/testsuite/gdb.perf/template-breakpoints.exp
> new file mode 100644
> index 0000000..e9fb669
> --- /dev/null
> +++ b/gdb/testsuite/gdb.perf/template-breakpoints.exp
> @@ -0,0 +1,65 @@
> +# Copyright (C) 2016-2018 Free Software Foundation, Inc.

Likewise.

> --- /dev/null
> +++ b/gdb/testsuite/gdb.perf/template-breakpoints.py
> @@ -0,0 +1,33 @@
> +# Copyright (C) 2016-2018 Free Software Foundation, Inc.
> +

Likewise.

> +
> +class TemplateBreakpoints (perftest.TestCaseWithBasicMeasurements):
> +    def __init__(self):
> +        super (TemplateBreakpoints, self).__init__ ("template-breakpoints")
> +
> +    def warm_up(self):
> +        for _ in range(0, 2):
> +            gdb.Breakpoint("template-breakpoints.cc:38").delete()

Can you set breakpoint on ThirdDimension::value(), so that it is less fragile.

-- 
Yao (齐尧)