From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wr1-x444.google.com (mail-wr1-x444.google.com [IPv6:2a00:1450:4864:20::444]) by sourceware.org (Postfix) with ESMTPS id 8E441381DCDF for ; Tue, 17 Mar 2020 22:27:59 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 8E441381DCDF Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=embecosm.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=andrew.burgess@embecosm.com Received: by mail-wr1-x444.google.com with SMTP id w16so11425274wrv.13 for ; Tue, 17 Mar 2020 15:27:59 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=embecosm.com; s=google; h=date:from:to:cc:subject:message-id:references:mime-version :content-disposition:in-reply-to:user-agent; bh=ntIb1gB54ph31LqF4cH6B9ICZfZvnnm+t9h3y3bAsZw=; b=WmEDOoXasN5xoVXRyYYEAqJIlYkmQaHKAIiXZsmybs9XVVHgBaLwhC3azF5IVSVWJB 5ZOud6ZfgejEFICv4VRe9rcr3J2bohZFtnN6pzoEomGTbLgqVS89HEIeXyBfoMJcLpP7 O/gaXHiYYfCfnpw4S5G+IpU2bS1tTpKXE3dF4VVW0fHE7zsPRXZyhLIjL+vLcpIqBOw/ VHSwrxf5AmzO3VV2oah1dkHOAlUa1AGXrRzOqNGZWPucCq3RIIO5YG+egn+b7XRKoY1Y juc9Nyxh7QOtQ/wiqGySadjPzd/QmvizsUT9H4BLJ4ZarIcybrBbKUiHzUQcypKzhPut 4u8Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:subject:message-id:references :mime-version:content-disposition:in-reply-to:user-agent; bh=ntIb1gB54ph31LqF4cH6B9ICZfZvnnm+t9h3y3bAsZw=; b=hGGp8fgsSo99pcPt4dxKnhcv8h0tOpnYVnsO5FVU7QRASe8NiSEjWZxtFN5vD/mLC6 7HXwBt2Qo8/vWKx9vV5/QsnmImukurr1JYHGpM+vVYyE6Xt3CyXHkNmq1+u/7BIaWzz+ lwj1tS57ByiTetk7YoiHEiJsZCR6KFtH7K3KxY6Y3wGaCyOHorAD4EMmsWibqSQ+LDgx j4JdCMgYP3Csru36gATjQHum3IofV4M35N2QAblgNaOY4A0/RQtoubTxy3dINIlifIgd /p3UInH8i7bpnwWiUB8buqglQcr5KSm3GChDMiubv2iY/G/EROcaFEl2pmFq93B/UA5a Z2ew== X-Gm-Message-State: ANhLgQ2Afs1HIzSf0G902Cgz/J/fuLHz3NX/l7EKxcPzH+cAj5YXEeGZ 5WUh5/HLcYECWgr22nIcjCpSyrs3LOQ= X-Google-Smtp-Source: ADFU+vtr9E7YmsmdoPd33sfpE2Msh9EF2d2vnsivj8JuOXF71pNVj5htG6VlKPBRNxSJmXbnZ0+1LA== X-Received: by 2002:a05:6000:10d:: with SMTP id o13mr1216357wrx.84.1584484078616; Tue, 17 Mar 2020 15:27:58 -0700 (PDT) Received: from localhost (host86-180-62-221.range86-180.btcentralplus.com. [86.180.62.221]) by smtp.gmail.com with ESMTPSA id k133sm1130274wma.11.2020.03.17.15.27.57 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Tue, 17 Mar 2020 15:27:57 -0700 (PDT) Date: Tue, 17 Mar 2020 22:27:57 +0000 From: Andrew Burgess To: Bernd Edlinger Cc: Christian Biesinger , "gdb-patches@sourceware.org" Subject: Re: [PATCHv3] Fix range end handling of inlined subroutines Message-ID: <20200317222757.GN3317@embecosm.com> References: <94e33268f64060fc887670f4ee5ed524050cbcc7.1580902412.git.andrew.burgess@embecosm.com> <20200311220231.GJ3317@embecosm.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: X-Operating-System: Linux/4.18.19-100.fc27.x86_64 (x86_64) X-Uptime: 22:22:55 up 32 days, 9:51, X-Fortune: Your password is pitifully obvious. X-Editor: GNU Emacs [ http://www.gnu.org/software/emacs ] User-Agent: Mutt/1.9.2 (2017-12-15) X-Spam-Status: No, score=-0.2 required=5.0 tests=DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, 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: Tue, 17 Mar 2020 22:28:02 -0000 * 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? 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. Thanks, Andrew