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

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

On 3/17/20 11:27 PM, Andrew Burgess wrote:
> * 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?
> 

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.