diff options
| author | Stephen Roberts <stephen.roberts@arm.com> | 2018-03-20 13:54:54 +0000 |
|---|---|---|
| committer | Stephen Roberts <stephen.roberts@arm.com> | 2018-03-20 14:04:17 +0000 |
| commit | 4ee89e903de920496a69c01df70db13a70a2a0be (patch) | |
| tree | 2086f28ed05a387d85e148d775934b5e3b2b0ae4 /gdb/symtab.c | |
| parent | ed3818775569116d7f09df3d81e22cb8169a8c06 (diff) | |
| download | gdb-4ee89e903de920496a69c01df70db13a70a2a0be.zip gdb-4ee89e903de920496a69c01df70db13a70a2a0be.tar.gz gdb-4ee89e903de920496a69c01df70db13a70a2a0be.tar.bz2 | |
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.
Diffstat (limited to 'gdb/symtab.c')
| -rw-r--r-- | gdb/symtab.c | 22 |
1 files changed, 11 insertions, 11 deletions
diff --git a/gdb/symtab.c b/gdb/symtab.c index 894a253..41aaef7 100644 --- a/gdb/symtab.c +++ b/gdb/symtab.c @@ -3046,8 +3046,6 @@ find_symbol_at_address (CORE_ADDR address) find the one whose first PC is closer than that of the next line in this symtab. */ -/* If it's worth the effort, we could be using a binary search. */ - struct symtab_and_line find_pc_sect_line (CORE_ADDR pc, struct obj_section *section, int notcurrent) { @@ -3214,15 +3212,17 @@ find_pc_sect_line (CORE_ADDR pc, struct obj_section *section, int notcurrent) if (item->pc > pc && (!alt || item->pc < alt->pc)) alt = item; - for (i = 0; i < len; i++, item++) - { - /* Leave prev pointing to the linetable entry for the last line - that started at or before PC. */ - if (item->pc > pc) - break; + auto pc_compare = [](const CORE_ADDR & pc, + const struct linetable_entry & lhs)->bool + { + return pc < lhs.pc; + }; - prev = item; - } + struct linetable_entry *first = item; + struct linetable_entry *last = item + len; + item = std::upper_bound (first, last, pc, pc_compare); + if (item != first) + prev = item - 1; /* Found a matching item. */ /* 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; } |