Re: [PATCHv3] Fix range end handling of inlined subroutines

[Andrew Burgess <andrew.burgess@embecosm.com>]

* Bernd Edlinger <bernd.edlinger@hotmail.de> [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
> > <bernd.edlinger@hotmail.de> 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 <vector>
> 
> int main()
> {
>   int i, m = 1000000;
>   stc::vector<int> 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