From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from EUR03-VE1-obe.outbound.protection.outlook.com (mail-oln040092072015.outbound.protection.outlook.com [40.92.72.15]) by sourceware.org (Postfix) with ESMTPS id B3A71393742C for ; Fri, 13 Mar 2020 08:03:19 +0000 (GMT) ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=IIYmbqeywhH3YibZ/9bs6tVYQImvOogakIZuybVVN8wKTMSca6O+2neTL9cioRDDZGyXJxnMeyDNNGDXGIGQkO2JXxKaAmuMShClvU6JRYA70s97Cm1QoYK6C1LXY88kVkycN2XL2rtGU++SjpX5vYVpAvvOKmmifFXObTZ0ctalDAkH4fhR3vJl4unWdAFBZ6TYKO6IG/vLHY7zWV5rxRSTAkwYznBxTP+/4ptPnVvWcrw6ge2W/znWd2OfmPN0xwufEV9EAFeojl7gbdBwsZBl0b/x+J1gAsGH62SGEO2k7Pj32BUPO/aXt/jSjLp2DOKRVYWA9teVh2V3bTHJKQ== 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=lq6JYrpPLQu/DtcYTW+4HwmR33d9b5jcD17ZIPlejFU=; b=RN797JkQ1H6/VNipkhh41VJ8mgFVIMY9+wfpdIp8Ma0LfTd9YcpJvdDumNN9OAvmQ5cGiBeSZVRBRFwMkipbmGxnfuzVlZZ5zIqDROpZ1CkwgkGv5DA34Wp8S5nsy0UAkFIyyOs86OxqrsDaSGITpbeiRriLFygaQeXVWNq0FDNhtA0cMvDE9/ET37N2vfPd/YGyzchpQxu7lZHljuF2sT2JTXXa+ON4x/qg1LHfKABAXPC+ukPzAdERKmi+FUnnchVvnfkzue8lIOCduhfHWcH0VEp14YoLSBDJhr+V8dwdM+KpArbhRX+heFSRdJ1H7CGk2IgLzW20pssz4Or+Mg== 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 VE1EUR03FT009.eop-EUR03.prod.protection.outlook.com (2a01:111:e400:7e09::37) by VE1EUR03HT125.eop-EUR03.prod.protection.outlook.com (2a01:111:e400:7e09::497) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.2814.13; Fri, 13 Mar 2020 08:03:17 +0000 Received: from AM6PR03MB5170.eurprd03.prod.outlook.com (10.152.18.56) by VE1EUR03FT009.mail.protection.outlook.com (10.152.18.92) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.2814.13 via Frontend Transport; Fri, 13 Mar 2020 08:03:17 +0000 X-IncomingTopHeaderMarker: OriginalChecksum:F8E762FEB95697BE3BDE63DED0B1B5B0BC6EC3DB8A0ED299A7F9475982165729; UpperCasedChecksum:7F9B3476555DE3B05919181CF4D0020C127141D24027754BD31DE106B1A3295F; SizeAsReceived:9427; 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.2793.021; Fri, 13 Mar 2020 08:03:17 +0000 Subject: Re: [PATCHv3] Fix range end handling of inlined subroutines To: Christian Biesinger Cc: Andrew Burgess , "gdb-patches@sourceware.org" References: <94e33268f64060fc887670f4ee5ed524050cbcc7.1580902412.git.andrew.burgess@embecosm.com> <20200311220231.GJ3317@embecosm.com> From: Bernd Edlinger Message-ID: Date: Fri, 13 Mar 2020 09:03:15 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.6.1 In-Reply-To: Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 7bit X-ClientProxiedBy: AM3PR07CA0091.eurprd07.prod.outlook.com (2603:10a6:207:6::25) To AM6PR03MB5170.eurprd03.prod.outlook.com (2603:10a6:20b:ca::23) X-Microsoft-Original-Message-ID: <4306d321-2766-572d-55f7-93de17b31bfa@hotmail.de> MIME-Version: 1.0 X-MS-Exchange-MessageSentRepresentingType: 1 Received: from [192.168.1.101] (92.77.140.102) by AM3PR07CA0091.eurprd07.prod.outlook.com (2603:10a6:207:6::25) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.2835.7 via Frontend Transport; Fri, 13 Mar 2020 08:03:16 +0000 X-Microsoft-Original-Message-ID: <4306d321-2766-572d-55f7-93de17b31bfa@hotmail.de> X-TMN: [U6Xhu/LeSmiOQr1Ah25uia6Wk35kf39+] X-MS-PublicTrafficType: Email X-IncomingHeaderCount: 50 X-EOPAttributedMessage: 0 X-MS-Office365-Filtering-Correlation-Id: df5e508b-c51e-444c-7d58-08d7c724fca4 X-MS-TrafficTypeDiagnostic: VE1EUR03HT125: X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: 4jOaC+ukQ1ZujZRr/BIJWm/knprvXmLFBve0NzxieiagUw7bZtn6iOaoarBlupR85BM5qqiqsNOIeTgcf+b/lYyhPdh0zVbFJ+UocHaudRr0EP1al0wkRrHa+b8ERDPMR4tuo61wQqoQJ7mHYVNTDbJa0tHD9pBvXopwGleudHNKP2sDVtqfNfxWaqlN4ORRiitSjI1JI2ScsYKjNhGmc1W/W0N6Wi++5QMw7Ns2uc8= X-MS-Exchange-AntiSpam-MessageData: yi+o0X5sGpuhjoKvTIZFfKPccG96fixKYubovpQJEg7NzeF2DSEry1r5aikXInHTR17VLouhWyfjU5Z9uaQJILn3ev5W65Nur9RI7nqH4+GS9NvD9nACUn6frXkWv64R9Ou+AsdcqwW0qh9XyJvz2g== X-OriginatorOrg: outlook.com X-MS-Exchange-CrossTenant-Network-Message-Id: df5e508b-c51e-444c-7d58-08d7c724fca4 X-MS-Exchange-CrossTenant-OriginalArrivalTime: 13 Mar 2020 08:03:17.7836 (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: VE1EUR03HT125 X-Spam-Status: No, score=0.4 required=5.0 tests=BAYES_00, FORGED_MUA_MOZILLA, FREEMAIL_FROM, MSGID_FROM_MTA_HEADER, RCVD_IN_DNSWL_NONE, SPF_HELO_PASS, SPF_PASS autolearn=no 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: Fri, 13 Mar 2020 08:03:21 -0000 On 3/12/20 7:27 PM, Christian Biesinger wrote: > On Thu, Mar 12, 2020 at 1:21 PM Bernd Edlinger > wrote: >> >> I am worried that the vector is not as efficient as it is necessary here. >> I know for instance that a straight forward >> >> m_inline_end_vector.push_back(pc); >> >> has often an O(n^2) complexity alone for this adding new elements, >> (and it can throw, which makes error handling a mess). > > push_back is not O(n^2). See > https://en.cppreference.com/w/cpp/container/vector/push_back: > "Complexity > Amortized constant" > > That's because it doubles the capacity whenever it has to resize. > > Christian > While that may be true for g++, this is not the case for all compilers. If you don't know which compiler will be used, (gcc, clang, diab, msvc to name a few) you cannot rely on that. I just repeated what I already learned the hard way, and tried the following #include int main() { int i, m = 1000000; stc::vector v; for (i = 0; i < m; i++) v.push_back(i); return 0; } Compiled it with visual studio 2010, and see it take a mutex 1 million times, allocate each time only one element more, does not use realloc so must move in every case. All in all, for a performance critical part in the software like this, I would not recommend to use a component where it depends so much on the compiler and the implementation details of the stl library. A similar surprise happens with stl::list's size(), which may be O(1) or O(n) is even documented that way. So that is my personal experience, in that field. And bad experiences last longer in my memory than good ones :( Bernd. >> But the performance of this table need to be O(n * log(n)) >> since n is often around 1.000.000 (when I debug large >> apps like gcc). >> >> A previous version of this patch used O(n^2) and was exactly doubling >> the execution time for loading of the debug info (for debugging gcc's cc1). >> Although that appears to be already done incrementally. >> >> >> Bernd.