From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from EUR04-VI1-obe.outbound.protection.outlook.com (mail-oln040092075093.outbound.protection.outlook.com [40.92.75.93]) by sourceware.org (Postfix) with ESMTPS id 59156385E01A for ; Mon, 23 Mar 2020 20:58:15 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 59156385E01A Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=hotmail.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=bernd.edlinger@hotmail.de ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=lGxsADV4wqC2YgBKwkI6MXJiMwIrusAonIBBIbtMz2/NcPhUFAGYWiDlf6x5TkvG6NV/KBP9ij+9tYLfP30vGrZnFN038O2B9RQBkAiltRf015iY2DnHuBVEXinxJ9/vYIxyfchcZ+819jLnwd+oEHtMBTpKDh0Oe3oH0YHg58LCutdMoAlMOwq5ObrqilUNz1OmoCViemqprMmOBp/VxvFrahgS0mYTWvtWU9VNsldx6arR5IWI0aPj7WdAkF/tf3bwbz7ABCw+rxGWAhNAya96iJJlfYx0ocbdDqakcv9WHHGRi5iY/pOAD2hq9TiqaRmyHVdb/iMl1s+4X/lCRw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=3rhgMVmPYTppjkqWa5H1dW1unXch3QC2s0yoRULdaoA=; b=EJ2mIflJriAqCTAcdfhdnXiB2LJDPtL/5XOH2fnVzVD+anj29mmoIbPbDzILAZoDveU6AF9t9TG48fn6PbYub9Fsj4g6KvA1B5vviJTZFQrz2J4EUDTOfeE6+tDjQNDRrvG+Dfme7hqdvO179meSaB9ofWV3fdTzv6LL0r0eDpGmd16UeLT9xGt5fQvWCbS5PGbN7571pXM8ydozsWYLPddWUhzsyPFpVlwe+ykjmDBjky/CxA4CRqxmZc7PpFmbImtEeTKf4bPlo19Fig+zuWylfVRqYHHYwrCxmPtScnlwnmYe+At8vdHr64svfcG+DYtKzLSXGjitkcnmPHuxSA== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=hotmail.de; dmarc=pass action=none header.from=hotmail.de; dkim=pass header.d=hotmail.de; arc=none Received: from HE1EUR04FT055.eop-eur04.prod.protection.outlook.com (2a01:111:e400:7e0d::3c) by HE1EUR04HT035.eop-eur04.prod.protection.outlook.com (2a01:111:e400:7e0d::317) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.2814.13; Mon, 23 Mar 2020 20:58:13 +0000 Received: from AM6PR03MB5170.eurprd03.prod.outlook.com (10.152.26.60) by HE1EUR04FT055.mail.protection.outlook.com (10.152.27.44) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.2814.13 via Frontend Transport; Mon, 23 Mar 2020 20:58:13 +0000 X-IncomingTopHeaderMarker: OriginalChecksum:BC98774D1C75EF0D09C9AE7EC4BA584BDDA46A0493E1244A668FE95D22FAFBCF; UpperCasedChecksum:E74259E35086394FAFB2BFF40FBC50D513F89CF4F7732E89B190AC3B12EF978A; SizeAsReceived:8730; Count:50 Received: from AM6PR03MB5170.eurprd03.prod.outlook.com ([fe80::1956:d274:cab3:b4dd]) by AM6PR03MB5170.eurprd03.prod.outlook.com ([fe80::1956:d274:cab3:b4dd%6]) with mapi id 15.20.2835.021; Mon, 23 Mar 2020 20:58:13 +0000 Subject: Re: [PATCHv3] Fix range end handling of inlined subroutines To: Andrew Burgess Cc: Christian Biesinger , "gdb-patches@sourceware.org" References: <20200311220231.GJ3317@embecosm.com> <20200317222757.GN3317@embecosm.com> <20200323175320.GR3317@embecosm.com> From: Bernd Edlinger Message-ID: Date: Mon, 23 Mar 2020 21:58:11 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.6.1 In-Reply-To: <20200323175320.GR3317@embecosm.com> Content-Type: text/plain; charset=windows-1252 Content-Language: en-US Content-Transfer-Encoding: 7bit X-ClientProxiedBy: ZR0P278CA0028.CHEP278.PROD.OUTLOOK.COM (2603:10a6:910:1c::15) To AM6PR03MB5170.eurprd03.prod.outlook.com (2603:10a6:20b:ca::23) X-Microsoft-Original-Message-ID: <3d181947-4255-5f77-69c6-502238946685@hotmail.de> MIME-Version: 1.0 X-MS-Exchange-MessageSentRepresentingType: 1 Received: from [192.168.1.101] (92.77.140.102) by ZR0P278CA0028.CHEP278.PROD.OUTLOOK.COM (2603:10a6:910:1c::15) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.2835.19 via Frontend Transport; Mon, 23 Mar 2020 20:58:12 +0000 X-Microsoft-Original-Message-ID: <3d181947-4255-5f77-69c6-502238946685@hotmail.de> X-TMN: [d3EJF11RhH6Zo92LneNbF2DLyZSRIk/B] X-MS-PublicTrafficType: Email X-IncomingHeaderCount: 50 X-EOPAttributedMessage: 0 X-MS-Office365-Filtering-Correlation-Id: 544e17a0-becc-45f1-45f3-08d7cf6ce6e2 X-MS-TrafficTypeDiagnostic: HE1EUR04HT035: X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: gnHsZfcEWoN0I5h5212zyAeXgesT+GENXk+7l2Of1XkvPafWZ0/3iBsrkrKSu7QPWPklLxRg0z7iA9lc50qg5seQYKKHprWqVCI1TIzMySRyC5xmYRHxz0Zwfs7gIa9HzM3lOgEC78NDVZXmBXkd0kqctdi4y66Nvl+PiWAlKSxS/oiQ2bUIS/gJnZ6OezAY X-MS-Exchange-AntiSpam-MessageData: y2UndyMON7rng9mf98UFXo2hZNw9rlD7KLHsMgECRFq5wLsGQxmUVDnJgzW4giZ0te7Uu41oIu+8m8Vcswy7z/zcZNStWdaU2usLHe6uxTpuISMHIvfAf3SGTIUHjrOBWBX0j5PbIceKft21PgJnjg== X-OriginatorOrg: outlook.com X-MS-Exchange-CrossTenant-Network-Message-Id: 544e17a0-becc-45f1-45f3-08d7cf6ce6e2 X-MS-Exchange-CrossTenant-OriginalArrivalTime: 23 Mar 2020 20:58:13.7528 (UTC) X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-CrossTenant-Id: 84df9e7f-e9f6-40af-b435-aaaaaaaaaaaa X-MS-Exchange-CrossTenant-FromEntityHeader: Internet X-MS-Exchange-CrossTenant-RMS-PersistedConsumerOrg: 00000000-0000-0000-0000-000000000000 X-MS-Exchange-Transport-CrossTenantHeadersStamped: HE1EUR04HT035 X-Spam-Status: No, score=-24.1 required=5.0 tests=BAYES_00, FORGED_MUA_MOZILLA, FREEMAIL_FROM, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_DMARC_STATUS, MSGID_FROM_MTA_HEADER, RCVD_IN_BARRACUDACENTRAL, RCVD_IN_DNSWL_NONE, SPF_HELO_PASS, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: gdb-patches@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gdb-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 23 Mar 2020 20:58:18 -0000 On 3/23/20 6:53 PM, Andrew Burgess wrote: > * Bernd Edlinger [2020-03-21 21:31:07 +0100]: > >> On 3/19/20 2:33 AM, Bernd Edlinger wrote: >>> On 3/17/20 11:27 PM, Andrew Burgess wrote: >>>> >>>> Are you arguing that we shouldn't use std::vector anywhere in GDB? Or >>>> that this particular piece of code shouldn't use std::vector? >>>> >>> >>> No, in general std::vector is just fine. >>> I think just here it is especially important to be below O(n*log(n)), >>> and don't depend on the underlying implementation. >>> >>>> It was my understanding that we were moving GDB away from bespoke >>>> container management code unless there was a very compelling reason. >>>> I think as a minimum any new code that was written not using std:: >>>> data structures (or some other gdb specific type) would need a comment >>>> explaining why, if nothing else to stop someone replacing the code >>>> with std:: types a few months down the line. >>>> >>> >>> Right, good point. >>> I can add a comment here, so that will not happen: >>> >>> index 46f985a..4f0d536 100644 >>> --- a/gdb/buildsym.c >>> +++ b/gdb/buildsym.c >>> @@ -736,6 +736,10 @@ struct blockvector * >>> void >>> buildsym_compunit::record_inline_range_end (CORE_ADDR end) >>> { >>> + /* The performance of this function is very important, >>> + it shall be O(n*log(n)) therefore we do not use std::vector >>> + here since some compilers, e.g. visual studio, do not >>> + guarantee that for vector::push_back. */ >>> if (m_inline_end_vector == nullptr) >>> { >>> m_inline_end_vector_length = INITIAL_LINE_VECTOR_LENGTH; >>> >>> >>> Does that look good (also from the english)? >>> >> >> Hi Andrew, >> >> how are you doing? >> >> are you ok? > > Sorry, I have not been ignoring this patch. It is top of my review > stack. It is being held up for a number of reasons, first Tom found a > number of issues with the original patch set, I've been trying to fix > these before reviewing your work in case the fixes had an impact. > > I posted some patches for the easier of the issues, but I've not > solved the harder bug yet. I'm pretty much decided to just go ahead > and review this patch anyway. I've probably lost track, what was the harder bug? > > But then, I'm still struggling with the choice not to use > std::vector. It's still not clear if there's actually a good reason > to avoid it in this case or not, so I feel I need to review other uses > of std::vector throughout GDB and see how your use compares. Do you > maybe have some performance figures you could share to help make the > case for using custom container type? > Sure, probably not as impressive as I thought, but nevertheless, the number of subroutines depends only on the debug-info, and I am not sure if the difference can be even higher depenent on the how the debug info looks exactly. What I did is compare a O(nlogn) vs. O(n^2) implementation which mimics the visual studio std::vector: diff --git a/gdb/buildsym.c b/gdb/buildsym.c index ae730e3..02ef2b8 100644 --- a/gdb/buildsym.c +++ b/gdb/buildsym.c @@ -746,19 +746,15 @@ struct blockvector * it shall be O(n*log(n)) therefore we do not use std::vector here since some compilers, e.g. visual studio, do not guarantee that for vector::push_back. */ - if (m_inline_end_vector == nullptr) - { - m_inline_end_vector_length = INITIAL_LINE_VECTOR_LENGTH; - m_inline_end_vector = (CORE_ADDR *) - xmalloc (sizeof (CORE_ADDR) * m_inline_end_vector_length); - m_inline_end_vector_nitems = 0; - } - else if (m_inline_end_vector_nitems == m_inline_end_vector_length) + CORE_ADDR *old_vec = m_inline_end_vector; + m_inline_end_vector_length ++; + m_inline_end_vector = (CORE_ADDR *) + xmalloc (sizeof (CORE_ADDR) * m_inline_end_vector_length); + + if (m_inline_end_vector_length > 1) { - m_inline_end_vector_length *= 2; - m_inline_end_vector = (CORE_ADDR *) - xrealloc ((char *) m_inline_end_vector, - sizeof (CORE_ADDR) * m_inline_end_vector_length); + memcpy(m_inline_end_vector, old_vec, sizeof(CORE_ADDR) * (m_inline_end_vector_length-1)); + xfree(old_vec); } m_inline_end_vector[m_inline_end_vector_nitems++] = end; make CFLAGS="-O2 -g -pg" CXXFLAGS="-O2 -g -pg" LDFLAGS="-g -pg" V=1 -j4 perf0.txt is O(nlogn) perf1.txt is O(n^2) % cumulative self self total time seconds seconds calls s/call s/call name perf0.txt: 0.00 4.43 0.00 33327 0.00 0.00 buildsym_compunit::record_inline_range_end(unsigned long) perf1.txt: 0.00 5.91 0.00 33327 0.00 0.00 buildsym_compunit::record_inline_range_end(unsigned long) so the function was called 33327 times, this O(nlogn) took 4.43 seconds and O(n^2) took 5.91 seconds. I think I cannot attach the perf0/1.txt because they are 2.8 MB each, but if you like to look at them I can upload to my skydrive. > Then the whole converting is_stmt entries to !is_stmt is still > concerning me. I appreciate your expanded text in the patch > description, but I need to do more testing to see the real impact of > this change. Most of my clients are driving GDB through some kind of > GUI, which means that break points are inevitably placed using > file:line sytnax. One of the most common complaints I get is when a > breakpoint is placed on one line, but GDB stops on another. Generally > my users can be quite forgiving of missing stack frames when inlining > is in play. What this means is an argument of if you did break here > you'd have a frame missing, so I'm not going to let you break there > any more isn't that compelling to me. > Note that your other patch is also deleting is-stmt locations, because the switching between the different cu's does that with the end-marker. > That isn't a rejection of the patch, it's just me explaining why it's > taking me some time to review. > Absolutely, no problem, we are not in a hurry. And thanks for all your time, and good co-operation. Thanks Bernd.