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

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

On 3/23/20 6:53 PM, Andrew Burgess wrote:
> * Bernd Edlinger <bernd.edlinger@hotmail.de> [2020-03-21 21:31:07 +0100]:
> 
>> On 3/19/20 2:33 AM, Bernd Edlinger wrote:
>>> On 3/17/20 11:27 PM, Andrew Burgess wrote:
>>>>
>>>> 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)?
>>>
>>
>> Hi Andrew,
>>
>> how are you doing?
>>
>> are you ok?
> 
> Sorry, I have not been ignoring this patch.  It is top of my review
> stack.  It is being held up for a number of reasons, first Tom found a
> number of issues with the original patch set, I've been trying to fix
> these before reviewing your work in case the fixes had an impact.
> 
> I posted some patches for the easier of the issues, but I've not
> solved the harder bug yet.  I'm pretty much decided to just go ahead
> and review this patch anyway.

I've probably lost track, what was the harder bug?

> 
> But then, I'm still struggling with the choice not to use
> std::vector.  It's still not clear if there's actually a good reason
> to avoid it in this case or not, so I feel I need to review other uses
> of std::vector throughout GDB and see how your use compares.  Do you
> maybe have some performance figures you could share to help make the
> case for using custom container type?
> 

Sure, probably not as impressive as I thought, but nevertheless,
the number of subroutines depends only on the debug-info, and
I am not sure if the difference can be even higher depenent on the
how the debug info looks exactly.

What I did is compare a O(nlogn) vs. O(n^2) implementation
which mimics the visual studio std::vector:

diff --git a/gdb/buildsym.c b/gdb/buildsym.c
index ae730e3..02ef2b8 100644
--- a/gdb/buildsym.c
+++ b/gdb/buildsym.c
@@ -746,19 +746,15 @@ struct blockvector *
      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;
-      m_inline_end_vector = (CORE_ADDR *)
-       xmalloc (sizeof (CORE_ADDR) * m_inline_end_vector_length);
-      m_inline_end_vector_nitems = 0;
-    }
-  else if (m_inline_end_vector_nitems == m_inline_end_vector_length)
+  CORE_ADDR *old_vec = m_inline_end_vector;
+  m_inline_end_vector_length ++;
+  m_inline_end_vector = (CORE_ADDR *)
+    xmalloc (sizeof (CORE_ADDR) * m_inline_end_vector_length);
+
+  if (m_inline_end_vector_length > 1)
     {
-      m_inline_end_vector_length *= 2;
-      m_inline_end_vector = (CORE_ADDR *)
-       xrealloc ((char *) m_inline_end_vector,
-                 sizeof (CORE_ADDR) * m_inline_end_vector_length);
+      memcpy(m_inline_end_vector, old_vec, sizeof(CORE_ADDR) * (m_inline_end_vector_length-1));
+      xfree(old_vec);
     }
 
   m_inline_end_vector[m_inline_end_vector_nitems++] = end;


make CFLAGS="-O2 -g -pg" CXXFLAGS="-O2 -g -pg" LDFLAGS="-g -pg" V=1 -j4

perf0.txt is O(nlogn)
perf1.txt is O(n^2)

             %   cumulative   self              self     total           
            time   seconds   seconds    calls   s/call   s/call  name    

perf0.txt:  0.00      4.43     0.00    33327     0.00     0.00  buildsym_compunit::record_inline_range_end(unsigned long)
perf1.txt:  0.00      5.91     0.00    33327     0.00     0.00  buildsym_compunit::record_inline_range_end(unsigned long)


so the function was called 33327 times, this O(nlogn) took 4.43 seconds
and O(n^2) took 5.91 seconds.

I think I cannot attach the perf0/1.txt because they are 2.8 MB each,
but if you like to look at them I can upload to my skydrive.


> Then the whole converting is_stmt entries to !is_stmt is still
> concerning me.  I appreciate your expanded text in the patch
> description, but I need to do more testing to see the real impact of
> this change.  Most of my clients are driving GDB through some kind of
> GUI, which means that break points are inevitably placed using
> file:line sytnax.  One of the most common complaints I get is when a
> breakpoint is placed on one line, but GDB stops on another.  Generally
> my users can be quite forgiving of missing stack frames when inlining
> is in play.  What this means is an argument of if you did break here
> you'd have a frame missing, so I'm not going to let you break there
> any more isn't that compelling to me.
> 

Note that your other patch is also deleting is-stmt locations,
because the switching between the different cu's does that with
the end-marker.

> That isn't a rejection of the patch, it's just me explaining why it's
> taking me some time to review.
> 

Absolutely, no problem, we are not in a hurry.
And thanks for all your time, and good co-operation.


Thanks
Bernd.