Replace the linear search in find_pc_sect_line with a binary search.
authorStephen Roberts <stephen.roberts@arm.com>
Tue, 20 Mar 2018 13:54:54 +0000 (13:54 +0000)
committerStephen Roberts <stephen.roberts@arm.com>
Tue, 20 Mar 2018 14:04:17 +0000 (14:04 +0000)
commit4ee89e903de920496a69c01df70db13a70a2a0be
tree2086f28ed05a387d85e148d775934b5e3b2b0ae4
parented3818775569116d7f09df3d81e22cb8169a8c06
Replace the linear search in find_pc_sect_line with a binary search.

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.

ChangeLog:

2018-03-20  Stephen Roberts  <stephen.roberts@arm.com>

        * gdb/symtab.c (find_pc_sect_line): now uses binary search.

gdb/testsuite/

        * gdb.perf/template-breakpoints.cc: New file.
        * gdb.perf/template-breakpoints.exp: New file.
        * gdb.perf/template-breakpoints.py: New file.
gdb/ChangeLog
gdb/symtab.c
gdb/testsuite/ChangeLog
gdb/testsuite/gdb.perf/template-breakpoints.cc [new file with mode: 0644]
gdb/testsuite/gdb.perf/template-breakpoints.exp [new file with mode: 0644]
gdb/testsuite/gdb.perf/template-breakpoints.py [new file with mode: 0644]