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

[Bernd Edlinger <bernd.edlinger@hotmail.de>]

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 :(


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.