From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from EUR05-AM6-obe.outbound.protection.outlook.com (mail-am6eur05olkn2049.outbound.protection.outlook.com [40.92.91.49]) by sourceware.org (Postfix) with ESMTPS id 9D0D3393FC25 for ; Thu, 19 Mar 2020 01:33:17 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 9D0D3393FC25 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=QQkQ/+FFQrIjt8biJrJuE5cz8sq+bYZQKmZfNZ6+ktXW/jeLPrJfFhqPOHW+7F3u5q45sCiDKkBCWgaCvH4gTME3A6fbLlEs9uB+jaaiuadvEqVDrGm8v0aZDAi+JaKKbqY5pHNceSWJERVhYzqK7ljFbsFooCW2EVyiTNE2bt4J7n1vXC4NM1OneVbBalpkBOmayDCMkhvFPBu3wTLp17TnIV7ClCFW1i6ZRyxDc0WLTZ7GzWkzWD7Zk3zPOQjUdFfLksoNiTrBS+xdrGfkk83/lShnaUjX2NqrMNuZeKnQHop7XIey6kBL0LR8ZPg2kdXlMjcwVZDxHJUS0eKXwg== 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=Qcxhq0ZXG/m2ZlCfSoK8gsb165CC6bv1IgyXSES0O+k=; b=iVYjrKFwsldSxsckC0xZN7H+PxAdLOv0nkVhUri3RBpOICUMdcRW92oP5GRhkscTMwRdErc6tjWlgY2F28E45v/JmlEs3wJsaZBiQDMPEIo7oxUelFMf03RGxJNA0dEt6sinSDRRO79er2qaGNxuO7abPlGqUMc4PL7xlAstjFvUsQeCNeHkeBpuzPQRiNsfuwH2PVqE5VsxSNQkCDD5x6AI7CHid+TyahcD9xjZqdnp5uPYenoseOuqWDZ5T4LWvx1ZuzK05krLpE0KJvgmRy2HWp4Q1yYKCHlhd3WXUSLL6kD1ifficpgpYod0k8prbqUERPwuEzPrOD7r3CDhSA== 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 DB8EUR05FT039.eop-eur05.prod.protection.outlook.com (2a01:111:e400:fc0f::3b) by DB8EUR05HT062.eop-eur05.prod.protection.outlook.com (2a01:111:e400:fc0f::258) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.2814.13; Thu, 19 Mar 2020 01:33:15 +0000 Received: from AM6PR03MB5170.eurprd03.prod.outlook.com (10.233.238.55) by DB8EUR05FT039.mail.protection.outlook.com (10.233.238.233) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.2814.13 via Frontend Transport; Thu, 19 Mar 2020 01:33:15 +0000 X-IncomingTopHeaderMarker: OriginalChecksum:6F8D7EA4DDABC167713BF86B4AD6838B69A800E08B02D5E73AB087DB4D2C0F6B; UpperCasedChecksum:919F2E97A5328F2F80219DA8F468B1484B0C39F0DBB9E58DB052984BC399559F; SizeAsReceived:8669; 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.017; Thu, 19 Mar 2020 01:33:15 +0000 Subject: Re: [PATCHv3] Fix range end handling of inlined subroutines To: Andrew Burgess Cc: Christian Biesinger , "gdb-patches@sourceware.org" References: <94e33268f64060fc887670f4ee5ed524050cbcc7.1580902412.git.andrew.burgess@embecosm.com> <20200311220231.GJ3317@embecosm.com> <20200317222757.GN3317@embecosm.com> From: Bernd Edlinger Message-ID: Date: Thu, 19 Mar 2020 02:33:14 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.6.1 In-Reply-To: <20200317222757.GN3317@embecosm.com> Content-Type: text/plain; charset=windows-1252 Content-Language: en-US Content-Transfer-Encoding: 7bit X-ClientProxiedBy: ZR0P278CA0020.CHEP278.PROD.OUTLOOK.COM (2603:10a6:910:1c::7) To AM6PR03MB5170.eurprd03.prod.outlook.com (2603:10a6:20b:ca::23) X-Microsoft-Original-Message-ID: <50225880-e6c9-cf87-17e1-e5c15e9510e7@hotmail.de> MIME-Version: 1.0 X-MS-Exchange-MessageSentRepresentingType: 1 Received: from [192.168.1.101] (92.77.140.102) by ZR0P278CA0020.CHEP278.PROD.OUTLOOK.COM (2603:10a6:910:1c::7) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.2835.18 via Frontend Transport; Thu, 19 Mar 2020 01:33:15 +0000 X-Microsoft-Original-Message-ID: <50225880-e6c9-cf87-17e1-e5c15e9510e7@hotmail.de> X-TMN: [Mw+42O8FWzborb7m0DwX+0B+iXxnNK+P] X-MS-PublicTrafficType: Email X-IncomingHeaderCount: 50 X-EOPAttributedMessage: 0 X-MS-Office365-Filtering-Correlation-Id: 863ed05d-a3c8-4936-9485-08d7cba57ec2 X-MS-TrafficTypeDiagnostic: DB8EUR05HT062: X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: x3cRtkJ6iwpcLquueHce0LUaDzfHDvKB0A/TvyQH8zIPH0qTt33IVffmul0wlCIPewjv5YaJqd0ArfcdGV4bIv+CUaOhXGElbc6CMB6OIvHaLzFOJ5WUzSmYMP1PfU2C+nRyzyep3wZFEbkSQvCJOrPT7k/Z3lOwTnkn+CCrXpGRdYCadzdvk1nPeDSB8W+Y9gJF16MoTFBXG47fx5gG4onizqz6xOwr97eeyVz8ack= X-MS-Exchange-AntiSpam-MessageData: NIfLQyQDxQ3z14pYeG9tMerIrPQhCphhQBU/e/f4w7eWZxbbXiCsbWiOZ2doBgK5sfvWPZQdm1oB4uRHG4XeFKFxvc/s1DaXr9YTBsIDxdizgKfLr17uuNlq81ON93JhoV1hpfWC2/Xr24m2ZA7sJA== X-OriginatorOrg: outlook.com X-MS-Exchange-CrossTenant-Network-Message-Id: 863ed05d-a3c8-4936-9485-08d7cba57ec2 X-MS-Exchange-CrossTenant-OriginalArrivalTime: 19 Mar 2020 01:33:15.8195 (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: DB8EUR05HT062 X-Spam-Status: No, score=-12.7 required=5.0 tests=FORGED_MUA_MOZILLA, FREEMAIL_FROM, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_DMARC_STATUS, MSGID_FROM_MTA_HEADER, RCVD_IN_DNSWL_NONE, SPF_HELO_PASS, SPF_PASS 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: Thu, 19 Mar 2020 01:33:19 -0000 On 3/17/20 11:27 PM, Andrew Burgess wrote: > * Bernd Edlinger [2020-03-13 09:03:15 +0100]: > >> 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 :( > > 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)? Thanks Bernd.