From patchwork Tue Mar 13 07:05:29 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Stephen Roberts X-Patchwork-Id: 26297 Received: (qmail 512 invoked by alias); 13 Mar 2018 07:06:01 -0000 Mailing-List: contact gdb-patches-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gdb-patches-owner@sourceware.org Delivered-To: mailing list gdb-patches@sourceware.org Received: (qmail 480 invoked by uid 89); 13 Mar 2018 07:05:59 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-24.9 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_SHORT, RCVD_IN_DNSWL_NONE, SPF_HELO_PASS, SPF_PASS autolearn=ham version=3.3.2 spammy= X-HELO: EUR01-HE1-obe.outbound.protection.outlook.com Received: from mail-he1eur01on0060.outbound.protection.outlook.com (HELO EUR01-HE1-obe.outbound.protection.outlook.com) (104.47.0.60) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 13 Mar 2018 07:05:56 +0000 Authentication-Results: spf=none (sender IP is ) smtp.mailfrom=Stephen.Roberts@arm.com; Received: from e112367-lin.warwick.arm.com (217.140.96.140) by DB5PR08MB0632.eurprd08.prod.outlook.com (2a01:111:e400:52c9::26) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P256) id 15.20.548.13; Tue, 13 Mar 2018 07:05:52 +0000 From: Stephen Roberts To: gdb-patches@sourceware.org Cc: nd@arm.com, Stephen Roberts Subject: [PATCH] This patch replaces the linear search in find_pc_sect_line with a binary search for faster performance. Date: Tue, 13 Mar 2018 07:05:29 +0000 Message-Id: <1520924729-12839-1-git-send-email-stephen.roberts@arm.com> MIME-Version: 1.0 X-ClientProxiedBy: AM4PR05CA0015.eurprd05.prod.outlook.com (2603:10a6:205::28) To DB5PR08MB0632.eurprd08.prod.outlook.com (2a01:111:e400:52c9::26) X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-HT: Tenant X-MS-Office365-Filtering-Correlation-Id: fdba268d-ac0b-4757-7771-08d588b0dbb0 X-Microsoft-Antispam: UriScan:; BCL:0; PCL:0; RULEID:(7020095)(4652020)(48565401081)(5600026)(4604075)(4534165)(4627221)(201703031133081)(201702281549075)(2017052603328)(7153060)(7193020); SRVR:DB5PR08MB0632; X-Microsoft-Exchange-Diagnostics: 1; DB5PR08MB0632; 3:7oQVVr55gZaTzMpM/r3RgvLMe0iS7Eso/qruGQ61V6taZQJkmwkLKUkk4OuT9Y8PtwUrToc8bXcEqQVX80SyvRfDWJd0ijoerw0knCo9h5MhOanY7wkRXxMUywTZXS+DizRl9qM3/3hsAAU/dbzs3drmDcSWk9Sb1BvddE08Zf9RXXIrCh9v+1rOEuwzWRZB8Iba82AtJtrAz+UKdIRJQzFkdPVeMB30hIFv3DgoEFx11KIKh+CaWD00UF50JEGa; 25:nqVxmW2FZ2gar0bTw1sYrcGN3/yJgH8+lpTkuntz4YyutkeBQbwMpTd8vbmgE/RTSSAkCk6NSTl55aP/0EC3r9PDTVdW2Hwuvg1E5pdTG6jyQTis08zQW+oRlNL49MkW4LdMIoYhBmDRJfpahw4h7xMqSwJJqEs3yOEGh2so9X28vR6wJRDCfyLfY72pruaEfltu1Brf7R4kfIN9voTEFqV57exs19qw/3tsKMXOutRoHFNdq8nz48UMdMdtygxSCRmGdtCqzIQ1rN5EJfEo61H55Bw1Md6zTNXRN3TA/sSkIHIiOl85xUnU2vwmnExp4V96jXO1gZCAUO/O6BLCMA==; 31:z7CETlOB9ioAoDzD+hD/HlBPPeNAmD/kzZ+5mCFaz+QmBrqPvM4XWVBPYSA4pPAPxIYMxlrwER2nlSgKJA4SFIbKjLB9iJTMgZHm1ykFw7sQj7RT8fuOr8I+hKBnW50E8Xkm9Ui4HxyM/UCZsmmld6Y+17SMOMgRXd+bOhTEVr/A6NF2OArgYqWFm+/YtOtHIwgwzWmLJZ7rWWHDR+bzhtBk1S6+bfoYDp7kge0fGD0= X-MS-TrafficTypeDiagnostic: DB5PR08MB0632: NoDisclaimer: True X-Microsoft-Exchange-Diagnostics: 1; DB5PR08MB0632; 20:bR2qiHGhkuKN3fDwtbmjtO4Je5RYIAnaijoVU36LilY3NOiuTKSDqgOcrDMIbETJqgEY+RBlw73pmfrD2cZPudvjc4ilCFu9ed76u57MJQvoEcmOoe0U/BaVN2WeGW6X42LNWbWFnEpewNlL3TiCDOMjzzJQeJIqfRdUPHUSaOU=; 4:ymWo1icFbrwdXQzvhoXN/svvz8OpHc8Szm2DUU1cGs0/Rv3YsbCPz9Q04aF+IFBgAgwerdU9GPPn9R69TERTqVuuqG9aeOI8DueqjpovutnPfVgKPl2fJiKG4tHmUZfhkGdbJhsHEx0MnfQG/QUHQsK+K05cPPWIFvrwEdr+sQh+MI0uSHZqg8vA6oDUarUdRFiXj3QGNxvP2WnyiulPCBRl6D3sgSfCrjYnporMpoByQUDDtFWghu/Yi3X8SH2FoUzmTJJH2oqgsBl8vWRvgIP6nboZWY++/bOWs7dIRl3935Tva+9V5Mr931k7sEnFmfCxuZYwZFQ/jTs2x1urU9289fayPKaQbgCPazi5t6Zj2NnDnVwY+6P+hEH+ovYJ X-Microsoft-Antispam-PRVS: X-Exchange-Antispam-Report-Test: UriScan:(250305191791016)(180628864354917)(22074186197030); X-Exchange-Antispam-Report-CFA-Test: BCL:0; PCL:0; RULEID:(8211001083)(6040522)(2401047)(8121501046)(5005006)(93006095)(93001095)(10201501046)(3002001)(3231221)(944501244)(52105095)(6055026)(6041310)(20161123564045)(20161123562045)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(20161123560045)(20161123558120)(6072148)(201708071742011); SRVR:DB5PR08MB0632; BCL:0; PCL:0; RULEID:; SRVR:DB5PR08MB0632; X-Forefront-PRVS: 0610D16BBE X-Forefront-Antispam-Report: SFV:NSPM; SFS:(10009020)(39380400002)(39860400002)(396003)(366004)(346002)(376002)(377424004)(54534003)(189003)(199004)(50226002)(16526019)(81156014)(47776003)(186003)(7696005)(51416003)(316002)(6306002)(6486002)(5660300001)(1857600001)(26005)(386003)(86362001)(59450400001)(25786009)(52116002)(66066001)(48376002)(50466002)(16586007)(8676002)(81166006)(8936002)(3846002)(6116002)(97736004)(72206003)(478600001)(2906002)(68736007)(53936002)(36756003)(2351001)(6916009)(4326008)(106356001)(305945005)(7736002)(2361001)(105586002)(6666003)(2004002); DIR:OUT; SFP:1101; SCL:1; SRVR:DB5PR08MB0632; H:e112367-lin.warwick.arm.com; FPR:; SPF:None; PTR:InfoNoRecords; MX:1; A:1; LANG:en; Received-SPF: None (protection.outlook.com: arm.com does not designate permitted sender hosts) X-Microsoft-Exchange-Diagnostics: =?us-ascii?Q?1; DB5PR08MB0632; 23:5oCqqtSo1lacCg1MlGDNqfiBYtXPGnvq+2iC7qAEA?= =?us-ascii?Q?yXYUqdxBZb07OaHS4gfDnKmi4y5smLAu4hf/kveJ142PCXF2uIKoXa2mbJLG?= =?us-ascii?Q?hft8dNO/bep1ZEYXV0TdEQ/7hmfeCJ+I81aZtWwK1chIzNm9sJJ40dKejC9g?= =?us-ascii?Q?FJALEN2RAnoRWLqcD5dGomuFMK/eP+NxbcXhi4Gf2EXhCZtLuJR3wj7trjJK?= =?us-ascii?Q?rFqVPKhtZ54U0d/Aq0MrI9j0qdqGiwE0MlYUVNAgAp77jYj5cJGMzf38/VrW?= =?us-ascii?Q?Ax3cn0XpVIo6m3o3q9c2Xkv3XK9MEUdFIhBqRIuIO3xy30TMFvNK2mBktUYi?= =?us-ascii?Q?Z/eyxXU3vp6kj8Bx3TJAlwgcqum+fZh+3zxj1sE59kVm9zkkLxBzRPbTb12K?= =?us-ascii?Q?GvqiuDNu25hWf8NbPTe63N79MIuY7XnV/4na9AQIscVB7m3PC4Hh1lvWo+ou?= =?us-ascii?Q?/qAKSVolb5Xg+vJ0FUl/HW6ymUrSRACXrs2AIDTPGkTIbAaj+Ep+F4i+xrkr?= =?us-ascii?Q?g69uaiD0WZhlp8l9bnSTDnuGiZ+dMYPkXSqFyt3AV+oBsjf8nVx8donjTfdz?= =?us-ascii?Q?QvwmLElTxobh6HkfUrBYsO8lCS+Y8wayFuu0VEJmXajJKNltAWU62ot6cl/6?= =?us-ascii?Q?c90ENufcg6GoWCrk9So7ic933p0KNR0rA/yYJJhBMqxE9s3UXoS5S3YOTvxw?= =?us-ascii?Q?W7EkjMhzNQZyhsDOP/uWZSJa4r2YkW7qgcTBjiRN2edGhAaYUgzY5LQo/FUd?= =?us-ascii?Q?a1aA+P1Z+dJ+sl0bAsj7FLnxO8Q3oZvW52957yVcocWjlijPO8yUjYpE0Zis?= =?us-ascii?Q?WFZ1FW+VBLvDbLRIF8o2Fv2+CbZ/uiVFr38NKgL32PHxG0hHwpoGFextSl3d?= =?us-ascii?Q?BV1xVhZrzS896lfgAxGsZ0+HfUjSZNfwkac83JRZjTCZSEujK/gJ1CiAuL6b?= =?us-ascii?Q?2cYV4J3UUe66PN2ExZFiIQy6MFbfsGg5NkJK6hdhZcrcKztA5HjhOWAhDjX4?= =?us-ascii?Q?1MkFwJLNE0A7fHYQr5Ikqi+w8RJat7HtV2hpjjnWSPF88jvvSSYpvV1oCRI7?= =?us-ascii?Q?8A29KbFAC//jgfVgPza+np7+XSkhGoetm7UnU8thz3ut4huaFUItJzYUfRG6?= =?us-ascii?Q?AY3e6sEsJm1SzuJOZ9MjSws4bEa4n4RbDRom6vyqLtHmYqgRlWlYVeFyPC4G?= =?us-ascii?Q?heOIJl092kDXDuRdkhxKvLYzZvA6otjFf18iKB2qvRxzuDcxLlsbuT+ww=3D?= =?us-ascii?Q?=3D?= X-Microsoft-Antispam-Message-Info: YWE49xAX+s38rQTvxzZWrdAj75ynhohEzpLl9YoWYUO+PtHk5z4mDIKz40A0h+wWmMq3a0FUIGxKYbXuZmi/BrH1Bqm6JU3swA/x/d82Lh0HZcfhnmSAQXUVeCOjLFN3F04qSMuZZCZBIVEarkYsQWjSu0/mJNWBqiEpQp0S08eoo/8AsPw9eg4AGjEY7TJC X-Microsoft-Exchange-Diagnostics: 1; DB5PR08MB0632; 6:Rn2Qcaur5qDCHGa2gGE0bAXgTxGrKKunfcrx0OjJ0dXUO1T/8HD/CGP07zdfug/vDlVQ/yB/xHo4dYNR+Qn0gBlMeY7ZIYWe4TaLPbxzf0+QeHWOIGa4ARoQ6kZf4atMecDSYdWmA7JcFLSFXGK1ZO0KE0lGXhjpxSWQx1egkC1/SRUZxNE2hTVjrzXp7285mUskq0LjlkRJ9h9/yEEynZvClqSPbhHAmMBspAbaE56JYWwnkwBOoPn0eIz6DZaBNlL+Lioxyi7TrmSY3yGEFq0jX5OU7L0v3YnpfRcIY6CkzpjXtWHYZPdU8kjSFmHez+NV/bNTOYqNPnbxvM56loQmD6rmGMkRUxgq/5RCX6I=; 5:tPr7su6LKsbaeyFkGcfk1FsPMDVR/4z4FcusSVnw8xniV+heEGVENY8buf+NOxIzp9d4J6x+BbygiiRGfWneYxatu15LtGTPuskKHpXDNba7wxAkAuWTSicW6EZMO7zFlE0kLcJmSG9nOGmkBcMXgi49ke2jyLvq5MM+Tncoses=; 24:qvixCteZ2ygy1fnEgAEPyIDOvW+b7deM16FGX4ORWpGf9UVsTNeijybxTuoSzc/yTGfWA/QJ53DDe0rlGA+kXUd0CzwtZSkHF35g0ehqmms=; 7:s1Y8vr+p6Y/CdqXsmfjeA3d+4XTuF4g7trAivRn31D5U8nIJL4F3/C8wmDkWICV6CvGstPCiPRdEfU+Vci/tKW0LfJuvkfwyEkvvnN1425iQUH1g2kldCWwtDPrw9eq+liZSKVQ+/h30wp7VO5bvEIW5Q5UQaQr09SN+9xaHDSwK0j6WMiOBVTP1DKAwnXOXXB1Ih1XLZAsRHQHc8UfsOfQtqmesjxHr+lZWaF37DXRnPWy0MgFzfPARRhJeJXdo SpamDiagnosticOutput: 1:99 SpamDiagnosticMetadata: NSPM X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 13 Mar 2018 07:05:52.1377 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: fdba268d-ac0b-4757-7771-08d588b0dbb0 X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-CrossTenant-Id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-Transport-CrossTenantHeadersStamped: DB5PR08MB0632 X-IsSubscribed: yes 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-08 Stephen Roberts * 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/symtab.c | 32 ++++---- gdb/testsuite/gdb.perf/template-breakpoints.cc | 97 +++++++++++++++++++++++++ gdb/testsuite/gdb.perf/template-breakpoints.exp | 65 +++++++++++++++++ gdb/testsuite/gdb.perf/template-breakpoints.py | 33 +++++++++ 4 files changed, 211 insertions(+), 16 deletions(-) create mode 100644 gdb/testsuite/gdb.perf/template-breakpoints.cc create mode 100644 gdb/testsuite/gdb.perf/template-breakpoints.exp create mode 100644 gdb/testsuite/gdb.perf/template-breakpoints.py diff --git a/gdb/symtab.c b/gdb/symtab.c index 5671953..063c59f 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) { @@ -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; - for (i = 0; i < len; i++, item++) + auto PCCompare = [](const CORE_ADDR &pc, + 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; + }; - 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. */ /* 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. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see . */ + +#include + +template +struct ThirdDimension +{ + int + value () const + { + ThirdDimension d3; + return d3.value(); + } +}; + +template +struct ThirdDimension +{ + int + value () const + { + // Please note - this testcase sets a breakpoint on the following line. + // It is therefore sensitive to line numbers. If any changes are made to + // this file, please ensure that the testcase is updated to reflect this. + std::cout << "Value: " << VAL << std::endl; + return VAL; + } +}; + +template +struct SecondDimension +{ + int + value () const + { + SecondDimension d1; + ThirdDimension d2; + return d1.value() + d2.value(); + } +}; + +template +struct SecondDimension +{ + int + value () const + { + ThirdDimension d2; + return d2.value(); + } +}; + +template +struct FirstDimension +{ + int + value () const + { + FirstDimension d1; + SecondDimension d2; + return d1.value() + d2.value(); + } +}; + +template +struct FirstDimension<0, J, K, VAL> +{ + int + value () const + { + SecondDimension<0, J, K, VAL> d2; + return d2.value(); + } +}; + +int +main (int argc, char *argv[]) +{ + FirstDimension product; + std::cout << product.value() << std::endl; + return 0; +} 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. + +# This program is free software; you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation; either version 3 of the License, or +# (at your option) any later version. +# +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU General Public License for more details. +# +# You should have received a copy of the GNU General Public License +# along with this program. If not, see . + +# This test case is to test the performance of GDB when setting breakpoints +# on heavily temlatized C++ code. + +# Parameters: +# EXPANSION_DEPTH: knob to control how many times template expansions occur + +load_lib perftest.exp + +if [skip_perf_tests] { + return 0 +} + +standard_testfile .cc +set executable $testfile +set expfile $testfile.exp + +# make check-perf RUNTESTFLAGS='template-breakpoints.exp EXPANSION_DEPTH=40' +if ![info exists EXPANSION_DEPTH] { + set EXPANSION_DEPTH 40 +} + +PerfTest::assemble { + global EXPANSION_DEPTH + global srcdir subdir srcfile + + set compile_flags {c++ debug} + lappend compile_flags "additional_flags=-DEXPANSION_DEPTH=${EXPANSION_DEPTH}" + + if { [gdb_compile "$srcdir/$subdir/$srcfile" ${binfile} executable $compile_flags] != ""} { + return -1 + } + + return 0 +} { + global binfile + + clean_restart $binfile + + if ![runto_main] { + fail "can't run to main" + return -1 + } + + return 0 +} { + + gdb_test "python TemplateBreakpoints().run()" + + return 0 +} diff --git a/gdb/testsuite/gdb.perf/template-breakpoints.py b/gdb/testsuite/gdb.perf/template-breakpoints.py new file mode 100644 index 0000000..27f74ce --- /dev/null +++ b/gdb/testsuite/gdb.perf/template-breakpoints.py @@ -0,0 +1,33 @@ +# Copyright (C) 2016-2018 Free Software Foundation, Inc. + +# This program is free software; you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation; either version 3 of the License, or +# (at your option) any later version. +# +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU General Public License for more details. +# +# You should have received a copy of the GNU General Public License +# along with this program. If not, see . + +from perftest import perftest + +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() + + def _do_test(self, bpcount): + for _ in range(1, bpcount): + gdb.Breakpoint("template-breakpoints.cc:38").delete() + + def execute_test(self): + for bpcount in range(1, 10): + tfunc = lambda bound_bpcount=bpcount: self._do_test(bound_bpcount) + self.measure.measure(tfunc, bpcount)